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

一、考试性质

普通高等学校本科插班生招生考试是由专科毕业生参加的选拔性考试。高等学校根据考生的成绩，按已确定的招生计划，德、智、体全面衡量，择优录取。该考生所包含的内容将大致稳定，试题形式多种，具有对学生把握本课程程度的较强识别、区分能力。

二.考试内容及要求

一、考试基本要求

通过数据结构与算法理论的学习，使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术;配合算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力，对理论和实践的操作使学生得到全面的领会和深刻的认识。

二、考核知识点及考核要求

本大纲的考核中，按照“识记”、“领会”、“简单应用”和“综合应用”等四个层次规定应达到的能力层次要求。各能力层次为递进等级关系，后者必须建立在前者的基础上，其含义是：

识记：要求考生知道有关的名词、概念、原理、知识的含义，并能正确认识或识别。

领会：要求在识记的基础上，能把握相关的基本概念、基本原理和基本方法，掌握有关概念、原理、方法的区别与联系。

简单应用：要求在领会的基础上，运用所掌握的基本概念、基本原理和基本方法中的少量知识点，分析和解决一般的理论问题或实际问题。

综合应用：要求在简单应用的基础上，运用学过的多个知识点，综合分析和解决比较复杂的实际问题。

第1章绪论

一、考核知识点

1、数据结构的基本概念

2、抽象数据类型的表示和实现

3、算法的概念和特性

4、算法时间复杂度和空间复杂度分析

二、考核要求

1、识记

(1)数据结构的研究内容

2、领会

(1)抽象数据类型的表示和实现

(2)算法的定义和特性

(3)评价算法优劣的基本标准

3、简单应用

(1)简单数据结构的程序设计

(2)简单数据结构程序的时间复杂度和空间复杂度分析

4、综合应用

(1)数据结构的一些基本概念

(2)算法的时间复杂度分析

第2章线性表

一、考核知识点

1、线性表的类型定义

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

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

4、线性表的应用

二、考核要求

1、识记

(1)线性表的定义

(2)线性表的特点

2、领会

(1)线性表的抽象数据类型定义

3、简单应用

(1)线性表的顺序存储和基本操作实现

(2)单链表的存储和基本实现

(3)双链表的存储和基本实现

(4)一元多项式的表示和基本运算

4、综合应用

(1)一般线性表的合并

(2)有序表的合并

第3章栈和队列

一、考核知识点

1、栈的类型定义

2、栈的存储结构表示和实现

3、栈与递归的实现

4、队列的类型

6、队列的存储结构标识和实现

二、考核要求

1、识记

(1)栈的类型定义

(2)队列的类型定义

2、领会

(1)栈的存储结构表示和实现

(2)队列的存储结构标识和实现

3、简单应用

(1)表达式求值

(2)打印杨晖三角形

(3)迷宫求解问题

(4)模拟汽车加油站问题

第4章串、数组和广义表

一、考核知识点

1、串的表示和实现

2、数组的存储方法

3、特殊存储结构

4、广义表的逻辑结构和存储结构

二、考核要求

1、识记

(1)串的表示和实现

(2)数组的存储方法

2、领会

(1)特殊结构的存储方法

(2)广义表的逻辑结构和存储结构

3、综合应用

(1)古典的模式匹配算法

第5章树和二叉树

一、考核知识点

1、二叉树的定义和术语

2、二叉树的性质，特殊的二叉树

3、二叉树的存储结构，顺序存储和二叉链表

4、二叉树的遍历(前序、中序、后序、层次)

5、树和森林的定义，树的存储

6、树、森林与二叉树的转换、

7、树的应用，哈夫曼树和哈夫曼编码

8、线索化二叉树

二、考核要求

1、识记

(1)二叉树的定义

(2)树和森林的定义

2、领会

(1)二叉树的术语

(2)特殊的二叉树

3、简单应用

(1)二叉树的存储结构

(2)线索化二叉树

(3)树、森林和二叉树的转换

4、综合应用

(1)二叉树的性质

(2)二叉树的遍历方法

(3)哈夫曼编码

第6章图

一、考核知识点

1、图的定义和术语

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

3、图的遍历(深度优先和广度优先)

4、构造最小生成树的短发

5、拓扑排序和关键路径

6、求最短路径问题

二、考核要求

1、识记

(1)图的定义和术语

2、领会

(1)图的邻接矩阵表示法

(2)图的邻接表表示法

3、简单应用

(1)图的遍历方法：深度优先遍历、广度优先遍历

3、综合应用

(1)最小生成树算法：普里姆算法、克鲁斯卡尔算法

(2)拓扑排序和关键路径

(3)最短路径问题算法：迪杰斯特拉算法、佛洛依德算法

第7章查找

一、考核知识点

1、查找的基本概念

2、基于线性表的查找

3、基于树表的查找

4、散列表

二、考核要求

1、识记

(1)查找的基本概念

(2)散列表的基本概念

2、简单应用

(1)顺序查找

(2)折半查找

(3)二叉排序树、平衡二叉树

3、综合应用

(1)散列函数的构造方法

(2)处理冲突的方法

(3)散列表的查找和分析

第8章排序

一、考核知识点

1、排序的基本概念

2、插入排序

3、交换排序

4、选择排序

5、归并排序

6、基数排序

7、排序算法分析

二、考核要求

1、识记

(1)排序的基本概念

2、简单应用

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

(2)快速排序、冒泡排序、2-路归并排序

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

(4)排序算法分析

三.考试形式及试卷结构

1、考试形式为闭卷，笔试，考试时间为120分钟，试卷满分为100分。

2、试卷内容比例：第一～四章占40%，第五、六章占40%，第七、八章占20%。

3、试卷题型比例：判断题占20%，选择题占30%，综合计算分析题占50%。

4、试卷难易比例：易、中、难分别为30%，50%，20%。

四.参考书目

严蔚敏.数据结构与算法(C语言版).人民邮电出版社.2011

五.题型示例

一、判断题(每题2分，对的打√，错的打×，共20分)

1.数据元素是数据的最小单位。()

2.图的拓扑有序序列不是唯一的。()

3.链式存储的线性表可以实现顺序存取。()

二、选择题(每题2分，共30分)

1.计算机内部数据表示的最小单位是()

A.数据

B.数据项

C.数据元素

D.数据库

2.线性表采用链式存储时，结点的存储地址是()

A.必须是不连续的

B.连续与否均可

C.必须是连续的

D.和头结点的存储地址相连续

3.栈与一般线性表的区别是()

A.元素个数

B.元素类型

C.逻辑结构

D.插入、删除元素的位置

三、综合计算分析题(共50分)

1.假设一棵二叉树的先序序列是：ABDFCEGH，中序序列是：BFDAGEEHC。试分析：

(1)画出这棵二叉树;

(2)将这棵二叉树转换成对应的树(或森林)。

2.设有一组关键字(9，1，23，14，55，20，84，27，30)，采用哈希函数：H(key)=key%8，表长为10，用开放地址法的二次探测法处理冲突。要求：

(1)对该关键字序列构造哈希表;

(2)计算其查找成功的平均查找长度。