上海第二工业大学

《数据结构与高级程序设计》考试大纲

一、考试基本要求

《数据结构与高级程序设计》(科目代码：804)是我校电子信息专业硕士生入学考试的专业基础课之一。考试目标是要求考生掌握高级程序设计的基本概念、各种数据类型及基本程序设计方法，掌握各种数据结构的特点、存储表示、运算方法以及在计算机科学中最基本的应用，并具备选用合适的数据结构，利用高级编程语言(C 语言)编写质量高、风格好的应用程序的能力。合格考生应当达到全国普通高等院校计算机专业优秀本科毕业生的水平，具有较好的计算机理论基础。

考试对象为报考我校专业硕士研究生入学考试的准考考生。

二、试题类型及分值

1. 答卷方式：闭卷、笔试

2. 试卷总分：150 分(其中高级程序设计占 70 分，数据结构部分占 80 分)

3. 题型比例：

第一部分：高级程序设计(共 70 分)

选择题、填空题、程序阅读题、编程题。

第二部分：数据结构部分(共 80 分)

选择题、简答题、分析题、计算题、编程题。

三、考试时间：3 小时

四、考试内容

1. 第一部分：高级程序设计

(1)掌握程序的基本结构;变量与数据类型;变量声明与赋值。熟练掌握 C 语言程序的基本结构;掌握基本变量的声明与访问。

(2)掌握关系运算符与关系表达式;枚举法的思路;循环结构;分支结构。理解 C 语言最基本的运算符与关系表达式的概念;熟练掌握运算符与关系表达式的最基本使用;理解枚举法的基本思想;熟练掌握枚举法的最基本使用;理解循环结构;熟练掌握循环结构的最基本使用(for 语句与 while 语句);理解分支结构;熟练掌握分支结构的最基本使用。

(3)掌握数组与一维数组的基本使用;筛法与排序法;结构与结构数组;二维数组。理解数组的基本概念;熟练掌握一维数组的基本使用;掌握二维数组的基本使用;理解筛法与排序法;掌握筛选法与排序法的最基本的使用。理解结构的基本概念;熟练掌握结构的基本使用;掌握结构数组的基本使用。

(4)掌握函数的基本概念、使用与应用;递推;递归。理解函数的基本概念;熟练掌握函数的定义、声明、调用、返回的基本操作;了解递推数列的定义与算法的程序实现;了解递归及其实现的基本思路与方法。

(5)掌握指针的基本概念与基本使用;指针与数组;字符串及其处理;指针与结构;指针与结构数组;引用的概念与应用;利用引用来传递参数;几种参数传递方式的比较。理解指针的基本概念;掌握指针的基本使用;掌握指针与数组(一维)的基本使用;掌握字符串的基本使用;了解指针与结构;了解指针与结构数组;理解引用概念;掌握引用基本使用;了解利用引用传递参数;掌握几种参数传递方式的比较。

(6)掌握流的基本概念与常用输入输出流格式控制;文件流;理解 I/O 流、文件流的基本概念;熟练掌握 I/O 流与文件流的基本使用;了解 I/O 流与文件流的格式控制。

2. 第二部分：数据结构

(1)了解数据结构和算法的形成和发展及在计算学科中所处的地位，并掌握数据结构和算法的基本概念和术语、算法描述及算法分析的基本方法。

(2)熟练掌握顺序线性表和链式线性表(重点单链表)及其基本操作，以及简单应用;顺序存储和链式存储的优缺点。

(3)掌握栈和队列的结构特征、顺序存储结构、基本操作及其简单应用;讲述栈与递归的关系，掌握核心概念——递归。

(4)掌握数组的定义及地址公式、特殊矩阵的存储方式及地址公式、稀疏矩阵的三元组存储方式及基本运算;了解广义表的基本概念。

(5)掌握树及二叉树的基本概念、基本性质和存储结构;熟练掌握二叉树的各种遍历(前序、中序、后序、层次)和恢复;掌握树、森林与二叉树的关系，及其相互转换方法;熟练掌握哈夫曼树及其编码的算法。

(6)掌握图的基本概念和存储结构(邻接矩阵、邻接表)，掌握图的基本类型与运算(连通图、有向无环图、图的遍历)及各类典型应用(最小生成树、拓扑排序、关键路径、最短路径)。

(7)掌握各类存储结构的查找算法(顺序查找、折半查找、分块查找、二叉排序树查找)，理解静态查找与动态查找的区别，掌握哈希表的基本思想、函数构造、冲突处理方法及查找)。

(8)掌握内部排序的基本概念及其常用排序方法(插入排序、二分插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序、基数排序)，掌握各种不同排序方法的适用场合。

五、参考书目

1.《数据结构》严蔚敏，清华大学出版社

2.《C 程序设计》谭浩强，清华大学出版社，2010 年