考试科目名称：数据结构与算法 　　一、考试的内容、要求和目的 　　1、考试内容 　　第1章概论（考核比重约：5%） 　　1)数据结构的基本概念和术语 　　2)算法和算法分析 　　第2章线性表（考核比重约：10%） 　　1)线性表的顺序表示和实现 　　2)线性表的链式表示和实现 　　3)双链表 　　4)循环链表 　　5)线性表实现方法的比较 第3章栈和队列（考核比重约：5%） 　　1)栈和队列的基本概念 　　2)栈和队列的顺序存储结构及其基本操作的实现 　　3)栈和队列的链式存储结构及其基本操作的实现 　　4)栈和队列的应用 　　第4章串（考核比重约：5%） 　　1)串的模式匹配 　　第6章树和二叉树（考核比重约：20%） 　　1)二叉树的定义及其主要特征 　　2)二叉树的顺序存储结构、链式存储结构及其基本操作的实现 　　3)二叉树的遍历（前序遍历、中序遍历、后序遍历、层次序遍历） 　　4)树的存储结构 　　5)森林与二叉树的转换 　　6)树和森林的遍历 　　第7章树和二叉树的应用（考核比重约：10%） 　　1)哈夫曼树和哈夫曼编码 　　2)堆和优先级队列 　　第8章图（考核比重约：10%） 　　1)图的概念 　　2)图的存储结构（邻接矩阵法、邻接表法） 　　3)图的遍历（深度优先遍历、广度优先遍历） 　　第9章图的应用（考核比重约：10%） 　　1)最小生成树（Prim算法、Kruskal算法） 　　2)拓扑排序 　　3)最短路径（Dijkstra算法、Floyd算法） 　　第10章集合与查找（考核比重约：10%） 　　1)基本概念 　　2)顺序查找 　　3)折半查找 　　4)二叉查找树 　　5)查找算法的分析及应用 　　第11章散列表（考核比重约：5%） 　　1)散列表的概念 　　2)构造散列函数的方法 　　3)解决冲突的方法 　　4)散列表的查找性能分析 　　第12章排序（考核比重约：10%） 　　1)排序的基本概念 　　2)插入排序（直接插入排序、折半插入排序、希尔排序） 　　3)交换排序（冒泡排序、快速排序） 　　4)选择排序（直接选择排序、堆排序） 　　5)二路归并排序 　　6)各种内部排序算法的比较 　　2、考试的要求和目的 　　软件工程专业《数据结构》课程本科插班生考试，要求考生比较系统地掌握课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。 　　软件工程专业本科插班生自命题考试是为测试考生是否具有插班就读的基本能力，选拔出优秀的专科毕业生而设置的具有选拔性质的考试，其目的是科学、公平、有效地测试考生掌握软件工程专业本科阶段专业知识、基本理论、基本方法的水平和分析问题、解决问题的能力，评价的标准是高等院校软件工程专业本科生所能达到的及格或及格以上水平，以利于软件工程专业择优选拔，确保本科插班生的招生质量。 二、考试的形式和结构 　　1、考核形式：闭卷 　　2、考试时间：120分钟 　　3、卷面满分：100分 　　4、试卷题型及赋分：单项选择题约20%、判断题约20%、综合应用题约30%、算法设计题约30% 　　5、试题难易比例：容易题约35%，中等难度题约45%，难题约20% 　　6、对考试辅助工具的要求：携带钢笔、圆珠笔或中性笔，以及铅笔、直尺等，禁止携带计算器。 三、教材及教学参考书 　　教材：算法与数据结构（第1版），冯广慧等，电子工业出版社 　　参考书： 　　1.数据结构：思想与实现（第2版），翁惠等,高等教育出版社,2017.11 　　2.算法与数据结构考研试题精析（第3版），陈守孔等,北京：机械工业出版社,2015.5