（1）依次取a中各数据，构造一棵二叉排序树。
（2）为了成功查找到48需要进行多少次元素间的比较? （3）给出对该二叉树后序遍历的序列。
3．设有序表为(2, 5, 11, 12, 30, 48, 58, 70, 78, 79, 90) ,元素的序号依次为 1,2,3,??，11.
（1）画出对上述查找表进行折半查找所对应的判定树（树中结点用序号表示） （2）说明成功查找到元素2需要经过多少次比较？
(3) 说明不成功查找元素75需要经过多少次比较？ (4) 给出中序遍历该折半查找判定树的序列
4．设有序表为（3，9，15，26，38，41，53，74，81，96，97，99），元素的 序号依 次为1,2,??,12。
（1）画出对上述有序表进行折半查找所对应的判定树（树结点用序号表示）。
（2）设查找5号元素(38)，需要进行多少次元素间的比较才能确定不能查到, 依次和 哪些元素进行了比较？（要求写出具体元素）。 （3）给出后序遍历该二叉树的序列。 (4) 给出中序遍历该二叉树的序列。
四、程序填空题
1. 设有一个不带头结点的单向链表，头指针为head, p 、prep 是指向结点类型的指针，
该链表在输入信息时不慎把相邻两个结点的信息重复输入,以下程序段是在该单向链表中查找这相邻两个结点,，把该结点的数据域data打印出来，并把其中之一从链表中删除，填写程序中的空格。
prep=head; p=prep->next;
while(p - > data!=prep- >data) { prep=p;
__(1)___ }
printf(“min=%d”, __(2)___); prep->next= __(3)___
2.学生信息存放在结构数组中，每个数组元素存放一个学生的信息，下标从0到n-1。
数组元素按学号num由小到大有序排列，以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字num等于k的记录，查找成功返回该记录的下标(数组元素的下标)。失败时返回-1，完成程序中的空格。
typedef struct
{
char sex; int num; …… }NODE;
int Binary_Search(NODE a[],int n, int k) {
int low,mid,high; low=0; high=n-1;
while(___(1)_____) {
mid=(low+high)/2; if(a[mid].num = =k)
return __(2)______; else if(___(3)_____) low=mid+1; else __(4)______; }
return -1 ; }
3 . 以下程序是折半插入排序的算法(按记录中关键字key排序)
设待排序的记录序列存放在a*1+,…a*n+中，以a[0]作为辅助工作单元，以下程序是要把a[i] 插入到已经有序的序列a*1+,…a*i-1]中。 void binsort (NODE a[ ],int n)
{ int x,i,j,s,k,m;
for （i=2；i<=__(1)___ ; i++） { a[0]=a[i]; x= a[i].key; s=1; j=i-1; while (s<=j) { m=__(2)___ if( x
for ( k=i-1;k>=j+1;k- -) __(5)___=a[k]; a[j+1]=a[0]; } }
4．以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回值是指向树结点的结构指针p（查找成功p指向查找到的树结点，不成功，则p指向为NULL），完成程序中的空格。
struct bnode { int key;
struct bnode *left;
struct bnode *right; } ;
typedef struct bnode Bnode
Bnode *BSearch(Bnode *bt, int k) /* bt用于接收二叉排序树 的根结点的指针，k用以
接收要查找的关键字*/
{ Bnode *p; if(bt = = NULL) return (bt); ___(1)_____
while(p->key != __(2)___)
{ if(k
___(3)_____; else ___(4)_____;
if(p==NULL) break; } return p ; }
期末综合练习一答案
一、单项选择题
1．C 2．B 3．C 4．D 5．A 6．B 7．D 8．A 9．C 10．B 11．D 12．C 1314．A 15．B 16．D 17．A 18．B 19.C 20．D 21．D 22．B 23．B 2425．D 26．B 27．A 28．B 29．C 30．A 二、填空题 1. 5
2．树形 3. 3
4．先进后出 5. sq->rear++; 6．3
7.2,4,3,5,6,8 8．4 9. 3
10．sq->fronf++; 11. 数据元素 12．sq->rear++;
13. front= =(rear+1)% MaxSize 14．12,14,13,15,16,18 15.直接插入排序 16．数据元素 17.8
18．front= =rear 19. p->prior； 20．折半插入排序
．A ．D 21. 结点的直接前驱 22．(3,4, a3,4) 23. 存储
24．P所指结点的直接前驱
三、综合应用题 1.
(1)图3 (2)中序遍历 1 , 3 , 5 , 7 , 8 , 9 , 10 , 12 , 13 (3) 5次 (4) 3,7,9,10,8,5,13,12,1
1 12 5 13 3 8 7 10 9
2
(1)图4 (4)4次 (5)15,48,56,30,74,62
图3