题目38
已知序列（70，83，100，105，10，32，7，9），请写出对此序列采用插入排序法进行升序排序时各趟的结果。 原始序列：（70），83，100，65，10，32，7，9 第1趟：（70，83），100，65，10，32，7,，9 第2趟：（70，83，100），65，10，32，7，9 第3趟：（65，70，83，100），10，32，7，9 第4趟：（10，65，70，83，100），32，7，9 第5趟：（10，32，65，70，83，100），7，9 第6趟：（7，10，32，65，70，83，100），9 第7趟：（7，9，10，32，65，70，83，100）题目39
已知序列（10，18，4，3，6，12，1，9，15，用归并排序法进行升序排序时各趟的结果。 原始序列：10,18,4,3,6,12,1,9,15,8 第1趟：[10,18][3,4][6,12][1,9][8,15] 第2趟：[3,4,10,18,][1,6,9,12][8,15] 第3趟：[3,4,10,18,][1,6,8,9,12,15] 第4趟：[1,3,4,6,8,9,10,12,15,18] 题目40
已知序列（17，18，60，40，7，32，73，65，序法对该序列作升序排列时的每一趟结果。
），请写出对此序列采85）请给出采用冒泡排 8原始序列：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）请在该树中再插入一个结点9.5作为叶结点，并使它仍然是一棵二叉排序树。
（1）A7 A4 A8 A2 A5 A9 A1 A3 A6 (2)8 5 1 （3）
数据结构形考作业
