贵州师范大学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年版
更多学历考试信息请查看学历考试网