《数据结构》考试大纲

1、数据结构考试大纲一、考试基本要求：通过本课程的学习，学生应比较系统地从数据结构的逻辑结构、存储结构和运算三个方面去掌握线性表、栈、队列、串、数组、广义表、树、图等常用的数据结构；并且掌握在各种常用的数据结构上实现得排序和查找算法，同时对算法的时间和空间复杂性有一定得分析能力；针对简单的应用问题，应能选择合适得数据结构及设计有效得算法解决之。这对于培养学生运用数据结构解决实际问题能力的培养有着重要的意义。二、考核知识范围及考核要求：第一章绪论1、合适的数据结构在解决实际应用问题中的关键性；以及学习数据结构的意义。2、数据、数据元素、数据项、数据结构等基本概念。3、数据结构的四种逻辑结构和两种存储

2、结构表示方法。4、抽象数据类型的表示和实现5、算法的五个特点。6、算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。7、算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。第二章顺序表1、线性表的类型定义2、顺序表的含义及特点，顺序表上的插入、删除操作及其平均时间性能分析3、链式表示和实现，单链表、双链表、循环链表链接方式上的区别；4、单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。5、循环链表上尾指针取代头指针的作用6、单循环链表上的算法与单链表上相应算法的异同点。7、双向链表的定义和相关算法。8、顺序表和链表的比较，以及如何选择其一作为其存储结构才能取

3、得较优的时空性能。第三章 栈与队列1、栈的抽象数据类型的定义2、栈的表示和实现3、栈的简单应用4、抽象数据类型队列的定义5、队列的链式表示和实现6、队列的顺序表示和实现第四章串1、串的定义、空串、空格串、子串、主串、串相等。2、串的基本操作。3、串的顺序存储结构及在顺序存储结构下基本操作的实现。4、串的堆分配存储表示及其在堆分配存储结构下基本操作的实现。5、串的链式存储表示第五章数组和广义表1、数组的顺序存储结构。2、二维数组的按行存储及按列存储和计算数组元素的地址计算公式。3、矩阵的压缩存储、特殊矩阵的表示。4、广义表的定义第六章树和二叉树11. 理解树的概念及相关术语2. 理解二叉树的概念

4、、相关术语、性质及存储结构3. 掌握二叉树的遍历算法4. 了解树（森林）与二叉树的对应关系5. 了解树（森林）的“孩子兄弟存储法”及遍历方法6. 掌握赫夫曼（ Huffman）树的构造及应用第七章图1. 理解图（网）的概念、相关术语及邻接表、邻接矩阵存储法2. 掌握图的遍历算法3. 掌握最小生成树、最短路径等算法第八章查找1. 掌握顺序查找、二分查找算法2. 掌握二叉排序树的查找、插入及删除算法3. 理解平衡二叉排序树及插入时的平衡方法4. 掌握哈希（ Hash）表的查找5. 了解查找成功及失败的平均查找长度第九章排序1. 理解排序的概念及相关术语2. 掌握直接插入、希尔（ Shell ）、快

5、速、堆、归并等排序算法3. 理解基数排序算法4. 了解二分插入、起泡、简单选择等排序算法5. 了解上述排序算法的时间复杂度、空间复杂度、稳定性6. 了解上述部分排序算法的适用场合三、考试形式及试卷结构1、考试形式为闭卷、笔试。考试时间为 120 分钟，试卷满分为 100 分。2、本门课程的命题考试， 根据本大纲所规定的考试内容和考试目标来确定考试范围和考核要求。考试命题会覆盖各章，并适当突出重点章节，体现本课程的内容重点。3、试题合理安排难易度结构。试题难易度可分为：易、较易、较难和难四个等级。每份试卷中，不同难度试题的分数比例为： 2：3：3：2。4、本课程考试的题型，一般有单项选择、填空、

6、算法填空、简单题、算法设计等五种类型。5、分数分配序号内容比例1绪论52线性表203栈和队列104串25数组和广义表326树和二叉树257图208查找59排序10合计100四、 参考书目数据结构（ C 语言版）严蔚敏吴伟民编著，清华大学出版社五、题型示例一、选择题（每小题2 分，共 30 分）1. 一个线性表顺序存储表示中，第一个元素的存储地址是1000，每个元素的长度为2，则第 5 个元素的地址是（）。A、 1010B、 1000C、 1008D、 1002二、填空题（每小题2 分，共 30 分）1、数据结构的形式地定义为：Data_Structure（D，R），其中 D是 _的有限集合， R是 D 上的_ 有限集合。三、完成算法（每题6 分，共 18 分）算法 1void conversion()/将十进制数转换为8 进制数int n,e;initStack(s);scanf( “%d”,&n);while(n)push(s,n%8);_;while(_)_;printf("%d",e);四、简答题（每题分，共 24 分）1.已知某二叉树的先根遍历序列为：ABCDEFG ，中序遍历