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

1、 绪论第一章 数据结构课程研究的内容是什么？其中哪个方面和计算机无关？1. 逻辑结构、存储结构，操作的实现答：非数值计算，包括数据的 2. 数据结构按逻辑结构可分为哪几类？（不要简单答线性和非线性） 算法分析主要研究哪几个方面？为什么要进行算法分析？（分析算法的效率以求改进），3 （ 时间效率和空间效率，即：空间复杂性和时间复杂性） 分析下面各程序段的时间复杂度。4 2. s=0; in; i+) 1. for (i=0; for i=0; in; i+) for (j=0; jm; j+) for(j=0; jn; j+) Aij=0; s+=Bij; sum=s; 3. x=0; for(

2、i=1; in; i+) 4. i=1; for (j=1; j=n-i; j+) while(i=n) x+; i=i*3; 1= 共执行了解：因为x+n-1+n-2+答：O（logn） 32 （n(n-1)/2，所以执行时间为On） 5、数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上设有数据逻辑结构S=（D,R），试按各小题所给条件画出有限集合。 关系 的 这些逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？ 1. 【严蔚敏习题集P7 1.3】 D=d1,d2,d3,d4 R=(d1,d2),(d2,d3),(d3,d4) 答： d

3、1d2d3d4 d1无直接前驱，是首结点 d4无直接后继是尾结点 1 1. D=d1,d2,d9 R=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) 答： 此图为树形结构 d1无直接前驱，是根结点 d2,d5,d7,d9无直接后继是叶子结点 2. D=d1,d2,d9 R=(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6) 答： 此图为图形结构 d1，d2无直接前驱，是开始结点 d6,

4、d7无直接后继是终端结点 (3) (2) 学习方法提示：“茴香豆的茴暂时不要做那些针对考试的同学们一定要把教材阅读，理解以后再做题，以后要参加那些考试的时候再说。平时一定要以理解为核心，没有必要有几种写法的题”把一些细枝末节，甲乙丙丁的条款记住，甚至有些说法，这样说也有理，那样说也有理，没，数据结构分几类，有的教材上写“线性和非线性二类”有必要钻牛角尖。比如上面习题中，作者是从不同的角度，还有的写“线性，树，图，集合四类”有的写“线性，树，图三类” 去看待的。作为学习，这个问题所谓的“标准答案”是次要的。比如评价顺序表的删除操作的不要强记公式，公式应该是自己理解，自己能推导出来。我本人就不记得

5、很多公式，复杂度，你应该记得思路，而不是公式（完全忘记了也没关系）但是要用的时候知道怎么自己推导出来，知道去哪里找到这个公式，那就行了，有些公式，“存储容量”人的大脑是有限的，要把这有限的在自己的工作中老用老用的，自然就记住了。 用来记住你要用的东西。和考试速度的时候才需要多看“标准答案”至于将来要参加程序员的考试的时候，需要。那些考试，总是把一个简单的说法用很复杂的方式转弯抹那些试题及所谓的“标准答案”在你不角地说出来，但在学习的过程中应该抓住实质与核心，而不是把精力放在牛角尖上。而当你渐渐地熟悉问题的实质以后，熟悉教材内容的时候，你发现那些说法都是晦涩难懂的， 大多数问题对你来说都是自然而

6、然的，是你自己能解决的。 欢迎大家共同讨论学习的方法。以后同学们和我的心得将整理以后继续发出。 杨华谨识 2 第二章 线性表 一、填空 1、 向一个长度为n的向量的第i个元素(1in+1)之前插入一个元素时，需向后移动 n-i+1 个元素。 向一个长度为n的向量中删除第i个元素(1in)时，需向前移动 n-i 个元素。. 2、 顺序表中插入或删除一个元素，需要平均移动 表中一半元素，具体移动的元素个数与 表长和该元素 在表中的位置 有关。 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序 表也称为 随机存取 的数据结构。.一个向量第一个元素的存储地址是100，每个元素的长 度为

7、2，则第5个元素的地址是 108 ；向一个有127个元素的顺序表中插入一个新元 素并保持原来顺序不变，平均要移动 63.5 个元素； 3、在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度 为O（n）。 现有一个具有五个元素的线性表L=23，17，47，05，31，若它以链接方式存储在下列100119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下所示： 05 U 17 X 23 V 31 Y 47 Z 100 120 其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？（10分） 答：X= 116 Y=

