作业1.线性表
（1） 在有序单链表中设计一高效算法删除所有值大于mink 且小于maxk 的元
素；思考题：你能将上述算法改为双向循环链表吗？
（2） 将带表头结点的单链表就地逆置
（3） 将顺序表逆置，要求用最少的附加空间
（4） 在有序顺序表中插入x ，插入后仍为有序的。

作业2. 栈、队列、数组
1．若进栈序列为abcd ，请给出全部可能的出栈序列和不可能的出栈序列。

2．循环队列如何判断队满和队空？
3．写出下面稀疏矩阵的三元组顺序表和十字链表表示。

4．设A 为n 阶对称阵，采用压缩存储存放于一维数组F[n(n+1)/2]中（从F[0]
开始存放），请分别给出存放上三角阵时任一矩阵元素aij （1≤i,j ≤n ）的地址
计算公式和存放下三角阵时任一矩阵元素aij （1≤i,j ≤n ）的地址计算公式。

作业3.树与二叉树
一、问答题
1、请分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

2、已知二叉树的先序遍历序列是EABDCFHGIKJ ，中序遍历序列是
ABCDEFGHIJK ，请构造二叉树，并写出其层次遍历序列和后序遍历序列。

3、将图1所示的森林转换成一棵二叉树。

A B C D G H I J K
E F L
图1
4、将如图2所示的二叉树还原成树或森林
400000503008000000000700200000A ⎡⎤⎢⎥⎢⎥
⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦
A
B
C
D
G
H
I J K
E F L L
L
图2
5、假设用于通信的电文由7个字母组成，字母在电文中出现的频率分别为
0.17、0.09、0.12、0.06、0.32、0.03、0.21。

试为这7个字母设计哈夫曼编码，并计算其带权路径长度。

二、二叉树采用二叉链表存储，试设计算法实现：
（1）设计递归算法实现二叉树中所有结点的左右孩子交换。

（2）统计以值为X 的结点为根的子树中叶子结点的数目。

（3）设计算法求二叉树的高
作业4 图
一、简答题：
1. 已知带权无向图如图所示： (1). 根据普里姆（Prim ）算法，求它的从顶点a 出发的最小生成树(写出过程，即添加顶点、边次序)； (2). 根据克鲁斯卡尔（Kruskal ）算法，求该图的最小生成树(写出过程，即添加边次序)。

2．已知带权有向图如图所示： (1). 画出该图的邻接矩阵存储结构； (2). 请写出该图的一个拓扑有序序列；
(3). 求从顶点a 到其余各顶点之间的最短路经及最短路经长度，并给出计算过程。

二、编程题：
用类C 语言设计算法判断有向图中是否存在由顶点v s 到v t 的路径（t s ），要求说明有向图的存储方式。

作业5 查找与排序
一、简答题：
1. 设有关键字序列{25，40，33，47，12，66，72，87，94，22，5，58}，散列
表长12，散列函数为h(key)=key%11，用线性探查再散列、链地址法处理冲突，请分别画出散列表，并计算在等概率情况下的查找成功的平均查找长度。

2. 已知待排序序列为{50，86，72，41，45，93，57，46}，请写出按下列排序
方法进行升序排序时的第一趟排序结果：
①简单排序；
③堆排序初建堆序列；
④冒泡排序。

3．设计一种方法，以少于2n-3次的比较在n个数中同时找出最大和最小值。