{
if(r!=NULL) {
if(r->lchild!=NULL && r->rchild!=NULL) if(r->lchild->data >r->rchild->data) {
BiTree t=r->lchild; r->lchild=r->rchild; r->rchild=t; }
change(r->lchild); change(r->rchild); } }
2. 统计出二叉树中大于给定值x的结点个数，该统计值由函数返回。
int count(BiTree r,ElemType x)
{
if(r!=NULL) {
if(r->data >x)
return count(r->lchild,x)+count(r->rchild,x)+1; else
return count(r->lchild,x)+count(r->rchild,x); } return 0;
}
3. 对具有n个结点的二叉树进行中序遍历，并将得到的结点值序列保存到数组中。
void preserve(BiTree r,ElemType a[],int n)
{
static int i=0; if(r!=NULL) {
26
preserve(r->lchild,a,n); a[i++]=r->data; preserve(r->rchild,a,n); } }
第6章 图
一、单项选择题
1. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为（ ）。
A）s B）s - 1 C）s+1 D）n 2. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为（ ）。
A）s B）s+1 C）s - 1 D）2s
3.在一个具有n个结点的无向图中，若具有e条边，则所有顶点的度数之和为（ ）。
A）n B）e C）2e D）n+e
4. 在一个具有n个顶点和e条边的无向图的邻接矩阵中，非零元素的个数为（ ）。
A）n B）ne C）e D）2e
5. 在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为（ ）。
A）n B）ne C）e D）2e
二、填空题
1. 在一个无向图中，所有顶点的度数之和等于所有边数的 倍。
2. 若一个有向图的顶点集为{ a, b, c, d, e, f }，其顶点偶对的集合为{ ,,
3. 在一个具有n个顶点的无向图中，要连通所有顶点，则至少需要 条边。 4. 表示图的两种存储结构为 和 。 5. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为 × 。 6. 对于一个具有n个顶点和e条边的无向图，在其对应的邻接表中，所含边结点的个数为 。
7. 图的深度优先搜索遍历，类似于树的 遍历；图的广度优先搜索遍历，类似与树的 遍历。
8. 一个图的顶点偶对集合为{ (a,c), (a,e), (b,e), (c,d), (d,e) }，从顶点a出发进行深度优先搜索遍历得到的顶点序列为 ；从顶点a出发进行广度优先搜索遍历得到的顶点序列为 。
27
参考答案
一、单项选择题
1.A 2.D 3.C 4.D 5.D
二、填空题
1. 2 2. 2, 4
3. n-1 4. 邻接矩阵，邻接表 5. n, n 6. e
7. 先序，层次 8. acdeb, acedb（答案不唯一）
第7章 查找与排序
一、单项选择题
1. 若查找每个元素的概率相等，则在长度为n的顺序表上，查找任一元素的平均查找长度为（ ）。
A）n B）n+1 C）(n+1)/2 D）(n-1)/2
2. 对长度为n的单链有序表，若查找每个元素的概率相等，则查找任一元素的平均查找长度为（ ）。
A）n/4 B）(n+1)/2 C）n/2 D）(n-1)/2
3. 对长度为9的顺序存储的有序表，采用折半法查找，在等概率情况下的平均查找长度为（ ）的值除以9。
A）18 B）20 C）25 D）22
4. 对长度为18的顺序存储的有序表，采用折半法查找，则查找第15个元素的查找长度为（ ）。
A）3 B）4 C）5 D）6
5. 对顺序存储的有序表（5，12，20，26，37，42，46，50，64），采用折半查找，则查找元素26的查找长度为（ ）。
A)2 B)3 C)4 D)5 6. 顺序查找法适合于存储结构为（ ）的线性表。
A）压缩存储 B）顺序存储或链式存储 C）索引存储 D）散列存储 7. 对线性表进行折半查找的前提条件是（ ）。
A）线性表以顺序方式存储，并且按关键字的查找频率排好序 B）线性表以顺序方式存储，并且按关键字的大小排好序 C）线性表以链式方式存储，并且按关键字的大小排好序 D）线性表以链式方式存储，并且按关键字的查找频率排好序
8. 在分块查找中，若用于查找表的长度为n，它被等分为k个子表，每个子表的长度均为n/k，则分块查找的平均查找长度为（ ）。
A）n+k B）k+k/n C）(k+k/n)/2+1 D）(k+k/n)/2
28
9. 在分块查找中，若用于查找表的长度为n，它被等分为若干个子表，每个子表的长度均为s，则分块查找的平均查找长度为（ ）。
A）(n+s)/2 B）(n+s)/2+1 C）(s+n/s)/2+1 D）(s+n/s)/2
10. 在分块查找中，若用于查找表的长度为144，它被等分为12个子表，每个子表的长度均为12，则分块查找的平均查找长度为（ ）。
A）12 B）24 C）13 D）79
11. 在分块查找中，若用于查找表的长度为117，它被等分为9个子表，则分块查找的平均查找长度为（ ）。
A）11 B）12 C）13 D）9
12.在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（ ）。
A）n B）log2n C）(h+1)/2 D）h
13.从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度的为（ ）。
A）O(n) B）O(1) C）O(log2n) D）O(n)
14.从具有n个结点的二叉排序树中查找一个元素，在最坏情况下的平均查找长度是（ ）。
A）n B）log2n C）(n+1)/2 D）(n-1)/2
15. 若对n个元素进行插入排序，在进行第i遍排序过程前，有序表中的元素个数为（ ）。
A）i B）i+1 C）i-1 D）1
16. 若对n个元素进行插入排序，在进行第i遍排序时，为寻找插入位置，最多需要进行（ ）次元素的比较（假设第0号元素放有待查元素关键字）。
A）i B）i-1 C）1 D）i+1 17. 若对n个元素进行插入排序，在进行第i遍排序时，假设元素a[i+1]的插入位置为，a[j]，则需要移动元素的次数为（ ）。
A）j-i B）i-j-1 C）i-j D）i-j+1 18. 对n个元素进行插入排序的过程中，共需要进行（ ）遍。
A）n+1 B）n C）2n D）n-1 19. 对n个元素进行插入排序的时间复杂度为（ ）。
A）O(1) B）O(n) C）O(n) D）O(log2n)
20. 在对n个元素进行冒泡排序的过程中，第一遍排序，最多需要进行（ ）对相邻元素之间的交换。
A）n-1 B）n C）n/2 D）n+1
21. 在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度的为（ ）。
A）O(1) B）O(n) C）O(n) D）O(log2n) 22. 在对n个元素进行冒泡排序的过程中，最坏情况下的时间复杂度为（ ）。
A）O(1) B）O(n) C）O(n) D）O(log2n) 23. 在对n个元素进行冒泡排序的过程中，最少需要（ ）遍完成。
222
2
29
A）1 B）n C）n-1 D）n/2
24. 在对n个元素进行快速排序的过程中，第一次划分最多需要移动（ ）次元素，包括开始把基准元素移动到临时变量中的一次。
A）n/2 B）n-1 C）n D）n+1 25. 在对n个元素进行快速排序的过程中，最好情况下需要进行（ ）遍。
A）n B）n/2 C）log2n D）2n 26. 在对n个元素进行快速排序的过程中，最坏情况下需要进行（ ）遍。
A）n B）n/2 C）log2n D）n-1 27. 在对n个元素进行快速排序的过程中，最好情况下的时间复杂度为（ ）。
A）O(1) B）O(n) C）O(nlog2n) D）O(log2n) 28. 在对n个元素进行快速排序的过程中，最坏情况下的时间复杂度为（ ）。
A）O(1) B）O(n) C）O(nlog2n) D）O(log2n)
29. 对元素序列（3，7，5，9，1）进行快速排序，在进行第一遍划分时，需要移动元素的次数为（ ），假设不包括开始把基准元素移动到临时变量的一次。
A）1 B）2 C）3 D）4
30. 在对下列四个序列进行快速排序时，各以第一个元素为基准进行第一遍划分，则在该次划分过程中，需要移动元素次数最多的序列为（ ）。
A）1，3，5，7，9 B）9，7，5，3，1 C）5，3，1，7，9 D）5，7，9，1，3
31.对元素序列（7，3，5，9，1，12，8，15）进行快速排序，在进行第一遍划分后，得到的左区间中元素的个数为（ ）。
A）2 B）3 C）4 D）5
32. 在对n个元素进行选择排序的过程中，在第i遍，需要从（ ）个元素中选择出最小值元素。
A）n-i+1 B）n-i C）i D）i+1
33. 对n个元素进行选择排序，在进行任一遍排序的过程中，为寻找最小值元素所需要的时间复杂度量级为（ ）。
A）O(1) B）O(n2)
C）O(log2n) D）O(n)
34. 若对n个元素进行归并排序，则进行归并的遍数为（ ）。
A）n B）n/2
C）?log2n? D）n-1
35. 对n个元素进行归并排序，在进行每一遍的时间复杂度量级为（ ）。
A）O(1) B）O(n2)
C）O(log2n) D）O(n)
36. 若一个元素序列基本有序，则选用（ ）方法较快。
A）插入排序 B）选择排序
30
22