四川师范大学-第一学期数据结构期末试题A.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。

四川师范大学计算机科学学院计算机科学与技术专业、 网络工程专业、
软件工程专业
－ 第一学期期末考试
数据结构试卷A卷
答卷说明: 1、 本试卷共 8页, 5个大题, 满分 100分, 120分钟完卷。
2、 本次考试为闭卷考试。
3、 本试卷适用于 级 1, 2, 3班。
题号
分数
一
二
三
四
五
总分
总分人
得分
评卷人
一、 单项选择题( 每小题2分, 共20分)
1.
单循环链表的尾结点的指针域的值为【
A．NULL
】。
B．0
D．尾结点地址
C．首结点地址
2.
3.
一个栈的输入序列为 a,b,c,d,e, 则栈的不可能输出序列是【
A．edcba B．decba C．abcde
在有 n个结点的链表 L中, 访问第 i个结点(i=1,2,… n)的算法 GetElem_L( L, i, &e) 的时间复
】。
D．dceab
杂度为【
】。
n +1
n
2
D．O( 2 )
A．O( n)
B．O(1)
C．O(
)
4.具有线性结构的数据结构是【
A．树 B．图
】。
C．广义表
D．栈
5.
最大容量为 n的循环队列, 队尾指针是 rear, 队头指针是 front, 则队空的条件是【
】
A.( rear+1) % n ==front
B .rear==front
C.
rear+1 ==front
D. (rear-1) % n ==front
6.
设字符串 S1＝”ABCDEFG”, S2＝”PQRST”, 则运算:
S＝
CONCAT(SUBSTR(S1,2,LEN(S2));SUBSTR(S1,LEN(S2),2)); 后的串值为【
】。
A. BCDEF
B. BCDEFG
C. BCDPQRST
D. BCDEFEF
计算机科学学院
计算机科学与技术、 网络工程、 软件工程专业
数据结构试卷 A第 1页 (共 8页)

7.
关键路径是事件网络中【
A．从源点到汇点的最短路径
C．最长的回路
】。
B．从源点到汇点的最长路径
D．最短的回路
8.
9.
具有 n个顶点的有向简单图最多有【
A．n B．n(n—1)
若广义表 A=( (a,b,c),(d,e,f)) ,则式子 GetHead(GetTail(GetHead(GetTail(A))))的值为【
】条边。
C. n(n+1)
D. n
2
】。
A．( a,b,c)
B．(d,e)
C．e
D．f
10.向一个栈顶指针为 hs的链栈中插入一个 s结点时, 应执行【
】。
A．hs->next=s;
B．s->next=hs;
hs=s;
C．s->next=hs->next; hs->next=s; D．s->next=hs;
hs=hs->next;
得分
评卷人
二、 填空题( 共10分, 每空2分)
1.
设有一个 10阶的对称矩阵 A, 采用压缩存储方式, 以行序为主存储, a1,1为第一个元素, 其
存储地址为 1, 每个元素占 1个地址空间, 则 a7,6的地址为
2.
3.
有 m个叶子结点的哈夫曼树, 其结点总数为
有一棵三叉树, 度为 1,2,3的结点数分别为 n1,n2,n3, 则该三叉树的叶子结点数 n0为
4.
5.
若二叉树用二叉链表作存储结构, 则在 n个结点的二叉树链表中只有
个非空
链域。
在有序表 A[1..12]中, 采用折半查找算法查等于 A[12]的元素, 所比较的元素下标依次为
。
得分
评卷人
三、 判断题, 用”×”或”√”确定以下说法错误或正确( 每小题1分, 共10分)
1.
2.
3.
数组是同类型值的集合。
(
(
(
)
)
)
栈和队列都是限制存取点的线性结构。
向一棵平衡二叉树中插入一个结点后, 一定会改变其平衡性。
计算机科学学院
计算机科学与技术、 网络工程、 软件工程专业
数据结构试卷 A第 2页 (共 8页)

