查找相关试题数据结构.ppt

查找相关试题数据结构1复****提要查找方法比较式查找法计算式查找法基于树的查找法基于线性表的查找法分块(或索引顺序表)查找法折半(或二分)查找法顺序查找法对存储结构和关键字排列方式没有特殊要求只适合顺序存储的有序表另建一个索引表,分块有序,块间可用折半查找,块内顺序查找二叉排序树平衡二叉树(AVL)B-树B+树——哈希法/散列法/杂凑法在记录存储位置与关键字之间建立确定的关系——哈希函数左子树上所有节点的值<根节点的值<右子树上所有节点的值左、右子树深度之差的绝对值不超过1的二叉排序树一种平衡的多路查找树,m叉树B-树的变型树,关键字信息全部在叶子结点中,其它结点是其索引21. 某顺序存储的表格中有90000个元素,已按关键字值升序排列,假定对每个元素进行查找的概率是相同的,且每个元素的关键字的值皆不相同。用顺序查找法查找时,平均比较次数约为() . 若查找每个记录的概率均等,则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度ASL为()。A.(n-1)/.(n+1)/’. 对长度为n的有序单链表,若查找每个元素的概率相等,则顺序查找到表中任一元素的平均查找长度为()。 B.(n+1)/2C.(n-1)/2 . 下面关于二分查找的叙述正确的是(),表可以顺序方式存储,,,,且表只能以顺序方式存储64. 有一个长度为12的有序表,按二分查找法对该表进行查找,在表内各元素等概率情况下,查找成功所需的平均比较次数为() /12 ,假设:n=11分析折半查找的平均查找长度639141025781112判定树1223333444412485. 适用于折半查找的表的存储方式及元素排列要求为(),,,,元素有序96. 有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时,()次比较后查找成功。