数据结构课程习题汇编解答

元素平均需要移动元素的个数是( )。

应用题

1 设数据集合d= {1，12，5，8，3，10，7，13，9}，完成下列各题：

1) 依次取d中各数据，构造一棵二叉排序树bt。 2) 如何依据此二叉树bt得到d的一个有序序列？ 3) 画出在二叉树bt中删除“12”后的树结构

2 已知一棵二叉数的前序遍历为ABDECFG中序遍历为DBEAFGC，画出该二叉树，并写出它的后序序列。

3 关键码集为{36,18,22,11,48,59,19,14,70},哈希表表长为11，hash(key)=key,用线性探测法处理冲突，并求出查找成功时的平均查找长度(给出步骤)

4 设一数组中原有数据如下：15，13，20，18，12，60。下面是一组由不同排序方法进行一遍排序后的结果。

（ ）排序的结果为：12，13，15，18，20，60 （ ）排序的结果为：13，15，18，12，20，60 （ ）排序的结果为：13，15，20，18，12，60 （ ）排序的结果为：12，13，20，18，15，60 5 有如图所示的带权有向图G，试回答以下的问题。(给出步骤)

1) 给出从顶点1出发的深度优先遍历序列和广度优先遍历序列。 2) 给出下图的一个拓扑序列。 3) 给出从顶点1到顶点8的关键路径。

6 4 4 5 1 3 3 6 4 7 4 9 6 2 5 8 2 5 4 2 12 7 3 3 6 给出一组关键字T={12，2，16，30，8，28，4，10，20，6，18}，写出用下列算法从小到大排序时第一趟结束时的序列

1） 希尔排序（第一趟排序的增量为5） 2） 快速排序（选第一个记录为枢轴）

7 已知一棵二叉树的先序遍历序列为：AEFBGCDHIKJ，中序遍历序列为：EFAGBCHKIJD。试写出此二叉树的后序遍历序列，并用图画出它的后序线索二叉树。

8 现有如下的稀疏矩阵A如图所示，要求用三元组表示A和它的转置矩阵。

?150?013??00??00030022?0?? ?6??0?9 对给定的有7个顶点的有向图的邻接矩阵如下：

(1)画出该有向图； (2)画出邻接表；

(3)若将图看成AOE－网，列出其关键活动及相应的有向边，关键路径长度是多少？

??????????????????2??????52?????3?1??????35????75?3???????????? 7??5????10设用于通讯的电文由8个字母A、B、C、D、E、F、G、H组成，字母在电文中出现的频率分别为：7、19、2、6、32、3、21、10。试为这8个字母设计哈夫曼编码。

11设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=1,2,3,?,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 12一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二叉树的形状。

13有关键字集合K={15，22，50，13，20，36，28，48，35，31，41，18}采用散列存取，散列表长为15，设散列函数H（K）=K MOD 13，解决冲突采用开放地址法中的二次探测再散列的方法，试将K值填入表中，并计算查找成功时的平均查找长度。

14假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自左向右）为ABECFGDHI,中序序列为BCDAFEHIG。请画出该二叉树，并将其转换为对应的森林。

15有一随机数组(25,84,21,46,13,27,68,35,20),现采用某种方法对它们进行排序,其每趟排序结果如下, 则该排序方法是什么?

初 始:25,84,21,46,13,27,68,35,20 第一趟:20,13,21,25,46,27,68,35,84 第二趟:13,20,21,25,35,27,46,68,84 第三趟:13,20,21,25,27,35,46,68,84 16 判断序列（12，70，33，65，24，56，48，92，86，33）是否为堆，如果不是，则把它调整为小堆。

17设一棵二叉树的先序、中序遍历序列分别为；先序遍历序列： A B D F C E G H 中序

2

2

2

遍历序列： B F D A G E H C

（1）画出这棵二叉树。

（2）画出这棵二叉树的后序线索树。 （3）将这棵二叉树转换成对应的树（或森林）。

18 已知含有8个结点的一棵二叉树，按先序、中序、后序进行遍历后，有些结点序号不清楚如下图示。要求构造出一棵符合条件的二叉树。 先根序遍历 _ 2 3 _ 5 _ 7 8 中根序遍历 3 _ 4 1 _ 7 8 6 后根序遍历 _ 4 2 _ _ 6 5 1

19 对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。

20 有向图 G=, 其中: V={V1, V2, V3, V4, V5}, E=｛<1, 2>, <1,3>, <2, 3>,<2, 4>, <3, 5>, <4, 5> ｝给出此有向图及该图的邻接表和邻接矩阵存储 21已知一棵3阶B-树如下图所示：

(1) 画出插入(18)的3阶B-树。

(2) 画出在插入(18)后的3阶B-树中删除(78) 后的3阶B-树

22设有下列带权无向图： (1) 请画出该图的邻接表。

(2) 列出深度优先遍历该图所得到的一个顶点序列。 (3) 请画出该图的一棵最小生成树。