数据结构(本)形考作业答案

本文档如对你有帮助，请帮忙下载支持！

第4趟： 129，256，301，694，076，438，742，751，863，937 第5趟： 129，256，301，076，438，694，742，751，863，937 第6趟： 129，256，076，301，438，694，742，751，863，937 第7趟： 129，076，256，301，438，694，742，751，863，937 第8趟： 076，129，256，301，438，694，742，751，863，937 第9趟： 076，129，256，301，438，694，742，751，863，937

题目41

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

（2）写出对上述堆对应的完全二叉树进行中序遍历得到的序列。 1） （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 15 7 16 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

1 2 3 4 5 6 7 8 9

本文档如对你有帮助，请帮忙下载支持！

(2) 8 5 1

（3）