贵州大学硕士研究生入学考试大纲考试科目代码/名称：831/程序设计与数据结构 一、考试基本要求本科目考试着重考核考生掌握程序设计与数据结构基本概念、基本思想、基本分析方法和基本理论的程度，要求考生对程序设计与数据结构理论体系的基本框架有一个比较全面的了解，并能综合运用所学的程序设计和数据结构的基本知识分析现实问题，并进行问题抽象、算法提炼和编程实现。2、适用范围适用于计算机科学与技术专业（学术型研究生）适用于计算机技术、软件工程专业（专业型研究生）三、考试形式闭卷，180 分钟四、考试内容和考试要求（一）程序设计部分（占考试内容的 50%）1程序设计基本知识考试内容：C 语言的基本知识、C 语言的符号体系、简单程序的设计；考试要求：（1）理解 C 语言程序的基本构成，变量的定义与变量名的基本规则；（2）领会类型修饰的使用和功能，整型与字符型数据的混合运算；（3）掌握算术表达式、赋值表达式与逗号表达式；数据的输入与输出、以及输入与输出的基本要求。2. 选择结构程序设计考试内容：条件选择语句 if 和 switch 的语法及其应用；考试要求：（1）领会 if 语句与条件表达式的区别、switch 语句的执行流程。（2）掌握 if 语句与 switch 语句在程序中的使用。3. 循环结构程序设计考试内容：for、while、do-while 三种循环控制语句的语法特点和应用；考试要求：（1）理解 for、while、do-while 语句的执行流程及其循环条件表达式的作用和以及区别；（2）掌握 break 与 continue 语句的区别与应用；（3）能熟练地用三种循环语句进行循环程序设计。4.函数考试内容：C 或 C+中函数的定义和使用；考试要求：（1）理解全局变量与局部变量、变量的生存期与作用域、变量的动态与静态存储方式等的区别；（2）了解在多个程序文件中函数与函数的关系；（3）熟练掌握在程序设计中正确使用函数；对于已知的递归算法，能写出相应的递归程序。5.数组考试内容：一维和二维数组的定义及其应用；考试要求：（1）理解一维数组与二维数组的地址结构、字符串的结束标志；（2）掌握常用的几个字符串函数；（3）掌握在程序设计中应用一维数组、二维数组、字符串；（4）掌握对数组进行简单排序和查找的方法；（5）掌握数组做函数参数的程序设计。6.指针考试内容：C 或 C+中指针的概念、定义、运算和应用；考试要求：（1）理解一维数组与二维数组的地址结构；（2）理解返回指针的函数与函数指针的区别；（3）理解指针数组、数组指针、指向指针的指针之间的关系与区别；（4）理解指针运算的用途和意义；（5）掌握在程序中利用指针操作数组元素、字符串，以及用指针作函数参数；掌握在程序中应用指针数组。7.结构体、共用体和枚举类型考试内容：结构体、共用体、枚举等自定义数据类型的定义和运用；考试要求：（1）理解结构体与共用体的区别；（2）掌握结构体、共用体、枚举类型数据的应用，会用 typedef 定义结构体、共用体等数据类型别名。8.文件考试内容：文件的打开和读取；考试要求：（1）理解文件指针的概念和定义；（2）掌握文件的打开方法、文件打开函数返回值的处理；（3）掌握在程序中读写外部的文本文件或者二进制文件的方法。（二）数据结构部分（占考试内容的 50%）1.基本概念考试内容：数据结构的基本概念；渐进算法分析方法。考试要求：（1）掌握数据结构的概念，包括数据的逻辑结构、存储结构、算法的概念，以及它们之间的关系。（2）掌握渐进算法分析方法，能够估算算法的时空复杂度2.线性表和字符串考试内容：线性表的特点，线性表的顺序实现和链式实现，线性表的应用；字符串的基本运算，字符串匹配算法。考试要求：（1）理解线性表的结构和特点，掌握线性表上基本操作的实现算法。（2）掌握顺序存储线性表的方法以及基本操作的实现算法。（3）掌握链接存储线性表的方法，并掌握单链表和循环链表的结构，以及基本操作的实现算法。（4）理解字符串的存储结构，字符串的基本运算。（5）掌握字符串简单的匹配算法。3.栈和队列考试内容：栈和队列的基本运算及其应用。 考试要求：（1）理解栈的定义和结构特点，掌握其存储方式（顺序存储和链接存储）和基本操作的实现算法。（2）理解队列的结构和特点，掌握其存储方式（顺序存储和链接存储）和基本操作的实现算法。4.递归考试内容：递归的基本概念，递归的简单应用。 考试要求：（1）理解递归的基本概念和实现原理，掌握用递归思想描述问题和构造算法的方法。（2）掌握求阶乘、汉诺塔等问题的递归解法。（3）了解用栈将递归改为非递归的方法。5.树和二叉树考试内容：树和二叉树考试要求：（1）理解树的结构和定义，掌握树的主要概念。（2）理解各种二叉树的结构，掌握其特点。（3）掌握二叉树的三种遍历方法的实现原理和性质，能将二叉树的遍历方法应用于求解二叉树的叶子结点个数。二叉树计数等问题，掌握遍历的非递归实现方法。（4）理解树的存储结构，掌握树的遍历等方法的实现。（5）理解霍夫曼编码的基本原理和使用。6.集合和搜索考试内容：集合、二叉搜索树和 AVL 树考试要求：（1）理解集合的基本概念，掌握常用实现集合的各种存储方法。（2）掌握无序线性表的顺序搜索、有序线性表的二分搜索。（3）理解二叉搜索树的定义和特点，掌握二叉搜索树插入和删除的算法。（4）理解 AVL 树的定义和特点，掌握 AVL 树上插入新结点的方法。7.图考试内容：图的存储，图的遍历，最小生成树，最短路径和活动网络。 考试要求：（1）掌握图的基本概念、图的邻接矩阵存储方式和邻接表存储方式。（2）掌握图的深度优先遍历和广度优先遍历方法。（3）掌握 Kluskal 和 Prim 生成最小生成树的方法。（4）掌握 Dijkstra 求单源最短路径的方法。（5）掌握 AOV 活动网络的拓扑排序方法，AOE 活动网络的关键路径的方法。8.排序考试内容：插入排序、交换排序、选择排序、归并排序和基数排序。考试要求：理解各种排序方法的实现，掌握各种排序算法的特点和时间复杂度，能按指定的排序方法实现对数表做排序。9.索引结构与散列考试内容：线性索引结构、B+树和 B-树索引结构、散列。 考试要求：（1）理解线性索引结构的特点。（2）理解 B+树和 B-树索引的结构，掌握 B+树和 B-树插入和删除方法。（3）理解散列的实现原理，能按指定的散列函数和解决冲突的方法构造散列表。