数据结构形考作业

已知序列（17，18，60，40，7，32，73，65，85）请给出采用冒泡排序法对该序列作升序排列时的每一趟结果。

原始序列：256,301,751,129,937,863,742,694,076,438 第1趟：256,301,129,751,863,742,694,076,438,937 第2趟：256,129,301,751,742,694,076,438,863,937 第3趟：129,256,301,742,694,076,438,751,863,937 第4趟：129,256,301,694,076,438,742,751,863,937 第5趟：129,256,301,076,438,742,694,751,863,937 第6趟：129,256,076,301,438,742,694,751,863,937 第7趟：129,076,256,301,438,742,694,751,863,937 第8趟：129,076,256,301,438,742,694,751,863,937 第9趟：129,076,256,301,438,742,694,751,863,937 题目41

（1）利用筛选过程把序列{42，82，67，102，16，32，57，52}建成堆（小根堆），画出相应的完全二叉树（不要求中间过程）。

（2）写出对上述堆对应的完全二叉树进行中序遍历得到的序列。 (1) 堆 初始树 （2）102,52,42,82,16,67,32,57 题目42

设查找表为（20，19，24，57，68，11）

（1）用冒泡对该表进行排序，要求写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多少趟冒泡？第j趟要进行多少次元素间的比较？

（2）在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。（要求以数据元素作为树结点）

（3）求在等概率条件下，对上述有序表成功查找的平均查找长度。 （1）原序列16 15 20 53 64 7

15 16 20 53 7 64 n-1趟 15 16 20 7 53 64 n-j次 15 16 7 20 53 64 7 15 16 20 53 64

(2)

（3）平均查找长度=（1*1+2*2+3*3）/6=14/6 题目43

如下是一棵二叉排序树，A1，A2，…，A9代表1，2，3，……，9中各个不同数字， （1）给出对该树中序遍历的结果。 （2）A3，A5，A7的值各为多少？

（3）请在该树中再插入一个结点作为叶结点，并使它仍然是一棵二叉排序树。 （1）A7 A4 A8 A2 A5 A9 A1 A3 A6 (2)8 5 1 （3）