数据结构习题与解析 (2010 年度畅销榜NO.3951 )

本书是与北京市高等教育学历文凭考试计算机专业教材《数据结构》(科学出版社出版)相配套的辅导教材。内容按照教材对应章节的先后次序安排，每章包括学习要点、习题解析及其参考答案，特别是对于每一个算法设计题都给出了解决该问题的算法思路，目的是为了更好地帮助读者理解答案。本书收集的习题覆盖面比较广泛，基本涉及了数据结构课程的所有习题类型。本书最后还给出了1998年至2002年北京市高等教育学历文凭\r\n\r\n考试数据结构试题及其答案。\r\n\r\n 本书不仅可以作为高等学校计算机专业的专科生与本科生学习数据结构课程的参考书，也可以作为参加高等教育学历文凭考试的考生以及报考计算机专业硕士研究生的考生的复习资料。\r\n
\r\n

第一章 概述 \r\n\r\n 1. 1　本章内容概述 \r\n\r\n 1. 2　习题与解答 \r\n\r\n 第二章　线性表 \r\n\r\n 2. 1　本章内容概述 \r\n\r\n 2. 2　习题与解答 \r\n\r\n 第三章　数组 \r\n\r\n 3. 1　本章内容概述 \r\n\r\n 3. 2　习题与解答 \r\n\r\n 第四章 堆栈与队列 \r\n\r\n 4. 1　本章内容概述 \r\n\r\n 4. 2　习题与解答 \r\n\r\n 第五章　广义表 \r\n\r\n 5. 1　本章内容概述 \r\n\r\n 5. 2　习题与解答 \r\n\r\n 第六章 串 \r\n\r\n 6. 1　本章内容概述 \r\n\r\n 6. 2　习题与解答 \r\n\r\n 第七章 树与二叉树 \r\n\r\n 7. 1　本章内容概述 \r\n\r\n 7. 2　习题与解答 \r\n\r\n 第八章 图 \r\n\r\n 8. 1　本章内容概述 \r\n\r\n 8. 2　习题与解答 \r\n\r\n 第九章 文件及查找 \r\n\r\n 9. 1　本章内容概述 \r\n\r\n 9. 2　习题与解答 \r\n\r\n 第十章 内排序 \r\n\r\n 10. 1　本章内容概述 \r\n\r\n 10. 2 习题与解答 \r\n\r\n 上机练习题 \r\n\r\n 附录 历年北京市高等教育学历文凭考试数据结构试题及答案 \r\n\r\n 参考文献 \r\n
\r\n

高等教育学历文凭考试是国家对尚不具备颁发国家承认学历的民办学校所招收的学生, 检验其接受高等教育结果的一种验收性考试. 1993年北京市在全国率先试点, 目前已走过10年的历程. 这10年来, 北京20余所民办学校共计招生近20多万人, 目前累计毕业生1万多人. 为国家的经济建设和社会稳定起到了积极的作用.

为做好高等教育学历文凭考试试点的基础工作, 1998年, 北京市自学考试办公室聘请一批专家为计算机应用专业编写了一套教材, 并委托科学出版社出版. 几年来, 在不断征求意见. 不断改进完善的基础上, 这套教材被几十所学校持续使用并得到了大家的认同. 教材稳定后, 应授课教师和同学们的要求, 科学出版社希望再组织编写一套教学参考书. 我们希望这套参考书能达到这样一种目的：

1. 它是按照教学大纲的内容, 提纲挚领地把全书的内容进行提炼, 这样可以使教者和学者对教与学的要求一目了然,

2. 它不应是教材的浓缩本, 而是结合实例指出和分析各章节的难点, 并提出合理的学习方法, 以起到指导学习的作用,

3. 为配合学习与课下的练习, 本书应配置一定的习题并附参考答案.

非常感谢的是, 本套教学参考书的编者——也就是教材的各位编写老师们——在学校繁重的教学和科研工作中, 对出版社的建议给予了积极的响应. 他们对本套教学参考书的编写提出了很多好的意见, 使得本套书更具有针对性和实用性. 希望通过出版社和编者的努力, 能使大家更好地掌握课程的基本内容和基本技能.

需要强调的是, 掌握正确的学习方法是非常重要的. 本套教学参考书与主教材是相辅相成的, 它对主教材的内容进行了简明扼要的介绍, 从而能起到辅助学习的作用, 但是它并不能替代主教材. 这一点希望大家在使用时充分注意.

