《数据结构》期末复习题答案

.

哈夫曼编码为：a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000 注意：答案不唯一

8.

试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。

301218743125116

WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69

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 其中： h1(key)=key+1 回答下列问题：

（1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？ （2）该散列表在等概率查找时查找成功的平均查找长度为多少？ 答：

（１）对关键字35、20、33和48进行查找的比较次数为３、２、１、１； （２）平均查找长度ASL 11.

请画出与下列二叉树对应的森林。

答：

i=0,1,…，m-1

?3?2?1?1?29?55

.

.

12.

对于给定结点的关键字集合K={5，7，3，1，9，6，4，8，2，10}，

（1）试构造一棵二叉排序树；

（2）求等概率情况下的平均查找长度ASL。 答：

5 3 1 2 （2）ASL=(1*1+2*2+3*4+4*3)/10=2.9 13.

给出下图对应的邻接矩阵，并给出A，B，C三个顶点的出度与入度

7 4 6 8 9 10

答案: 邻接矩阵为： A B C D E F

A?0B??1C?0?D?0E?1?F??000100?01000??00111??00000? 10100??10010??其中顶点A的入度为2，出度为1； 其中顶点B的入度为2，出度为2； 其中顶点C的入度为1，出度为3；

.

.

14.

已知图5.32如下所示，求从顶点a到其余各顶点的最短路径。（给出求解过程）

b 6 a 3 c 2 5 d 2 3 f 5 3 4 答：

e 终点 b c d e f vj S 15.

阅读下列算法，并回答问题：

6 (a,b) 3 (a,c) ? ? ? c {a,c} 5 (a,c,b) 6 (a,c,d) 7 (a,c,e) ? b {a,c,b} 最短路径求解过程 6 (a,c,d) 7 (a,c,e) ? d {a,c,d} 7 (a,c,e) 9 (a,c,d,f) e {a,c,e} 9 (a,c,d,f) f {a,c,d,f} （1）假设串由合法的英文字母和空格组成，并以’\\0’作结束符。设串s=”??I?am?a???student”(?表示空格符)，写出f30

（s）的返回值；

（2）简述算法f30的功能。 int f30 (char*s) 答案：

(1) 4

(2)算法功能：统计单词的个数。

16.

阅读下列函数,并回答问题：

（1）假设队列q中的元素为(a,b,c,d,e),其中“a”为队头元素。写出执行函数调用Conv(&q)后的队列q； （2）简述算法Conv的功能。

答案：

（1） （2）

17.

e，d，c，b，a 将队列里的值反转

阅读下列函数,并回答问题：

.