科目代码、名称:

885 数据结构（C语言版）

专业类别：

■学术型 □专业学位

适用专业:

教育技术学

一、基本内容

1、数据结构基础

数据结构基本概念及相关术语、抽象数据类型的表示与实现、算法和算法分析；

2、线性表

线性表的类型定义、线性表的顺序和链式表示和实现、线性链表、循环链表、双向链表；

3、 栈和队列

栈与栈的应用、队列、串类型的定义、串的表示和实现、串操作应用；

4、 数组和广义表

数组的定义、数组的顺序表示和实现、矩阵的压缩存储、广义表的定义、广义表的存储结构；

5、 树和叉树

树的定义和基本术语、二叉树、遍历二叉树和线索二叉树、树和森林、赫夫曼树及其应用；

6、 图

图的定义和术语、图的存储结构、图的遍历、图的连通性问题（无向图的连通分量和生成树、最小生成树）、有向无环图及其应用、最短路径；

7、 查找

静态表的查找、动态查找表、哈希表；

8、 内部排序

插入排序、快速排序、选择排序、归并排序、基数排序、各种内部排序方法的比较；

9、 外部排序

外存信息的存取、外部排序方法的应用；

10、文件

有关文件的基本概念、顺序文件、索引文件、直接存取文件、多关键字文件；

※ 要求数据结构算法设计题编程全部采用C语言。

二、考试要求（包括考试时间、总分、考试方式、题型、分数比例等）

考试时间3小时，总分150分，考试方式为闭卷考试，试卷题型及分数比例为:

简答题：100分;

算法设计题：50分;

三、主要参考书目

1.《数据结构》(C语言版)，严蔚敏、吴伟民，清华大学出版社，2011；

2.《数据结构题集》(C语言版)， 严蔚敏、吴伟民，清华大学出版社，2007；

3.《C程序设计》（第四版），谭浩强，清华大学出版社，2012；