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