时循环也能终止执行，若给定值为K，表的长度为n，查找表的数据单元用R.item表示，键值用key表示，则在表尾设置岗哨的相应方法描述为_________。 10．对于二叉排序树的查找，若根结点元素的键值大于被查找元素的键值，则应该在该二叉树的_________上继续查找。
11．采用二次探测法解决冲突问题，对于键值为K、容量为m的闭散列表，若散列地址为d0，则发生冲突后，其第三个后继散列地址d3为___________。
12．对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到已排序的有序表时，为寻找其插入位置需比较________次。
13.对n个元素进行冒泡排序时，最少的比较次数是___________。 三.应用题（共30分）
1．已知序列(17，18，60，40，7，32，73，65，85)，请给出采用冒泡排序
法对该序列作升序排序时每一趟的过程。(6分)
2．如图所示，在栈的输入端有6个元素，顺序为A，B，C，D，E，F能否在
栈的输出端得到序列DCFKBA及EDDFCA?若能，给出栈操作的过程，若不能，简述其理由。(8分)
11
5．设散列函数为H(K)=K mod 11，散列表长度为11(散列地址空间0．．10)，给定表(SUN，MON，TUE，WED，THU，FRI，SAT)中，取单词的第一个字母在英语字母表中的序号为键值K，构造一开散列表，并用拉链法解决有关地址冲突。(7分)
四、设计题（共14分）
1.设以二叉链表为二叉树的存储结构,结点的结构如下: lchild data rchild 求二叉树中叶子结点的数目
2.已知奇偶转换排序如下所述:第一趟对所有奇数i,a[i]和 a[i+1]进行比较,第二趟对所有偶数i,将a[i]和a[i+1]进行比较,每次比较时若a[i]>a[i+1],则将两者交换,以后重复上述二趟过程交替进行,直至整个数组有序。 （1） 试问：排序结束的条件是什么？（2分）
12
（2） 编写一个实现上述排序过程的算法：void oesort(int a[],int n)。 其中data域为整数,试设计一个算法void change(bitreptr r):若结点左孩子的data域的值大于右孩子的data域的值,则交换其左、右子树。（6分）
模拟试卷八参考答案
一、单项选择题(每小题2分，共30分) 1.C 2.D 3.D 4.B 5.A 6.D
7.B
8.A
9.D
10.D
11.C 12.A 13.B 14.B 15.A
二、填空题(每空2分，共26分) 1.O(m*n)
2. 索引表
3.p->next=q->next; 5. 深度优先搜索 6.pop(s),push(s,5) 7.B、Ｃ
9.R.item[n+1].key=k 10. 左子树
11.(do+22)%m
13.n-1
三、应用题(共30分) 1. (6分) 依题意：
1趟 (17,18,60,40,7,32,73,65,85) 2趟 (17,18,40,7,32,60,65,73,85) 3趟 (17,7,18,32,40,60,65,73,85) 4趟 (7,17,18,32,40,60,65,73,85) 5趟 (7,17,18,32,40,60,65,73,85)
4.Ls!=NUUL 8.A、D、G 12.3
13
第5趟元素未交换,则排序结束。(各1分) 2. (8分)
1. 能得到序列: DCFEBA(1分)
操作过程如下:push,push, push,push,pop,pop, push,push, pop,pop, pop,pop(4分) 2. 不能得到序列:EDBFCA(1分)
因为要得到E需将A,B,C,D顺序入栈, 根据LIFO原则, 不可能A在C之前出栈(2分) 3.(6分)
先序遍历序列:ABCDFGHE 中序遍历序列:BADGFHCE 后序遍历序列:BGHFDECA ★各2分 4.(3分) V2 V4 V0 V1 V3 5. (7分)
0 1 2 3 4 5 6 ^ SAT WED ^ MON ^ ^ ^ ^ 14 FRI ^ SUN SAT ^ TUE THU ^
四、设计题(共14分) 1. (6分)：
int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目 {
if(!T) return 0; //空树没有叶子
else if(!T->lchild&&!T->rchild) return 1; //叶子结点
else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数}//LeafCount_BiTree
2.(8分)：
void OE_Sort(int a[ ],int n)//奇偶交换排序的算法 {
change=1; while(change) {
change=0;
15
for(i=1;i
a[i]<->a[i+1]; change=1; }
for(i=0;i
a[i]<->a[i+1]; change=1; } }//while }//OE_Sort
分析:本算法的结束条件是连续两趟比较无交换发生
16