《数据结构》

一、考试目的

考核普通高等学校专科（含高职）应届毕业生对于《数据结构》课程基本知识掌握是否达到教学大纲所规定的要求。

二、考试要求及内容

第1章绪论

1、掌握数据、数据元素、数据项、数据结构等基本概念。

2、掌握数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。

3、掌握数据结构的两大类逻辑结构和四种常用的存储表示方法。

4、理解算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。

5、掌握算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。

第2章线性表

1、理解线性表的逻辑结构特征。

2、理解线性表上定义的基本运算，并能利用基本运算构造出较复杂的运算。

线性表的顺序存储结构，要求达到“综合利用”层次。　

3、理解顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系。

4、掌握顺序表上的插入、删除操作及其平均时间性能分析。　

5、理解利用顺序表设计算法解决简单的应用问题。　　

6、掌握链表如何表示线性表中元素之间的逻辑关系。　　

7、掌握链表中头指针和头结点的使用。　

8、理解单链表、双链表、循环链表链接方式上的区别。　

9、掌握单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。

10、理解循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。

11、理解双链表的定义及其相关的算法。　　

12、掌握利用链表设计算法解决简单的应用问题。　

13、理解顺序表和链表的主要优缺点。

14、掌握针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能。

第3章栈和队列

1、理解栈的逻辑结构特点，栈与线性表的异同。

2、掌握顺序栈和链栈上实现的进栈、退栈等基本算法。

3、理解栈的“上溢”和“下溢”的概念及其判别条件。

4、掌握利用栈设计算法解决简单的应用问题。

5、理解队列的逻辑结构特点，队列与线性表的异同。

6、掌握顺序队列（主要是循环队列）和链队列上实现的入队、出队等基本算法。

7、理解队列的“上溢”和“下溢”的概念及其判别条件。

8、了解使用数组实现的循环队列取代普通的顺序队列的原因。

9、掌握循环队列中对边界条件的处理方法。

10、掌握利用队列设计算法解决简单