《数据结构》2020年秋季学期在线作业（三）
试卷总分:100 得分:100
一、单选题 (共 15 道试题,共 75 分)
1.下列说法正确的是 （ ）。
A.树的先根遍历序列与其对应的二叉树的先根遍历序列相同
B.树的先根遍历序列与其对应的二叉树的后根遍历序列相同
C.树的后根遍历序列与其对应的二叉树的先根遍历序列相同
D.树的后根遍历序列与其对应的二叉树的后根遍历序列相同
2.题目和答案如下图所示：
{图}
A.A
B.B
C.C
D.D
3.下列判断正确的是（ ）。
A.二叉树是树的特例。
B.具有n个结点的完全二叉树的深度为n/2。
C.Huffman树是带权路径长度最小的二叉树，树中权值越大的叶子结点距离根结点越远。
D.栈和队列都是限制存取点的线性结构。
4.关于完全二叉树，不正确的描述是（ ）。
A.每个结点必须首先有左儿子，然后才能有右儿子。
B.在具有相同结点的所有二叉树中，它的高度最小。
C.每个结点的左右子树的高度最多相差为1。
D.没有度为1的结点。
5.哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行（ ）次探测。
A.k
B.k-1
C.k(k-1)/2
D.1+k(k-1)/2
6.在具有n个结点的二叉树（二叉链表表示）中，值为空的链域数为（ ）。
A.n-1
B.2n-1
C.n+1
D.2n+1
7.数组A中，每个元素A的长度为3个字节，行下标i从1到8。列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[5][8] 的起始地址为（ ）。
A.SA+141
B.SA+180
C.SA+222
D.SA+225
8.二维数组A的每个元素是由6个字符组成的串，其行下标i=0、1、…、8，列下标j=1、2、…、4、若A按行先存储，元素A[8，5]的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。
A.A[8，5]
B.A[3,10]
C.A[5,8]
D.A[0,9]
9.题目和答案如下图所示：
{图}
A.A
B.B
C.C
D.D
10.二叉查找树的查找效率与二叉树的树型有关, 在（ ）时其查找效率最低。
A.结点太多
B.完全二叉树
C.呈单枝树
D.结点太复杂。
11.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
A.顺序表
B.单链表
C.双链表
D.单循环链表
12.假设主串的长度为m，模式串的长度为n，KMP算法的时间复杂度为（ ）。
A.n+m
B.n*m
C.n
D.m
13.题目和答案如下图所示：
{图}
A.A
B.B
C.C
D.D
14.下面关于完全二叉树的特点叙述不正确的是（ ）。
A.只有最后一层是不满的，不满层的结点首先出现在左边
B.至多只有最下面的两层结点的度小于2
C.左子树的高度不会小于右子树的高度，且左、右子树高度最大相差±1
D.叶子只能出现在最后两层上；
15.若串S=“software”,其子串数目是（ ）。
A.8
B.37
C.36
D.9
二、判断题 (共 5 道试题,共 25 分)
16.将一棵树转换成二叉树后，根结点没有左子树。
17.二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。
18.线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。
19.有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。
20.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
转载请注明：奥鹏作业之家 » 华东《数据结构》2020年秋季学期在线作业（三）【标准答案】