北京市高等教育自学考试委员会办公室

2002年4月3日

数据结构是高等学校计算机专业重要的专业基础课程之一, 本课程主要讲述数据结构的基本概念, 各种常见的数据结构, 包括数据的逻辑结构. 存储结构以及在这两种结构的基础上对数据实施的基本运算(算法)以及对算法的时间. 空间和其他方面进行度量分析等几个方面. 通过本课程的学习, 学生能够运用课程所讨论的概念和方法更好地进行算法设计与算法分析, 掌握计算机进行数据处理的基本原理和技巧, 进一步提高程序设计

的能力. 为此, 本课程要求学生熟练掌握常见数据结构的逻辑结构. 存储结构以及不同存储结构之间的差异, 掌握各种基本运算的实现算法, 并能够了解基本的算法分析方法. 学好本课程的主要目的是为学生打好专业基础, 提高计算机应用水平与能力.

数据结构课程是一门实践性非常强的课程. 要学好这门课程, 除了课堂教学之外, 课后还需要进行大量的练习与一定量的上机实践. 只有通过这些环节的学习才可能更好地. 更有效地掌握本课程要求掌握的知识. 为此目的, 我们编写了这本关于习题与练习的书.

1998年作者受北京市高等教育自学考试委员会的委托, 编写了数据结构课程的教材《数据结构》(科学出版社出版), 应该说, 本书是与之相配套的辅导教材, 内容也是按照教材对应章节的先后次序安排的. 其实, 本书早在几年之前就打算出版, 只是作者一直顾虑编写一本详尽的习题解答, 是否会对本课程的教学工作带来一些干扰. 尽管如此, 在多数教师与学生的要求以及有关部门的大力协助下, 本书最终还是面世了.

数据结构课程的习题类型一般可以分为三类. 一类称为概念题, 它包括是非判断题. 简答题. 选择题(单选或多选)与填空题几种形式. 另一类为算法题, 通常包括算法设计与算法填空两种形式. 还有一类介于这两类题型之间, 习惯称之为综合题或者问题求解题.

这类题概念性一般不是很强, 也不是写算法, 很可能就是一种方法的具体应用. 对于上述几种题型, 本书基本上都涉及到了, 并且所有的题目都给出了相应的参考答案, 尤其是对于每一个算法设计题, 在给出具体算法之前, 都分别给出了解决该问题的算法思路, 目的是为了更好地帮助读者理解答案. 另外, 对于有些能够比较充分体现数据结构课程所讨论的知识在解决实际问题中的应用的算法, 书中给出了具体的C语言程序, 但是限于篇幅, 只是象征性地给出了10个程序. 考虑到本书的主要读者为北京市参加高等教育学历文凭考试的学生, 作者在本书的最后分别给出了1998年至2002年北京市高等教育学历文凭考试数据结构试题及其答案, 供这些读者查阅与参考.

本书内容比较丰富, 收集的习题覆盖面也比较广泛, 既有较容易的基本题目, 也有一些难度适中的题目, 当然, 书中也收集了少量难度相对较大的题目. 读者可以按照本课程的教学大纲与考试大纲的要求, 并根据自己的实际情况选择合适的题目进行练习. 因此, 本书不仅可以作为高等学校计算机专业的专科生与本科生学习数据结构课程的学习参考书籍, 也可以作为报考计算机专业硕士研究生的考生的复习资料, 因为书中少量题目就是来自近几年硕士研究生的入学试卷.

应该说明的是, 问题的答案一般都不是惟一的, 尤其是算法题的解答更是如此, 作者在书中给出的解答也不是完美的, 有些答案的细节可能还有值得商榷的地方, 读者千万不要照抄照搬, 读者在经过自己的学习. 领会的基础上完全可以根据自己的理解写出正确的结果, 不要求读者得到的结果与本书给出的解答完全一致, 很可能读者的结果更优秀. 因此, 本书仅仅起到一个抛砖引玉的作用, 愿读者开发出更多更好的解答. 对于由于编写时间仓促而导致书中出现的谬误, 作者在表示歉意的同时也诚恳地欢迎读者给予批评指正, 并希望你们能够将答案寄给我们, 作者将不胜感激.

作 者

2002年2月