第八章
一、单项选择题
(2) 一(5) DDCCD (6)一(9) DCCC 二、填空题
（1）8 （2）15 （3） 4.3 （4）中序 （5）记录的键值 （6）7 （7）63 （8）17 （9）17 （10）O(n) (11)O(log2n) (12)越大
（13）散列函数 （14）处理冲突方法 （15） 装填因子 （16）索引表
（17）该块的起始地址 （18） 100 （19）100 （20）101 （21）?log2(n+1)? (22)同义词 （23）n(n+1)/2 (24) 63 (25) m (26)?m/2? (27)m-1 (28) ?m/2?-1 (29)m (30)?m/2? 三、应用题
1．判定树见下图。
查找成功的平均查找长度
ASL=（1+2*2+3*4+4*6）/13=41/13 查找失败时与键值最多比较次数为4。
2．二叉排序树见右图。在等概率情况下， 查找成功的平均查找长度ASL=29/9≈3.2 查找失败时，与键值最多比较次数是5。
3.构造一棵平衡二叉排序树
的过程见右图。
等概率情况下，查找成功的平均查找长度 ASL=（1+2*2+3*4+4*2）/9≈2.8
查找失败时，与键值的最多比较次数是4。
4.按不同的输入顺序输入4、5、6，建立相应的不同形态的二叉排序树见下图。
5.键值序列：{25，40，33，47，12，66，72，87，94，22，5，58} 散列地址： 3 7 0 3 1 0 6 10 6 0 5 3 用拉链法处理冲突，构造的散列表如下图：
33
0 1 2 3 4 5 6 7 8 9 10 11 ^ ^ ^ ^ ^ 33 12 25 5 72 40 ^ 66 22 ^
47 58 ^ ^ ^ 94 ^ 87 ^ 在等概率的情况下，查找成功的平均查找长度： ASL=（7+2*3+3*2）/12=19/12=1.4 查找失败的平均查找长度： ASL=（4+2*1+3*2）/12=1 6.已知散列表是：
1 1 2 3 4 5 6 7 8 9 10 11 12 50 21 57 45 37 查找key = 21 57 45 50
h0=key = 8 5 6 11 d=key+1 = 11 3 2 7 h1=(h0+d) = 6 8 8 5 h2=(h1+d) = 10 查找成功比较次数 2 2 3 2
查找成功的平均查找长度ASL=（1+2+2+2+3）/5=2 四、算法设计
1．按中序遍历二叉排序树可得到一个按键值从小到大排列的有序表，利用这个特点来判别二叉树是否为二叉排序树，算法如下：
#define max 99 #define min 0
int judge(BTnode *bt) { BTnode *s[max],*p=bt; int top=0,preval=min; do {
while(p)
{s[top++]=p; p=p->lchild; }
if(top>0) {p=s[--top];
if(p->data preval=p->data; p=p->rchild; } }while(p||top>0) return 1; } 第九章 34 一、单项选择题 (1)-(5) ABABC (6)-(10) ADDAC (11)-(15) BBADB (16)-(20) DBCAB (21)-(25) ADCBA 二、填空题 （1）插人排序 (2)交换排序 (3)选择排序 (4)归并排序 (5)基数排序 2 (6)O(nlog2n) (7)O(n) (8)O(nlog2n) (9)快速 (10)堆 (11)归并 (12)快速 (13)归并 (14)堆 (15)3 (16)选择 (17)O(n) (18)O(nlog2n) (19)O(nlog2n) 2 (20) n (22) 5 (23)4 (24) 8 三、应用题 1.解 不稳定的排序方法有快速排序、直接选择排序、堆排序，分别举例说明如下： （1）快速排序 给定键值序列{9，6，6}进行快速排序。 排序结果为{6，6，9}。 （2）堆排序 给定键值序列为{9,7,6,6}进行堆排序（小顶堆）的过程见下图。 9 6 9 9 (9) 6 6 6 (6) (6) 7 7 7 7 (7) 堆排序的结果为{6，(6) (6) (6) 6 9 6，7，9}。 （3）直接选择排序，例：给定排序码值序列为{6，6，4}，直接选择排序后结果为{4，6，6}。 （4）希尔排序，例给定排序码值序列为{4，2，2，5}，设d1=2,d2=1时，排序结果为{2，2，4，5}。 2.解： 冒泡排序： 第一趟：17，18，40，7，32，60，65，73，85 第二趟：17，18，7，32，40，60，65，73 第三趟：17，7，18，32，40，60，65 第四趟：7，17，18，32，40，60 第五趟：7，17，18，32，40（没有发生交换，结束排序） 3.解：希尔排序： 原序列： 10 18 14 13 16 12 11 9 15 8 d1=5 一趟排序 10 11 9 13 8 12 18 14 15 16 d2=2 结果 二趟排序 { 8 11 9 12 10 13 15 14 18 16} d3=1 结果 三趟排序结果 {8，9，10，11，12，13，14，15，16，18} 4．初始序列（1）{90，86，48，73，35，40，42，58，66，20}对应的完全二叉树见下图： 35 它是一个大顶堆。 初始序列（2）{12，70，34，66，24，56，90，86，36}对应的完全二叉树不是堆，将其调整成堆的过程见左图： 四、算法设计题 1． 单链表结点类型定义为： typedef struct node {int key; struct node *next; }Lnode; 直接选择排序是每次从n-i+1个结点中选择码值最小者，与第i个结点的码值进行交换，设p指向第i个结点，min指向无序表中码值最小的结点，算法描述如下： Void selesort1(Lnode *h) {Lnode *p,*q,*min; int x; p=h->next; while(p) {min=p; q=p->next; while(q) {if(q->key if(min!=p) {x=p->key; p->key=min->key; min->key=x; } p=p->next; } } 2.快速排序非递归算法描述如下（其中s为顺序栈）： void Quicksort1(RecType t[],int n) {int top,low=0,high=n,i,j,*s; RecType x; S=(int *)malloc(sizeof(int)*2*n); Top=0; Do{ while(low {i=low;j=high;x=r[i]; do{ while((r[i].key>=x.key)&&(i r[j]=r[i];j--;} }while(i if((i+1) 36 s[++top]=high;} high=i-1; if(top>0) {low=s[top--]; high=s[top--];} }while(top>0||low 37