《数据结构》课程考试大纲

红太狼 2023-02-20 08:15 15阅读 0赞

### 《数据结构》课程考试大纲 ###

*   *  一、考试科目概述
     *  二、考试内容
     *  三、考试方式与试卷结构
     *  四、参考书目

## 一、考试科目概述 ##

数据结构是计算机程序设计的重要理论技术基础，《数据结构》课程是一门专业基础课。要求考生比较系统地理解数据结构的基本概念和基本知识，**掌握表、栈、队列、树和图等数据结构的基本特征和在计算机上实现的方法**，要求考生具有一定的抽象思维能力、逻辑推理能力、综合运用所学的知识分析问题和解决问题的能力。

## 二、考试内容 ##

<table> 
 <thead> 
 <tr> 
 <th>第 x 章 (名称)</th> 
 <th align="left">专题(名称)</th> 
 <th align="left">知识与技能考核点</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>第一章 绪论</td> 
 <td align="left">数据结构基本概念和术语, 算法、算法的描述和算法分析。</td> 
 <td align="left">(1) 了解非数值问题的数学模型是表、树和图之类的数据结构 (2) 理解数据、数据元素、数据对象、数据结构和数据类型的定义 (3) 掌握数据的逻辑结构和存储结构及其种类；算法的重要特征等 (4) 会根据语句的最大频度计算算法的时间复杂度</td> 
 </tr> 
 <tr> 
 <td>第二章 线性表</td> 
 <td align="left">线性表的定义、线性表的逻辑结构、 线性表的顺序存储结构和链式存储结构， 单向链表、循环链表和双向链表， 一元多项式的表示及相加</td> 
 <td align="left">(1) 了解线性表的定义和线性结构的特点。 (2) 理解线性表的顺序存储和链式存储，理解数组与单链表表示表的优缺点。 (3) 掌握顺序表中数据元素的 存储位置的计算，顺序表、单向链表、循环链表和双向链表的 查找、插入、删除 等有关操作。 (4) 会用单链表编写简单操作算法。 (5) 能够从 时间 和 空间复杂度 的角度综合比较两种存储结构的 特点及适用场合。</td> 
 </tr> 
 <tr> 
 <td>第三章 栈和队列</td> 
 <td align="left">栈的定义、栈的表示和实现； 队列的定义、队列的表示和实现，链队列、循环队列。</td> 
 <td align="left">(1) 了解栈和队列的定义 (2) 理解线性表、栈和队列特点及区别，栈对实现递归过程的作用 (3) 掌握顺序栈、链栈的入栈和出栈操作，顺序队列、链队列的入队和出队操作，栈和队列的空和满的判断。</td> 
 </tr> 
 <tr> 
 <td>第四章 树和二叉树</td> 
 <td align="left">树的结构定义和基本操作、二叉树的定义、 二叉树的性质、二叉树的存储结构、遍历二叉树，树和森林、树的存储结构、森林与二叉树的转换、树的遍历，最优二叉树和哈夫曼编码。</td> 
 <td align="left">(1) 了解树的定义和二叉树的定义 (2) 理解二叉树的性质、二叉树的存储结构 (3) 掌握遍历二叉树的方法、森林与二叉树的转换、最优二叉树的构造和哈夫曼编码 (4) 会利用 二叉树的先根、中根和后根遍历 解决有关二叉树的应用问题，会采用二叉链表存储结构编写与二叉树简单递归的算法</td> 
 </tr> 
 <tr> 
 <td>第五章 图</td> 
 <td align="left">图的定义和术语、图的存储结构：邻接矩阵和邻接表， 图的遍历：深度优先搜索和广度优先搜索，无向网的最小生成树，有向网的最短路径。</td> 
 <td align="left">(1) 了解图的定义和术语，生成树和最小生成树、最短路径的概念 (2) 理解邻接矩阵中元素的含义和邻接表中结点的含义 (3) 掌握 深度优先搜索 和 广度优先搜索 算法思想 (4) 会用 Prim算法 和 Kruskal算法 手工构造 无向网的最小生成树，会找出 有向网任意顶点间的最短路径。</td> 
 </tr> 
 <tr> 
 <td>第六章 查找</td> 
 <td align="left">静态查找表：顺序查找、二分查找 和分块查找； 动态查找表：二叉排序树；哈希查找、哈希函数的构造方法和处理冲突的方法</td> 
 <td align="left">(1) 了解顺序查找、二分查找 和分块查找的概念，以及二叉排序树、哈希查找等概念。 (2) 掌握二叉排序树的查找、插入和删除操作算法思想。 (3) 掌握 哈希函数的构造方法和处理冲突的方法，会用哈希函数、加上 开放地址法或拉链法建立哈希表。</td> 
 </tr> 
 <tr> 
 <td>第七章 内部排序</td> 
 <td align="left">直接插入排序、希尔排序、快速排序、简单选择排序、堆排序、归并排序和基数排序。各种内部排序方法的比较。</td> 
 <td align="left">(1) 了解 排序算法的稳定性问题 (2) 理解直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序和基数排序的基本思想。 (3) 会写出排序执行过程，能够对各种排序算法进行分析比较。</td> 
 </tr> 
 </tbody> 
</table>

## 三、考试方式与试卷结构 ##

1.考试方式：闭卷，笔试

2.试卷分数：满分150分

3.考试时间：120分钟

4.题型比例：

**(1) 填空题：30%；**

**(2) 选择题：30%；**

**(3) 判断题：10%；**

**(4) 应用题：20%；**

**(5) 算法题：10%。可以是算法阅读、算法填空、算法改错和算法编写等多种形式。**

5.命题的指导思想和原则：

全面考查学生对本课程的基本原理、基本概念和主要知识点学习、理解和掌握的情况。**命题原则：题目数量多、份量小**，范围较全面，最基本的知识一般要占60%左右，一般难度试题的题目要占25%左右，较难的题目要占15%左右。总体客观性的题目占70%左右。适当压缩大题目在总的考分中所占的比例。