图4
14．n个元素进行冒泡法排序，通常需要进行__ n-1__趟冒泡。 15．如图5所示的二叉树，其先序遍历序列为__ abdefcg __。
16．二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是__不正确____的。(回答正确或不正确)
17．图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是_正确_____的。(回答正确或不正确) 18．根据搜索方法的不同，图的遍历有__深度优先搜索遍历_、 _广度优先搜索遍历_ 两种方法 19．对记录序列排序是指按记录的某个关键字排序，记录序列按__主关键字_______排序结果是唯一的。
20．按某关键字对记录序列排序，若关键字 相等 的记录在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。
三、综合题
1．（1）利用筛选过程把序列{42，82，67，102，16，32，57，52}建成堆（小根堆），画出该堆（不要求中间过程）。
a b c d e f g 图5 16 42 32 52 82 67 57 102 （2）写出对上述堆对应的完全二叉树进行中序遍历得到的序列。
答：102，52，42，82，16，67，32，57
2．设查找表为(16,15,20,53,64,7),
(1)用冒泡法对该表进行排序（要求升序排列），写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多少趟冒泡？第j趟要进行多少次元素间的比较？
答： (1)原序列16 15 20 53 64 7
15 16 20 53 7 64 n-1趟 15 16 20 7 53 64 n-j次
16
15 16 7 20 53 64 15 7 16 20 53 64 7 15 16 20 53 64
(2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树.(要求以数据元素作为树结点)
15 20 64 7 53 16 (3)平均查找长度=（1*1+2*2+3*3）/6=14/6
3．
(1) 设有查找表{5,14,2,6,18,7,4,16,3},依次取表中数据，构造一棵二叉排序树。
5 2 14 4 6 18 3
7 16 （2）说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。
答： 中序遍历
中序 2，3，4，5，6，7，14，16，18
4．（1）设有一个整数序列{50，38，16，82，110，13，64}，依次取出序列中的数，构造一棵二叉排序树
50 38 82 16 64 110 13
（2）利用上述二叉排序树，为了查找110，经多少次元素间的比较能成功查到，为了查找15，经多少次元素间的比较可知道查找
失败
17
答： 三次；四次
5．（1）对给定权值2，1，3，3，4，5，构造哈夫曼树。 18 11 7 6 5 3 4 3 3
2 1 wpl1=45
（2）同样用上述权值构造另一棵哈夫曼树，使两棵哈夫曼树有不同的高度，并分别求两棵树的带权路径长度。18 7 11 3 4 6 5 2 1 3 3
四、程序填空题
1．以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、rear分别是链队列的队头、队尾指针
struct node { ElemType data;
struct node *next; };
struct node *front，*rear;
void InQueue(ElemType x) __ malloc(sizeof (struct node))__; p->next=NULL;
__ rear->next=p ___; __ p ____; 2．设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。 #define NULL 0 void main( )
{NODE a,b,c,d,*head,*p; 18
{
struct node *p;
p= (struct node*) p->data=x;
rear= }
a.data=6; b.data=10; c.data=16;
d.data=4; /*d是尾结点*/ head= &a ; a.next=&b; b.next=&c; c.next=&d;
d?next=NULL ; /*以上结束建表过程*/ p=head; /*p为工作指针，准备输出链表*/ do
{printf(“%d\\n”, p->data ); p=p->next ; }while( p!=NULL ); }
3．以下函数在head为头指针的具有头结点的单向链表中删除第i个结点，
struct node { int data;
struct node *next; };
typedef struct node NODE int delete(NODE *head,int i ) {
NODE *p,*q; int j; q=head; j=0;
while((q!=NULL)&&( __ j __ q=q->next ___; j++; } if(q==NULL) return(0); p= __ q->next ____; __ q->next ____=p->next; free(___p ____); return(1); } 4．以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中，左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。 void Postorder (struct BTreeNode *BT) { if(BT!=NULL){ Postorder(BT->left) ; Postorder(BT->right) ; printf(“%c”,BT->data) ; } } 19