2020年10月自考试题《数据结构导论》答案

 

应用题，每题6分

1.写出该稀疏矩阵的三元组表示法。

答案：

（0,0,5）

（2,1,-1）

（2,3,7）

（3,1,6）

（4,4,9）

（5,5,8）

2.将下图所示的二叉树转化为森林。

 

答案：

3.设某通信系统中一个待传输的文本中有6个不同的字符a,b,c,d,e,f，出现的频率分别为0.5，0.7，1.4，2.2，2.4，2.8，画出哈夫曼树并写出哈夫曼编码。（要求左孩子的权值小于右孩子的权值）

答案：

哈夫曼树如下图：

字符a的哈夫曼编码为：1000

字符b的哈夫曼编码为：1001

字符c的哈夫曼编码为：101

字符d的哈夫曼编码为：00

字符e的哈夫曼编码为：01

字符f的哈夫曼编码为：11

4.选定散列函数为H(key)=key mod 13，试用链地址法建立键值为26,41,25,65,07,15,12,49,51,31,62的散列表。

答案：

 

5.有一键值序列{83,40,63,13,84,35,96,57,39,79,61,15}，写出直接选择排序和冒泡排序第一趟的结果。（按键值由小到大）

答案：

直接选择排序：

13，【83,40,63,84,35,96,57,39,79,61,15】

冒泡排序：

【40,63,13,83,35,84,57,39,79,61,15】,96