8、 0 Z= 100 首址= 108 末址= 112 （小心） 二、简答题 1. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 答： 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。 优点：存储密度大（用动态分配的方法，一般都情况下都接近1），存储空间利用率高。缺点：插入或删除元素时不方便。顺序表才适合随机存取； 链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针;优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（lchild /叶子结点 else

9、 return Leaf_Count(T-lchild)+Leaf_Count(T-rchild);/左子树的叶子数加 上右子树的叶子数 /LeafCount_BiTree 3.编写按层次顺序（同一层自左至右）遍历二叉树的算法。 或：按层次输出二叉树中所有结点； 解：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。 这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。 技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，以此产生了按层次输出的效果。 void LayerOrder(Bitree

10、T)/层序遍历二叉树 InitQueue(Q); /建立工作队列 EnQueue(Q,T); while(!QueueEmpty(Q) DeQueue(Q,p); visit(p); if(p-lchild) EnQueue(Q,p-lchild); if(p-rchild) EnQueue(Q,p-rchild); /LayerOrder 9 图第七章 在一个图中，所有顶点的度数之和等于图的边数的倍。 2 1. 1 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的2. 倍。 3. 个结点的无向图最多有有条边。8 28 4. 有8个结点的有向完全图有 56 条边。 5. 有8个结点的

11、无向连通图最少有 7 条边。 6. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 出度 。 7. 设有一稀疏图G，则G采用 邻接表 存储较省空间。 设有一稠密图G，则G采用 邻接矩阵 存储较省空间。（选填邻接表/邻接矩阵） 8. 如果n个顶点的图是一个环，则它有 n 棵生成树。 （以任意一顶点为起点，得到n-1条边）9. 已知图的邻接矩阵如下，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是 0 1 3 4 2 5 6 ，按广度优先遍历的结点序列是 0 1 2 3 4 6 5 。 0111101?1001100?0001100?1001110?0111001?000110

12、1?0011001?10. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是 0 1 2 3 。 11. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是 0 3 2 1 。 12. 用邻接表表示图进行广度优先遍历时，通常是采用 队列 来辅助实现算法的。 13. 拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。 14. 请对下图的无向带权图， (1)按普里姆算法求其最小生成树，计算生成树权值和； (2)按克鲁斯卡尔算法求其最小生成树，计算生成树 10 权值和。? 根据上面两问，你可能猜测什么出什么结论(3) ! 。可以直接由原始

13、图画出最小生成树，而且最小生成树只有一种（类）解：设起点为a 最小生成树 到其他各顶点间的最短路径的算法。Dijkstra15.复习电子讲义中利用算法求图中从顶点a （此题不交） 第八章 查找 顺序查找1. （线性查找）在数据的存放无规律而言的线性表中进行检索的最佳方法是。 2. 假设在有序线性表a20上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。设有100个结点，用二分法查找时，最大比较次数是 7 。对22个记录的有序表作折半查找，当查找失败时，至少需要比较 5 次关键字。 解：显然，平均查找长度

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

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

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

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

18、则按平均情况选择。 10 了解外部排序的概念：当数据量很大，不能完全在内存中完成的时候，需要和外存交换数据，比如每个段内部排序，再归并。而归并会使用到败者树，置换-选择过程，最佳归并树等等技术。将来如果工作遇到很大量的数据要排序的时候，碰到这几个名词的时候，记得回来阅读这里就可以了。如果暂时不用，是没有必要阅读的，除非你感兴趣。（不要偏执，老师我本人就没有仔细阅读过?，可见同学们现在是在打基础，但是如果能学来致用是最好的了） - 关于软件技术的学习 一、数据结构是软件技术中基础的基础，希望大家考试以后继续多学习。更不要把教材扔了。你做过笔记的书扔掉是非常可惜的，因为你自己的笔记会帮助你将来迅速

19、想起过去学过的内容。如果你的教材上密密麻麻地写满了阅读中的标志，疑问，心得，那真是一本不可多得的好参考书。 二、严老师的教材是中国数据结构教材里写的最严谨的，也是最难的教材，实现的效率相对其他教材比较高，缺点是语言非常简练形式化（即：公式化，数学化）的语言比较多，初学的时候难以阅读。但是经过一个学期的学习，大家应该习惯了。当然，如果还有困难的地方，可以参考比较浅显的教材。而教材中的参考书目2更是一本（分三本很厚的卷）算法大全，作者是Donald EKnuth，号称算法的宗师。该书是一本更难更全的书。完整阅读是不太可能了，但可以当很好的工具书。 三、徐士良的常用算法程序集是一本比较全的算法集，已

20、经完全用C语言实现，也是 13 可以常常查阅的工具书。 四、其实谁也不可能平时把教材上的所有算法都记得，所以学的好的标准应该是：认真琢磨了教材中的算法了吗？想通了吗？读懂了吗？重要的结论而记得了吗？另外就是要选一些自己喜欢的，你觉得比较实用的算法来上机调试通过。希望假期同学们能做这件事情。曾经有一个同学花了一个假期留在学校通过上机的方式深入学习数据结构，我想他现在一定已经很熟练了。 五、数据结构中的一大重要概念是抽象数据类型，所以在后来的算法中，大家看到函数参数不在是学习C语言的时候都是基本类型，比如整型，字符型等等。中常常有一抽象到一个层次的结构作为参数，比如，队列来作为一个函数的参数辅助实

21、现其他算法。在实际工作中，如果不是特别的要求，需要自己设计结构，很多经典结构可以使用别人实现好的。所以，C+中的继承机制可以帮助你很好地使用别人的算法。所以，特别介绍一本书：潘爱民等翻译的C+ primer，这本书里讲了很多泛型程序设计，教你如何使用别人的结构，虽然它是一本C+教材，而且翻译过来叫“初步入门”的教材，但是它是一本很难的教材，学完数据结构以后再看才会觉得轻松。象队列，链表，二叉树等结构在标准的C+库中已经有很好的实现，一般不用自己写了，那么为什么要学习数据结构呢，因为只有经历这个过程，你才懂得去选择使用别人的结构，比如什么时候选用链表，什么时候使用顺序表，捅排序为什么不使用数组等

22、等。只有深入学习过，你曾经沧海，才能不轻易忘记。而在标准C+库和其他公司的库中，我觉得大家要尽量使用标准，这样才有比较好的移植性。 在非标准的库中，经过若干年的竞争，微软的MFC占了绝对的优势，而Borland 的OWL（但它几乎消失了确实是很优秀的，只是因为boland商业运作不如微软成功，Borland C+ 4.0错过了进入32位程序的最佳时机，当然，MFC组织得也很好） 。 六、如果你想解决更深入的问题，而不是熟练的程序员而已，算法值得一读。Sartaj Sahni写的数据结构算法与应用C+语言描述，在各大网上书店都被评价为五星级。书的前一半写了数据结构，后一半写了经典算法，包括模拟退

23、火，贪心算法，货郎担问题等等。建议你在在图书管借来，做一个略读。算法部分的目录如下： 第13章 贪婪算法13.1 最优化问题13.2 算法思想13.3 应用13.3.1 货箱装船13.3.2 0/昔背包问题13.3.3 拓扑排序13.3.4 二分覆盖13.3.5 单源最短路径13.3.6 最小耗费生成树13.4 参考及推荐读物 第 14章分而治之算法14.1 算法思想14.2 应用14.2.1 残缺棋盘14.2.2 归并排序14.2.3 快速排序14.2.4 选择14.2.5距离最近的点对14.3 解递归方程14.4 复杂性的下限14.4.1 最小最大问题的下限14.4.2 排序算法的下限 第 15章动态规划 15.1 算法思想15.2 应用15.2.1 0/l背包问题15.2.2 图像压缩15.2.3 矩阵乘法链 15.2.4 最短路径15.2.5 网络的无交叉子集15.2.6 元件折叠15.3 参考及推荐读物 第 16章回溯16.1 算法思想16.2 应用16.2.1 货箱装船16.2.2 0/1背包问题16.2.3 最大完备子图16.2.4 旅行商问题16.2.5 电路板排列 第17章分枝定界17.1 算法思想17.2 应用17.2.1 货箱