4.
5.
6.
二叉树是树的特殊形式。
(
(
)
)
由树转换成二叉树, 其根结点的右子树总是空的。
用邻接矩阵存储一个图时, 在不考虑压缩存储的情况下, 所占用的存储空间大小只与图
中顶点的个数有关, 而与图的边数无关。
(
)
7.
对任意一个图, 从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该
图的每个顶点。
(
)
8.
向二叉排序树插入一个新结点时, 新结点一定成为二叉排序树的一个叶子结点。
(
)
9.
在一棵树中, 如果结点 A有 3个兄弟, 而且 B是 A的双亲, 则 B的度是 5 。(
)
10.
快速排序总比简单排序快。
(
)
得分
评卷人
四、 简答题( 每小题6分, 共30分)
1.已知某二叉树的前序序列为 EBADCFHGI, 中序序列为 ABCDEFGHI, 画出该二叉树, 并写出该二
叉树的后序序列, 画出该二叉树的后序线索化树。
计算机科学学院
计算机科学与技术、 网络工程、 软件工程专业
数据结构试卷 A第 3页 (共 8页)

2．简述拓扑排序的过程, 判定下图是否能进行拓扑排序, 如果能, 请给出一个拓扑排序序列,
如果不能, 请给出理由。
0
1
2
3
4
5
6
7
8
3.下图表示一个地区的通讯网, 边表示城市间的通讯线路, 边上的权表示架设线路花费的代价,
如何选择能沟通每个城市且总代价最省的 n-1条线路, 画出你的选择, 并写出这 n-条路的总代价。
计算机科学学院
计算机科学与技术、 网络工程、 软件工程专业
数据结构试卷 A第 4页 (共 8页)

4.已知待排序文件各记录的关键字顺序如下:
1327
49
38
65
97
76
49
( 1) 请写出快速排序过程中第一趟的排序结果。
( 2) 什么是排序算法的稳定性? 请问快速排序是否稳定?
5．假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,36,18,70,49,80), 哈希地址空间为
HT[0 .. 12], 若采用除留余数法构造哈希函数和拉链法处理冲突, 试画出最后得到的哈希表。
计算机科学学院
计算机科学与技术、 网络工程、 软件工程专业
数据结构试卷 A第 5页 (共 8页)

得分
评卷人
五、 用类 C语言描述下列算法, 并给出必要说明。 ( 共30分)
1.在带头结点的单链表 La中删除所有大于数值 x的结点并打印出所删除的结点个数。( 本小题 8
分)
已知线性表的单链表存储结构如下:
typedef struct Lnode {
ElemType data;
Lnode * next;
}Lnode,*LinkList;
给出算法 Status DeleteList( LinkList &La, ElemType x), 并给出必要的注释。
2.二叉树采用二叉链表存储, 给出求二叉树单分支结点数目的算法。( 本小题 8分)
(提示: 单分支结点是度为 1的结点)
//二叉树的存储表示
typedef struct BiTNode{
计算机科学学院
计算机科学与技术、 网络工程、 软件工程专业
数据结构试卷 A第 6页 (共 8页)

ElemType data;
Stuct BiTNode * lchild,*rchild;//左右指针标志
}BiTNode,*BiTree
3.用算法实现: 建立有向图邻接表的存储结构, 并实现求给定顶点 v的出度。( 本小题 14分)
已知图的弧的结点结构:
typedef struct ArcNode {
int
adjvex;
//该弧所指向的顶点的位置
struct ArcNode
} ArcNode;
*nextarc;
//指向下一条弧的指针
顶点的结点结构
typedef struct VNode {
VertexType
data;
//顶点信息
ArcNode
*firstarc; //指向第一条依附该顶点的弧
} VNode, AdjList[MAX_VERTEX_NUM];
图的结构定义:
计算机科学学院
计算机科学与技术、 网络工程、 软件工程专业
数据结构试卷 A第 7页 (共 8页)

typedef struct {
AdjList
vertices;
int
vexnum, arcnum;
} ALGraph;
( 1) 试写出建立邻接表的算法: Status createDG(ALGraph &G )
( 2) 试写出计算结点 v的出度算法: int OutDegree(ALGraph &G, VertexType v)
计算机科学学院
计算机科学与技术、 网络工程、 软件工程专业
数据结构试卷 A第 8页 (共 8页)