资源描述
1 中国科学院大学 硕士研究生入学考试 程序设计 考试大纲 本 程序设计 考试大纲适用于 中国科学院大学 计算机科学与技术 类 的硕士研究生入 学考试。 程序设计 是计算 机科学与技术及相关学科的重要基础，主要内容包括数据结构 和 C 程序设计 两 大部分。要求考生对计算机科学与技术及相关学科的基本概念有较深入、系统的 理解，掌握各种数据结构的定义和实现算法， 对 C 语言的基本知识有较深入的了解，掌握 程序设计的基本方法，并具有综合运用所学知识分析问题和解决问题的能力。 一、考试内容 数据结构 1、绪论 （ 1）数据结构的基本概念，数据的 逻辑结构、存储结构。 （ 2）算法的定义、算法的基本特性以及算法分析的基本概念。 2、线性表 （ 1）线性关系、线性表的定义，线性表的基本操作。 （ 2）线性表的顺序存储结构与链式存储结构 (包括单链表、循环链表和双向链表 )的构造原 理。在以上两种存储结构上对线性表实施的最主要的操作 (包括三种链表的建立、插入和删 除、检索等 )的算法设计。 3、堆栈与队列 （ 1）堆栈与队列的基本概念、基本操作。 （ 2）堆栈与队列的顺序存储结构与链式存储结构的构造原理。 （ 3）在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作对应 的算法设计。 4、串 （ 1）串的基本概念、串的基本操作和存储结构。 （ 2）串的模式匹配算法和改进的 KMP 算法 5、数组和广义表 （ 1）数组的概念、多维数组的实现 （ 2）对称矩阵和稀疏矩阵的压缩存储 （ 3）广义表的基本概念 6、树与二叉树 （ 1）树的定义和性质 （ 2）二叉树的概念、性质和实现 （ 3）遍历二叉树和线索二叉树 （ 4）树和森林 （ 5）赫夫曼树及其应用 （ 6）树的计数 2 7、图 （ 1）图的定义，基本概念，图的分类，常用名词术语。 （ 2）图的邻接矩阵存储方法、邻接表存储方法的构造原理。 （ 3）图的遍历操作 。 （ 4）最小生成树，最短路径， AOV 网与拓扑排序。 8、文件及查找 （ 1）数据文件的基本概念和基本术语，数据文件的基本操作。 （ 2）顺序文件、索引文件、散列 (Hash)文件。 （ 3）顺序文件的顺序查找方法、排序连续顺序文件的折半查找方法以及其他文件的基本查 找方法。 9、内排序 （ 1）排序的基本概念，排序方法的分类。 （ 2）插入排序法 (含折半插入排序法 )、选择排序法、泡排序法、快速排序法、堆积排序法、 归并排序、基数排序。各种排序方法排序的原理、规律和特点，各种排序算法的时空复杂度 简单分析。 程序设计 1、 基本知识 （ 1） C 语言 的数据类型 （ 2） C 语言 中各种类型常量的表示法 （ 3） 各类数值 型 数据间的混合运算 （ 4） C 运算符 （ 5） 关系表达式及运算，逻辑表达式及运算 2、 顺序、选择与循环结构程序设计 （ 1） 赋值语句，格式输入与输出 （ 2） if 语句， switch 语句 （ 3） goto、 while、 do-while、 for、 break、 continue 语句 3、 数组 （ 1） 一维数组的定义和引用 （ 2） 二维数组的定义和引用 （ 3） 字符数组的定义和引用 4、 函数 （ 1） 函数定义与调用 （ 2） 局部变量和全局变量 （ 3） 变量 的存储类型 （ 4） 内部函数与外部函数 5、 指针 （ 1） 地址和指针的概念 （ 2） 数组的指针和指向数组的指针变量 （ 3） 字符串的指针和指向字符串的指针变量 （ 4） 函数的指针和指向函数的指针变量 （ 5） 指针数组和指向指针的数组 3 6、 结构体和共同体 （ 1） 结构体变量的定义和使用方法 （ 2） 指向结构体类型变量的指针 （ 3） 用指针处理链表 （ 4） 共同体变量的定义和使用方法 （ 5） 枚举类型 7、 位运算 （ 1） 位运算符和位运算 （ 2） 位段 8、 文件 （ 1） 文件类型指针 （ 2） 文件操作，包括打开、关闭、读写和定位等。 二、考试要求 数据结构 1、 掌握有关数据结构的基本概念，包括数据的逻辑结构、存储结构 。 2、 掌握 算法 的基本概念以及算法分析的 基本方法。 3、 掌握线性表的基本概念 ，在 两种存储结构 下 的构造原理 及相应的操作； 4、 掌握堆栈和队列的基本概念与特征 以及 在两种存储结构下如何对堆栈和队列进行插 入和删除等操作， 具备使用 堆栈与队列 解决实际问题的能力。 5、 掌握串的基本概念 以及 串的存储结构和相关的 算法 。 6、 掌握数组、广义表和稀疏矩阵的基本概念 以及 基本操作 。 7、 掌握树型结构的逻辑特征以及 各种存储结构的构造原理，能够 熟练 使用 基于树的 三 种遍历方法 。 8、 掌握二叉排序树的 逻辑特征、建立过程，具备使用其解决实际问题的能力。 8、 了解 图的逻辑结构的特点 以及 常用的两种存储方法， 了解 最小生成树 (Prim 算法和 Kruskal 算法 )、最短路径、拓扑排序的求解过程。 9、 掌握各种顺序文件的结构与相应的查找方法 以及 各种查找算法之间时空效率的差 异； 了解 散列文件的建立、散列函数的选择 (构造 )原则、处理散列冲突的方法以及 了解散列文件的建立、散列函数的选择 (构造 )原则、处理散列冲突的方法以及基于 散列的查找 。 10、 掌握各种排序方法的排序特点和排序过程，能够对每一种排序方法 在 时间、空间、 排序 的稳定性等 方面 进行简单分析。 程序设计 1、 掌握 C 语言的基本 数据类型 、 各种 运算符和表达式 。 2、 掌握 C 语言的基本控制结构 。 4 3、 掌握数组的定义、 数组 元素的引用、 数组的初始化， 掌握 与 字符串 相关的库函数。 4、 掌握 函数的 定义 语法 ， 掌握 函数调用中参数 的 传递 机制 ； 掌握局部 变量和全局变量 的有效范围， 掌握 auto、 static、 register、 extern 变量的概念 及特性 。 5、 掌握 结构体类型变量的 定义 、 结构体变量 的引用、 结构体变量 的 初始化 方法 ，掌握 结构体数组的定义、初始化和结构体数组的应用 ， 掌握共同体变量的定义和使用方 法 ， 掌握 枚 举类型的一般概念、 定义格式及使用方法。 6、 掌握 地址和指针的 基本 概念 ， 重点 掌握如何使用指针来处理数组、 字符串 以及结构 体， 掌握 函数 指针的基本概念以及使用； 7、 了解 位运算符的使用方法，能利用它们处理具体问题； 了解位段 的概念及 使用 规则 。 8、 掌握 FILE 的定义 以及 对文件进行 的各种 操作 的库函数 。 三、主要参考书目 1、 数据结构（ C 语言版），严蔚敏 、 吴伟民 ， 清华大学出版社 ， 2012 年 ； 2、 C 程序设计 （ 第三版 ） ， 谭浩强 ， 清华大学出版社 ， 2005 年 。 编制单位： 中国科学院大学 编制日期： 2021 年 6 月 18 日
展开阅读全文