浙江师范大学硕士研究生入学考试初试科目

考　试　大　纲

科目代码、名称: 885数据结构与程序设计

适用专业: 081200计算机科学与技术（一级学科）

一、考试形式与试卷结构

（一）试卷满分 及 考试时间

本试卷满分为150分，考试时间为180分钟。

（二）答题方式

答题方式为闭卷、笔试。

试卷由试题和答题纸组成；答案必须写在答题纸（由考点提供）相应的位置上。

（三）试卷题型结构

1．单项选择题：10小题，每小题2分，共20分

2．填空题：10小题，每小题2分，共20分

3．程序填空与程序分析题题：5小题，每小题6分，共30分

4．解答题：5小题，每小题8分，共40分

5．算法与程序设计题：3小题，第1、2小题每小题12分，第3小题16分，共40分

二、考查目标（复习要求）

全日制攻读硕士学位研究生入学考试数据结构与程序设计科目考试内容包括《数据结构》和C语言程序设计课程的主要内容，要求考生系统掌握相关学科的基本知识、基础理论和基本方法，并能运用相关理论和方法分析、解决程序设计中的实际问题。

三、考查范围或考试内容概要

第一章　绪论

1．什么是数据结构

2．基本概念和术语

3．抽象数据类型的表示与实现

4．算法与算法分析

第二章　线性表

1．线性表的类型定义

2．线性表的顺序表示和实现

3．线性表的链式表示和实现

4．线性表的应用

第三章　栈和队列

1．栈

2．栈的应用

3．栈与递归的实现

4．队列及其应用

第四章　串

1．串类型的定义

2．串的表示和实现

3．串的模式匹配算法

第五章 数组和广义表

1．数组的定义

2．数组的顺序表示及实现

3．矩阵的压缩存储（特殊矩阵、稀疏矩阵）

4．广义表的定义

5．广义表的存储结构

6．m元多项式的表示

7．广义表的递归算法（求广义表的深度、复制广义表、建立广义表）

第六章　树与二叉树

1．树的定义和基本术语

2．二叉树的定义、性质和存储结构

5．遍历二叉树和线索二叉树

6．树和森林（树的存储结构、森林与二叉树的转换、树和森林的遍历）

7．Huffman树及其应用

第七章　图

1．图的定义和术语

2．图的存储结构（数组、邻接表、邻接多重表）

3．图的遍历

4．生成树和最小生成树

5．有向无环图及其应用(拓扑排序、关键路径)

6．最短路径（Dijkstra算法、Floyd算法）

第八章　检索

1．静态查找表（顺序表、有序表、顺序索引表）

2．动态查找表（二叉排序树和平衡二叉树、B树）

3．哈希表

第九章　排序

1．排序的基本概念

2．插入排序（直接插入排序、其它插入排序、希尔排序）

3．选择排序（简单选择排序、树形选择排序、堆排序）

4．交换排序（冒泡排序、快速排序）

5．归并排序

6．基数排序

7．各种内部排序算法的比较

参考教材或主要参考书：

1．《数据结构》（C语言版），严蔚敏，吴伟民编著，清华大学出版社，ISBN:978-7-302-14751-0

四、样卷