数据结构习题解析

1数据结构教程习题解析与算法上机实现胡元义王磊编著内容简介本书从实践角度对数据结构内容进行了完善和补充，是与作者出版的另一本《数据结构教程》配套使用的辅助教材；全书一方面对《数据结构教程》中的习题给出了深入浅出的解析，另一方面对《数据结构教程》中出现的算法和部分习题算法调试了近80个上机实现程序并涵盖了数据结构的所有内容，这对深入掌握和灵活运用数据结构知识，提高解题和编程的思维、方法以及实际动手能力都有很大的帮助。本书也是一本难得的数据结构算法实现资料，可以配合目前各类数据结构（C语言）教材使用，起到衔接教学与实践的作用。此外，本书也可作为考研资料以及计算机应用人员的实用资料和参考书。前言数据结构是计算机及相关专业的主干课程之一，其目的是让读者学习、分析和研究数据对象的特性及数据的组织方法，以便选择合适的数据逻辑结构和存储结构，设计相应的运算操作，把现实世界中的问题转化为计算机内部的表示与处理的方法。在信息科学领域，尤其是在系统软件和应用软件的设计和应用中要用到各种数据结构，因此，掌握数据结构对提高软件设计能力和程序编制水平有很大的帮助。本书分为两篇。第1篇为习题解析，共9章，分别为《数据结构教程》中各章的习题解析。该篇可在学习数据结构课程时同步使用，以帮助学生对数据结构知识的学习和掌握有一个比较全面、深入和系统的认识，达到使理论转化为能力的目的。习题解析部分是作者在多年讲授数据结构课程基础上总结、归纳编写而成，大多数取自历年的考研试题。为了便于正确理解有关数据结构的概念，掌握解题思路、方法和技巧；各章的习题大多给出了详尽的解题过程，对有代表性的习题，也给出了详细的分析、归纳和说明。此外，针对某些难题，书中还给出了一些新的解题思路和方法。通过习题解析，引导学生由基本概念出发寻找求解数据结构问题普遍的思路和方法，并由此深化对理论知识的理解，达到举一反三、提高分析问题与解决问题能力的目的。由于习题许多都选自历届考研试题，因此也可作为考研复习资料。第2篇为算法上机实现，对《数据结构教程》中出现的算法和部分习题算法给出了近80个上机实现程序并涵盖了数据结构的所有内容，这对深入掌握和灵活运用数据结构知识，提高编程的思维、方法和实际动手能力都有很大的帮助。数据结构课程对理论与实践的要求都相当高，并且内容多难度大，虽然大多数数据结构教材都强调了实践的重要性，但缺乏供实践练习的材料和环节，很多教材对算法的描述也只是概述性的伪代码，而无法直接上机实现，学生很难将这些算法转化为实现程序。本篇对《数据结构教程》中所有的算法都给出了上机实现程序和详细的程序注释，阅读起来一目了然，能够很快的掌握算法的精髓和实现手段，使得学生对数据结构知识的实践与应用有一个比较全面、深入和系统的认识，达到理论与实践相结合的目的。通过上机实践，可以开拓学生的视野，培养创新能力。此外，本篇给出的上机程序无论从涵盖了数据结构内容的全面性、完整性、实用性以及程序设计的新颖性都具有突出的特点，因此是一本难得的实用计算机资料。由于作者水平所限，书中难免存在错误和不妥之处，敬请读者批评指正。2作者2011年10月目录第1篇习题解析第1章绪论习题解析第2章线性表习题解析第3章栈和队列习题解析第4章串习题解析第5章数组与广义表习题解析第6章树与二叉树习题解析第7章图习题解析第8章查找习题解析第9章排序习题解析第2篇算法上机实现第10章线性表算法上机实现10.1顺序表基本运算10.2在表头插入生成单链表10.3在表尾插入生成单链表10.4单链表基本运算10.5双向链表基本运算10.6静态链表10.7例2.1算法实现10.8例2.2算法实现10.9例2.3算法实现10.10例2.4算法实现10.11例2.5算法实现第11章栈和队列算法上机实现11.1顺序栈基本运算11.2链栈基本运算11.3循环队列基本运算11.4链队列基本运算11.5例3.1算法实现11.6例3.5算法实现第12章串算法上机实现12.1顺序串基本运算12.2生成链串与求串长、串连接运算12.3求子串运算12.4串插入运算312.5串的简单模式匹配12.6串的无回溯KMP匹配第13章数组与广义表算法上机实现13.1矩阵转置13.2矩阵的快速转置13.3稀疏矩阵的十字链表存储13.4生成广义表及求广义表长度和深度运算第14章树与二叉树算法上机实现14.1二叉树的遍历14.2二叉树的非递归遍历14.3另一种后序非递归遍历二叉树的方法14.4由二叉树的遍历序列恢复二叉树14.5二叉树遍历的应用14.6中序线索二叉树14.7哈夫曼树及哈夫曼编码14.8例6.4算法实现第15章图算法上机实现15.1建立无向图的邻接矩阵15.2图的深度优先搜索15.3图的广度优先搜索15.4图的连通性15.5深度优先生成树15.6广度优先生成树15.7最小生成树的Prim算法15.8最小生成树的Kruskal算法15.9单源点最短路径的Dijkstra算法15.10每一对顶点间最短路径的Floyd算法15.11拓扑排序15.12关键路径第16章查找算法上机实现16.1顺序查找16.2折半（二分）查找16.3分块查找16.4二叉排序树的建立、结点的查找和删除16.5平衡二叉树的建立、结点的查找和删除16.6哈希（Hash）查找第17章排序算法上机实现17.1插入排序17.2折半插入排序17.3希尔（Shell）排序17.4冒泡排序17.5双向冒泡排序17.6快速排序17.7选择排序417.8堆排序17.9归并排序的递归算法实现17.10归并排序的非递归算法实现17.11基数排序第18章各章习题算法上机实现精选18.1删除单链表中值相同的结点18.2用两个栈模拟一个队列18.3将链串S中首次与链串T匹配的子串逆置18.4统计二叉树叶子个数的非递归算法实现18.5判定一二叉树是否为完全二叉树18.6按层次遍历二叉树18.7求二叉树中第一条最长的路径18.8邻接矩阵转换为邻接表18.9求无向连通图中距顶点v0路径长度为k的所有结点18.10深度优先遍历的非递归算法实现18.11用深度优先搜索对图中所有顶点进行拓扑排序18.12判定一二叉树是否为二叉排序树18.13单链表存储下的选择排序18.14快速排序的非递归算法实现18.15归并排序的迭代算法实现参考文献5第1篇习题解析第1章绪论习题解析1.单项选择题（1）研究数据结构就是研究____。A.数据的逻辑结构B.数据的存储结构C.数据的逻辑结构和存储结构D.数据的逻辑结构、存储结构及其数据在运算上的实现（2）下面关于算法的说法，错误的是____。A.算法最终必须由计算机程序实现B.为解决某问题的算法和为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上说法都是错误的（3）数据的____包括集合、线性、树和图4种基本类型。A.存储结构B.逻辑结构C.基本运算D.算法描述（4）数据的存储结构包括顺序、链接、散列和____4种基本类型。A.向量B.数组C.集合D.索引（5）关于逻辑结构，以下说法错误的是____。A.逻辑结构与数据元素本身的形式和内容无关B.逻辑结构与数据元素的相对位置有关C.逻辑结构与所含结点的个数无关D.一些表面上很不相同的数据可以有相同的逻辑结构（6）根据数据元素之间关系的不同特性，以下4类基本逻辑结构反映了4类基本数据的组织形式。下面解释中错误的是____。A.集合中任何两个结点之间都有逻辑关系，但组织形式松散B.线性结构中结点按逻辑关系依次排列成一条“锁链”C.树形结构具有分支、层次的特点，其形态有点像自然界中的树D.图状结构中各结构点按逻辑关系互相缠绕，任何两个结点都可以邻接（7）下面程序的时间复杂度为____。for(i=0;im;i++)for(j=0;jn;j++)A[i][j]=i*j;A.O(m2)B.O(n2)C.O(m×n)D.O(m+n)【解析】（1）数据结构包括逻辑结构、存储结构及数据在运算上的实现这三部分内容。故选D。（2）程序中的语句最终都要转化（编译）成计算机的可执行指令，而算法则无此限制，即算法可以采用自然语言、流程图等形式描述。为解决某问题的算法和为该问题编写的程序含义不一定相同，因为这个程序可能不满足有穷性（出现死循环）。此外，算法的可行性是指每一条指令都应在有限时间内完成。因此，A、B、C项都是错误的，故选D。（3）选B（4）选D6（5）数据的逻辑结构是对数据之间关系的描述，它与数据元素之间的相对位置无关；故选项B错，即选B。（6）集合结构的数据元素之间除了“属于同一集合”的联系之外没有其它关系；故选项A错，即选A。（7）程序段由两重for循环组成；外层for循环执行m次，内层for循环执行n次，即循环体赋值语句共执行了m×n次，故选C。2.多项选择题（1）数据元素是________。A.数据集合中的一个个体B.数据的基本单位C.数据的最小单位D.一个结点E.一个记录（2）数据结构被形式地定义为(K,R)，其中其中K是①的有限集，R是K上的②有限集。A.算法B.数据元素C.数据操作D.逻辑结构E.操作F.映像G.存储H.关系（3）线性结构的顺序存储结构是一种①的存储结构，线性结构的链式存储结构是一种②的存储结构。A.随机存取B.顺序存取C.索引存取D.散列存取E.随机存取和索引存取（4）算法分析的目的是①，算法分析的两个主要方面是②。①A.找出数据结构的合理性B.研究算法中输入和输出关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性②E.空间复杂度和时间复杂度F.正确性和简单性G.可读性和文档性H.数据复杂性和程序复杂性（5）算法指的是①，它必须是具备输入、输出和②等5个特性。①A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法②E.可执行性、可移植性和可扩充性F.可行性、确定性和有穷性G.确定性、有穷性和稳定性H.易读性、稳定性和安全性【解析】（1）数据元素是数据集合中的一个“个体”，是数据的基本单位，在有些情况下数据元素也称为元素、结点、顶点和记录等。故选A、B、D、E。（2）选：①B；②H。（3）顺序存储结构是一种随机存取结构；链式存储结构是一种顺序（一个结点一个结点的顺序查找）存取结构，故选：①A；②B。（4）算法分析的目的是考察算法的时间和空间效率，以求改进算法或对不同的算法进行比较。因此选；①C；②E。（5）选①C；②F。3.填空题（1）一个数据结构在计算机中的______称为存储结构。（2）对于给定的n个元素，可以构造出的逻辑结构有____、_________、________和________4种。（3）数据是描述客观事物的数、字符以及所有________计算机中并被计算机程序所______的符号集合。（4）线性结构中的元素之间存在______关系，树形结构中元素之间存在______关系，图形7结构中的元素之间存在______关系，而集合结构中的元素之间不存在______关系。（5）数据结构是研究数据的________和________以及它们之间的相互关系，并对这种结构定义相应的且设计出相应的______。（6）数据的______结构与数据元素本身的内容和形式无关。（7）一个算法的时空性能是指该算法的________和________；前者是算法包含的______，后者是算法需要的______。【解析】（1）数据的存储结构是数据结构在计算机中的实现方法，包括数据结构中数据元素的表示以及数据元素之间关系的表示。因此填：表示。（2）根据数据元素之间关系的不同特性，可以划分为集合结构、线性结构、树形结构和图结构。故填：集合结构线性结构树形结构图结构。（3）应填：能够输入到处理。（4）应填：一对一一对多多对多逻辑。（5）应填：逻辑结构存储结构运算算法。（6）应填：逻辑。（7）应填：时间性能（或时间效率）空间性能（或空间效率）计算量存储量。4.判断题（1）顺序存储方式只能用于存储线性结构。（2）数据元素是数据的最小单位。（3）算法可以用不同的语言描述，如果用C语言编写一个程序则程序就是算