数据结构课后习题答案合集

《数据结构课后习题答案合集》由会员分享，可在线阅读，更多相关《数据结构课后习题答案合集（15页珍藏版）》请在金锄头文库上搜索。

1、1第一章第一章 绪论绪论1. 数据结构课程研究的内容是什么？其中哪个方面和计算机无关？数据结构课程研究的内容是什么？其中哪个方面和计算机无关？ 答：非数值计算，包括数据的答：非数值计算，包括数据的 逻辑结构、存储结构，操作的实现逻辑结构、存储结构，操作的实现2. 数据结构按逻辑结构可分为哪几类？（不要简单答线性和非线性）数据结构按逻辑结构可分为哪几类？（不要简单答线性和非线性）3为什么要进行算法分析？（分析算法的效率以求改进）为什么要进行算法分析？（分析算法的效率以求改进） ，算法分析主要研究哪几个方面？，算法分析主要研究哪几个方面？ （ 时间效率和空间效率，即：空间复杂性和时间复杂性）时间效

2、率和空间效率，即：空间复杂性和时间复杂性） 4分析下面各程序段的时间复杂度。分析下面各程序段的时间复杂度。5、数据结构被形式地定义为（数据结构被形式地定义为（D, R） ，其中，其中 D 是是 数据元素数据元素 的有限集合，的有限集合，R 是是 D 上上 的的 关系关系 有限集合。有限集合。设有数据逻辑结构设有数据逻辑结构 S=（D,R） ，试按各小题所给条件画出，试按各小题所给条件画出 这些逻辑结构的图示，并确定相对于关系这些逻辑结构的图示，并确定相对于关系 R，哪些结点是开始结点，哪些结点，哪些结点是开始结点，哪些结点 是终端结点？是终端结点？ 1. 【严蔚敏习题集严蔚敏习题集 P7 1.

3、3】 D=d1,d2,d3,d4d1,d2,d3,d4 R=(d1,d2),(d2,d3),(d3,d4)R=(d1,d2),(d2,d3),(d3,d4) 答：答： d1d2d3d4d1d2d3d4 d1d1无直接前驱，是首结点无直接前驱，是首结点 d4d4无直接后继是尾结点无直接后继是尾结点2. s=0;for i=0; ilchild /叶子结点 else return Leaf_Count(T-lchild)+Leaf_Count(T-rchild);/左子树的叶子数加 上右子树的叶子数 /LeafCount_BiTree 3.编写按层次顺序（同一层自左至右）遍历二叉树的算法。 或：按

4、层次输出二叉树中所有结点； 解：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。这是一个循环算法，用 while 语句不断循环，直到队空之后自然退出该函数。 技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即 使得它的左右孩子结点入队，以此产生了按层次输出的效果。 void LayerOrder(Bitree T)/层序遍历二叉树 InitQueue(Q); /建立工作队列 EnQueue(Q,T); while(!QueueEmpty(Q) 0 1 0 1 0 1 1921 32 01 0 1 0 1 710 6 01 2 3字母编号对

5、应编码出现频率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10字母编号对应编码出现频率111000.072000.193111100.02411100.065100.326111110.037010.21811010.1010 DeQueue(Q,p); visit(p); if(p-lchild) EnQueue(Q,p-lchild); if(p-rchild) EnQueue(Q,p-rchild); /LayerOrder 第七章第七章 图图1. 在一个图中，所有顶点的度数之和等于图的边数的 2 倍。 2.

6、 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 1 倍。 3. 有 8 个结点的无向图最多有 28 条边。 4. 有 8 个结点的有向完全图有 56 条边。 5. 有 8 个结点的无向连通图最少有 7 条边。 6. 有向图 G 用邻接表矩阵存储，其第 i 行的所有元素之和等于顶点 i 的 出度 。 7. 设有一稀疏图 G，则 G 采用 邻接表 存储较省空间。 设有一稠密图 G，则 G 采用 邻接矩阵 存储较省空间。 （选填邻接表/邻接矩阵） ） 8. 如果 n 个顶点的图是一个环，则它有 n 棵生成树。 （以任意一顶点为起点， 得到 n-1 条边）9. 已知图的邻接矩阵如下，根据

7、算法思想，则从顶点 0 出发按深度优先遍 历的结点序列是 0 1 3 4 2 5 6 ，按广度优先遍历的结点序列是 0 1 2 3 4 6 5 。10. 已知图的邻接表如下所示，根据算法，则从顶点 0 出发按深度优先遍历的结点序列是 0 1 2 3 。11. 已知图的邻接表如下所示，根据算法，则从顶点 0 出发按广度优先遍历的结点序列是 0 3 2 1 。01000111011000010110101100110010001100100110111101112. 用邻接表表示图进行广度优先遍历时，通常是采用 队列 来辅助实现算法的。 13. 拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程

8、来完成的。 14. 请对下图的无向带权图， (1)按普里姆算法求其最小生成树，计算生成树权 值和； (2)按克鲁斯卡尔算法求其最小生成树，计算生成 树权值和。 (3)根据上面两问，你可能猜测什么出什么结论?解：设起点为 a。可以直接由原始图画出最小生成树，而且最小生成树只有一种（类）!15.复习电子讲义中利用 Dijkstra 算法求图中从顶点 a 到其他各顶点间的最短路径的算法。 （此题不交）第八章第八章 查找查找1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找）顺序查找（线性查找） 。2. 假设在有序线性表假

9、设在有序线性表 a20上进行折半查找，则比较一次查找成功的结点数为上进行折半查找，则比较一次查找成功的结点数为 1；比较两次；比较两次 查找成功的结点数为查找成功的结点数为 2 ；比较四次查找成功的结点数为；比较四次查找成功的结点数为 8 ；平均查找长度为；平均查找长度为 3.7 。设有。设有 100 个结点，用二分法查找时，最大比较次数是个结点，用二分法查找时，最大比较次数是 7 。对。对 22 个记录的有序个记录的有序 表作折半查找，当查找失败时，至少需要比较表作折半查找，当查找失败时，至少需要比较 5 次关键字。次关键字。 解：解：显显然，平均然，平均查查找找长长度度O（ （log2n）

10、 ）high) return 0; /查找不到时返回 0 mid=(low+high)/2; if(ST.elemmid.key= =key) return mid; else if(ST.elemmid.keykey) 13return Search_Bin_Recursive(ST, key, low, mid-1); else return Search_Bin_Recursive(ST, key, mid+1, high); /Search_Bin_Recursive 原来的文件上没有写快速排序，这里补上。 注意：不要抄书，一定要自己画出结果。有余力的同学请阅读复杂度分析，否则只需要了

