陇东学院专升本计算机科学与技术专业考试大纲历年真题录取分数线

《数据结构》

一、考试目的

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

二、考试要求及内容

第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、掌握利用队列设计算法解决简单