2013年贵州师范大学硕士研究生入学考试050程序设计与数据结构大纲(复试)
2013-01-12来源:贵州师范大学网

贵州师范大学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年版

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

推荐信息
Baidu
map