11、 解第 8 题结论。电子讲义上的程序还是要尽量读懂。 1 直接插入排序：重复 p266 图 10.1 的排序过程；阅读复杂度分析。 2 Shell 排序：见 p271 图 10.5 的关键字。先画第一趟排序过程（就使用直接选择排序） ， 然后，以趟为单位画出每一趟排序的排序结果。阅读复杂度分析。 3 冒泡排序：见 p273 图 10.6,对初始关键字，先画第一趟排序过程，然后，以趟为单位画 出每一趟排序的排序结果。阅读复杂度分析。 4 快速排序：见 p275 图 10.7，先画第一趟排序过程，然后，以趟为单位画出每一趟排序 的排序结果。阅读复杂度分析。 5 直接选择排序：利用上题的关键字，先画

12、第一趟排序过程，然后，以趟为单位画出每 一趟排序的排序结果。阅读复杂度分析。 （直接插入法的核心操作是寻找插入位置，而 直接选择法的核心操作是寻找无序中最小的一个。 ） 6 堆排序：对 p280 末的关键字序列，重复 p281 图 10.12 的建堆过程；重复图 10.11 的过 程，输出堆顶元素，即最小元素以后，将剩余部分整理成堆的过程。阅读时间复杂度 分析。注意结论：堆排序的效率是比较高的，但是首先有一个建堆的过程，所以在数 据量很大的时候使用效果才好。 7 归并排序：重复 p283 图 10.13 的排序过程（每一次都使用二路） 。阅读时间复杂度分析。8 基数排序（桶排序）：对关键字序列

13、： 710，342，014，686，006，841，429，134，068，264，使用低关键字优先的方法进 行排序。画出排序的逻辑过程（暂时不考虑存储） 。提示：建立 0 到 9 十个桶（10 个桶： 数的进制数） 。经过 3 次分配与收集（3 次：关键字序列中的最大位数） ，则完成整个排序过程。 9 记忆 p289，10.7 节的表格。注意以下结论 1)理论上已经证明：O(n log n)是排序算法的 最底线，不要花时间去发明时间复杂度更低的算法，只能在已知道数据的某些特性的 情况下，做一些的改进，但产生数量级上差别不太可能。2）快速排序在数据已经基本 有序的情况下，退化为冒泡排序 O(n

14、2)，而冒泡排序加上一定检测机制后可做到 O(n)， 所以排序算法的选择要根据数据的特征来做，若无法提前得知数据特点，则按平均情 况选择。 10了解外部排序的概念：当数据量很大，不能完全在内存中完成的时候，需要和外 存交换数据，比如每个段内部排序，再归并。而归并会使用到败者树，置换-选择过程， 最佳归并树等等技术。将来如果工作遇到很大量的数据要排序的时候，碰到这几个名 词的时候，记得回来阅读这里就可以了。如果暂时不用，是没有必要阅读的，除非你 感兴趣。 （不要偏执，老师我本人就没有仔细阅读过，可见同学们现在是在打基 础，但是如果能学来致用是最好的了）-14关于软件技术的学习 一、数据结构是软件

15、技术中基础的基础，希望大家考试以后继续多学习。更不要把教材扔 了。你做过笔记的书扔掉是非常可惜的，因为你自己的笔记会帮助你将来迅速想起过去学 过的内容。如果你的教材上密密麻麻地写满了阅读中的标志，疑问，心得，那真是一本不 可多得的好参考书。 二、严老师的教材是中国数据结构教材里写的最严谨的，也是最难的教材，实现的效 率相对其他教材比较高，缺点是语言非常简练形式化（即：公式化，数学化）的语言比较 多，初学的时候难以阅读。但是经过一个学期的学习，大家应该习惯了。当然，如果还有 困难的地方，可以参考比较浅显的教材。而教材中的参考书目2更是一本（分三本很厚的 卷）算法大全，作者是 Donald EKnuth，号称算法的宗师。该书是一本更难更全的书。 完整阅读是不太可能了，但可以当很好的工具书。 三、徐士良的常用算法程序集是一本比较全的算法集，已经完全用 C 语言实现，也是 可以常常查阅的工具书。 四、其实谁也不可能平时把教材上的所有算法都记得，所以学的好的标准应该是：认真琢 磨了教材中的算法了吗？想通了吗？读懂了吗？重