南京工业大学数据结构
作业答案作业
集团标准化工作小组 [Q8QX9QT-X8QQB8Q8-NQ8QJ8-M8QMN]
第六次作业
1. 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
（1） 画出描述折半查找过程的判定树；
（2） 若查找元素54，需依次与哪些元素比较 （3） 若查找元素90，需依次与哪些元素比较
（4） 假定每个元素的查找概率相等，求查找成功时的平均查找长度。 2. 设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。
K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出Hash表，试回答下列问题： （1） 画出哈希表的示意图；
（2） 若查找关键字63，需要依次与哪些关键字进行比较 （3） 若查找关键字60，需要依次与哪些关键字比较
（4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
3. 在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。
4. 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。
1. 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
（5） 画出描述折半查找过程的判定树；
（6） 若查找元素54，需依次与哪些元素比较 （7） 若查找元素90，需依次与哪些元素比较
（8） 假定每个元素的查找概率相等，求查找成功时的平均查找长度。
解：
（1） 先画出判定树如下（注：mid=(1+12)/2=6）：
30
5 63
3 7 42 87
4 24 54 72 95
(2) 查找元素54，需依次与30, 63, 42, 54 等元素比较； (3) 查找元素90，需依次与30, 63,87, 95, 72等元素比较；
（4） 求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；
但最后一层未满，不能用8×4，只能用5×4=20次， 所以ASL＝1/12（17＋20）＝37/12≈
2. 设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。
K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出Hash表，试回答下列问题：
（5） 画出哈希表的示意图；
（6） 若查找关键字63，需要依次与哪些关键字进行比较 （7） 若查找关键字60，需要依次与哪些关键字比较
（8） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 解： （1）画表如下： 0 1 2 63 3 49 4 5 6 7 8 24 9 40 10 10 11 12 13 14 30 15 31 16 46 17 47 32 17 （2） 查找63,首先要与H(63)=63=15号单元内容比较，即63 vs 31 ,no; 然后顺移，与46,47,32,17,63相比，一共比较了6次！
（3）查找60,首先要与H(60)=60=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。
（4） 对于黑色数据元素，各比较1次；共6次；
对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次， 所以ASL=1/11（6＋2＋3×3）＝17/11=1.≈
3. 在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。 答：
12
7 17
2 11 16 21 4 9 13
验算方法： 用中序遍历应得到排序结果： 2,4,7,9,11,12,13,16,17，21
4. 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。
解：注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别：“若一棵非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结点的值不大于右子树的根的值，则是二叉排序树”
（即不能只判断左右孩子的情况，还要判断左右孩子与双亲甚至根结点的比值也要遵循（左小右大）原则）。
若要采用递归算法，建议您采用如下的函数首部：
bool BisortTree(BiTree T, BiTree&PRE)，其中PRE为指向当前访问结点的前驱的指针。
（或者直接存储前驱的数值，随时与当前根结点比较） 一个漂亮的算法设计如下：
int last=0, flag=1; // last是全局变量，用来记录前驱结点值，只要每个结点都比前驱大就行。
int Is_BSTree(Bitree T) //判断二叉树T是否二叉排序树，是则返回1，否则返回0 {
if(T->lchild&&flag) Is_BSTree(T->lchild);
if(T->data
if(T->rchild&&flag) Is_BSTree(T->rchild); return flag; }//Is_BSTree
南京工业大学数据结构作业答案作业
