1简述快速排序算法的基本思想。

2二叉树T的前序遍历序列和中次遍历序列分别是ABCDEFG和CBEDAFG，试画出该二叉树，并写出二叉树的后序遍历序列和层次遍历序列。

3假设字符a,b,c,d,e,f,g,h的使用频度分别是0.15,0.19,0.07,0.08,0.04,0.23，0.13，0.11画出哈夫曼树并写出a,b,c,d,e,f,g,h的Huffman（哈夫曼）编码。

4画出对关键字序列（5，12，20，32，38，45，60，72，90，100）进行折半查找得到判定树，并求出关键字在等概率情况下查找成功的平均查找长度。

5画出二叉树的五种基本形态。

6用序列（46，88，45，39，70，58，101，10，66，34）建立一个二叉排序树，画出建立二叉排序树的过程。

7设哈希（Hash）表的地址范围为0到17，哈希函数为：H（K）＝K MOD16。

K关键字，用线性探测法再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）构造Hash表，试回答下列问题：
(1)（4分）画出哈希表的示意图；
(2)（4分）若查找关键字63，需要依次与哪些关键字进行比较？
(3)（2分）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

8已知一组元素的排序码为（36，25，48，12，65，20），写出用直接插入排序法每次向前面有序表插入一个元素后的排列结果。

9已知如下所示长度为10的表（45，12，32，20，75，25，8，50，90，64），按表中元素顺序构造一棵二叉排序树。

并求在等概率情况下查找成功的平均查找长度。

10写出快速排序的思想，并写出下列序列一趟快速排序的结果，（49，38，65，20，76，13，27，80，50）
11设一个散列表长度为13，散列函数采用H（key）=key%13，并用线性探测再散列解决冲突，将下列关键码（19、14、23、01、68、20、84、27、55、11、10）散列到表中，求等概率情况下查找成功时的平均查找长度。

12判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。

（1）100，85，98，77，80，60，82，40，20，10，66
（2）100，85，40，77，80，60，66，98，82，10，20
（3）10，20，40，60，66，77，80，82，85，98，100
13试写出循环队列判空和判满的条件（队列最大容量为M）。

14已知长度为l2的表{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}，试按表中元素的次序依次插入一棵初始为空的二叉排序树，大小按字母序，请画出插入之后的二叉排序树，并求在等概率情况下查找成功的平均查找长度。

15设一个散列表包含hashSize=13个表项，其下标从0到12，散列函数采用除留余数法H （key）=key%13，并采用线性探测再散列解决冲突，将下列关键码（10、100、32、45、58、126、3、29、200、400）散列到表中，并求等概率情况下查找成功时的平均查找长度。

16将关键字序列（7、8、30、11、18、9、14）散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组，散列函数为：H（key）=（key×3）MOD10，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。

问题：
（1）请画出所构造的散列表；
（2）分别计算等概率情况下，查找成功和查找不成功的平均查找长度。