说明：
上机作业3道，10分 平时作业4道，10分
交作业时间：
上机时间地点：新校区 B603,606，第4、5、7周周六晚上6点——9点。
上机作业一：第5、6、8周周五之前交上一次上机作业 作业邮箱：dlut.zhangsw@
平时作业：交纸质作业 作业一：第4周周五下课 作业二：第6周周二下课 作业三：第7周周二下课
作业四：第8周周五下课（没学的请自己预习后写好）
所有作业请按时交纳，不收补交作业。
线性表
上机作业一：
1． 将顺序表逆置，要求用最少的附加空间。
2． 从键盘读入n 个整数（升序），请编写算法实现： （1） CreateList()：建立带表头结点的单链表； （2） PrintList()：显示单链表，（形如：H->10->20->30->40）; （3） InsertList()：在有序单链表中插入元素x ； （4） ReverseList()：单链表就地逆置；
（5） DelList()：在有序单链表中删除所有值大于mink 且小于maxk 的元素。
选作：使用文本菜单完成功能选择及执行。
栈、队列、数组。
作业一：
1． 若进栈序列为ABCD ，请写出全部可能的出栈序列和不可能的出栈序列。
2． 简要说明循环队列如何判断队满和队空？ 3． 设A 为n 阶对称矩阵，采用压缩存储存放于一维数组F[n(n+1)/2]中（从F[0]
开始存放），请分别给出存放上三角阵时任一矩阵元素a ij （1≤i,j ≤n ）的地址计算公式和存放下三角阵时任一矩阵元素a ij （1≤i,j ≤n ）的地址计算公式。
4． 写出下面稀疏矩阵的三元组顺序表和十字链表表示。
4000005030080
000000
00700A ⎡⎤⎢⎥⎢⎥⎢⎥
=⎢⎥
⎢
上机作业二
栈采用顺序栈存储，试设计算法实现将表达式转换成后缀表达式输出。
例如，输入表达式： a+b/c-(d*e+f)*g 输出其后缀表达式：abc/+de*f+g*-
树
作业二：
1． 请分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
2． 已知二叉树的先序遍历序列是EABDCFHGIKJ ，中序遍历序列是ABCDEFGHIJK ，
请构造二叉树，并写出其层次遍历序列和后序遍历序列。
3． 将下图所示的森林转换成一棵二叉树。
A
B C D G
H I J K
E F
L
4． 将下图所示的二叉树还原成树或森林。
A
B
C
D
G
H
I
J
K
E
F
L
M
N
5． 假设用于通信的电文由7个字母组成{A,B,C,D,E,F,G}，字母在电文中出现
的频率分别为0.17、0.09、0.12、0.06、0.32、0.03、0.21。
试为这7个字母设计哈夫曼编码，并计算其带权路径长度WPL 。
上机作业三：
二叉树采用二叉链表存储，试设计算法实现：
1．CreateBT (BiTree &T)：从键盘输入二叉树的先序遍历序列字符串（以”#”代表空结点），建立其二叉链表；
如输入：AB#D##CE#F### 则建立如下图所示二叉树的二叉链表 2．ExchangeBT(BiTree T ): 设计递归算法实现二叉树中所有结点的左右孩子交换；
3．CountLeaf(BiTree T, TElemType x, int &count ): 统计以值为x 的结点为根的子树中叶子结点的数目；
4．DispBiTree(BiTree T, int level ) : 按树状打印二叉树。
打印得到：#C
###F ##E A ##D
#B
提示：对于根为T ，层次为level 的子树：
① 打印其下一层(level+1层)右子树； ② 打印根结点；
③ 打印其下一层(level+1层)左子树；
*结点左边的’#’个数为其层次数*
图
作业三
1．已知带权有向图如图所示，画出该图的邻接矩阵存储结构。
2．无向图邻接表存储结构如图所示：
(1) 画出该无向图；
(2) 写出在该邻接表上，从顶点1出发所得到的深度优先遍历(DFS)和广度优先遍历(BFS)序列。
B
C F
A E D
1
2
3
4
5
6
7
8
查找、排序
作业四
1．对下标为1～9的有序表进行折半查找，画出折半查找的判定树；并计算在等概率情况下查找成功的平均查找长度ASL。
2．设有关键字序列{25，40，33，47，12，66，72，87，94，22，5，58}，散列表长12，散列函数为h(key)=key%11，用线性探查再散列、链地址法处理冲突，请分别画出散列表，并计算。
3．已知待排序序列为{50，86，72，41，45，93，57，46}，请写出按下列排序方法进行升序排序时的第一趟排序结果：
①直接插入排序；
②冒泡排序；
③简单选择排序；
④堆排序初建堆序列。
4．设计一种方法，以少于2n-3次的比较在顺序存储的n(n>=2)个数中同时找出最大和最小值。