天大21年春《数据结构》在线作业二【答案】奥鹏作业满分答案
《数据结构》在线作业二
试卷总分:100 得分:100
一、单选题 (共 40 道试题,共 100 分)
1.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（）。
A.先序遍历
B.中序遍历
C.后序遍历
D.按层遍历
2.具有4个顶点的无向完全图有（）条边。
A.6
B.12
C.16
D.20
3.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ ）。
A.2i+1
B.2i
C.i/2
D.2i-1
4.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论（）是正确的。
A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D.以上都不对
5.程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（ ）。
A.O(n)
B.O(nlog2n)
C.O(n2)
D.O(n3 /2)
6.设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（ ）。
A.99
B.97
C.91
D.93
7.在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。
A.n
B.n+1
C.n-1
D.n/2
8.不含任何结点的空树（）。
A.是一棵树
B.是一棵二叉树
C.是一棵树也是一棵二叉树
D.既不是树也不是二叉树
9.设有序表中的元素为(13，21，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（ ）次比较。
A.1
B.2
C.3
D.4
10.设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（ ）个。
A.4
B.5
C.6
D.7
11.在一个图中，所有顶点的度数之和等于所有边数的（）倍。
A.1/2
B.1
C.2
D.4
12.设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（ ）。
A.20
B.256
C.512
D.1024
13.散列表的平均查找长度（）。
A.与处理冲突方法有关而与表的长度无关
B.与处理冲突方法无关而与表的长度有关
C.与处理冲突方法有关而与表的长度有关
D.与处理冲突方法无关而与表的长度无关
下列各种排序算法中平均时间复杂度为O(n2 )是（ ）。
A.快速排序
B.堆排序
C.归并排序
D.冒泡排序
15.设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（ ）。
A.小于等于m的最大奇数
B.小于等于m的最大素数
C.小于等于m的最大偶数
D.小于等于m的最大合数
16.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）。
A.n
B.(n-1)的平方
C.n-1
D.n的平方
17.对于静态表的顺序查找法，若在表头设置岗哨，奥鹏答案，则正确的查找方式为（）。
A.从第0个元素往后查找该数据元素
B.从第1个元素往后查找该数据元素
C.从第n个元素往开始前查找该数据元素
D.与查找顺序无关
21.用某种排序方法对线性表（ 25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：⑴ 25，84，21，47，15，27，68，35，20；⑵ 20，15，21，25，47，27，68，35，84；⑶ 15，20，21，25，35，27，47，68，84；⑷ 15，20，21，25，27，35，47，68，84。则所采用的排序方法是（）。
A.选择排序
B.希尔排序
C.归并排序
D.快速排序
19.二叉树是非线性数据结构，所以（）。
A.它不能用顺序存储结构存储
B.它不能用链式存储结构存储
C.顺序存储结构和链式存储结构都能存储
D.顺序存储结构和链式存储结构都不能使用
20.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（ ）。
A.F，H，C，D，P，A，M，Q，R，S，Y，X
B.P，A，C，S，Q，D，F，X，R，H，M，Y
C.A，D，C，R，F，Q，M，S，Y，P，H，X
D.H，C，Q，P，A，M，S，R，D，F，X，Y
21.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（ ）个结点。
A.2n
B.n+l
C.2n-1
D.2n+l
