6．
(1) 设有查找表{5,14,2,6,18,7,4,16,3},依次取表中数据，构造一棵二叉排序树。
（2）说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。
四、程序填空题
1．以下冒泡法程序对存放在a[1]，a[2]，??，a[n]中的序列进行排序，完成程序中的空格部分，其中n是元素个数，要求按升序排列。
void bsort (NODE a[ ], int n) { NODE temp;
int i,j,flag;
for(j=1; （1） ;j++); {flag=0;
for(i=1; （2） ;i++) if(a[i].key>a[i+1].key)
{flag=1; temp=a[i];
（3） ; （4） ; }
if(flag= =0)break; } }
程序中flag的功能是（5）
2．以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。
void Preorder (struct BTreeNode *BT)
{ if(BT!=NULL){
（1） ; （2） ;
（3） ; } }
3．设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。
#define NULL 0
void main( )
6
{NODE a,b,c,d,*head,*p; a.data=6; b.data=10; c.data=16;
d.data=4; /*d是尾结点*/ head= （1） ; a.next=&b; b.next=&c; c.next=&d;
（2） ; /*以上结束建表过程*/ p=head; /*p为工作指针，准备输出链表*/ do
{printf(“%d\\n”, （3） ); （4） ; }while( （5） ); }
4．以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。
void Inorder (struct BTreeNode *BT) { if(BT!=NULL){
（1） ; （2） ; （3） ; } }
7
答案
一、单项选择题 1．D 2．C 3．D 4．C 5．D 6．A 7．A 8．A 9．D 10．D 11．C 12．A 13．D 14．A 15．C 16．D 17．B 18．D 19．D 20．C 21.D 22．A 23．B 24、B 25．D 26．A 27．A 28．C 29．A 30．A
二、填空题
1．物理（存储） 3．线性
5．结点的直接后继 结点的直接前驱 7．p->next=head;
9．h=h->next;
11．串长度相等且对应位置的字符相等 13．先序、中序、后序、层次 15．2n-1
17．7
19．abdgcefhi 21．存储地址 23．正确 2．p=p->next; 4．p->next=head； 6．hs->data;hs->next; 8．（r+1）%MaxSize=f 10．4 12．4；2 14．18
16．正确
18．先进后出（后进先出） 先进先出 20．顺序存储结构
22．2k
-1
24．顺序存储 链式存储
三、综合题
8
（后进后出） 1． (1) 41
83 49 47 43 47 43 47 41 41 43 59 83 43 59 49 49 49 83 59 83 47 41 47 41 43 59 83 49 59
图3 (2) 83 83
图4
9
83 49 41 59 43 43 47 43 59 47 49 47 49 41 83 59 41 59 49 47 47 49 59 43 41 83 43 41
2．
（1）s=（NODE*）malloc(sizeof(NODE));s->data=1;
（2）p->next=s;
s->next= NULL；
free(s)
（3）head = head ->next； （4）p1->next= p->next；
p->next=p1；
3．
(1)19，48，84，116，200 (2) 6 3 9 1 4 7 11 2 5 8 10 12
图5 (3)3次 4． （1） 22 12 130 10 15 25 150
19 100 200
（2）4次；3次
10