中国石油大学《数据结构》复习题及答案

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 (kR[k+1]) { x = R[k]; R[k] = R[k+1]; R[k+1] = x; exchange =1; }

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 data) { pre = pa; pa = pa -> next;}

12