数据结构第四教学单元测验练习题(答案)_数据结构习题答案4

数据结构第四教学单元测验练习题(答案)由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构习题答案4”。

《数据结构》

2n10．散列函数越复杂越好，因为这样随机性好，冲突概率小.× 11．Hash表的平均查找长度与处理冲突的方法无关。×

12．负载因子(装填因子)是散列表的一个重要参数，它反映散列表的装满程度。√ 13.若散列表的负载因子α

三、填空题

1.顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__（1）n __次。2.在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__（2）5 __。

3.在有序表A[1„20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是____（3）1,3,6,8,11,13,16,19__。4.有序表(12,18,24,35,47,50,62,83,90,115，134)使用二分法查找90时，需___（4）2_次查找成功，查100时，需___（5）4_次才能确定不成功。

5.在n个记录的有序顺序表中进行折半查找，最大比较次数是___（6）log2n+1__。（取下界）

6.平衡因子的定义是___（7）结点的左子树的高度减去结点的右子树的高度___ 7.高度为8的平衡二叉树的结点数至少有___（8）54__个。（参照教材P238：N0=0,N1=1,N2=2,公式Nh=Nh-1+Nh-2+1）

8.动态查找表和静态查找表的重要区别在于前者包含有___（9）插入 _和__（10）_删除__运算，而后者不包含这两种运算。

四、应用题

1.假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题：

(1).画出描述折半查找过程的判定树；

(2).若查找元素54，需依次与那些元素比较?(3).若查找元素90，需依次与那些元素比较?(4).假定每个元素的查找概率相等，求查找成功时的平均查找长度。

2.一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。

3.依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树【华中理工大学 2000 五（10分）】

(1)试画出生成之后的二叉排序树;(2)对该二叉排序树作中序遍历，试写出遍历序列;(3)假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。

4.设哈希函数H（k）=3 K mod 11，散列地址空间为0～10，对关键字序列（32,13,49,24,38,21,4,12）按下述两种解决冲突的方法构造哈希表（1）线性探测再散列（2）链地址法，并分别求出等概率下查找成功时的平均查找长度；