数据结构与算法复习提纲
线性表部分：
1、 顺序表的基本操作：创建、插入、删除、查找、修改、遍历、
输出
2、 带头结点单链表的基本操作：创建、插入（头插、尾插、任意
位置插入）、删除（头删、尾删、任意位置删除）、查找、修改、定位、输出、求表长、遍历的基本应用
3、 带头结点的循环单链表的基本操作：创建、插入（头插、尾插、
任意位置插入）、删除（头删、尾删、任意位置删除）、查找、修改、定位、输出、求表长、遍历的基本应用
4、 线性表的应用：有序顺序表的插入；有序单链表的插入；顺序
表的逆置、单链表的逆置；顺序表归并、单链表归并 栈和队列部分：
1、 顺序栈的基本操作：创建、入栈、出栈、取得栈顶元素（注意
top变量的取值）、判栈空、判栈满、遍历
2、 链栈的基本操作：创建、入栈、出栈、判栈空、遍历 3、 循环队列的基本操作：创建、入队、出队、队空队满的判定条
件、求队列长度、遍历；
4、 链队列的基本操作：创建、入队、出队、队空、遍历 5、 表达式求值：栈中数据的变化过程 树和二叉树
1、 二叉树的5个基本性质
2、 二叉树的顺序存储结构
3、 二叉链表存储，相关的基本操作：前中后三种遍历、层次遍历、
创建、求结点个数、求叶子个数、求深度、基于遍历的应用 4、 树的孩子兄弟链表存储结构，相关的基本操作：创建、查找某
个结点的孩子、插入一个结点、遍历输出
5、 树的孩子兄弟链表存储结构，相关的基本操作：创建、求深度、
先根遍历、插入结点
6、 二叉树、树与森林的应用：由两种遍历序列确定一棵二叉树；
二叉树的三种遍历序列；由两种遍历序列确定一棵树；树（森林）与二叉树之间的相互转换；
7、 哈夫曼树及其应用：构造哈夫曼树、哈夫曼编码、求wpl；注
意：构造哈夫曼树过程相关存储结构的变化 图的部分
1、 图的基本概念
2、 图的邻接矩阵存储结构：创建、深度遍历、广度遍历 3、 图的邻接表存储结构：创建、深度遍历、广度遍历 4、 最小生成树：prim算法、kruscal算法 5、 最短路径：迪杰斯特拉算法、floyd算法 6、 拓扑排序、关键路径 查找与排序部分
1、 带哨兵的顺序查找：算法、ASL
2、 折半查找：算法、查找判定树、成功与不成功的ASL
3、 二叉排序树的构造、平衡二叉树的构造、成功与不成功的ASL 4、 哈希表：构造、线性探测、二次探测、拉链法；成功与不成功
的ASL
5、 直接插入排序、希尔排序、冒泡排序、快速排序， 一趟排序
的结果。
试卷样题
1、 假设通信电文使用的字符集为{a,b,c,d,e,f}，字符在电文中出现的频率分别为34，5，12，23，8，18。请构造哈夫曼树（要求树中左孩子结点的权值小于右孩子结点的权值），并设计哈夫曼编码(10分)。
2、设一棵二叉树的前序序列为1，2，3，4，5，6，7，8，9，其中序序列为2，3，1，5，4，7，8，6，9，试画出该二叉树(10分)。
3、已知无向图G，V(G)={1，2，3，4}，E(G)={(1，2)，(1，3)，(2，3)，(2，4)，(3，4)}，试画出G的邻接表。并简述，已知点i时，如何在邻接表上找到与i点相邻的所有点(10分)。
4、给定关键字序列{ 55， 31， 11， 37， 46， 73， 63， 02， 07 } （1）构造平衡二叉树，画出每加入一个新结点时二叉树的形态。若发生不平衡，指明需做的平衡调整类型及调整的结果(8分)。
（2）计算该平衡二叉树在等概率下查找成功的平均查找长度(2分)。 5、设散列表的长度为13，散列函数为H（h）= k，给定的关键字序列为19，14，23，01，68，20，84，27。试画出用线性探测法解决冲突时所构成的散列表(10分)。
6、设待排序序列为{10，18，4，3，6，12，1，9，15，8}，请给出希尔排序一趟的结果。增加量序列为5。（5分）
7、 图示为有向图，用Dijkstra算法求出从源点1到其它各顶点的最短路径。
5 2 8 4 9 10 2 2 4 20 1 15 6 3
8、试简述一种判定有向图G中是否有环（回路、圈）的方法(5分)。 9、给定如下有向图，完成问题（15分）。
1）从顶点V1出发的深度优先遍历序列； 2）从顶点V1出发的广度优先遍历序列；
3）求从V1到V8的关键路径。要求过程：计算每个顶点的最早、最晚发生时间；每项活动最早、最迟开始时间。
10、以顺序表为存储结构，写一算法，删除线性表中从第i个元素开始的k个元素(10分)。
11、用带头结点的循环链表作为队列的存储表示，不设头指针而只设一个尾指针rear指向队尾结点。试写出该链式队列的入队和出队算法(10分)。
复习题目：
一、
应用题
练习题1
1、 画出满足以下条件的二叉树形态
1） 前序和中序遍历序列相同 2） 中序和后序遍历序列相同 3） 前序和后序遍历序列相同
2、 已知一棵含有n个结点的树中，只有度为0和度为k的结点，求叶结点
的个数？要求写出求解过程。
3、 一棵度为3的树中,度为3的结点数为2个，度为2的结点数为1个，度
为1的结点数为2个，求度为0的结点数？写出求解过程。 4、 设权W=（0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10） (1) 构造哈夫曼树，求WPL(8分)。
(2) 写出这8个字母的哈夫曼编码（2分）。 5、 对森林做以下操作：
(1)转换成二叉树
(2)给出二叉树的三种遍历序列
6、 假设用于通讯的电文由8个字母组成，字母在电文中出现的频率分别为
7，19，2，6，32，3，21，10，
7、 已知一棵树的先根遍历序列为GFKDAIEBCHJ，后根遍历序列为
DIAEKFCJHBG，画出该树。
8、 假设一棵二叉树的中序序列为cbedahgijf和后序序列为cedbhjigfa。
(1)请画出该二叉树 (2)给出其先序遍历序列
9、 已知无向图如下所示，回答问题：
1）写出邻接矩阵；（4分）
2）在邻接矩阵存储上，写出以顶点1作为源点的深度优先遍历序列；（3分）