XX大学成人教育学院2022-2023学年度第二学期期末考试
《数据结构》复习试卷1
__________学习中心（教学点）批次：层次：
专业：学号：身份证号：
姓名：得分：
一单选题 (共10题，总分值20分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。)
1. 一棵高为k的二叉树最少有（  B  ）个结点。（2 分）
A. k-1
B. k
C. 2k-1
D. 2k-1
2. 广义表(a,(b,(),c))的深度为（  C  ）。（2 分）
A. 1
B. 2
C. 3
D. 4
3. 含n个顶点的有向图最多有（  B  ）条弧。（2 分）
A. n
B. n(n-1)
C. n(n+1)
D. n2
4. 设对下图从顶点a出发进行深度优先遍历，则（  A  ）是可能得到的遍历序列。
（2 分）
A. acfgdeb
B. abcdefg
C. acdgbef
D. abefgcd
5. 具有n个顶点的有向强连通图最少有（  B ）条弧。（2 分）
A. n-1
B. n
C. n(n-1)
D. n(n-1)/2
6. 下列叙述中错误的是（  B  ）。（2 分）
A. 树的度与该树中结点的度的最大值相等
B. 二叉树就是度为2的有序树
C. 有5个叶子结点的二叉树中必有4个度为2的结点
D. 满二叉树一定是完全二叉树
7. 由树转换而得的二叉树，根结点（  B  ）。（2 分）
A. 没有左子树
B. 没有右子树
C. 左右子树都有
D. 视树的形态而定
8. 一棵二叉树中第６层上最多有（  C  ）个结点。（2 分）
A. ２
B. 31
C. 32
D. 64
9. 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，则A中的
元素A[66，65]在数组B中的位置K=（  A  ）。（2 分）
A. 195
B. 196
C. 197
D. 198
10. 设图Ｇ的邻接矩阵A=，则图Ｇ中共有（  B  ）个顶点。（2 分）
A. 1
B. 3
C. 4
D. 9
二多选题 (共5题，总分值10分，下列选项中至少有2个或2个以上选项符合题目要求，请在答题卡上正确填涂。)
11. （ ACD  ）二叉排序树不可以得到一个从小到大的有序序列。（2 分）
A. 先序遍历;
B. 中序遍历;
C. 后序遍历;
D. 层序遍历
12. 对线索二叉树叙述正确的是（  ABCDE ）。（2 分）
A. 加上线索的二叉树称为线索二叉树
二叉树的深度为k
B. 指向前驱和后继的指针称为线索;
C. 若二叉树结点的左孩子指针为空，可用其指向其前驱;
D. 若二叉树结点的右孩子指针为空，可用其指向其后继;
E. 对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化
13. 以下说法中正确的是（  ABC  ）。（2 分）
A. 无向图中的极大连通子图称为连通分量;
B. 连通图的广度优先遍历中一般要采用队列来暂存刚访问过的顶点;
C. 图的深度优先遍历中一般要采用栈来暂存刚访问过的顶点;
D. 有向图的遍历不可采用广度优先遍历方法
14. 已知广义表L=（（x,y,z），a，（u，t），w），下列运算中结果为原子项的是（  BD ）。
（2 分）
A. tail(head（tail（tail（L））））
B. head（tail（L））
C. tail（head（L））
D. head(head（tail（tail（L））））
15. 先序序列和中序序列相同的二叉树有（  ACD  ）。（2 分）
A. 空二叉树;
B. 左单支树;
C. 右单支树;
D. 根树
三判断题 (共9题，总分值9分正确的填涂“A”，错误的填涂“B”。)
16. 最小生成树是指边数最少的生成树。（1 分）（  B ）
17. 二叉树中序线索化后，不存在空指针域。（1 分）（  B ）
18. 若图G有环，则G不存在拓扑排序序列。（1 分）（    A ）
19. 二叉树不是树的特殊情况。（1 分）（  A ）
20. 具有10个叶结点的二叉树中，有9个度为2的结点。（1 分）（  A ）
21. 如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G一定有2个连通分量。
（1 分）（  A ）
22. 在有向图中，各顶点的入度之和等于各顶点的出度之和。（1 分）（  A ）
23. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。（1 分）（  A ）
24. 二叉树的前序遍历并不能唯一确定这棵树，但是如果我们还知道该树的根结点是哪一个，
则可以确定这棵二叉树。（1 分）（  B ）
四简答题 (共2题，总分值20分 )
25. 试写出对如下无向图从顶点Ａ出发进行广度优先遍历可能得到的所有遍历序列。
（10 分）
答：ABCEGHFD
ABCEHGFD
ACBGHEDF
ACBHGEDF
26. 试将下图中的树转化为二叉树。
（10 分）
答：
五综合题 (共3题，总分值41分 )
27. 试设计算法，对以邻接矩阵存储的无向图进行深度优先遍历。（13 分）
答：int depth(BiTree t){
if (!t) return 0;
if(t->lchild)//有左子树
if (t->rchild){ //左、右子树均有
hl=depth(t->lchild); //求左子树高度
hr=depth(t->rchild); //求右子树高度
return hl>hr?hl+1:hr+1;
}
else //只有左子树
return depth(t->lchild)+1;
else //无左子树