云南大学考研计算机专业复试各科大纲.doc

1. 计算机基本工作原理硬件系统构成，硬件基本工作原理，进制转换，数值编码，软件系统构成，系统软件构成，操作系统功能，计算机语言的划分。2. 顺序、选择、循环结构输入输出格式，各类基本算法问题，比如：闰年、素数、数字位数、简单方程求解的二分法和牛顿法、基本排序算法等。3. 函数库函数的使用，自定义函数的声明、定义、调用，值传递与地址传递，递归函数等。4. 数组一维数组、二维数组、多维数组的定义、初始化、访问，数组的动态产生，函数传递数组等。5. 字符串字符串的长度、大小写转换、拼接、插入、删除等基本操作。6. 矩阵矩阵的基本操作，包括初始化、生成单位阵、转置、各种镜像翻转、逆矩阵、行列式等。第一章 c语言概述 一、c语言出现的历史背景 二、c语言的特点 三、c程序介绍第二章 数据结构和算法 一、数据结构和算法的概念和术语 二、抽象数据类型的表示与实现 三、算法的特性和表示 四、程序设计方法和算法分析第三章 数据类型、运算符与表达式 一、c的数据类型 二、常量与变量 三、整型数据 四、实型数据 五、字符型数据 六、变量赋初值 七、各类数值型数据间的混合运算 八、算术运算符和算术表达式 九、赋值运算符和赋值表达式 十、逗号运算符和逗号表达式第四章 顺序程序设计 一、c语句概述 二、赋值语句 三、数据输入输出的概念及在c语言中的实现四、字符数据的输入输出五、格式输入与输出第五章 选择结构程序设计 一、关系运算符和关系表达式 二、逻辑运算符和逻辑表达式 三、if语句 四、switch语句第六章循环控制 一、goto语句以及用goto语句构成循环 二、while语句 三、do-while语句 四、for语句 五、循环的嵌套 六、几种循环的比较 七、break语句和continue语句第七章 数组 一、一维数组和二组数据的定义和引用 二、字符数组、串的类型定义、表示和实现 三、串的模式匹配算法四、数组的顺序表示和实现 五、矩阵的压缩存储 六、广义表的定义 七、广义表的存储结构 八、m元多项式的表示 九、广义表的递归算法第八章 函数 一、函数定义的一般形式 二、函数参数和函数的值 三、函数的调用 四、函数的嵌套调用 五、函数的递归调用 六、数组作为函数参数 七、局部变量和全局变量八、变量的存储类别九、内部函数和外部函数十、如何运行一个多文件的程序第九章 预处理命令 一、宏定义 二、“文件包含”处理 三、条件编译第十章 指针 一、地址和指针的概念 二、变量的指针和指向变量的指针变量 三、数组的指针和指向数组的指针变量 四、字符串的指针和指向字符串的指针变量 五、函数的指针和指向函数的指针变量 六、返回指针值的函数 七、指针数组和指向指针的指针第十一章 结构体与共用体 一、定义结构体类型变量的方法 二、结构体变量的引用 三、结构体变量的初始化四、结构体数组五、指向结构体类型数据的指针 六、用指针处理链表 七、共用体 八、枚举类型 九、用typedef定义类型第十二章 位运算 一、位运算符和位运算 二、位段第十三章 文件和程序调试 一、c文件概述 二、文件类型指针 三、文件的打开与关闭 四、文件的读写 五、文件的定位六、出错的检测、七、程序调试第十四章 c+对c的扩充 一、c+的特点 二、最简单的c+程序 三、c+的输入输出 四、函数的重载 五、带缺省参数的函数 六、变量的引用类型 七、内置函数 八、作用域运算符 九、动态分配撤销内存的运算符new和delete第十五章 c+的面向对象基础 一、类和对象 二、构造函数和折构函数 三、继承与派生第十六章 线性表和栈和队列 一、线性表的类型定义 二、线性表的顺序和链式表示和实现 三、一元多项式的表示及相加 四、栈的表示和实现 五、栈与递归的实现 六、队列和离散事件模拟第十七章 树和二叉树 一、树的定义和基本术语 二、二叉树、遍历二叉树和线索二叉树 三、树和森林、树与等价问题 四、赫夫曼树及其应用 五、回溯法与树的遍历、树的计数第十八章 图 一、图的定义和术语 二、图的存储结构、图的遍历 三、图的连通性问题、有向无环图及其应用、最短路径第十九章 查找和内部排序 一、静态查找表、动态查找表 二、哈希表三、插入排序 四、快速排序 五、选择排序 六、归并排序 七、基数排序842-数据结构与程序设计考试大纲第一章 绪论 一、什么是数据结构 二、基本概念和术语 三、抽象数据类型的表示与实现 四、算法和算法分析第二章 线性表 一、线性表的类型定义 二、线性表的顺序表示和实现 三、线性表的链式表示和实现四、一元多项式的表示及相加第三章 栈和队列 一、栈二、抽象数据类型栈的定义三、栈的表示和实现 四、栈的应用举例五、栈与递归的实现 六、队列七、离散事件模拟第四章 串 一、串类型的定义 二、串的表示和实现三、串的模式匹配算法四、串操作应用举例第五章 数组和广义表 一、数组的定义 二、数组的顺序表示和实现 三、矩阵的压缩存储 四、广义表的定义 五、广义表的存储结构 六、m元多项式的表示 七、广义表的递归算法第六章 树和二叉树 一、树的定义和基本术语二、二叉树三、遍历二叉树和线索二叉树四、树和森林五、树与等价问题 六、赫夫曼树及其应用七、回溯法与树的遍历 八、树的计数第七章 图 一、图的定义和术语 二、图的存储结构 三、图的遍历 四、图的连通性问题 五、有向无环图及其应用 六、最短路径第八章 动态存储管理 一、可利用空间表及分配方法 二、边界标识法 三、伙伴系统 四、无用单元收集 五、存储紧缩第九章 查找 一、静态查找表 二、动态查找表 三、哈希表第十章 内部排序 一、插入排序 二、快速排序 三、选择排序 四、归并排序 五、基数排序第十一章 外部排序 一、外存信息的存取 二、外部排序的方法 三、多路平衡归并的实现 四、置换选择排序 五、最佳归并树第十二章 文件 一、有关文件的基本概念 二、顺序文件 三、索引文件 四、isam文件和vsam文件 五、直接存取文件(散列文件) 六、多关键字文件第十三章 数据类型、运算符与表达式 一、c的数据类型 二、常量与变量 三、整型数据 四、实型数据 五、字符型数据 六、变量赋初值 七、各类数值型数据间的混合运算 八、算术运算符和算术表达式 九、赋值运算符和赋值表达式 十、逗号运算符和逗号表达式第十四章 指针 一、地址和指针的概念 二、变量的指针和指向变量的指针变量 三、数组的指针和指向数组的指针变量 四、字符串的指针和指向字符串的指针变量 五、函数的指针和指向函数的指针变量 六、返回指针值的函数 七、指针数组和指向指针的指针（一）数据结构1.数据结构基本概念数据、数据元素、数据项、算法。2.基本数据结构及算法线性表结构，不同结构线性表的建立、查找、插入和删除等基本算法及其时间复杂度。栈和队列的结构及应用。3.树和二叉树树的定义和术语，二叉树(完全二叉树、满二叉树)的定义和性质(结论)、二叉树的存储结构顺序表示法和链表表示法；二叉树的三种遍历方法及相应的递归算法。树的路径长度、树的带权路径长度、赫夫曼树（最优二叉树）的构造方法；赫夫曼编码方法。4.查找关键字、查找平均查找长度；静态查找表的查找算法（顺序查找、折半查找）及其效率(最坏和平均长度)。排序二叉树的定义、排序二叉树的基本操作、排序二叉树的查找算法及其效率。哈希法的特点、哈希函数和散列地址；构造哈希函数的几种方法：直接定址法、除留余数法、平方取中法、折叠法、数字分析法；处理冲突的方法：开放定址法和链地址法。5.内部排序排序的目的、分类和排序方法的稳定性的定义。简单的排序算法：直接插入排序算法、冒泡排序算法、简单选择排序、快速排序算法的思想。（二）数据库技术基础1.数据库基本概念数据库、数据库管理系统、数据库系统、数据模型、关系数据库；数据管理的发展过程，数据库管理系统的主要功能。信息世界中的实体、属性、联系，以及关系数据模型中的关系、属性、元组和键码等基本概念。2.数据模型层次模型、网状模型、关系模型，重点为关系模型。关系、关系性质、候选码、外码、主码、主属性、非主属性、关系模型完整性约束、关系模式、关系数据库等基本概念。关系模型的数学基础及其运算：并、差、交、笛卡尔积、投影、选择、自然连接等。3.关系数据库标准语言SQLSQL语言的特点，基本语法，基本表、视图、索引等概念。数据定义：创建数据库、创建基本表、表结构的修改、基本表的删除；索引的建立与删除。数据查询:SELECT语句，具体包括：（1）简单查询（单表查询），包括正确书写选择条件、排序输出、聚合运算以及分组处理；（2）连接查询（多表查询）；（3）嵌套查询（子查询）。数据操纵：基本表数据的插入、删除、修改。视图的操作：定义视图、查询视图、更新视图、撤消视图。4.关系数据模型规范化理论关系模式设计中可能出现的问题及其产生原因以及解决的途径。函数依赖、完全函数依赖、部分函数依赖、传递函数依赖的定义。范式概念：第一范式（1NF）、第二范式（2NF）和第三范式（3NF）的定义，能判别关系模式的范式等级。关系模式的分解（规范到3NF）的步骤、分解的原则和分解的方法。（三）C语言程序设计基础1.C语言基本语法和程序结构字符集、标识符、关键字、常量定义、变量定义、数据类型、操作符、表达式计算；源程序结构、C语言程序的开发过程。2.程序语句和控制结构语句、复合语句、空语句、if选择结构、if-else选择结构、switch选择结构、while语句、do-while语句、for语句、continue语句、break语句、return语句。3.函数函数的定义与调用、函数返回值、函数原型、参数传递、默认参数、变量的存储类别、变量的生命期与作用域、递归函数、编译预处理指令。4.数组一维数组的定义、一维数组元素的引用、一维数组的初始化、多维数组的定义、多维数组元素的引用、多维数组的初始化、字符数组的定义、字符数组的初始化、字符数组的引用、字符串、字符串的输入输出、字符串处理函数、传递数组参数。5.指针地址和指针的概念、定义指针变量、建立指针、间接引用指针、指针的初始化、指针运算、用指针给函数传参数，用指针操作数组。6.结构结构类型的定义和使用、为函数传递结构参数。（四）计算机网络1.计算机网络基本概念计算机网络与互联网的发展历史、计算机网络的组成与功能、计算机网络的分类。2.计算机网络体系结构与参考模型计算机网络分层结构；计算机网络协议、接口、服务等概念；OSI参考模型和TCP/IP模型。3.数字通信信道、信号、宽带、码元、速率、帧等基本概念；电路交换、报文交换与分组交换；差错控制。4.传输介质双绞线