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