新数据结构讲义.docVIP

第九讲 总复习课 我们回顾一下学过的内容，数据结构是一门专业课。本课程的目的和任务是使学生较全面地掌握各种常用的数据结构，为学习后续软件课程提供必要的基础，提高运用数据结构解决实际问题的能力。 第一章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义，要求了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。 第二章的目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。要求能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。 第三章的目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算，重点是掌握栈和队列在两种存储结构上实现的基本运算。 第四章的目的是介绍串的逻辑结构，存储结构及其串上的基本运算，重点是掌握串上实现的模式匹配算法。 第五章的目的是介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念。重点是熟悉多维数组的存储方式，矩阵的压缩存储方式，广义表的定义及其求表头和表尾的运算。 第六章的目的是介绍二叉树的定义，性质，存储结构，遍历，线索化，树的定义，存储结构，遍历，树和森林与二叉树的转换，哈夫曼树及哈夫曼编码等内容。重点是掌握二叉树的遍历算法及其 有关应用。 第七章的目的是介绍图的基本概念，两种常用的存储结构，两种遍历算法以及图的应用算法，要求重点掌握在图的两种存储结构上实现的遍历算法。难点是图的应用算法：求最小生成树，求最短路径以及拓扑排序。 第八章的目的是介绍五类内部排序方法的基本思想，排序过程，算法实现，时间和空间性能的分析以及各种排序方法的比较和选择。重点掌握快速排序，堆排序，归并排序和基数排序的基本思想及排序过程，难点是这四个排序算法的实现。 第九章的目的是介绍线性表，树和散列表的查找方法，算法实现和各种查找方法的时间性能分析。重点掌握顺序查找，二分查找，二叉查找树上查找以及散列表上查找的基本思想和算法实现。 第十章的目的是介绍存储在外存上的数据结构（即文件）的有关概念，各种文件的特点，组织方法及查询和更新操作，要求对这些内容做一般性的了解。 本课程内容多，难度大，要求具有较强的程序设计能力及离散数学，C语言基础，从数据结构的逻辑结构，存储结构和数据的运算三个方面去理解各种数据结构的异同之处及相互之间的关系，懂得从定义和实现两个层次去分析各种数据结构。通过多练习多动手，培养自己的程序设计经验和素质，多做算法设计题来理解，消化和巩固所学的知识，提高分析问题，解决问题的能力以及编程能力。设计较复杂算法的方法和步骤是：首先明确算法要解决的问题目标，选择合适的数据结构，确定在所选的数据结构上必须有哪些操作，写出抽象的算法；然后确定存储结构，对抽象算法中每个操作逐步求精地写出最终的程序。 要求全面系统地学习各章节内容，弄懂和记住各种概念，方法，结论的内涵和外延，注意区分相仿的概念，方法，结论，掌握它们之间的联系。 单项选择题 1、线性表的链接实现有利于 运算。 A、插入 B、读表元 C、查找 D、定位 2、串的逻辑结构与 的逻辑结构不同。 A、线性表 B、栈 C、队列 D、树 3、设单链表中指针P指着结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为 。 A、P→next=P→next→next B、P= P→next C、P=P→next→next D、P→next=P 4、设一数列的顺序为：1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为 。 A、3，2，5，6，4，1 B、1，5，4，6，2，3 C、2，4，3，5，1，6 D、4，5，3，6，2，1 5、如果结点A有3个兄弟，而且B为A的双亲，则B的度为 。 A、3 B、4 C、5 D、1 6、线索化二叉树中某结点D，没有左孩子的主要条件是 。 A、D→Lchild=Null B、D→ltag=1 C、D→Rchild=Null D、D→ltag=0 7、下面的序列中， 是堆。 A、1，2，8，4，3，9，10，5 B、1，5，10，6，7，8，9，2 C、9，8，7，6，4，8，2，1 D、9，8，7，6，5，4，3，7 8、具有n个顶点的完全有向图的边数为 。 A、n(n-1)/2 B、n(n-1) C、2n D、(n+1)(n-