《数据结构》作业5
得 分：
教师签名： 第八章 查找
一、 填空题
1、以顺序查找方法从长度为n的线性表中查找一个元素时，平均查找长度为_____________，时间复杂度为________________。
2、以二分查找方法从长度为n的线性表中查找一个元素时，平均查找长度小于等于_____________，时间复杂度为________________。
3、以二分查找方法从长度为12的有序表中查找一个元素时，平均查找长度为________________。
4、以二分查找方法查找一个线性表时，此线性表必须是_________________的________________表。
5、从有序表（12，18，30，43，56，78，82，95）中依次二分查找43和56元素时， 其查找长度分别为___________和_____________。
6、对于二分查找所对应的判定树，它既是一棵__________又是一棵____________。 7、假定对长度n=50的有序表进行二分查找，则对应的判定树高度为____________， 判定树中前5层的结点数为______________，最后一层的结点数为____________。 8、在索引表中，每个索引项至少包含____________域和__________域这两项。 9、 假定一个线性表为（12，23，74，55，63，40，82，36），若按Key%3条件进行划分，使得同一余数的元素成为一个子表，则得到的三个子表分别为： __________________、___________________和_______________________。 10、 在索引表中，若一个索引项对应主表中的一条记录，则称此索引为__________索引，若对应主表中的若干条记录，则称此索引为_____________索引。
11、 在稀疏索引表上进行二分查找时，若当前查找区间为空，则不是返回-1表示查
第 37 页 共 49 页
找失败，而是返回该区间的____________。
12、假定长度n=100的线性表进行索引查找，并假定每个子表的长度均为n，则进行索引查找的平均查找长度为_____________，时间复杂度为_____________。 13、 对长度n =10000的线性表进行二级索引查找，每级索引表中的索引项是下一级20个记录的索引，则一级索引表的长度为_____________，二级索引表的长度为_________。
14、 在线性表的_____________存储中，无法查找到一个元素的前趋或后继元素。 15、 在线性表的__________存储中，对每一个元素只能采用顺序查找。
16、 假定对线性表（38，25，74，52，48）进行散列存储，采用H(K)=K % 7作为 散列函数，若分别采用线性探查法和链接法处理冲突，则对各自散列表进行查找的平均查找长度分别为____________和____________。
17、 假定要对长度n=100的线性表进行散列存储，并采用链接法处理冲突，则对于长度m=20的散列表，每个散列地址的单链表的长度平均为_____________。 18、在线性表的散列存储中，处理冲突有____________和_____________两种方法。 19、 对于一棵含有N个关键字的m阶B_树，其最小高度为____________，最大高度为________________。
20、已知一棵3阶B_树中含有50个关键字，则该树的最小高度为____________， 最大高度为________________。
21、 一棵9阶B_树中，每个非树根结点的关键字数目最少为____________个，最多为________________个。
22、 在一棵m阶B_树中，每个非树根结点的关键字数目最少为____________个，最多为__________个，其子树数目最少为___________，最多为___________。 23、 在一棵B_树中，所有叶子结点都处在____________上，所有叶子结点中空指针数等于所有__________总数加1。
24、 散列存储是根据元素的____________计算存储地址的一种存储方法，此地址称为____________地址。
25、 分块查找是____________查找中的一种特例。
第 38 页 共 49 页
二、 应用题
1、 设有序顺序表中的元素依次为12，23，26，37，54，60，68，75，82，96。试画出对其折半查找时的判定树，并计算查找成功时的平均查找长度。
2、 在序列{ 3，8，12，30，36，38，42，50，68 }中，用折半查找法查找关键字32时，需要在哪个区间内和哪些元素进行比较，做多少次比较?
第 39 页 共 49 页
3、 假定一个待散列存储的线性表为(32，75，29，63，48，94，25，46，18，70)，散列地址空间为HT[13]，若采用除留余数法构造散列函数，处理冲突采用线性探查法，试求出每个元素的散列地址，画出最后得到的散列表，求出平均查找长度。
第 40 页 共 49 页
相关推荐：
loading