树和二叉树：纸质作业
一、已知二叉树T逻辑结构如下图所示，请分别用顺序存储和二叉链表存储法表示此树。
二、将下面的森林F=﹛T1，T2，T3﹜转换为对应的二叉树，并写出相应二叉树的先根遍历序列。
三、将下列由三棵树组成的森林转换为二叉树，并写出相应二叉树的中根遍历序列
B A C D E F K H L G I J M N O P 四、已知树T的孩子链表存储结构如图所示，试画出此树逻辑结构，以及此树转换成的二叉树逻辑结构，并写出二叉树的后根遍历序列
五、设一棵二叉树的先序序列为：A B D F C E G H 中序遍历序列为： B F D A G E H C （1）画出这棵二叉树。
（2）将这棵二叉树转换成对应的树（或森林）。 六、给定集合{15,3,14,2,6,9,16,17}
（1）构造相应的huffman树（规定：二叉树中两个结点，权值小的结点居左） （2）计算它的带权路径长度
（3）写出它的huffman编码：（规定：左子树编码为0，右子树编码为1,左小右大） 七、假设通信电文使用的字符集为{a,b,c,d,e,f}，各字符在电文中出现的频度分别为：0.34，0.05，0.12，0.23，0.08，0.18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子节点的权值小于右孩子节点的权值，左分支表示字符“0”，右分支表示字符“1”)，然后分别写出每个字符对应的编码。
八、假定教室中有A、B、C、D、E五个设备，需编写一套指令集对五个设备进行自动开关控制，五个设备一天中的使用次数分别是7，5，2，4，9次。为使得指令集长度最短，请对五个设备进行编码，要求画出哈夫曼树，并写出五个设备所对应的哈夫曼编码。
九、假定用于通讯的电文仅有8个字母C1，C2，?，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树，并写出8个字符的哈夫曼编码
十、A,B,C,D,E的权值为{3, 2, 4, 5, 1}，用此权值构造哈夫曼（Huffman）树，并求此哈夫曼（Huffman）树和各个字符的哈夫曼编码（左分支为0，右分支为1）
纸质作业2：排序
一、初始关键字序列如下：{49，38，65，97，76，13，27，49，55 04}，请写出它们的希尔排序的全过程(其中d=5,3,1）
二、给定的关键字序列21，22，27，78，40，05，47，69，12，99，要按升序排序，请写出采用冒泡排序法前3趟的结果，和用堆排序法选择出最大和次大关键字的结果（图）
三、已知某文件的记录关键字集为{50，10，75，40，45，85，80}，写出快速排序方法进行排序的前2次划分的结果
四、已知某文件的记录关键字集为{50，10，30，40，45，85，80}，要从小到大进行排序，请分别写出直接插入排序的前2趟结果和直接选择排序的前3趟结果。 五、设要将序列（17,8,3,25,16,1,13,19,18,4,6,24）中的关键字按升序重新排列，请给出对该序列进行冒泡排序的第一趟排序结果、及以第一个元素为枢轴的快速排序的第一次划分的结果。
纸质作业3：查找
一、设哈希（Hash）表的地址范围为0～13，哈希函数为：H（K）＝K MOD 13。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：
（23，24，32，4，31，30，46，47）造出Hash表，试回答下列问题： （1） 画出哈希表的示意图；
（2） 若查找关键字30，需要依次与哪些关键字进行比较？ （3） 若查找关键字14，需要依次与哪些关键字比较？ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
二、请用序列（45，24，53，12，37，93）建立一棵二叉排序树，画出该树，并求在等概率情况下，查找成功的平均查找长度。
三、选取哈希函数H(key)＝keyMod 11，用线性探测再散列开放定址法解决冲突。试在0～10的散列地址空间内对关键字序列?19、11、31、23、17、27、41、13、91、61?构造哈希表，并计算在等概率下成功查找的平均查找长度。
四、设有一组关键字{9,1,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的线性探测再散列方法解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
五、设哈希（Hash）表的地址范围为0～17，哈希函数为：H （K）=K MOD 16，K为关键字，用线性探测再散列法处理冲突，输入关键字序列：{10，24，32，17，31，30，46，47，40，63，49}造出哈希表，试回答下列问题：
（1）画出哈希表示意图；
（2）若查找关键字63，需要依次与哪些关键字比较? （3）若查找关键字60，需要依次与哪些关键字比较?
（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 六、对于序列：12，16，23，34，45，57，78，91，95，100，112进行二分法查找：
（1）画出二分查找判定树
（2）求出等概率情况下，该二分查找的ASL？
（3）查找元素95需要经过几次比较？和哪些元素比较？
（4）查找元素20需要经过几次比较确定找不到？和哪些元素比较？
七、已知如下所示长度为12的表(34,25,68,72,21,15,49,29,77,8,19,102)
（1）按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树
（2）并求其在等概率的情况下查找成功的平均查找长度。