数据结构参考题及答案（修正版）

34、指向前趋节点和后继节点的指针称为线索，加了线索的二叉树称为___线索二叉树___。

35、常用的图的遍历方法有两种；深度优先搜索和____广度优先搜索_____。 36、为了能有效地应用HASH查找技术，必须解决的两个问题是____构造一个好的hash函数_____和___确定解决冲突的方法____。

37、顺序表中逻辑上相邻的元素的物理位置 相邻 。单链表中逻辑上相邻的元素的物理位置 不 相邻。

38、在一个长度为n的数组的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 n-i 个元素。

四、简答题。

1、已知两个一元多项式A(x)和B(x)如下：

A(x) = 3 + 5x + 7x5 + 9x15 B(x) = 4x – 7x5+ 21x7 要求给出图形示意表示：

（1）采用单链表表示一元多项式A(x)和B(x)

（2）给出求和A(x)+B(x)多项式的单链表（要求给出结点指针变化过程）

2、简述下列术语：数据，数据元素、数据对象、数据结构、存储结构。

3、简述栈和线性表的差别。

4、试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区

别。

5、已知一棵树边的集合为

{(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法画出此树，并回答下列问题。

（1） 哪个是根结点？ a

（2） 哪些是叶结点？ d m n j k f l （3） 哪个是g的双亲？ c

（4） 哪些是g的祖先？ a b c （5） 哪些是g的孩子？ j k （6） 哪些是e的子孙？ i m n

（7） 哪些是e的兄弟？哪些是f的兄弟？ dgfh degh （8） 结点b和n的层次各是多少？ 2 5 （9） 树的深度是多少？ 5

（10）以结点c为根的子树的深度是多少？ 2 （11）树的度是多少？ 3

6、何谓队列的“假溢出”现象，如何解决？

7、简述队列和堆栈这两种数据类型的相同点和差异处。

8、线索二叉树的特点是什么？分别写出二叉树的先序，中序，后序遍历结果，并画出这个二叉树的中序线索链表图。a b c d e

先序：abdce 中序：bdaec 后序：dbeca

9、对于下图，试给出：

（1）每个顶点的入度，出度。

d(1)+ = 1, d(1)- = 2 d(2)+ = 2, d(1)- = 2 d(3)+ = 3, d(3)- = 1 d(4)+ = 3, d(4)- = 0 d(5)+ = 2, d(5)- = 3 d(6)+ = 1, d(6)- = 2

（2）邻接矩阵和入边表图示。 （3）强连通分量。

1，23652，4

1 4

5

6

2 3

000100010010101000000011邻接矩阵

000111 010000000000入边矩阵(逆邻接矩阵)

101010

11010000100101000000100010、已知一组元素的排序码为:（46,74,16,53,14,26,40,38,86,65,27,34）写出用直接选择排序方法进行每趟排序的结果。 【14】,74,16,53,46,26,40,38,86,65,27,34 【14,16】,74,53,46,26,40,38,86,65,27,34 【14,16,26】,53,46,74,40,38,86,65,27,34 【14,16,26,27】,46,74,40,38,86,65,53,34 【14,16,26,27,34】,74,40,38,86,65,53,46 【14,16,26,27,34,38】,40,74,86,65,53,46 【14,16,26,27,34,38,40】,74,86,65,53,46 【14,16,26,27,34,38,40,46】,86,65,53,74 【14,16,26,27,34,38,40,46,53】,65,86,74 【14,16,26,27,34,38,40,46,53,65】,86,74 【14,16,26,27,34,38,40,46,53,65,74】,86 【14,16,26,27,34,38,40,46,53,65,74,86】

11、设二叉树的顺序存储结构如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 E A F ∧ D ∧ H ∧ ∧ C ∧ ∧ ∧ G I ∧ ∧ ∧ ∧ B （1） 根据其存储结构，画出该二叉树。

（2） 写出按前序、中序、后序遍历该二叉树所得的结点序列。

前序：EADCBFHGI 中序：ABCDEFGHI

后序：BCDAGIHFE

（3） 画出二叉树的后序线索化树。

12、已知某电文中只有ABCDE共5个字母，权值集合W={0.25,0.10,0.20,0.30,0.15}，试分析Huffman树的生成过程，画出存储结构表（初态和终态），以及最终的Huffman树，并用0/1给ABCDE这5个字母分别编码，最后写出电文：BAACDE的Huffman编码。

A(00),B(110),C(10),D(01),E(111).

BAACDE(11000001001111);

13、某系统在通信联络中只可能出现八种字符，它们分别是ABCDEFGH，其概率分别为0.05，0.19，0.18，0.09，0.12，0.23，0.13，0.01。现要对这八种字符进行Huffman编码，写出该编码值。画出该Huffman树(权值大的结点做左孩子)，在所有的结点上标出其权值，并求出这棵树的带权路径长度。 A(01010) B(11) C(000) D(0100) E(011) F(10) G(001) H(01011)

L(n)=0.05*5+0.19*2+0.18*3+0.09*4+0.12*3+0.23*2+0.13*3+0.01*5 = 2.79 14、已知一组元素为（46，25，78，62，12，37，70，29），试画出按元素排列次序插入生成的一棵二叉排序树。

15、简述起泡算法的过程，并写出使用起泡排序方法对下面的整数数列进行排序的结果（写出每趟排序后的结果）： {97，66，49，38，26，17，9，6}。 {66，49，38，26，17，9，6,(97)} {49，38，26，17，9，6,(66, 97)} {38，26，17，9，6,(49, 66, 97)} {26，17，9，6,(38, 49, 66, 97)} {17，9，6,(26, 38, 49, 66, 97)} {9，6,(17, 26, 38, 49, 66, 97)} {6,(9, 17, 26, 38, 49, 66, 97)} {(6, 9, 17, 26, 38, 49, 66, 97)}

16、画出下列二叉排序树的平衡结果图，要求：

（1）已知初始查找表的关键字序列为（70,100,80,30,75），构造并画出初始二叉排序树，标明各结点平衡因子。

（2）插入关键字20，

a. 画出失衡后的二叉排序树，标明各结点平衡因子

b. 画出重新平衡后的二叉排序树，标明各结点平衡因子

17、什么是有向网？已知有向网G=(V

,E)，其中顶点集V={a,b,c,d,e}，边集为：E={,, , , }，E中的每条边是一个三元组，分别表示弧尾，弧头和边的长度（权重）。画出有向网G，写出其邻接矩阵。

500000001000010

000020030018、关键字集合为{19, 36,23, 82,14,55,68,11, 01}，哈希函数为：Hash(key)=key mod 7，试写出哈希表的链地址处理图。

19、写出如下所示二叉树的叶子结点和非终端结点以及各结点所在的层次、树的深度、树的深度，并且写出该树的先序遍历、中序遍历、后序遍历和层次遍历的结果。

叶子结点: GHMJ

非终端结点: ABCDEF

结点所在层次: A(1),B(2),C(2),D(3),E(3),F(3),G(4)H(4),J(4),M(4) 树的深度: 4

先序：ABDGEHCFMJ 中序：DGBEHACMFJ 后序：GDHEBMJFCA 层次：ABCDEFGHMJ ○A ○B ○C ○D ○E ○F ○G ○H ○M ○J

20、用快速排序方法对数据集｛23 45 12 90 78 56｝进行排序，写出快速排序第一趟的详细过程，以及简述后面的递归过程。 ｛23 45 12 90 78 56｝ ｛23 45 12 90 78 56｝ ｛23 45 12 90 78 56｝ ｛23 45 12 56 78 90｝ ｛23 45 12 56 78 90｝ ｛(23 45 12 56) 78 (90)｝

21、对于下面两个图，求出：

（1）无向图中每个顶点的度，有向图中每个顶点的入度，出度和度。 d(0)=4, d(1)=2, d(2)=3, d(3)=3, d(4)=2.

d(0)+ = 2, d(0)- = 2, d(1)+ = 1, d(1)- = 2, d(2)+ = 1, d(2)- = 3 d(3)+ = 2, d(3)- = 1, d(4)+ = 2, d(0)- = 0 （2）画出有向图的邻接距阵。 100101010010011

0000100000（3）下面是否是连通图或强连通图，如果不是，画出连通分量或强连通分量。

4 0 1

0 3

2 1 2 3 4

22、给出下列AOV网的可能的拓扑排序序列。拓扑排序序列是否唯一？在什么

情况下拓扑排序无法完成。 CDBAE或DCBAE或…… 不唯一

在含有回路的时候拓扑排序无法完成

○A ○E ○B ○D

○C

23、已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。

（1）画出该二叉树

（2）写出其后序序列；

ABCDEFGH

24、已知带权无向图的邻接表如下所示，其中边表结点的结构为：

依此邻接表从顶点C出发进行深度优先遍历。