华中科技大学硕士研究生入学《软件基础》考试大纲

（代码：849）

第一部分：考试说明

      软件基础是华中科技大学空间信息科学与技术专业硕士生入学选考的专业基础课之一。

考试范围：C语言、数据结构与数据库系统基础。

考试形式与试卷结构：

（一） 答卷形式：闭卷，笔试；所列题目均为必答题。

（二）  答题时间：180分钟。

（三）  各部分考察比例：

   C语言部分  ：  30%

数据结构部分： 30%

数据库部分  ： 40%

（四）  试卷结构与考试题型

试卷共150分,基本的考试题型有：

(1)单项选择题和多项选择题；

(2)填空题(基本概念、基本知识、基本方法)；

(3)画图题；

(4)简答题；

(5)应用题(求解问题)；

(6)算法和程序设计填空题；

(7)算法和程序设计与分析题；

(8)其它题型。

第二部分：考察要点

C语言部分：

一、C语言的结构
1.程序的构成，MAIN函数和其他函数。
2.头文件，数据说明，函数的开始和结束标志。
3.源程序的书写格式
4.C语言的风格。

二、数据类型及其运算

1.C的数据类型（基本类型，构造类型，指针类型，空类型）及其定义方法。

2.C运算符的种类、运算优先级和结合性。

3.不同类型数据间的转换与运算。

4.C表达式类型（赋值表达式、算术表达式、关系表达式、逻辑表达式、条件表达式、逗号表达式）和求值规则。

三、基本语句

1.表达式语句，空语句，复合语句。
2.数据的输入和输出，输入输出函数的调用。
3.复合语句。
4.GOTO语句和语句标号的使用。

四、选择结构程序设计

1.用if语句实现选择结构。
2.用switch语句实现多分支选择结构。
3.选择结构的嵌套。

五、循环结构程序设计

1.for 循环结构。
2.while和do while循环结构。
3.continue语句和break语句。
4.循环的嵌套。

六、数组的定义和引用
1.一维数组和多维数组的定义、初始化和引用。
2.字符串与字符数组。

七、函数

1.库函数的正确调用。
2.函数的定义方法。
3.函数的类型和返回值。
4.形式参数与实在参数,参数值的传递。
5.函数的正确调用,嵌套调用,递归调用。
6.局部变量和全局变量。

八、指针

1.指针的概念，变量的指针与指向变量的指针变量，包括定义、引用以及指针变量作为函数参数。

2.数组的指针，包括指向数组的指针变量的定义与赋值、通过指针引用数组元素、数组名作为函数参数。

3.字符串的指针与指向字符串的指针变量。

九、结构体

1.结构体的定义方法和引用方法。
2. 结构体数组及其初始化。

数据结构部分：

一、绪论

1． 掌握数据、数据元素、数据对象、数据结构、存储结构和数据类型的概念和术语的含义；

2． 掌握算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。

二、线性表
1 掌握线性表的逻辑结构特性是数据元素之间存在着的线性关系；
2 熟练掌握线性表的顺序存储结构和链式存储结构的描述方法及循环 链表, 双向链表的特点；
3 熟练掌握线性表在顺序存储结构和各种链表结构上的查找、插入和删除的算法；
  4 能够从时间和空间复杂度的角度综合比较两种存储结构的不同特点及其适用的场合。

三、栈和队列
  1 熟练掌握栈和队列的结构特性----操作受限的线性表；
  2 熟练掌握栈类型在两种存储结构表示时的基本操作实现方法；
  3 熟练掌握循环队列和链队列的基本操作实现算法；
  4 熟练掌握栈和队列的满和空的条件和它们的描述方法；

四、 树和二叉树
  1 熟悉树的基本定义及其相关的术语的含义（如孩子、兄弟,深度、度等概念）；
  2 熟练掌握二叉树的结构特性，了解相应的证明方法, 理解常见的二叉树（如满二叉树，完全二叉树，Huffman树，平衡二叉树，排序二叉树）有关理论结论；
  3 熟悉二叉树的二叉链存储结构特点及适用范围；
  4 熟悉三种遍历二叉树的递归算法（先序, 中序和后序）；
  5 掌握树和森林与二叉树的转换, 及其各自遍历的对应关系；
  6 了解实现树的各种操作的算法；
  7 掌握最优树的特性，掌握Huffman树及其应用。

五、 图
1 掌握图的定义和术语（如顶点，边，度及其相互之间的数量关系,连通性与生成树等）；
2 掌握图的两种存储结构：数组表示法（邻接矩阵）、邻接表，了解实际问题的求解效率与采取何种存储结构和算法有密切关系；
3 掌握图的两种遍历策略：深度优先搜索和广度优先搜索；图的遍历和树的遍历之间的类似与差异；

六、内部排序
1 掌握排序的定义和各种排序方法的基本思想及其特点；
2 了解各种排序方法的排序过程及其依据的原则，基于“关键字间的比较”进行排序的方法可以分为插入排序、交换排序、选择排序、归并排序和基数排序；
3 熟练掌握快速排序和堆排序等方法的实例排序过程；
4 能够进行各种排序方法的时间复杂性(平均情况与最坏情况)估计或分析；
5 一般了解排序方法“稳定”的含义。

数据库部分：

一、        绪论
1、  了解数据管理技术的发展过程
2、  掌握数据库管理系统的概念和功能
3、  掌握数据库系统的特点
4、  掌握数据库的三级模式结构
5、  掌握数据库的两级映像功能及数据独立性
6、  掌握概念模型与数据模型的区别
7、  掌握数据模型的组成要素和典型的数据模型

二、 关系数据库
1、  掌握关系模型的组成
2、  掌握关系的完整性约束
3、  掌握关系的基本术语和形式化定义
4、  掌握关系代数

三、 SQL语言
1、  掌握数据定义语言
2、  重点掌握数据查询语言
3、  掌握数据更新语言
4、  掌握视图的定义与使用
5、  掌握数据控制语言

四、 关系数据库理论
1、  掌握函数依赖概念
2、  掌握部分函数依赖和传递函数依赖的概念
3、  理解规范化程度不高的范式可能存在的问题
4、  掌握1NF、2NF、3NF、BCNF等范式的定义

五、 关系数据库设计
1、  掌握数据库设计的步骤及各阶段的任务
2、  熟练掌握概念结构设计方法和e-r图设计方法
3、  熟练掌握将e-r图转换成关系模式的方法
4、  了解数据库的物理设计、数据库实施与维护

六、 并发控制
1、  理解数据库并发操作引起的问题
2、  掌握数据库并发控制的意义和实现技术
3、  掌握共享锁和排他锁的特点
4、  掌握三级封锁协议

参考书 ：

谭浩强  张基温《C语言程序设计教程》   高等教育出版社

谭浩强 《C程序设计》  清华大学出版社

萨师煊，王珊.数据库系统概论（第三版）.北京：高等教育出版社，2001

严蔚敏等编，《数据结构》（C语言版），清华大学出版社

严蔚敏等编，《数据结构题集》（C语言版），清华大学出版社