贵州师范大学2013年硕士研究生入学考试大纲 （复 试）

(科目：050程序设计与数据结构)

程序设计

【考查目标】

1、掌握结构化程序设计的基本方法，了解面向对象程序设计的基本思路，对两种方法编写的程序有读、改、写的能力，能实现计算机常用算法的编制。

2、对计算机语言有较好的了解，能识别程序语言中的语法错误，能用像C++等语言编程。

一、语言基本知识

1、像程序设计语言C/C++的发展，程序设计语言词、句子的组成，数据类型与表达式等概念

2、程序设计的上机过程，运行调试中常见错误的鉴别

3、了解常用的程序风格和规范

二、面向过程程序设计方法

1、程序的基本组成，算法的概念和表示

2、顺序结构、选择结构和循环结构语句的语法规定，及运用三种结构编写程序

3、掌握函数组装程序的意义，对库函数、自定义函数、局部变量和全程变量有正确的知识，并能用函数进行程序设计，了解递归函数

4、对批量数据的处理，能正确运用数组或结构体进行程序设计，能熟练处理字符数据

5、了解指针、文件和异常处理

三、面向对象程序设计方法

1、面向对象程序设计的基本思想，能看懂面向过程程序设计和面向对象程序设计方法的程序，面向对象程序设计方法的特点

2、了解类与对象、封装、重载、继承的概念

数据结构

一、考试科目：

数据结构

二、适用专业：

计算机应用技术

三、考试性质：

《数据结构》是计算机各专业的核心基础课程。在研究生复试时通过对该课程的考核，以检验考生在本科阶段对该课程的掌握情况，确保被录取者具有基本的专业理论基础及程序设计能力，能顺利完成研究生阶段的学业。

四、考试的基本要求：

系统地理解数据结构的基本概念和基本理论，具备综合应用相关知识分析问题和解决问题的能力。具体要求如下：

1．各种基本类型的数据结构的概念、特征、操作、存储表示和基本应用；

2．各种基本查找表的概念、特征及其查找方法

3．基本的排序方法；

4．基本算法性能的分析与评价；

5．使用C（或C++）语言的风格描述算法和进行程序设计。

五、考试内容与具体要求：

1．算法与数据结构

了解数据结构、抽象数据类型的基本概念，熟悉掌握数据的逻辑结构与存储结构，掌握算法定义、算法的基本特性、算法分析的基本概念和方法。

2．线性表

线性表的定义、逻辑结构、存储结构、基本操作、基本算法性能的分析。

3．栈

栈的定义、特性、存储结构、基本操作、基本算法性能的分析，栈与递归算法及其基本应用。

4．队列

队列的定义、特性、存储结构、基本操作、基本算法性能的分析以及基本应用。

5．串

串的定义、基本概念、存储结构与基本操作；串的模式匹配算法；

6．数组与广义表

(1)数组的定义、存储结构与基本操作；特殊矩阵和稀疏矩阵的压缩存储；

(2)广义表的基本性质，求广义表的长度、表头与表尾。

7．树和二叉树

(1)树的基本概念和基本操作；

(2)二叉树的基本概念、性质及存储结构；二叉树的先序、中序及后序遍历的算法；

(3)树与二叉树之间的转换、森林与二叉树之间的转换；

(4) 哈夫曼树(Huffman)的概念，哈夫曼编码的构造及带权路径长度的计算。

8．图

(1)图的基本概念和基本操作；

(2)图的存储结构：邻接矩阵、邻接表与逆邻接表表示法；

(3)图深度优先搜索遍历与广度优先搜索遍历；

(4)生成树、最小生成树的概念；克鲁斯卡尔(Kruskal)算法,普里姆(Prim)算法。

9．查找

(1)查找的概念，关键字比较次数与平均查找长度；

(2)顺序查找、折半查找、分块查找、索引顺序表的查找算法；

(3)二叉排序树与平衡二叉树，B-树与B+树；

(4)哈希(Hash)表的概念，哈希函数的基本构造方法与解决冲突的基本方法，哈希表的建立和查找。

(5)各种查找算法的性能分析及其应用。

10．内部排序

(1)排序的概念及其排序的稳定性；关键字比较次数与记录移动次数；

(2)交换类排序：冒泡排序与快速排序；

(3)插入类排序：直接插入排序、折半插入排序、2-路插入排序、希尔排序。

(4)选择类排序:直接选择排序、锦标赛排序、堆排序。

(5归并排序。

(6)基数排序。

(7)种排序算法的评价（稳定性、时间复杂度、空间复杂性度）及其应用。

六、考试形式与试卷结构：

1．考试方式：闭卷，笔试。

2．考试时间：60分钟；

3．考查内容及分值比例：

(1) 基本概念、基本知识、基本方法约占50%；

(2) 综合应用、算法和程序设计与算法分析约占50%。

4．试卷题型结构：

试卷共计50分，基本题型如下：

(1)单项选择题：10分，占20%；

(2)填空题（含程序填空题）：10分，占20%

(3)综合应用题（包括简答题、解答题、分析算法与程序的功能）：20分，占40%；

(4)算法与程序设计：10分，占20%

七、参考书：

严蔚敏，吴伟民．《数据结构》(C语言版) ．清华大学出版社．1997年版

更多学历考试信息请查看学历考试网