18秋学期《数据结构Ⅱ》在线作业3-0001 试卷总分:100 得分:0 一、 单选题 (共 20 道试题,共 100 分) 1. 下面的说法中正确的是 (1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。
18秋学期《数据结构Ⅱ》在线作业3-0001
试卷总分:100 得分:0
一、 单选题 (共 20 道试题,共 100 分)
1. 下面的说法中正确的是
(1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。
(2)按二叉树定义，具有三个节点的二叉树共有6种。
A.(1)，(2)
B.(1)
C.(2)
D.(1)，(2)都错
2. n个顶点的有向完全图中含有向边的数目最多为
A.n-1
B.n
C.n(n-1)/2
D.n(n-1)
3. 深度为h的满m叉树的第k层的结点(1=<k=<h)数有
A.mk-1
B.mk-1
C.mh-1
D.mh-1
4. 下面关于线性表的叙述中，错误的是
A.线性表采用顺序存储，必须占用一片连续的存储单元。
B.线性表采用顺序存储，便于进行插入和删除操作。
C.线性表采用链接存储，不必占用一片连续的存储单元。
D.线性表采用链接存储，便于插入和删除操作。
5. 在计算机内实现递归算法时所需的辅助数据结构是
A.栈
B.队列
C.树
D.图
6. 在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是
A.1
B.2
C.3
D.5
7. 设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
A.2
B.3
C.5
D.6
8. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为
A.O(0)
B.O(1)
C.O(n)
D.O(n2)
9. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的
A.层次遍历算法
B.前序遍历算法
C.中序遍历算法
D.后序遍历算法
10. 一棵树高为K的完全二叉树至少的结点是
A.2k –1
B.2k-1 –1
C.2k-1
D.2k
11. 一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
A.O(n)
B.O(e)
C.O(n+e)
D.O(n2)
12. for（i=0；i<m；i++）
for（j=0；j<t；j++）
c［i］［j］=0；
for（i=0；i<m；i++）
for（j=0；j<t；j++）
for（k=0；k<n；k++）
c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；
上列程序的时间复杂度为
A.O（m+n×t）
B.O（m+n+t）
C.O（m×n×t）
D.O（m×t+n）
13. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
A.4
B.5
C.8
D.9
14. 对于哈希函数H(key)=key%13,被称为同义词的关键字是
A.35和41
B.23和39
C.15和44
D.25和51
15. 已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是
A..{25,36,48,72,23,40,79,82,16,35}
B..{25,36,48,72,16,23,40,79,82,35}
C..{25,36,48,72,16,23,35,40,79,82}
D..{16,23,25,35,36,40,48,72,79,82}
16. 含n个关键字的二叉排序树的平均查找长度主要取决于
A.关键字的个数
B.树的形态
C.关键字的取值范围
D.关键字的数据类型
17. ．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是
A.逆拓扑有序
B.拓扑有序
C.无序的
D.A和B
18. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为
A.5
B.6
C.7
D.8
19. 某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是
A.空或只有一个结点
B.高度等于其结点数
C.任一结点无左孩子
D.任一结点无右孩子
20. 无向图中一个顶点的度是指图中
A.通过该顶点的简单路径数
B.与该顶点相邻接的顶点数
C.通过该顶点的回路数
D.与该顶点连通的顶点数
