《数据结构》2020年秋季学期在线作业（三）

adminhan

下列说法正确的是（）。
A:树的先根遍历序列与其对应的二叉树的先根遍历序列相同
B:树的先根遍历序列与其对应的二叉树的后根遍历序列相同
C:树的后根遍历序列与其对应的二叉树的先根遍历序列相同
D:树的后根遍历序列与其对应的二叉树的后根遍历序列相同

题目和答案如下图所示：
A:A
B:B
C:C
D:D

下列判断正确的是（）。
A:二叉树是树的特例。
B:具有n个结点的完全二叉树的深度为n/2。
C:Huffman树是带权路径长度最小的二叉树，树中权值越大的叶子结点距离根结点越远。
D:栈和队列都是限制存取点的线性结构。

关于完全二叉树，不正确的描述是（）。
A:每个结点必须首先有左儿子，然后才能有右儿子。
B:在具有相同结点的所有二叉树中，它的高度最小。
C:每个结点的左右子树的高度最多相差为1。
D:没有度为1的结点。

哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行（）次探测。
A:k
B:k-1
C:k(k-1)/2
D:1 k(k-1)/2

在具有n个结点的二叉树（二叉链表表示）中，值为空的链域数为（）。
A:n-1
B:2n-1
C:n 1
D:2n 1

数组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

二维数组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]

题目和答案如下图所示：
A:A
B:B
C:C
D:D

二叉查找树的查找效率与二叉树的树型有关,在（）时其查找效率最低。
A:结点太多
B:完全二叉树
C:呈单枝树
D:结点太复杂。

若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。
A:顺序表
B:单链表
C:双链表
D:单循环链表

假设主串的长度为m，模式串的长度为n，KMP算法的时间复杂度为（）。
A:n m
B:n*m
C:n
D:m

题目和答案如下图所示：
A:A
B:B
C:C
D:D

下面关于完全二叉树的特点叙述不正确的是（）。
A:只有最后一层是不满的，不满层的结点首先出现在左边
B:至多只有最下面的两层结点的度小于2
C:左子树的高度不会小于右子树的高度，且左、右子树高度最大相差±1
D:叶子只能出现在最后两层上；

若串S=“software”,其子串数目是（）。
A:8
B:37
C:36
D:9

将一棵树转换成二叉树后，根结点没有左子树。
A:错误
B:正确

二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。
A:错误
B:正确

线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。
A:错误
B:正确

有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。
A:错误
B:正确

哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
A:错误
B:正确