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

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