本站
非官方网站，
信息完全免费，仅供参考，不收取任何费用，具体请以官网公布为准！
考 试 大 纲
科目代码、名称: 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
四、样卷
