考试大纲085212软件工程

深圳大学2011年专业学位硕士研究生入学考试大纲

学院（盖章）：计算机与软件学院 领域代码： 085212   领域名称：  软件工程  

考试科目代码：    811    考试科目名称：    数据结构与算法             

一、考试基本要求

本考试大纲适用于报考深圳大学软件工程的硕士研究生入学考试。《数据结构与算法》是为招收软件工程硕士生而设置的具有选拔功能的水平考试。它的主要目的是测试考生对数据结构以及计算机算法的各项内容的掌握程度。要求考生熟悉计算机处理数据的基本方法，掌握计算机加工的数据结构的特性，熟悉为实际应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并掌握算法的时间分析和空间分析技术。要求考生能够编写符合软件工程规范、结构清楚、正确易读的算法（程序）。

二、考试内容和考试要求

1、 算法及其复杂性

算法与程序

算法的复杂性及其表示 

最坏、最好和平均情况分析

时间复杂性分析的基本方法

2、 线性表、栈、队

向量（顺序表）、链表（静态链表、单链表、双向链表、循环链表）及相关算法

栈、队，了解其应用，理解递归

3、 树和二叉树

树（森林）、二叉树及其性质；两者的对应关系

二叉树遍历

赫夫曼（Huffman）树的构造及应用

4、 图

图（网）的概念及其邻接矩阵和邻接表存储法

图的遍历、最小生成树、最短路径、拓扑排序、关键路径等算法

5、 查找

顺序查找、二分查找

二叉排序树、平衡二叉排序树及插入、删除时的平衡方法

哈希（Hash）表

了解查找成功及失败的平均查找长度

6、 内部排序

排序的概念及相关术语

“插入”、“起泡”、“快速”、“选择”、“堆”、“归并”、基数”等排序算法

三、考试基本题型