下列说法中正确的是( )。 Ⅰ.对有2 500个记录的索引顺序表(分块表)进行查找,最理想的块长为50 Ⅱ.顺序查找法只适合于顺序存储结构,不适合于链式存储结构 Ⅲ.折半查找过程所对应判定树是一棵完全二叉树 Ⅳ.理想情况下,散列表的平均比较次数可达到

admin2019-03-15  36

问题 下列说法中正确的是(    )。
Ⅰ.对有2 500个记录的索引顺序表(分块表)进行查找,最理想的块长为50
Ⅱ.顺序查找法只适合于顺序存储结构,不适合于链式存储结构
Ⅲ.折半查找过程所对应判定树是一棵完全二叉树
Ⅳ.理想情况下,散列表的平均比较次数可达到1次

选项 A、Ⅰ、Ⅳ
B、Ⅱ、Ⅲ、Ⅳ
C、Ⅲ、Ⅳ
D、Ⅰ、Ⅱ、Ⅲ、Ⅳ

答案A

解析 Ⅰ:分块查找的平均查找长度不仅和表的总长度n有关,而且和所分的子表个数有关,对于n给定的情况下,s取时,平均查长度取得最小值,所以最理想块长为50,故Ⅰ正确(注意:此题务必记住该结论)。
补充:分块查找的数据组织方式为:数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块。
Ⅱ:顺序查找法就是从线性表的一端开始顺序查找,并且逐个检查关键字是否满足给定的条件。所以顺序存储结构和链式存储结构均适合(表可以无序),故Ⅱ错误。
补充:顺序查找法的平均查找长度。
若查找每个记录的概率相等,则在具有n个记录的连续文件中采用顺序查找法查找一个记录,其平均查找长度为(n+1)/2。查找第一个记录的查找长度为1,查找第n个记录的查找长度为n,并且查找每个记录的概率相等,即均为1/n,则顺序查找法的平均查找长度为

Ⅲ:判定树的结构一定是先排满一层,再排下一层,所以只有最低一层可能不满。并且最低一层的叶子结点也不一定是从左到右按序排放,故不一定是完全二叉树,故Ⅲ错误。
Ⅳ:在理想情况下,散列表通过散列函数可直接计算得到元素的位置,所以平均比较次数可达到1,故Ⅳ正确。
转载请注明原文地址:https://kaotiyun.com/show/zICi777K
0

最新回复(0)