考研复习专业课#2021年西安石油大学数据结构与程序设计考研大纲

考研复习>>专业课>>正文2021年西安石油大学数据结构与程序设计考研大纲

更新时间：2020/11/313:21:06

西安石油大学2021年硕士研究生招生考试

（808）数据结构与程序设计考试大纲

一 、考察目标

“数据结构与程序设计”入学考试是为招收计算机科学与技术类硕士生而实施的选拔性考试，主要涉及数据结构、C/C++程序设计课程的内容 。主要包括三大常用数据结构的逻辑
、物理表示与基本操作算法实现部分的知识 ，各种结构的经典应用和问题求解。考生应掌握各种数据结构及其操作，具备一定的算法设计与分析能力
，能够根据实际问题选择合适的数据结构并设计算法实现
。要求考生具有较全面的数据结构表示与实现的基础知识；具有较高的分析问题和解决问题的能力；具有较强的综合知识运用能力。

二、考试主要内容

1．绪论

1.1数据结构的基本概念；

1.2抽象数据类型；

1.3算法和算法的时间复杂度 。

2.线性表

2.1线性表概述；

2.2线性表的顺序表示和实现；

2.3线性表的链式表示和实现；

2.4静态链表；

2.5线性表的基本运算
。

3.堆栈和队列

3.1堆栈；

3.2堆栈应用；

3.3队列；

3.4优先级队列。

4.串

4.1串概述；

4.2串的存储结构；

4.3串基本操作的实现算法；

4.4串的模式匹配算法-BF和KMP算法 。

5.数组

5.1数组概述；

5.2动态数组；

5.3特殊矩阵的压缩存储；

5.4稀疏矩阵的压缩存储
。

6.递归算法

6.1递归的概念；

6.2递归算法的执行过程；

6.3递归算法的设计方法；

6.4递归过程和运行时栈；

6.5递归算法的时间效率分析。

7.树和二叉树

7.1树；

7.2二叉树；

7.3二叉树的设计和实现；

7.4二叉树遍历；

7.5线索二叉树；

7.6哈夫曼树；

7.7等价问题；

7.8树与二叉树的转换；

7.9树的遍历 。

8.图

8.1图概述；

8.2图的存储结构；

8.3图的实现；

8.4图的遍历；

8.5最小生成树；

8.6最短路径；

8.7拓扑排序；

8.8关键路径
。

9.排序

9.1排序的基本概念；

9.2插入排序；

9.3选择排序；

9.4交换排序；

9.5归并排序；

9.6基数排序；

9.7排序算法性能比较。

10.查找

10.1查找的基本概念；

10.2静态查找；

10.3动态查找；

10.4哈希查找；

三 、考试形式及试卷结构

考试形式为闭卷笔试 。考试时间为3小时
。

试卷结构：

单项选择题（20%）

填空题（13%）

简答题（20%）

算法理解与设计题（47%）