科目代码

893

科目名称

软件工程基础综合

内容范围或要点：

范围

线性表、栈和队列、串、数组和广义表、树和二叉树、图、查找、内部排序。

线性表

线性表的定义、逻辑结构、存储结构；线性表的顺序表示、链式表示；顺序表和链表的插入和删除等操作。

栈和队列

栈的定义、栈的顺序表示和链式表示、顺序栈、链栈的入栈和出栈操作；队列的定义、队列的顺序表示和链式表示、顺序队列、链队列的入队和出队操作；循环队列的队空和队满的判断。

串

串类型的定义、串的表示和实现、串的模式匹配算法、模式匹配的一种改进算法（KMP方法)。

数组和广义表

数组的定义、数组的顺序表示和实现；广义表的定义、存储结构。

树和二叉树

树的定义和基本术语；二叉树的定义、性质、存储结构；遍历二叉树、线索二叉树；树的存储结构、森林与二叉树的转换、树和森林的遍历；最优二叉树(赫夫曼树)、赫夫曼编码。

图

图的定义和术语、图的表示方法（数组表示法、邻接表）、图的深度优先搜索和广度优先搜索、最小生成树、有向无环图的拓扑排序及关键路径、从某个源点到其余各顶点的最短路径、每一对顶点之间的最短路径。

查找

静态查找表（顺序表的查找、有序表的查找）、动态查找表（二叉排序树和平衡二叉树）、哈希表的定义、哈希函数的构造方法、处理冲突的方法、哈希表的查找及其分析。

排序

排序概述、插入排序（直接插入排序、希尔排序）、快速排序、选择排序（简单选择排序、堆排序）、归并排序、基数排序、各种内部排序方法的比较讨论。

参考书目：

《数据结构（C语言版）》严蔚敏 吴伟民 编著  清华大学出版社

《数据结构题集（C语言版）》严蔚敏 吴伟民 米宁 编著  清华大学出版社

科目代码

993

科目名称

软件工程综合

内容范围或要点：

基于C语言的程序设计具有专业基础的特点，基础性要求掌握C 语言本身的语法原理与程序结构，专业性要求采用常用算法与程序模式达到应用程序设计与程序编码的目的。通过判断选择、程序阅读、函数设计、程序填空、程序设计等试题形式，重点考查数据类型、基本运算、流程控制、数组运用、函数及参数传递、指针运用、结构体运用等基础知识和应用能力。

基本概念

理解基本数据类型及其定义方法、存储性质和表示形式；理解变量、常量在程序的编码、编译和执行时刻的意义；掌握各种运算符的功能、优先级和结合性；运用算术表达式、关系表达式和逻辑表达式实现运算，以及混合运算的类型转换；熟练赋值语句存储运算结果，以及运算结果的格式化输入与输出。

流程控制结构

了解过程程序设计的特点与方法；熟悉算法过程分析及其流程图描述；掌握顺序、选择和循环基本流程控制结构和函数设计。

数组应用（包括一维、二维、字符型数组）

 理解基本数据类型、复合数据类型、数据结构等概念；掌握数组的定义、初始化、存储顺序、输入/输出、元素引用；运用数组数据结构解决数值集合的运算或字符数据集合的运算；运用字符串操作相关的库函数。

函数应用

理解程序设计中的模块化思想、模块四种属性和模块化程序设计方法；熟悉程序组成结构设计，并采用结构图描述程序的组成结构；掌握函数定义、调用、参数传递和函数值返回；掌握函数的直接调用、嵌套调用和递归调用；理解局部变量、全局变量以及变量的存储类别。

编译预处理

掌握宏定义、参数宏定义、文件包含、条件编译等的一般概念、定义格式及使用方法。

指针应用

理解地址和指针的概念；掌握各种类型指针的原理和运用方法，包括变量与指针、数组与指针、字符串与指针、函数与指针、指针数组等。

结构体和共同体

掌握结构体变量的定义和使用方法；掌握指向结构体类型变量的指针；掌握动态内存分配与撤消函数使用方法；运用指针处理链表；掌握共同体变量的定义和使用方法；掌握枚举类型的一般概念、定义格式及使用方法。

位运算

掌握位运算符和位运算。理解位段。

文件应用

理解文件类型指针；掌握文件的打开、关闭、读写和定位等文件操作和运用方法。

参考书目

《C语言程序设计》（第二版)潭浩强编著，清华大学出版社，1999年，ISBN 7-302-03806-6/TP.2205。