数据结构与算法习题解答和实习指导
2011-4
清华大学
朱明方//吴及
139
《数据结构与算法习题解答和实习指导》是主教材《数据结构与算法》的配套辅导用书，其内容包括主教材中各章习题的解答和上机实习指导两部分。在习题解答部分中，对主教材中的各章习题作了详细解答，有意识地突出了对重要概念和知识点的解释，对可以用多种方法和思路解决的问题，同时给出几种不同的求解方法或算法。 上机实习指导部分中，包括上机实验指导和上机大作业两部分。其中，实验部分配合课程内容给出了12个实验；而上机大作业部分要求在规定时间内独立上机完成6个与实际问题比较贴近、有一定综合性的作业题。为兼顾读者希望有足够的独立思考空间和解决难以下手的实际情况，在实验和上机大作业题中，除了明确目的、要求以外，还给出了求解的思路或实现算法的提示。 通过这些书面和上机的练习，可以加深读者对课程中的重要概念和知识点的理解，掌握重要知识的应用、锻炼独立分析问题和解决问题的能力，从而达到更好的学习效果。 《数据结构与算法习题解答和实习指导》可作为普通高等院校数据结构课程的辅助教材，也可供自学者参考。
第一部分 习题解答第1章 绪论1.1 重点与难点1.2 习题解答第2章 线性表及其顺序存储2.1 重点与难点2.2 习题解答第3章 链表3.1 重点与难点3.2 习题解答第4章 树与二叉树4.1 重点与难点4.2 习题解答第5章 图5.1 重点与难点5.2 习题解答第6章 查找6.1 重点与难点6.2 习题解答第7章 排序7.1 重点与难点7.2 习题解答第二部分 上机实习指导I 实验指导实验要求实验一 线性表及其应用实验二 火车车厢重排问题实验三 求解迷宫问题实验四 简单算术表达式的处理实验五 求解简单背包问题实验六 链表及其应用实验七 实验室机时机位的管理实验八 实现I-Iuffman编码实验九 文件管理的模拟人实验十 求网络站点间的最短连接实验十一 查找最高分与次高分实验十二 报告日程安排与听众统计Ⅱ 上机大作业作业1 简单的公路交通查询系统设计作业2 实现字音转换作业3 销售网点扩充与查询问题作业4 基于词表的词频统计作业5 天然气输送方案设计作业6 实现简单中文分词参考文献
版权页：插图：为了分析一个算法的时间复杂度，一般情况下需要考察算法中基本语句的执行次数，找出其与问题规模刀的函数关系厂，从而得到算法的渐近时间复杂度。所谓基本语句是执行次数与算法的执行次数成正比的语句，它是算法中的关键操作。算法的基本语句大多包含在循环和递归结构中；对于单循环结构，循环体中的简单语句就是基本语句，其执行次数的大0表示就是该算法段的渐近时间复杂度；对于并列的循环结构，要先分析各个循环结构的渐近时间复杂度，然后利用大0表示法的加法规则求出算法的时间复杂度；对于多层嵌套的循环结构，最内层循环中的简单语句就是算法的基本语句，要自外向内逐层分析各层循环的渐近时间复杂度，再利用大0表示法的乘法规则来求出算法的渐近时间复杂度；对于递归结构，则可以根据递归过程递推出基本语句的执行次数，进而得到它的大0表示。总之，只要分析求出算法中关键操作的执行次数与问题规模的函数关系，也就得到了该次数的大0表示，从而也就求出了算法的渐近时间复杂度。
《数据结构与算法习题解答和实习指导》是由清华大学出版社出版的。
