东北师范大学计算机科学与技术专业《数据结构》作业及答案3
搜题
1、某二叉树结点的前序序列为ECBAD，中序序列为EBCDA，则该二叉树结点的后序序列为()。
A.ABCED
B.DECAB
C.DEABC
D.BDACE
本题答案：
D
D
2、存放在外存中的数据的组织结构是()。
A.数组
B.表
C.文件
D.链表
本题答案：
C
C
3、在下述几种排序方法中，不稳定的排序方法是()。
A.直接插入排序
B.冒泡排序
C.直接选择排序
D.归并排序
本题答案：
C
C
4、“堆积”问题是由于()引起的。
A.同义词之间发生冲突
B.散列函数
C.不同的同义词子表结合在一起
D.散列表“溢出”
本题答案：
C
C
5、若要求尽可能快地对序列进行稳定的排序，则应选()。
A.快速排序
B.归并排序
C.起泡排序
D.希尔排序
本题答案：
B
B
6、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为()。
A.n
B.(n-1)/2
C.n/2
D.(n+1)/2
本题答案：
D
D
7、用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是()。
A.逆拓扑有序
B.拓扑有序
C.无序的
D.部分有序的
本题答案：
A
A
8、设根结点的层数为0，若高度为h的二叉树上只有度为0和度为2的结点，则此二叉树上所包含的结点数至少为()。
A.h+1
B.2h-1
C.2h
D.2h+1
本题答案：
D
D
9、在下列情况中，可称为二叉树的是()。
A.每个结点至多有两棵子树的树
B.哈夫曼树
C.每个结点至多有两棵子树的有序树
D.每个结点只有一棵右子树
本题答案：
B
B
10、广义表(a，b，c，d)的表头是()。
A.a
B.()
C.(a，b，c，d)
D.(b，c，d)
本题答案：
C
C
11、设散列地址空间为0~m-1，key为关键字，用p去除key，将得到的余数作为key的散列地址，即h(key)=key%p。为了减少发生冲突的频率，一般取p为()。
A.小于等于m的最大奇数
B.小于等于m的最大偶数
C.小于等于m的最大素数
D.小于等于m的最大合数
本题答案：
C
C
12、有m个叶结点的哈夫曼树所具有的结点数为()。
A.m
B.m+1
C.2m-1
D.2m
本题答案：
C
C
13、树最适合用来表示()。
A.有序数据元素
B.无序数据元素
C.元素之间具有分支层次关系的数据
D.元素之间无联系的数据
本题答案：
C
C
14、在下面的排序方法中，其比较次数与待排序记录的初始排列状态无关的是()。
A.直接插入排序
B.快速排序
C.直接选择排序
D.归并排序
本题答案：
C
C
15、有n个顶点的有向图的边数最多为()。
A.n
B.n(n-1)
C.n(n-1)/2
D.2n
本题答案：
B
B
16、假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测?()
A.k-1次
B.k次
C.k+1次
D.k(k+1)/2次
本题答案：
D
D
17、在排序方法中，从未排序序列中挑选记录，并将其依次放入已排序序列(初始时为空)的一端的方法，称为()。
A.希尔排序
B.插入排序
C.归并排序
D.选择排序
本题答案：
D
D
18、在下面的叙述中，正确的是()。
A.树的先根遍历序列与其对应的二叉树的前序遍历序列相同
B.树的先根遍历序列与其对应的二叉树的中序遍历序列相同
C.树的先根遍历序列与其对应的二叉树的后序遍历序列相同
D.树的后根遍历序列与其对应的二叉树的后序遍历序列相同
本题答案：
A
A
19、有n个顶点的无向图的边数最多为()。
A.n
B.n(n-1)
C.n(n-1)/2
D.2n
本题答案：
C
C
20、在排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为()。
A.直接选择排序
B.冒泡排序
C.直接插入排序
D.希尔排序
本题答案：
C
C
21、快速排序的速度在所有排序方法中最快，而且所需附加空间也最少。()
A.错误
B.正确
本题答案：
A
A
22、在中序线索二叉树中，每一非空的线索均指向其祖先结点。()
A.错误
B.正确
本题答案：
B
B
23、当待排序记录已经从小到大排序或从大到小有序时，快速排序的执行时间最省。()
A.错误
B.正确
本题答案：
A
A
24、快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。()
A.错误
B.正确
本题答案：
A
A
25、二叉树中除叶结点外，任一结点X，其左子树根结点的值小于该结点X的值﹔其右子树根结点的值大于等于该结点X的值，则此二叉树一定是二叉排序树。()
A.错误
B.正确
本题答案：
A
A