《数据结构综合练习及答案》由会员分享，可在线阅读，更多相关《数据结构综合练习及答案（17页珍藏版）》请在金锄头文库上搜索。
1、 1 练练 习习 1. 内存中一片连续空间（不妨假设地址从内存中一片连续空间（不妨假设地址从 1 到到 m） ，提供给两个 栈 ） ，提供给两个 栈 S1 和和 S2 使用，怎样分配这部分存储空间，使得对任一个 栈，仅当这部分空间全满时才发生上溢。 使用，怎样分配这部分存储空间，使得对任一个 栈，仅当这部分空间全满时才发生上溢。 答：答：S1 空间地址空间地址 1-M S2 空间地址空间地址 M-1 即即 S1 存储地址不断增加，存储地址不断增加，S2 存储地址为不断减小。存储地址为不断减小。 2. 叙述前序和中序遍历二叉树的步骤；一棵前序序列为叙述前序和中序遍历二叉树的步骤；一棵前序序列为
2、1,2,3,4 的二叉树的二叉树,其中序序列可能是其中序序列可能是 4,1,2,3 吗吗?设一棵二叉树的前序 序列为 设一棵二叉树的前序 序列为 1,2,3,4,5,6,7,8,9,其中序序列为其中序序列为 2,3,1,5,4,7,8,6,9,试画出 该二叉树。 试画出 该二叉树。 答：前续遍历：根答：前续遍历：根-左左-右。右。 中续遍历：左中续遍历：左-根根-右。右。 不可能为不可能为 4、1、2、3. 2 3. 设有一个关键码的输入序列设有一个关键码的输入序列 55, 31, 11, 37, 46, 73, 63 , (1) 从空树开始构造平衡二叉搜索树从空树开始构造平衡二叉搜索树, 画
3、出每加入一个新结 点时二叉树的形态。若发生不平衡 画出每加入一个新结 点时二叉树的形态。若发生不平衡, 指明需做的平衡旋转的类型 及平衡旋转的结果。 指明需做的平衡旋转的类型 及平衡旋转的结果。(2) 计算该平衡二叉搜索树在等概率下的查 找成功的平均查找长度。 计算该平衡二叉搜索树在等概率下的查 找成功的平均查找长度。 答：（答：（1）构造平衡二叉搜索树：）构造平衡二叉搜索树： 5555 31 55 31 11 55 31 11 右旋 55 31 11 37 55 31 11 37 46 先左旋，再右旋 46 31 11 3755 46 31 11 3755 73 46 31 37 55 73
4、 先右旋，再左旋 11 46 31 37 55 7311 63 先右旋，再左旋 46 31 37557311 63 （2）平均查找长度为树高度）平均查找长度为树高度 h=3. 3 4. 设散列表为设散列表为 HT012,即表的大小为即表的大小为 m=13。现采用双散列法 解决冲突。散列函数和再散列函数分别为： 。现采用双散列法 解决冲突。散列函数和再散列函数分别为： H0(key)=key%13; 注：是求余数运算（注：是求余数运算（mod） Hi=(Hi-1+REV(key+1)%11+1)%13; i=1,2,3,，m-1 其中，函数其中，函数 REV（x）表示颠倒）表示颠倒 10 进制数
5、进制数 x 的各位，如的各位，如 REV(37)=73,REV(7)=7 等。若插等。若插 入的关键码序列为入的关键码序列为2,8,31,20,19,18,53,27。 (1)试画出插入这试画出插入这 8 个关键码后的散列表。个关键码后的散列表。 (2)计算搜索成功的平均搜索长度计算搜索成功的平均搜索长度 ASL。 答： （答： （1） （注：代码看附录） （注：代码看附录） 0 27 1 53 2 2 3 4 5 31 6 19 7 20 8 8 9 18 10 11 12 （2）ASL = (1 + 1 + 1 + 1 + 1 + 2 + 1 + 1)/8 = 1.125 4 5. 下图表
6、示一个地区的通讯网，边表示城市间的通讯线路，边 上的权表示架设线路花费的代价，如何选择能沟通每个城市 且总代价最省的 下图表示一个地区的通讯网，边表示城市间的通讯线路，边 上的权表示架设线路花费的代价，如何选择能沟通每个城市 且总代价最省的 n-1 条线路，画出所有可能的选择。条线路，画出所有可能的选择。 答：有两种选择：答：有两种选择： 1 5 2 6 16 18 4 11 6 3 5 1 5 2 6 6 16 18 4 11 3 5 6. 给出一组关键字：给出一组关键字：29，18，25，47，58，12，51，10，分别 写出按下列各种排序方法进行排序时的变化过程： ，分别 写出按下列各
7、种排序方法进行排序时的变化过程： （1）归并排序）归并排序 每归并一次书写一个次序。每归并一次书写一个次序。 （2）快速排序）快速排序 每划分一次书写一个次序。每划分一次书写一个次序。 （3）堆排序）堆排序 先建成一个最大堆，然后每从堆顶取下一个元素 后，将堆调整一次。 先建成一个最大堆，然后每从堆顶取下一个元素 后，将堆调整一次。 答： （答： （1）归并排序：划分）归并排序：划分 29 18 25 4758 12 5110 29 18 25 4758 12 5110 29 18 25 4758 12 5110 29 18 25 4758 12 5110 5 归并：归并： 10 12 18
8、1925 47 5158 18 19 25 4710 12 5158 18 19 25 4712 58 1051 29 18 25 4758 12 5110 （2）快速排序：）快速排序： 29 18 25 4758 12 5110 10 18 25 2958 12 5147 10 18 25 2958 12 5147 10 18 25 2947 12 5158 10 18 25 2947 12 5158 10 18 25 2912 47 5158 10 18 25 2912 47 5158 10 18 25 2912 47 5158 注：红色数字为选定的注：红色数字为选定的 Pivot，绿色为
9、位置选定元素。，绿色为位置选定元素。 （3）堆排序：）堆排序： 建最大堆：建最大堆： 29 18 25 4758 12 5110 29 18 25 4758 12 5110 29 18 51 4758 12 2510 29 58 51 4718 12 2510 58 29 51 4718 12 2510 注：红色为调整的结点，绿色为调整结束。注：红色为调整的结点，绿色为调整结束。 取一个元素之后，数列为取一个元素之后，数列为10，29，51，47，18，12，25，10 调整：调整： 10 29 51 4718 12 25 51 29 10 4718 12 25 51 29 25 4718 1
10、2 10 6 7. 假设用于通讯的电文由假设用于通讯的电文由 5 个字母组成，个字母组成，A B C D E F ，字母 在电文中的出现频率分别为 ，字母 在电文中的出现频率分别为 0.09，0.12，0.07，0.22，0.23， 0.27，画出哈夫曼树，并写出各个字符的哈夫曼编码。 （左子 树根节点值不大于右子树根节点值） ，画出哈夫曼树，并写出各个字符的哈夫曼编码。 （左子 树根节点值不大于右子树根节点值） 答：答：Huffman 树：树： 0.220.230.27 0.12 0.070.09 编码：编码： 0.09 1111 0.12 110 0.07 1110 0.22 00 0.2
11、3 01 0.27 10 8. 已知序列（已知序列（50，72，43，85，75，20，35，45，65，30） ，请 以顺序插入方式构造二叉排序树， 并画出删除结点 ） ，请 以顺序插入方式构造二叉排序树， 并画出删除结点 72 之后的 二叉排序树。 之后的 二叉排序树。 7 答：建立二叉排序树（二叉搜索树）答：建立二叉排序树（二叉搜索树） 5050 72 50 72 43 50 72 43 85 50 72 43 85 75 50 72 43 85 75 20 50 72 43 85 75 20 35 50 72 43 85 75 20 35 45 50 72 43 85 75 20 35
12、 4565 50 72 43 85 75 20 35 4565 30 采用替换删除法，删除结点采用替换删除法，删除结点 72 后：后： 50 75 43 85 20 35 4565 30 8 9. 已知带权无向图已知带权无向图 G 的邻接矩阵是的邻接矩阵是 A。 (1) 画出图画出图 G； (2) 分别画出一颗从分别画出一颗从 V1 出发的深度优先生成树和广度优先生 成树； 出发的深度优先生成树和广度优先生 成树； (3) 画出一棵最小生成树。画出一棵最小生成树。 答：图答：图 G 为：为： （2）从）从 V1 出发出发 深度优先生成树为：深度优先生成树为： V1 V5V2 V4 V6 V3
13、A= 6 0 5 0 0 4 0 5 0 6 0 0 0 0 6 0 0 7 6 0 0 0 0 2 3 4 0 7 2 0 0 6 0 0 6 3 V1 V2 V3 V4 V5 V6 9 广度优先生成树为：广度优先生成树为： V1 V5V2 V4 V6 V3 （3）最小生成树：）最小生成树： V1 V5 V2 V4 V6 2 43 6 V3 5 10. 假定一组记录的排序码为假定一组记录的排序码为(46，79，56，38，40，84，50，42)， 利用堆排序方法画出初始大顶堆（以树状表示） 。 ， 利用堆排序方法画出初始大顶堆（以树状表示） 。 答：图示如下：答：图示如下： 10 1 5
14、6 7 8 4 2 3 11. 图的深度优先搜索类似于图的深度优先搜索类似于BFS,不同之处在于使用栈代替不同之处在于使用栈代替BFS 中的队列，进出队列的操作改为入出栈的操作。即当一个顶 点的一个邻接点被搜索后，下一个搜索的出发点应该是最近 入栈 中的队列，进出队列的操作改为入出栈的操作。即当一个顶 点的一个邻接点被搜索后，下一个搜索的出发点应该是最近 入栈(栈顶栈顶)的顶点。 用的顶点。 用 深度优先搜索方法搜索下图深度优先搜索方法搜索下图,设初始出 发点为 设初始出 发点为 1。 11 (1) 画出搜索过程中栈的变化。画出搜索过程中栈的变化。 7 3 6 6 5 8 空 1 2 2 2
15、2 4 4 4空 (2) 写出顶点的访问次序 （当从某顶点出发搜索他的邻接点时， 请按邻接点序号递增序搜索 写出顶点的访问次序 （当从某顶点出发搜索他的邻接点时， 请按邻接点序号递增序搜索,以使答案唯一） 。以使答案唯一） 。 12. 按 照 次 序 输 入 关 键 字 的 值 建 立按 照 次 序 输 入 关 键 字 的 值 建 立2-3树树 (3阶阶B- 树树):(68,54,82,35,75,90，103，22)。 (1)请画出所建的请画出所建的 2-3 树。树。 (2)如果此后依次删除如果此后依次删除 22,75， 画出每一步执行后的， 画出每一步执行后的 2-3 树的状态。树的状态。
16、 答： （答： （1）2-3 树为：树为： 12 （2）删除操作：）删除操作： 13 13已知如下树林，画出对应的二叉树。 已知如下树林，画出对应的二叉树。 答：转化为二叉树为： 答：转化为二叉树为： A BE CFG DH I J 14. 已知二叉树，画出中序的线索。 已知二叉树，画出中序的线索。 14 答：线索化后为： 答：线索化后为： 15. 以下图为例， 按以下图为例， 按 Dijkstra 算法计算得到的从顶点算法计算得到的从顶点 A 到其他各 个顶点的最短路径和最短路径长度。 到其他各 个顶点的最短路径和最短路径长度。 A B C DE 1 18 5 5 2 2 2 15 答：运用答：运用 Dijkstra 算法可生成如下：算法可生成如下： A BC 1 DE 5 2 2 最短路径(A) 长度 B A-B 1 C A-B-D-C 8 D A-B-D 6 E A-B-D-E 8 16 附
