数据结构复习题：
一、判断题
1、（）采用循环链表作为存储结构的队列就是循环队列。
2、（）哈夫曼树一定是完全二叉树。
3、（）选择排序是一种稳定的排序方法。
4、（）在顺序存储结构的线性表中，取第i个元素操作的时间复杂度为O(1)。
5、（）有向图中第i个顶点的出度等于其邻接矩阵中第i行非0元素的个数。
6、（）在按值有序的线性链表中可以采用折半查找法进行查找。
7、（）只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。
8、（）在具有n个结点的完全二叉树中，无法确定其叶子结点的个数。
9、（）一棵树转换成二叉树后，该二叉树的根结点一定没有右子树。
10、（）对任意一个图，从它的某个顶点出发进行一次深度或广度优先搜索遍历时，均
可访问到该图的每个结点。
11、（）二叉树的存储结构必须采用二叉链表结构。
12、（）给定一组关键字序列，按顺序构造二叉排序树，其树的形态与关键字的排列顺
序无关。
13、（）当初始序列为逆序时，简单选择排序的比较次数达到最多。
14、（）在单链表表示的线性表中，取线性表第i个元素操作的时间复杂度为O(n)（n
为链表长度）。
15、（）具有n结点的二叉树，其最大深度为n。
16、（）在具有13个叶子结点的二叉树中，其度为2的结点个数一定为12。
17、（）具有n个顶点无向图，其生成树中一定存在n-1条边。
18、（）能采用折半查找法进行查找的查找表必须是有序并为顺序存储。
19、（）若一棵二叉树中不存在度为1的结点，则该二叉树一定是一棵完全二叉树。
20、（）快速排序是目前所有排序方法中效率最高的稳定排序。
二、选择填空
1、下列排序方法中，排序所花时间不受数据初始排列特性影响的算法是＿＿＿＿。
A）冒泡排序B）简单选择排序C）快速排序D）直接插入排序
2、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2
个，那么度为0的结点数为＿＿＿＿个。
A）4 B）5 C）6 D）7
3、对于给定的8个元素：34，76，45，18，26，54，92，65，按给定顺序生成一棵二叉排序树，
该树的深度为＿＿＿＿。
A）4 B）5 C）6 D）7
4、在具有n个结点的线索树中，线索的个数为＿＿＿＿。
A）n-1 B）n C）n+1 D）不确定
5、若对给定的关键字序列利用折半查找方法进行查找，则关键字序列需满足的条件是
_________。
A）顺序存储且有序B）顺序存储且升序
C）链式存储且有序D）有序
6、在一个单链表中，已知q指针所指结点为p指针所指结点的前驱，若在p、q之间插入s
所指结点，则主要操作为_________。
A）s->next = p->next ; p->next = s ; B）q->next = s ; s->next = p ;
C）p->next = s->next ; s->next = p ; D）p->next = s ; s->next = q ;
7、在具有n个顶点的无向图的邻接表中表结点总数最多为_________。
A）n*( n-1 ) B）n*n C）2*n*( n-1 ) D）n*( n-1 )/2
8、设一个输入序列为1，2，3，4，5，6，则借助一个栈所得到的输出序列不可能是_________。
A）3，2，5，6，4，1 B）4，5，3，6，2，1
C）2，4，3，5，1，6 D）1，5，4，6，2，3
9、设循环队列存储空间的下标范围是0..n-1，当队列头尾指针分别为f和r时，队列长度为
_________。
A）r - f B）r – f +1 C）(r – f + 1 ) % n D）(r – f + n ) % n
10、如果二叉树T是由多叉树F转换而成，那么树F的后根序列应该是二叉树T的_________。
A）层次遍历序列B）先序序列
C）中序序列D）后序序列
11、下列排序方法中，不稳定的排序方法是＿＿＿＿。
A）冒泡排序B）简单选择排序
C）归并排序D）直接插入排序
12、在具有n个结点的二叉树中，其空指针域的个数为＿＿＿＿。
A）2n+1B）n-1C）n+1D）不确定
13、对给定模式串abaabcac，其next值为_________。
A）01122312 B）01121321
C）01234512 D）01112212
14、若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有_________个结点。
A）33B）34C）35D）不确定
15、设循环队列存储空间的下标范围是0..n-1，当队列尾指针rear，队列长度为len时，循
环队列中队头元素所在位置为_________。
A）rear - len B）rear – len +1
C）(rear – len + 1 ) % n D）(rear – len + n ) % n
16、在非空二叉树的中序遍历序列中，根结点的左边应该_________
A）只有左子树上的所有结点 B）只有左子树上的部分结点
C）只有右子树上的所有结点 D）只有右子树上的部分结点
17、在一个链表中，已知p指针指向链表中一个非空结点，现要删除链表中p指针所指结点，
其时间复杂度为O(1)的结构为________。
A）无头单循环链表B）双循环链表
C）带头单循环链表D）带头单链表
18、已知二叉树的先序序列为：ABDGCEFH，中序序列为：DGBAECHF，则其后序序列
为：_________。
A）BDGCEFHA B）GDBECFHA
C）BDGAECHF D）GDBEHFCA
19、如果二叉树T是由多叉树F转换而成，那么树F的叶子在二叉树T中应是满足_________
条件结点。
A）左子树为空且右子树非空B）左、右子树均为空
C）左子树为空D）右子树为空
20、对二叉排序树进行_________遍历，可以得到该二叉树所有结点构成的有序序列。
A）层次B）先序C）中序D）后序
三、简答下列各题
1、设循环队列存储在一段连续存储空间中，其空间大小为QSIZE，若队列中只设rear和quelen 来分别指示队尾元素的位置和队列中的元素个数，给出队列的满和空条件以及队头元素的位置。
2、对下图
1）写出邻接矩阵
2）画出其最小生成树
3）写出从顶点A出发深度优先遍历和广度优先遍历的遍历序列（顶点顺序按从上到下、从左到右）
3、将下列森林转化为二叉树
