数据结构题型题集题解/考研辅导丛书
2005-10
科学出版
刘坤起等
426
近几年，由于教师资源短缺，系里引进了不少年轻教师。在布置教学任务时，一些年轻教师常常不约而同地选择像“数据结构”这样一些自己认为比较容易教的课程，而像“数理逻辑”、“算法设计与分析”等一些课程，少有人问津。为此，我心里常想，难道“数据结构”课程真的就很容易教吗？ 为了回答这个问题，并澄清“数据结构”课程教学中存在的一些认识问题，我查阅了一些文献，特别是收集了厦门大学计算机科学系“数据结构”课程的教学大纲和教学规程，并进行了认真的学习和思考。阅读了这些文献，深入思考后，大有拨云见日、茅塞顿开之感，深感教育与教学活动实属科学研究的范畴，并意识到其重要性。于是，我专门在系里组织了一个“数据结构”课程教学研讨会。与会教师共同学习了这些文献，并就该课程教学中存在的有关问题展开了认真而热烈的讨论，初步解决了长期以来存在的争论，取得了广泛共识。这次会议的效果看来的确不错，原来那些认为“数据结构”课程是比较容易教的部分教师放弃了自己的观点，感到要真正教好一门课程是不容易的，而做一个好教师则更难！ 我们的教学研讨会是从下面的问题引发并渐次展开的，经过整理后的讨论意见，或许对读者深入理解“数据结构”课程的要点有着参考价值。
《数据结构：题型 题集 题解》是为了配合高等学校计算机科学与技术专业的“数据结构”课程的教学而编写的，是“数据结构”课程的配套教材。全书共分题型与题解、思考题集和试题集三篇，共精选并收录1000多道题目，题目类型丰富、覆盖面广，而且对题目的解题方法和规律进行了较系统的总结和归纳；《数据结构：题型 题集 题解》的算法描述采用数学语言（带自然语言的算术、代数运算、函数运算等），体现了计算机科学与技术学科的抽象描述求解问题与具体实现解决问题相分离的学科特点。 该书适合高等学校计算机科学与技术专业本科、专科学生以及从事计算机科学与技术专业教学的教师阅读，也适用于即将参加计算机科学与技术专业硕士研究生入学考试、软件人员水平考试的考生和成人计算机教育的学生、各类计算机培训班学生、计算机的自学者学习“数据结构”课程时参阅。
第1篇 题型与解题第1章 绪论1.1 题型归纳与典型例题1.1.1 题型之一——基本概念题1.1.2 题型之二——证明题1.1.3 题型之三——算法的复杂性分析1.2 习题1.2.1 基本题1.2.2 算法的复杂性分析题1.3 习题解答1.3.1 基本题解答1.3.2 算法的复杂性分析题解答第2章 线性表2.1 题型归纳与典型例题2.1.1 题型之一——基本题2.1.2 题型之二——算法设计题2.2 习题2.2.1 基本题2.2.2 算法设计题2.3 习题解答2.3.1 基本题解答2.3.2 算法设计题解答第3章 栈与队列3.1 题型归纳与典型例题3.1.1 题型之一——基本题3.1.2 题型之二——证明题3.1.3 题型之三——算法设计题3.2 习题3.2.1 基本题3.2.2 证明题3.2.3 算法设计题3.3 习题解答3.3.1 基本题解答3.3.2 证明题解答3.3.3 算法设计题解答第4章 串4.1 题型归纳与典型例题4.1.1 题型之一——基于某种存储结构的串的基本运算的算法设计4.1.2 题型之二——其他类型的算法设计4.1.3 题型之三——与模式匹配有关的问题4.2 习题4.2.1 基本题4.2.2 算法设计题4.3 习题解答4.3.1 基本题解答4.3.2 算法设计题解答第5章 数组与广义表5.1 题型归纳与典型例题5.1.1 题型之一——在一维数组的存储表示下，对应元素下标关系的计算5.1.2 题型之二——特殊矩阵及其在一维数组的压缩存储表示下，对应元素下标关系的计算5.1.3 题型之三——算法设计题5.2 习题5.2.1 基本题5.2.2 计算题5.2.3 算法设计题5.3 习题解答5.3.1 基本题解答5.3.2 计算题解答5.3.3 算法设计题解答第6章 树形结构6.1 题型归纳与典型例题6.1.1 题型之一——基本题6.1.2 题型之二——证明题6.1.3 题型之三——算法设计题6.2 习题6.2.1 基本题6.2.2 证明题6.2.3 算法设计题6.3 习题解答6.3.1 基本题解答6.3.2 证明题解答6.3.3 算法设计题解答第7章 图结构7.1 题型归纳与典型例题7.1.1 题型之一——基本题7.1.2 题型之二——证明题7.1.3 题型之三——算法设计题7.1.4 题型之四——图的应用算法7.2 习题7.2.1 基本题7.2.2 证明题7.2.3 算法设计题7.3 习题解答7.3.1 基本题解答7.3.2 证明题解答7.3.3 算法设计题解答第8章 查找8.1 题型归纳与典型例题8.1.1 题型之一——基本题8.1.2 题型之二——证明题8.1.3 题型之三——算法设计题8.2 习题8.2.1 基本题8.2.2 证明题8.2.3 算法设计题8.3 习题解答8.3.1 基本题解答8.3.2 证明题解答8.3.3 算法设计题解答第9章 排序9.1 重点题型与典型例题9.1.1 题型之一——基本题9.1.2 题型之二——证明题9.1.3 题型之三——算法设计题9.2 习题9.2.1 基本题9.2.2 证明题9.2.3 算法设计题9.3 习题解答9.3.1 基本题解答9.3.2 证明题解答9.3.3 算法设计题解答第10章 文件10.1 题型归纳与典型例题10.1.1 题型之一——基本题10.1.2 题型之二——算法设计题10.2 习题10.2.1 基本题10.2.2 算法设计题10.3 习题解答10.3.1 基本题解答10.3.2 算法设计题解答第2篇 思考题集第11章 思考题集11.1 绪论11.2 线性表11.3 栈与队列11.4 字符串11.5 数组与广义表11.6 树形结构11.6.1 证明题11.6.2 算法设计题11.7 图结构11.7.1 基本题11.7.2 证明题11.7.3 算法设计题11.8 查找11.9 排序11.10 文件第3篇试题集第12章 计算机科学与技术专业本科结业数据结构试题集数据结构试题之一数据结构试题之二数据结构试题之三数据结构试题之四厦门大学数据结构试题西北大学数据结构试题中国科学技术大学数据结构试题合肥工业大学数据结构试题上海交通大学数据结构试题第13章 计算机科学与技术专业硕士研究生人学考试数据结构试题集中国科学院（计算所、软件所、中国科技大学）数据结构试题（2004）北京大学数据结构试题（2004）清华大学数据结构试题（2003）北京航空航天大学数据结构试题（2004）北京理工大学数据结构试题（2003）北京交通大学数据结构试题（2004）北京工业大学数据结构（含C++）试题（2003）北京邮电大学数据结构试题（2003）中国人民大学数据结构试题（2001）北京科技大学数据结构试题（2004）南开大学数据结构试题（2004）天津大学数据结构试题（2002）太原理工大学数据结构试题（2004）山东大学数据结构试题（2001）吉林大学数据结构试题（2004）东北大学数据结构试题（2002）哈尔滨工业大学数据结构试题（2003）哈尔滨工程大学数据结构试题（2004）大连理工大学数据结构试题（2004）上海交通大学数据结构试题（2004）复旦大学数据结构试题（2002）同济大学数据结构试题（2002）南京大学数据结构试题（2004）东南大学数据结构试题（2003）南京航空航天大学数据结构试题（2002）南京理工大学数据结构试题（2005）苏州大学数据结构试题（2001）合肥工业大学数据结构试题（2003）浙江大学数据结构试题（2002）中山大学数据结构试题（2003）华南理工大学数据结构试题（2004）国防科技大学数据结构试题（2001）湖南大学数据结构试题（2004）中南大学数据结构试题（2004）武汉大学数据结构试题（2004）华中科技大学数据结构试题（2004）武汉理工大学数据结构试题（2003）电子科技大学数据结构试题（2002）重庆大学数据结构试题（2002）贵州大学数据结构试题（2004）西北工业大学数据结构试题（2004）西安电子科技大学数据结构试题（2005）西北大学数据结构试题（2002）参考文献后记
（3）优点是多个链栈一般不考虑栈的溢出（仅受用户内存空间限制）。缺点是栈中元素要以指针相链接，比顺序存储多占用了存储空间。 二、已知进入栈或队列的元素顺序。给出其出栈或出队顺序的问题 对于栈来说，若给定n个不同的元素依次进栈，出栈元素的顺序总数刚好满足卡塔南数列的计算。不管是栈，还是双端队列，读者都应该总结其中的规律。 例3 设一个双端队列，元素进人该队列的次序为a，b，c，d。试分别求出以下条件的输出序列： （1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。 （2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列。 （3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。 答：（1）d，a，c，b；（2）d，b，a，c；（3）d，b，c，a。 三、递归过程的跟踪 给定一个递归算法，要求给出该递归算法中栈状态的变化过程是常见的一种题型。这种题目要求读者真正弄清栈与递归的关系。典型问题就是梵塔问题，要求读者能够手工完成该递归算法的运行，重要的是真正掌握其中栈的变化情况。 例4 设有类C语言描述的递归函数sum（n）如下： ……
