东大18秋学期《数据结构Ⅱ》在线作业3答案答案
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.与该顶点连通的顶点数
东大18秋学期《数据结构Ⅱ》在线作业3答案历年真题如下：
