7.
假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}，请为这8个字母设计哈夫曼编码。
8. 试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。 9.
画出与如图所示森林对应的二叉树。
10.
已知一个散列表如下图所示： 35 20 33 48 59 0 1 2 3 4 5 6 7 8 9 10 11 12
其散列函数为h(key)=key, 处理冲突的方法为双重散列法，探查序列为： hi=(h(key)+i*h1(key))%m i=0,1,…，m-1 其中： h1(key)=key+1 回答下列问题：
（1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？ （2）该散列表在等概率查找时查找成功的平均查找长度为多少？ 11.
请画出与下列二叉树对应的森林。
9
12.
对于给定结点的关键字集合K={5，7，3，1，9，6，4，8，2，10}，
（1）试构造一棵二叉排序树；
（2）求等概率情况下的平均查找长度ASL。 13.
给出下图对应的邻接矩阵，并给出A，B，C三个顶点的出度与入度
14.
已知图5.32如下所示，求从顶点a到其余各顶点的最短路径。（给出求解过程）
b 6 a 3 c 15.
阅读下列算法，并回答问题：
4 2 3 2 5 5 d 3 f e （1）假设串由合法的英文字母和空格组成，并以’\\0’作结束符。设串
s=”??I?am?a???student”(?表示空格符)，写出f30（s）的返回值； （2）简述算法f30的功能。 int f30 (char*s) {
int i, n, inword; n=inword=0;
for (i=0;s[i]!=’\\0’;i++)
if (s[i]!=’?’&& inword==0) {
inword=1;
10
n++;
}
else if (s[i]==’?’&& inword==1) inword=0; return n; }
16.
阅读下列函数,并回答问题：
（1）假设队列q中的元素为(a,b,c,d,e),其中“a”为队头元素。写出执行函数调用Conv(&q)
后的队列q；
（2）简述算法Conv的功能。
void Conv (Queue *Q) { Stack S; InitStack(&S); while (!QueueEmpty(Q)) Push(&S, DeQueue(Q)); while (! StackEmpty(&S)) ＥnQueue(Q,Pop(&S)); } 17.
阅读下列函数,并回答问题：
已知整形数组L［1..8］中的元素依次为（19，18，15，17，16，13，12，10），阅读下列函数，并写出执行函数调用sort(L, 8)时，对L进行的头两趟（pass分别为0和1）处理结果。
void sort (int R[],int n) { int pass = 0, k, exchange, x; do { k=pass%2+1; exchange = 0; while (k
K+=2;
11
} pass ++; }while (exchange = = 1|| pass <=1); } 18.
已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为m，散列函数为Hash(key)=key%m。链表的key next 结点结构为： 。请在空缺处填入适当内容，使其成为一个完整算法。 void f33 (LinkList L, LinkList H［］, int m)
{//由带头结点的单链表L生成散列表H，散列表生成之后原链表不再存在 int i,j;
LinkList p,q; for (i=0;i H［i］= (1) ; p=L->next; while(p) { q=p->next; j=p->key%m; (2) ; H［j］=p; (3) ; } free(L); } 19. 下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。 void union (LinkList La, LinkList Lb) { //本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中 LinkList pre = La, q; LinkList pa = La -> next; LinkList pb = Lb -> next; free (Lb); while (pa && pb) { if (pa -> data 12