专业名称：软件工程

《程序设计》考试大纲

一、考试的总体要求

本考试大纲适用于报考江南大学软件工程专业硕士学位研究生入学考试。《程序设计》是计算机相关学科的重要基础，主要考核内容为基于数据结构的程序设计。要求考生对计算机科学与技术学科的基本知识、基本理论、基本方法有较深入、系统的理解，掌握各种数据结构的定义和实现算法，对C语言的基本知识有较深入的了解，掌握程序设计的基本方法，并具有综合运用所学知识分析问题和解决问题的能力。

二、考试的内容

（一） 程序设计基础

1．C语言的基本数据类型、各种运算符和表达式、基本控制结构。

2．数组的定义、数组元素的引用、数组的初始化，掌握与字符串相关的库函数。

3．函数的定义语法，函数调用中参数的传递机制；局部和全局变量的有效范围。

4．结构体类型变量的定义、引用、初始化方法，结构体数组的定义、初始化和应用，共同体变量的定义和使用方法。

5．地址和指针的基本概念，如何使用指针来处理数组、字符串以及结构体，函数指针的基本概念以及使用。

6．FILE的定义以及对文件进行的各种操作的库函数。

（二）线性表

1．理解线性表的概念、定义、逻辑结构和存储结构。

2．熟练掌握线性表的顺序结构及其各种基本运算。

3．熟练掌握单链表、循环链表、双向链表的存储结构及其各种基本运算。

4．理解链表的应用——稀疏多项式存储和运算。

（三） 栈和队列

1．掌握栈的定义、表示、实现和应用。

2．掌握递归的概念和递归的实现过程。

3．掌握队列的定义以及顺序(循环队列)和链式存储结构的实现。

（四） 串

1．了解串的基本概念及顺序和链式存储结构。

2．掌握串的各种基本运算。

3．了解串的模式匹配算法。

（五） 数组和广义表

1．掌握数组的顺序存储结构。

2．理解稀疏数组的概念和压缩存储的方法。

3．理解稀疏矩阵的三元组存储结构和基本运算。

4．了解稀疏矩阵的十字链表存储结构。

5．理解广义表的基本概念，掌握广义表的存储结构。

（六） 树

1．理解树的基本概念及其存储结构。

2．熟练掌握二叉树的定义、性质以及各种存储结构和遍历算法。

3．掌握线索二叉树的概念、存储结构及线索化算法。

4．掌握树和森林与二叉树间的转换，掌握树和森林的遍历算法。

5．掌握哈夫曼树的概念、存储结构和应用。

（七） 图

1．理解图的基本概念，掌握图的邻接矩阵和邻接表的存储结构。

2．了解十字链表，邻接多重表等存储结构。

3．熟练掌握图的深度优先和广度优先遍历算法。

4．理解图的连通性、最小生成树的概念。

5．掌握求最小生成树算法。

6．理解有向无环图的概念，掌握拓扑排序和关键路径算法。

7．理解带权最短路径的概念，掌握求最短路径的算法。

（八） 查找

1．理解查找的概念及其效率的评价方法。

2．理解静态查找表的概念，熟练掌握顺序、折半和分块查找算法。

3．理解动态查找表和二叉排序树的概念。

4．了解平衡二叉树的概念。

5．理解哈希表的含义，掌握哈希函数的构造和处理冲突的基本方法。

（九） 内部排序

1．掌握插入类排序的算法：直接插入排序、希尔排序。

2．掌握交换类排序的算法：冒泡排序、快速排序。

3．掌握选择类排序的算法：简单选择排序、堆排序。

4．了解归并排序、基数排序的思想，了解外排序的概念。

三、考试形式

1．考试题型为综合程序设计题；

2．考试总分150分；

3．考试时间为3小时。

4．考试方式为闭卷手写答题。