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. 一棵二叉树中第6层上最多有(  C  )个结点。(2 分)
A. 2
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. 设图G的邻接矩阵A=,则图G中共有(  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. 试写出对如下无向图从顶点A出发进行广度优先遍历可能得到的所有遍历序列。
(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 //无左子树

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。