数据结构习题解答与实验指导
2004-12
中国铁道出版社
石强 等 著
199
无
“数据结构”是计算机科学与技术等电子信息类相关专业的一门核心基础课程。本书将各章的知识要点进行归纳和总结，对难以理解的问题进行讲解和指导，对涉及重要知识点的典型题目进行分析和解答，帮助读者理解数据结构的内容，掌握各种数据结构的表示方法及应用实现。此外，“数据结构”是一门理论与实践紧密结合的课程，不仅要能够理解基础理论知识，针对具体问题选择和设计出适当的逻辑结构、存储结构及相应的算法，还要能在此基础上编写出结构清晰、正确易读、符合软件工程规范的程序。在“数据结构”课程的教学中，除了课堂教学外，每周还应有不少于两个学时的实验课程。 本书根据国内“数据结构”课程的实际教学情况，在内容上力图具有一定的先进性和较强的适应性。遵循这一原则，在编写中着重讲述原理、概念和实例。为了提高学生实践技能，编写了实验指导部分。根据“数据结构”课程内容，给出了7个实验题目，对每个题目给出了明确的实验要求，同时还给出了规范的实验步骤。此外，附录中还提供了实验报告范例。 本书是《数据结构（第三版）》（书号：978-7-113-11025-3，中国铁道出版社，刘振鹏、罗文劫、石强编著）的配套用书，按照最新考研大纲修订，是作者在总结多年指导学生实验课教学和讲授“数据结构”课程经验的基础上编写的。作为普通高等教育“十一五”国家级规划教材《数据结构（第三版）》的配套用书，全书保持了第二版的基本框架，对各章节内容进行了扩充和修正，增加了链表、栈、树、图、排序中的一些必要知识点，使内容更加全面；进一步优化了算法，增加和完善了重点算法的注释；增加了近几年硕士研究生入学考试中的一些经典题目，并进行了详细而全面的解析。在本次修订过程中，作者着重强调了与考研大纲的一致性，强调了C++中面向对象思想在算法中的体现，进一步细化和完善验证性实验的实现过程和综合性实验的设计细节，且书中所有程序都在VC++6.0环境下调试通过。 本书分为两部分：第一部分是理论知识与习题解答，第二部分是实验指导。第一部分由罗文劫、常萌修订，第二部分由石强修订。全书由石强统稿。 在本书的编写过程中，参考了一些国内外优秀教材及数据结构习题集和实验教程。刘振鹏、张小莉等老师对本书的编写提出了许多宝贵意见，对此表示衷心的感谢。 尽管我们做了很大的努力，但由于水平有限，书中难免有不妥之处，恳请读者予以指正。
《数据结构习题解答与实验指导（第3版）》由两部分组成。第一部分为学习提要和习题解答，其内容为数据结构各部分的知识要点、典型例题解析和习题解答，帮助学生提纲挈领地掌握知识重点、巩固所学内容；第二部分为实验指导，根据数据结构课程的教学重点，给出7个实验题目，每个题目都有明确的实验要求，同时还给出了规范的实验步骤，此外在《21世纪高等院校计算机专业规划教材：数据结构习题解答与实验指导（第3版）》附录中还提供了一个实验报告范例。 《21世纪高等院校计算机专业规划教材：数据结构习题解答与实验指导（第3版）》力图通过典型例题的解析对具有代表性实验的指导，帮助学生深入学习、掌握并灵活运用数据结构知识。《21世纪高等院校计算机专业规划教材：数据结构习题解答与实验指导（第3版）》配合主教材使用，起到衔接课堂教学、实验教学以及课下辅导的作用。 《21世纪高等院校计算机专业规划教材：数据结构习题解答与实验指导（第3版）》适合作为高等院校“数据结构”课程的参考书，也可作为研究生入学考试的辅导材料，对于从事计算机应用及开发的技术人员以及广大的计算机及相关专业的自学者，也具有一定的参考价值。
第一篇 学习提要和习题解答第1章 绪论1．1 重点难点指导1．1．1 相关术语1．1．2 算法的描述和分析1．2 典型例题解析1．2．1 选择题1．2．2 判断题1．2．3 填空题l．3 课后习题选解第2章 线性表2．1 重点难点指导2．1．1 相关术语2．1．2 线性表的顺序存储2．1．3 链表2．1．4 线性表的基本运算2．2 典型例题解析2．2．1 选择题2．2．2 判断题2．2．3 简答题2．2．4 算法设计题2．3 课后习题选解第3章 栈和队列3．1 重点难点指导3．1．1 相关术语3．1．2 栈3．1．3 队列3．1．4 栈的应用3．1．5 队列的应用3．2 典型例题解析3．2．1 选择题3．2．2 填空题3．2．3 简答题3．2．4 算法设计题3．3 课后习题选解第4章 串4．1 重点难点指导4．1．1 相关术语4．1．2 串的基本运算4．1．3 串的存储结构4．1．4 字符串匹配算法实功4．2 典型例题解析4．2．1 基本运算题4．2．2 选择题4．2．3 填空题4．2．4 算法设计题4．3 课后习题选解第5章 数组和广义表5．1 重点难点指导5．1．1 相关术语5．1．2 多维数组5．1．3 特殊矩阵5．1．4 稀疏矩阵5．1．5 广义表5．2 典型例题解析5．2．1 选择题5．2．2 填空题5．2．3 简答题5．2．4 算法设计题5．3 课后习题选解第6章 二叉树6．1 重点难点指导6．1．1 相关术语6．1．2 二叉树的存储结构6．1．3 二叉树的遍历运算6．1．4 二叉树的基本应用6．2 典型例题解析6．2．1 选择题6．2．2 判断题6．2．3 填空题6．2．4 应用题6．2．5 算法设计题6．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．2．4 应用题7．2．5 算法设计题7．3 课后习题选解第8章 图8．1 重点难点指导8．1．1 相关术语8．1．2 图的基本操作8．1．3 图的存储表示8．1．4 图的遍历8．1．5 图的应用8．2 典型例题解析8．2．1 判断题8．2．2 选择题8．2．3 填空题8．2．4 应用题8．2．5 算法设计题8．3 课后习题选解第9章 查找9．1 重点难点指导9．1．1 相关术语9．1．2 线性表查找9．1．3 排序树上的查找9．1．4 哈希表9．2 典型例题解析9．2．1 判断题9．2．2 选择题9．2．3 应用题9．2．4 算法设计题9．3 课后习题选解第10章 排序10．1 重点难点指导10．1．1 相关术语10．1．2 插入排序10．1．3 交换排序10．1．4 选择排序10．1．5 归并排序10．1．6 基数排序10．1．7 外部排序10．2 典型例题解析10．2．1 判断题10．2．2 选择题10．2．3 填空题10．2．4 算法设计题10．3 课后习题选解第二篇 实验指导第11章 实验的一般步骤11．1 概述11．2 实验步骤第12章 实验安排实验一 约瑟夫（Josephus）环问题实验二 一元多项式相加问题实验三 停车场模拟管理程序的设计与实现实验四 农夫过河问题的求解实验五 哈夫曼编／译码的设计与实现实验六 简单校园导游程序的设计与实现实验七 简单个人书籍管理系统的设计与实现附录A 实验报告范例参考文献
2.数据类型 数据类型是一个值的集合以及在这些值上定义的一组操作的集合。 在高级程序设计语言中，数据类型可分为如下两类： 原子类型：其值不可分解。如c语言中的整型、实型、字符型等。 结构类型：其值可分解为若干成分。如c语言中的数组、结构等。 3.抽象数据类型 抽象数据类型是指抽象数据的组织和与之相关的操作。它可以看做是数据的逻辑结构及其在逻辑结构上定义的操作。 抽象数据类型的特征是使用与实现相分离，实行封装和信息隐蔽。也就是说，在抽象数据类型设计时，把类型的定义与其实现分离开来。 4.数据结构 数据结构是指互相之间存在着一种或多种关系的数据元素的集合，是指数据元素之间的相互关系，即数据的组织形式。它包括以下3方面的内容： 逻辑结构：数据之间的逻辑关系。 存储结构：数据元素及其关系在计算机存储器内的表示。 数据的运算：对数据对象施加的操作。 5.两类逻辑结构 （1）线性结构 线性结构的逻辑特点：若结构为非空集，有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和直接后继，如线性表。 线性结构只有一个直接前驱和直接后继。 （2）非线性结构 非线性结构的逻辑特点：一个结点可能有多个直接前驱和直接后继，如树形结构和图形结构。 非线性结构可能有多个直接前驱和多个直接后继。 6.数据逻辑结构的4种基本形态 集合结构：数据元素问的关系是“属于同一个集合”。 线性结构：数据元素之间存在着一对一的关系。 树形结构：数据元素之间存在着一对多的关系。 图形结构：数据元素之间存在着多对多的关系。 ……
无