（1）树中哪个结点为根结点？哪些结点为叶子结点？ （2）结点B的双亲为哪个结点？其子女为哪些结点？ （3）哪些结点为结点D的兄弟？哪些结点为结点K的兄弟？ （4）结点A、C的度分别为多少？树的度为多少？ （5）以结点B为根的子树的高度为多少？
答案：（1）A;E,G,H,I,C,J,K,L
(2)A;E,F,G,H,I (3)B,C,L;J
(4)4;0;4 (5)3
56、设某密码电文由a,b,c,d,e,f,h,i 8个字母组成，每个字母在电文中的出现
频率分别是7，19，2，6，32，3，21，10，试为这8个字母设计相应的哈 夫曼编码
答案：a:1110;b:00;c:11010;d:1100;e:10;f:11011;h:01;i:1111 57、设有一无向图G=(V,E),其中
V={1,2,3,4,5,6},E={(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5)}。
（1） 按上述顺序输入后，画出其相应的邻接表；
（2） 在该邻接表上，从顶点4开始，写出DFS序列和BFS序列。
58、已知散列函数为H(K)=K mod 7,健值序列为19, 01, 23, 14, 55, 68, 11, 82, 36，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度
参考答案：
开散列表省略， ASL= 13/9
59、已知序列（70，83，100，65，10，32，7，9），请给出采用直接插入排序法对该序列作升
序排序时的每一趟的结果
六、程序填空题
1、p是指向待删结点的前趋结点
void delete_lklist(lklist head,int I) {
p=find_lklist(head,I-1)
if(p!=NULL)&&( ( p–>nex ) !=NULL) {
q= p –>next;
p –>next= ( q –>next ) ; free(q); }
else error(“不存在这样的结点”)； }
2、单链表的插入操作
void insert_lklist(lklist head,datatype x,int I) {
p=find_lklist(head,I-1) if(p=NULL)
error(“不存在这样的结点”） else {
s= ( malloc ) (size);
s –>data=( x );
s –>next = p –>next; p –>next=( s ); } }
3、顺序表的插入操作
# define maxsize 100
typedef int DataType; typedef struc{
DataType data[maxsize]; int last; } Sqlist;
Void Insert_sqlist(Sqlist L，DataType x，int I) { if (L.last==( maxsize )) error(“表满”）； if(I<( 1 ) || I>( L.last+1 ))
error(“非法位置”）； for(j=L. last;j>=I;j--)
L.data[j]= (L.data[j-1] ); L.data[I-1]=x; L. last= ( L.last+1 ); }
4、查找第一个与给定值X相同的表结点的序号。 Pointer find_lklist(lklist head,int I) {
p=( head );j=0;
while(p –>next!=NULL)&&( ( p –> data ) !=x) {
p=( p –>next );j++; }
if p –> data ==x return(p); else return(0); }
5、顺序表上的查找算法。
int Search_Seq(SSTable ST, KeyType key) {。
ST.elem[( 0 )].key = key; // “哨兵”
for (i=ST.length; ST.elem[i].key!=key; ( i-- )); // 从后往前找 return i; // 找不到时，i为0 } // Search_Seq
6、INITIATE()的功能是建立一个空表。请在________处填上正确的语句。 lklist initiate_lklist() /*建立一个空表*/
{__ t=malloc(size)_; ___t –>next=NULL _; return(t); }
7、以下为求单链表表长的运算，分析算法，请在 ________处填上正确的语句。 int length_lklist(lklist head) /*求表head的长度*/ { p=head ;
j=0;
while(p->next!=NULL) {__ p=p –>next _; j++;
}
return(j); /*回传表长*/ }
8、以下对r[h],r[h+1],??r[p]子序列进行一趟快速排序。请分析算法，并在________上填充适当的语句。
int quickpass(list r,int h,int p)
{i=h;j=p;x=r[i];/*置初值，以第一个记录的键值为标准*/ while(i {while((r[j].key>=x.key)&&(i { (r[i]=r[j] );i++;/* 将r[j].kiy if(i r[i]=x;return(i);/*一趟快速 排序结束，将x移至正确的位置*/ } 9、在一个单链表中的P所指的结点之前插入一个S所指结点，可执行如下操作。 S->next= ( p->next ) ; p->next=s; t=p->data; p->data= ( s->data ) ; s->data= ( t ) ; 10、以下算法在有序表R中用二分查找法查找键值等于K的元素，请分析程序，并在________上填充合适的语句。 int binsearch(sqtable R,keytype K) {low=1;hig=R.n;/*置查找区间初值。low,hig分别标记查找区间的下、上界*/ while(low<=hig) {mid=（low+hig)/2; switch {case K==R.item[mid].key:return(mid);/*找到，返回位置mid*/ case K } return(0);/*若区间长度已为0但仍不成功，则返回0，表示查找不成功*/ } 11、以下为单链表的建表算法，分析算法，请在____处填上正确的语句。 lklist create_lklist2() /*直接实现的建表算法。*/ { head=malloc(size); p=( head ); scanf(“%f”,&x); while(x!=’$’) { q=malloc(size); q->data=x; p->next=q; ( p=q ); scanf(“%f”,&x); } ( p->next=NULL ); return(head); } 12、以下为冒泡排序的算法。请分析算法，并在________上填充适当的语句。 void bulbblesort(int n,list r) /*flag为特征位，定义为布尔型*/ {for(i=1;i=( n-1 );i++) {( flag=1 ); for(j=1;j=n-i;j++) if(r[j+1].key 13、顺序表的删除操作 # define maxsize 100 typedef int DataType; typedef struc{ DataType data[maxsize]; int last; } Sqlist; Void delete_sqlist(Sqlist L，int I) { if(I<1 || I>( L.last+1 )) error(“非法位置”）； for(j=I+1;j>= L.last;j++) L.data[j-2]= ( L.data[j-1] ); L. last=( L. last-1 ); }