绪论：
1、 什么是数据、数据元素、数据项、数据结构、
数据类型、抽象数据类型
2、 数据结构和算法的研究范畴；
3、 数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系；
数据结构的二元组表示，对应的图形表示，序偶和边之间的对应关系；
4、 算法的定义、算法的特性和五大要素、算法的评价、算法的时间和空间代价； 5、 空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法（数量级表示）；渐进的
空间复杂度。
6、 计算语句频度和估算算法时间复杂度方法； 7、 算法的描述：用伪C语言/C/VB；
8、 给定算法的最好、最差和平均这三种情况的时间复杂度的计算
线性表：
1、 线性表的概念、线性表的逻辑结构特性 2、 线性表的几种存储实现方式：
顺序存储 链式存储
3、 在使用上述存储结构的线性表上实现指定操作功能（包括线性表的各种基本运算，比如：
搜索、插入、删除、查找、归并、排序等）的算法的设计与分析 4、 线性表的顺序存储结构的类型定义和实现 5、 应用顺序表作为集合的简单操作
6、 链表与线性表一样，是一种实现级结构 7、 指针基本操作
8、 向链表中一个结点之后（前）插入新结点或从链表中删除一个结点的后缀结点的指针链
接过程
9、 单链表的结构···
10、单链表的定义、构造、插入与删除等算法 11、双向链表的特点、定义及相关算法的实现
12、循环链表的特点和类型定义，以及用循环链表解决问题的方法 13、静态链表的定义、特点及相关操作的实现
堆栈鱼队列：
1、 栈的定义、特性和栈的抽象数据类型的描述
2、 栈的顺序表示、链式表示以及相应操作和运算的实现和分析，注意栈空和栈满的条件 3、 利用栈解决简单问题的算法分析和设计
4、 栈的应用：火车车厢重排问题、数制转换问题、表达式求值问题和括号匹配问题 5、 算术表达式的前缀、中缀和后缀表示法，以及相互转换的规则
1
6、 三种表达式求值的算法，重点：堆栈的使用 7、 队列的定义、特性
8、 队列的顺序表示、链式表示以及相应操作和运算的实现
9、 利用队列解决简单问题的算法分析和设计，重点：离散事件仿真
10、循环队列的定义、特性及其抽象数据类型定义，循环队列的插入与删除算法 11、循环队列的特征：特别是循环队列中队头与队尾指针的变化情况
算法策略：
1、 递归与分而治之的概念、算法设计思想、应用条件、基本步骤 2、 递归向菲递归的转换
3、 利用分而治之和递归策略解决问题的分治法和回溯法 4、 其他策略：分支定界、穷举、贪婪等 5、 分而治之与递归策略的类型应用：···
树：
1、 树、森林的概念，相关定义和术语，特别是树的递归定义 2、 树的性质及其应用
3、 二叉树的性质、定义，顺序、链式表示，节点数的计算 4、 二叉树中结点编号规则和对应的顺序存储结构 5、 二叉树的遍历：中序、前序、后序、层次
6、算术表达式树，以及前、中、后缀表达式的对应 7、递归树的概念
8、二叉排序树的定义、性质、建立方法
9、堆的定义，堆的建立、最小堆和最大堆的异同，向堆中插入元素、删除元素的过程，堆的向上和向下调整等操作
10、最有二叉树的定义和实现，树的带权路径长度的计算，根据若干个叶子结点的权最优二叉树的过程
排序与查找：
1、 直接顺序查找、二分查找算法
2、 插入类排序：直接插入排序、折半插入排序、链式插入排序、希尔排序（思想、过程、
时间空间复杂度）
3、 交换类排序：直接选择排序、堆排序
4、 归并类排序|：二路归并排序、自然归并排序
5、 线性时间排序：计数排序、箱子排序、链式基数排序 6、 排序的基本概念、分类、工作过程和性能分析方法
7、 每一种排序算法的设计思想、算法描述、排序过程、稳定性及三种情况下的时间、空间
复杂度分析：平均情况、最好情况、最坏情况 8、 搜索（查找）的概念；静态搜索结构 9、 基于有序顺序表的搜索
顺序搜索（顺序查找）的过程
2
折半搜索（二分查找）的过程 二叉搜索（二叉查找）的过程
对于一个给定值元素，某查找算法的平均查找长度（即查找路径上的元素数）和性能（时间和空间复杂度）
例 题
线性表部分：
已知线性表L为你大二下学期所有课程的成绩列表，试根据该列表回答以下问题： 1、 写出L的具体形式化描述；
2、 设L的存储方式为线性单链表，设计一个具有较高运行效率的算法，实现对线性表L的
就地逆置操作，分析其时间复杂度和空间复杂度，绘制在算法执行过程中L的变化情况。 3、 设L的存储方式为顺序存储表示，设计一个具有较高运行效率的算法，删除表L中所有
不及格课程的成绩，保留所有及格课程的成绩，分析其时间复杂度，绘制算法执行过程中L的变化情况。
排序与查找部分：
已知线性表L为你在大二上学期所学课程的成绩列表，完成下列所有排序算法，分析其工作思想，写出每一趟排序结束时的关键码状态：
①二路归并排序；②基数排序；③计数排序；④直接插入排序；⑤最大堆排序； ⑥最小堆排序；⑦冒泡排序；⑧直接插入排序；⑨快速排序；
利用上一题中得到的已排序的有序表L’，用二分查找算法查找与你的《信号与系统》课程的成绩相同的结点，写出查找算法，分析其时间和空间复杂度，并画出查找比较的工作过程。
树形结构部分：
已知线性表L为你在大二上学期所有课程的成绩列表，试根据该列表回答以下问题：
1、 画出按初始排序顺序输入线性表L时，所得到的二叉排序树T’；并 利用该二叉排序树
T’，查找与你的《电路理论》课程的成绩相同的结点，给出具体查找比较过程。
2、 设L为某二叉树T的顺序存储映像，请绘制这颗二叉树T，并设表示《电路理论》课程
成绩的结点为A，请回答：
① 哪些结点是结点A的兄弟？结点A的度是多少？并绘制由该二叉树所表示的森林。 ② 给出对该二叉树的进行前序、中序、后序和层次遍历而得到的访问序列。 ③ 画出将二叉树T调整为最小堆的全过程。
3、 设某系统在通信联络中采用0,1,2,3,4,5,6,7,8,9,X共11个字符来描述具体的通信内容，设
这11个字符在某通信报文中的出现次数列表即为线性表L，试为其设计赫夫曼编码，并利用的所设计的Huffman编码对你自己的身份证号进行编码，写出编码过程和结果。
堆栈和队列部分：
1、 设计求解24点问题的相关算法；
3
2、 设计算法，求解杨辉三角问题；
算法综合部分：
1、 利用分而治之策略和递归算法求解九连环和梵塔问题，并分析求解其最短的执行步数。
若有可能，请将递归算法转成改写相应的非递归算法。 2、 利用回溯搜索算法求解连连看问题。 3、 利用回溯搜索算法求解立体迷宫问题。 4、 利用分支定界算法求解迷宫最短路径问题。 5、 利用贪婪算法求解对对碰问题。
九连环问题：下环
若要将n个环全部从钢梁上取下来，需要经过下列步骤： DownLink(n){
将n-2个环全部取下； DownLink(n-2); 将第n个环取下； DownLink(n); 将n-2个环放上钢梁； UpLink(n-2);
将n-1个环全部取下。 DownLink(n-1);}
九连环问题：上环
若要将n个环全部按移动规则放上钢梁，需经过下列步骤： UpLink(n){ 将n-2个环全部放上钢梁； UpLink(n-2); 第n个环放上钢梁； UpRing(n); 将n-2个环取下； DownLink(n-2); 将n-1个环全部放上钢梁 UpLink(n-1);} 九连环问题：最短步数（计算） ······
笔试考核注意事项：
算法设计题：
① 求写出算法设计思想，否则将失分； ② 用伪C代码/C描述算法；
③ 对所设计的算法进行时间和空间复杂度分析
认真、谨慎地审题，耐心、仔细地答题，严格按题目要求完成试题！
4
2010-11-9
因篇幅问题不能全部显示，请点此查看更多更全内容