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

适用专业: 081200 计算机科学与技术

一、考试形式与试卷结构

(一)试卷满分及考试时间

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

(二)答题方式

答题方式为闭卷、笔试。

试卷由试题和答题纸组成;答案必须写在答题纸相应的位置上。

(三)试卷题型结构

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

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

3.程序填空与程序分析题题：4小题，每小题6分，共24分

4.解答题：4小题，第小题10分，共40分

5.算法与程序设计题：3小题，第1、2小题每小题14分，第3小题18分，共46分

二、考查目标(复习要求)

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

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

第一章　概论

1.数据结构的基本概念与术语

2.算法与算法分析

第二章　线性表及其顺序存储

1.线性表

2.顺序表及其应用

3.栈的概念及其应用

4.队列的概念及其应用

第三章　线性表及其链式存储

1.链式存储

2.单链表

3.带头结点的单链表及其应用

4.循环单链表与双链表

5.链式栈与链式队列

第四章　字符串、数据与特殊矩阵

1.字符串及模式匹配

2.特殊矩阵的压缩存储

3.稀疏矩阵

第五章　递归

1.递归的基本概念与递归程序设计

2.递归程序设计执行过程的分析

3.递归程序到非递归程序的转换

第六章　树

1.树的概念

2.树的存储结构

3.树的遍历

第七章　二叉树

1.二叉树的基本概念

2.二叉树的存储结构

3.二叉树的遍历(递归与非递归)

4.穿线二叉树的基本概念与构造

5.树、森林和二叉树的转换

第八章　图

1.图的基本概念

2.图的存储结构(邻接矩阵法、邻接表法)

3.图的遍历

4.生成树与最小生成树

5.最短路径

6.拓扑排序

7.关键路径

第九章　检索

1.检索的基本概念

2.线性表的检索

3.二叉排序树

4.平衡二叉排序树

5.Huffman树

6.B-树

7.散列表的检索

8.查找算法的分析及应用

第十章　排序

1.排序的基本概念

2.插入排序(直接插入排序、折半插入排序、希尔排序)

3.选择排序(简单选择排序、堆排序)

4.交换排序(冒泡排序、快速排序)

5.二路归并排序(merge sort)

6.基数排序

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

8.内部排序算法的应用

参考教材或主要参考书：

1.《数据结构》(C语言版)第二版，李云清，杨庆红，揭安全 编著，人民邮电出版社，ISBN:978-7-115-20703-6