成都信息工程学院
2013年硕士研究生入学考试自命题科目
考试大纲
考试科目：软件工程专业基础 科目代码：807
一、考试的总体要求
本科目考试内容涵盖C语言程序设计、数据结构两部分内容。
（一）C语言程序设计部分
要求掌握C语言的基本内容及程序设计的基本方法、常用算法与编程技巧，掌握结构化程序设计思想。选择适当的数据类型表示实际问题，能使用函数进行模块化程序设计，掌握应用计算机解决和处理实际问题的思维方法与基本能力。
（二）数据结构
理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现；熟练掌握经典算法的演化过程；具备选择合适的数据结构和方法进行问题求解的能力；能够对算法性能进行简单分析。
二、考试的内容及比例
（一）C语言程序设计部分
1. C语言基础 (约10%)
（1）C语言程序基本结构特点；
（2）基本数据类型，整数、实数、字符和字符串常量的表示方法，变量定义和初始化，能选择正确的数据类型处理实际问题；
（3）基本运算的实现（包括算术运算、关系运算、逻辑运算、条件运算、赋值运算），各类数值型数据间的混合运算；
（4）数据输入输出的概念及在Ｃ语言中的实现，包括字符数据的输入输出、格式输入与输出。
2.程序控制结构（约10%）
（1）用if、switch实现分支结构的程序设计；
（2）用while语句、do while语句和for语句实现循环结构的程序设计，循环嵌套的实现方法；
（3）用循环实现迭代、枚举、递归等常用算法。
3、数组 (约20%)
（1）一维数组、二维数组的定义和引用方法；
（2）字符数组和字符串处理函数的使用；
（3）能应用数组处理实际问题，如字符串处理、数列计算、矩阵运算等。
4、函数 (约30%)
（1）函数定义的一般形式，函数参数和函数返回值，包括数组、指针作为函数的参数，指针作为函数的返回值；
（2）函数调用的一般形式、函数的嵌套和递归调用；
（3）变量的存储类别、局部变量和全局变量的使用；
（4）通过函数定义、函数调用实现模块化程序设计。
5、指针 (约15%)
（1）地址和指针的概念，指针变量的定义；
（2）通过指针变量引用各类指向实体（包括普通变量、数组、结构体和指针）；
（3）指针数组和命令行参数（argc、argv）的意义和实现。
6、结构体 (约10%）
（1）结构体类型变量的定义、成员引用、初始化的方法；
（2）结构体数组的使用；
（3）结构体嵌套的定义、成员引用、初始化的方法。
7、文件 （约5%）
（1）文件有关的基本概念、文件类型指针；
（2）文件打开与关闭、文件读写，文件定位操作的实现。
（二）数据结构部分
1、绪论（约5%）
（1）数据结构的基本概念，数据的逻辑结构、存储结构；
（2）算法的定义、算法的基本特性以及算法分析的基本概念。
2、线性表（约20%）
（1）线性表的定义和基本操作；
（2）线性表的实现：顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)；线性表的应用——表的建立、插入与删除、检索等操作对应的算法设计(含递归算法的设计)。
3、栈、队列和稀疏矩阵（约15%）
（1）栈与队列的基本概念、基本操作；
（2）栈与队列的顺序存储结构与链式存储结构的构造原理；
（3）在不同存储结构的基础上对栈与队列实施插入与删除等基本操作对应的算法设计；
（4）栈与队列的应用。
（5）对称矩阵和稀疏矩阵的压缩存储；
4、树与二叉树(约20%)
（1）树的定义和性质；
（2）二叉树的概念、性质和实现；
（3）二叉树的顺序存储结构和链式存储结构；
（4）遍历二叉树和线索二叉树；
（5）树和森林；
（6）赫夫曼树及其应用。
5、图(约10%)
（1）图的基本概念和常用名词术语；
（2）图的邻接矩阵存储方法、邻接表存储方法的构造原理；
（3）图的遍历操作及连通性问题；
（4）最小生成树，最短路径，AOV网与拓扑排序，关键路径。
6、查找(约10%)
（1）查找的基本概念；
（2）顺序表的顺序查找方法、有序顺序表的折半查找方法；
（3）二叉排序树、平衡二叉树和B树；
（4）哈希表的构造及其查找；
（5）查找算法的分析及应用。
7、内排序(约20%)
（1）排序的基本概念，排序方法的分类；
（2）各种排序方法排序的原理、规律和特点，包括：插入排序法(含折半插入排序法和希尔排序)、选择排序法（含堆排序）、冒泡排序法、快速排序法、归并排序、基数排序；
（3）排序算法性能的简单分析（时空复杂度）。
三、考试题型及比例
（一）C语言程序设计部分
考试满分75分，其中：
1、客观题（选择、判断） 20分
2、程序完善题 15分
3、编程题 40分
（二）数据结构部分
考试满分75分，其中：
1、客观题（选择、判断） 15分
2、算法设计题 30分
3、综合题 30分
四、考试形式及时间
考试形式为笔试，考试时间为 3 小时。
2013成都信息工程学院考研软件工程专业基础考试大纲
