《数据结构教学大纲与考核要求》由会员分享，可在线阅读，更多相关《数据结构教学大纲与考核要求（12页珍藏版）》请在金锄头文库上搜索。
1、 数据数据结结构构 授授课课内容与学内容与学时时分配建分配建议议教材:数据结构 （C 语言版）第二版，李云清，杨庆红，揭安全编著，人民邮电出版社章节内容基本内容学时进度数据的逻辑结构与存储结构 数据类型与抽象数据类型算法和算法分析 学习要求与建议，考核方式说明第 1 章，概论本章建议学时4 学时重点为算法 时间复杂度 分析。线性表 顺序表 栈 队列 栈与队列的应用（表达式求值等） 补充：顺序表的应用举例（如有序合并等）第 2 章，线性表及其 顺序存储本章建议学时8 学时重点为线性 表的特点， 顺序表的算 法实现，栈 和队例的实 现与应用。链式存储 单链表（查找，插入，删除，建表） 带头结点的单
2、链表的基本操作（查找，插入， 删除）补充：带头结点单链表的应用（头插法建表， 尾插法建表，链表倒置，链表归并，链表排 序等）循环单链表双链表链式栈与链式队列第 3 章，线性表及其 链式存储 本章学时建议10 学时重点是带头 结点的单链 表查找、插 入、删除结 点的方法。 基于带头结 点单链表常 见算法实现。 此处为历年 考研常考题。字符串模式匹配 快速模式匹配（KMP）算法 特殊矩阵的压缩存储第 4 章，字符串与特 殊矩阵本章学时建议4 学时难点是快速 模式匹配算 法的思想， next向量的 求解方法递归程序设计递归程序执行过程分析 递归程序到非递归程序的转换（重点介绍中 点优先输出问题的转换
3、方法，背包问题可让 学生课后阅读）递归程序应用举例 另补充一些基于线性表的递归问题举例（如 求线性表的最大数，链表倒序输出，线性表 倒置等）第 5 章，递归本章建议学时4 学时重点是递归 程序的执行 过程分析， 复杂递归到 非递归程序 的转换撰写人：揭安全、李云清、杨庆红、化志章、钟林辉、石海鹤以上教学学时建议合计 62 节理论学时，加上节假日因素，教学内容尽量控制在 16 周（64 节）完成。第 16 或第 17 周上机考试，第 17 周复习答疑，18-19（20）周学校期末考试。 为重点内容，为要求学生课后自学内容（建议教师提问考核）章节内容基本内容学时进度树的基本概念树的存储表示 树的遍
4、历 树的线性表示（括号表示）树的线性表示（层号表示）第 6 章，树型结构本章建议学时4 学时重点是树的 存储结构， 树的遍历及 其特点二叉树的基本概念二叉树的存储结构 二叉树的遍历递归算法（程序实现） 二叉树遍历的非递归实现 （程序实现） 二叉树上的其它运算（递归程序实现） 穿线二叉树（思想与方法） 树、森林与二叉树的相互转换方法第 7 章，二叉树 本章建议学时4 学时重点是二叉 树的遍历 （递归与非 递归）基于二叉树 的递归算法图的概念图的存储结构（邻接矩阵，邻接表） 图的遍历（BFS,DFS） 最小生成树 最短路径 拓扑排序 关键路径算法第 8 章，图本章学时建议10 学时重点：图的 遍历
5、，最小 生成树，最 短路径，拓 扑排序，关 键路径算法 的思想顺序表检索二叉排序树平衡二叉排序树（AVL 树） 最佳二叉排序树 Huffman 树及其应用 B-树 散列第 9 章，检索本章学时建议8 学时重点是二叉 排序树、 Huffman 树 与散列表排序的基本概念直接插入排序、二分插入排序、Shell 排序 直接选择排序（C 语言学过） 、堆排序 冒泡排序（C 语言学过） 、快速排序 归并排序 基数排序第 10 章，排序本章学时建议6 学时重点掌握算 法思想，算 法程序实现， 算法时间性 复杂性与稳 定性分析。附附 1、 、 数据数据结结构构 考研大考研大纲纲【考查目标考查目标】1.理解数
6、据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。3.能够选择合适的数据结构和方法进行问题求解。一、线性表一、线性表（一）线性表的定义和基本操作（二）线性表的实现1.顺序存储结构2.链式存储结构3.线性表的应用二、栈、队列和数组二、栈、队列和数组（一）栈和队列的基本概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用（五）特殊矩阵的压缩存储三、树与二叉树三、树与二叉树（一）树的概念（二）二叉树1.二叉树的定义及其主要特征2.二叉树的顺序存储结构和链式存储结构3.二叉树的
7、遍历4.线索二叉树的基本概念和构造5.二叉排序树6.平衡二叉树（三）树、森林1.书的存储结构2.森林与二叉树的转换3.树和森林的遍历（四）树的应用1.等价类问题2.哈夫曼（Huffman）树和哈夫曼编码四、图四、图（一） 图的概念（二） 图的存储及基本操作1.邻接矩阵法2.邻接表法（三） 图的遍历1.深度优先搜索2.广度优先搜索（四） 图的基本应用及其复杂度分析1.最小（代价）生成树2.最短路径3.拓扑排序4.关键路径五、查找五、查找（一） 查找的基本概念（二） 顺序查找法（三） 折半查找法（四） B-树（五） 散列（Hash）表及其查找（六） 查找算法的分析及应用六、内部排序六、内部排序（一
8、） 排序的基本概念（二） 插入排序1.直接插入排序2.折半插入排序（三） 气泡排序（bubble sort）（四） 简单选择排序（五） 希尔排序（shell sort）（六） 快速排序（七） 堆排序（八） 二路归并排序（merge sort）（九） 基数排序（十） 各种内部排序算法的比较（十一）内部排序算法的应用【知识点解析知识点解析】1线性表线性表线性表是一种最简单的数据结构，在线性表方面，主要考查线性表的定义和基本操作、线性表的实现。在线性表实现方面，要掌握的是线性表的存储结构，包括顺序存储结构和链式存储结构，特别是链式存储结构，是考查的重点。另外，还要掌握线性表的基本应用。2栈、队列和数
9、组栈、队列和数组栈和队列是两种特殊的线性表，在这方面，要求我们掌握栈和队列的基本概念，以及他们之间的区别。对于栈和队列的存储结构(包括顺序存储结构、链式存储结构)要有较深的理解，对于栈和队列的应用，例如，排队问题、子程序调用问题、表达式问题等，要搞清楚。一维数组属于线性表范畴，但多维数组不属于线性表。在这方面，主要掌握数组的存储结构，例如按行优先、按列优先等，某个元素存在的地址是什么。对于特殊矩阵(二维数组)的压缩存储原理也要搞清楚。3树与二叉树树与二叉树二叉树和树是两种不同的概念，这一点是必须要搞清楚的。在这个部分，我们要掌握树的定义、二叉树的定义及主要特征(特殊的二叉树、二叉树的性质)。在
10、二叉树的顺序存储结构和链式存储结构方面，特别是链式存储结构，因为很多应用都是建立在链式存储基础上，例如，二叉树的遍历(前序遍历、中序遍历、后序遍历)就是一种典型的应用。在特殊的二叉树中，完全二叉树的概念是必须要搞清楚的，其次，线索二叉树的基本概念和构造、二叉排序树、平衡二叉树的基本概念和应用，特别是二叉排序树的基本性质和特点要能很好地理解。多棵独立的树就组成了森林，树的存储结构和遍历、森林的遍历、树和二叉树的转换、森林和二叉树的转换等知识，也要有了了解。最后就是树的应用，通常会作为综合应用类试题出现，包括等价类问题、哈夫曼(Huffman)树和哈夫曼编码等。4图图在数据结构中，图的结构是最复杂
11、的，这里的概念也是最多的。我们要掌握图的基本概念(有向图、无向图、连通、路径、子图、出度、入度、生成树、最短路径、关键路径等)。图的存储及基本操作主要有邻接矩阵法和邻接表法，我们要掌握这有向图和无向图的这 2 种存储方法，要清楚图的连通和存储方法之间的关系。例如，一个顶点的出度和临界矩阵中 1 的个数有什么关系，等等。图的遍历方法有深度优先搜索和广度优先搜索，我们要掌握这 2 种遍历方法的算法实现。给出一个具体的图，要能知道它的遍历次序。在数据结构课程中，图的基本应用是最多的，也是最复杂的，我们要掌握这些应用的复杂度分析。要掌握的具体应用主要包括最小(代价)生成树、最短路径、拓扑排序、关键路径
12、。在给出的一个具体的图中，我们要会利用已知条件，求出上述应用的结果。5查找查找在给定的数据集合中查找某个关键值就是查找，查找的基本方法主要有顺序查找法、折半查找法、B-树、散列(Hash)表及其查找。考的比较多的是折半查找和散列表，我们要掌握它们的基本概念和方法，例如散列表的碰撞如何解决，装载因子的概念等。另外，我们要掌握各种查找算法的分析及应用，最好能把各种查找在查找成功、查找失败的情况下的最好、平均、最坏的平均查找次数的计算方法搞清楚。6内部排序内部排序根据考试大纲，只考查内部排序。所谓内部排序，就是在内存中进行排序。在这一部分中，主要要掌握直接插入排序、折半插入排序、冒泡排序(bubbl
13、e sort)、简单选择排序、希尔排序(shell sort)、快速排序、堆排序、二路归并排序(merge sort)、基数排序的基本概念和方法。搞清楚这些排序方法的流程，以及它们之间的区别。在这个知识点，一个很重要的考查点就是各种内部排序算法的比较，一般的书上都会有这样的一个表格，列出了所有排序在各种情况下(最好、最坏、平均)的时间复杂度和空间复杂度，这个表是需要我们记下来的。当然，如果我们能掌握复杂度的计算方法，自己能推算出来，那就更好了。最后，就是要掌握内部排序算法的基本应用，以及算法的实现。附附 2、 、 数据数据结结构构 期末考期末考试试笔笔试样题试样题2007-2008 学年上学期
14、学年上学期 数据数据结结构构 期末考期末考试试题试试题 B课课程代号：程代号：262208 注意事注意事项项：请将答案全部写到答题纸上，并注明题号！一、单项选择题（每小题 2 分，共 16 分）1若将数据结构形式定义为二元组(K，R)，其中 K 是数据元素的有限集合，则 R 是 K 上 （ ） A操作的有限集合 B映象的有限集合 C类型的有限集合 D关系的有限集合 2在头指针为 head 且表长大于 1 的单循环链表中，指针 p 指向表中某个结点，若 p- next-next=head，则（ ） Ap 指向头结点 Bp 指向尾结点 C*P 的直接后继是尾结点 D *p 的直接后继是头结点 3在
15、具有 n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（ ） AO(1) BO(n)CO(nlogn) DO(n2) 4队列和栈的主要区别是（ ） A逻辑结构不同 B存储结构不同 C所包含的运算个数不同 D限定插入和删除的位置不同 5若进栈序列为 a,b,c，则通过入出栈操作可能得到的 a,b,c 的不同排列个数为（ ）A4 B5 C6 D7 6一棵含 18 个结点的二叉树的高度至少为( ) A3 B4 C5 D6 7在一个带权连通图 G 中，权值最小的边一定包含在 G 的（ ） A最小生成树中B深度优先生成树中 C广度优先生成树中D深度优先生成森林中 8已知一组关键字为25,48,36,72,79,82,23,40,16,35，其中每相邻两个数为有序子序列。 对这些子序列进行一趟长度为 2 的两两归并的结果是( ) A25,36,48,72,23,40,79,82,16,35 B25,36,48,72,16,23,40,79,82,35 C25,36,48,72,16,23,35,40,79,82 D16,23,25,35,36,40,48,72,79
