查找(相关试题)数据结构

《查找(相关试题)数据结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》（C语言版）第9章查找计算机与信息工程学院于江德复习提要查找方法比较式查找法计算式查找法基于树的查找法基于线性表的查找法分块（或索引顺序表）查找法折半（或二分）查找法顺序查找法对存储结构和关键字排列方式没有特殊要求只适合顺序存储的有序表另建一个索引表，分块有序，块间可用折半查找，块内顺序查找二叉排序树平衡二叉树（AVL）B-树B+树——哈希法/散列法/杂凑法在记录存储位置与关键字之间建立确定的关系——哈希函数左子树上所有节点的值<根节点的值<右子树上所有节点的值左、右子树深度之差的绝对值不超过1的二叉排序树一种平衡的多路查找树，m叉树B-树的变型树，关键字信息全部在叶子结点中

2、，其它结点是其索引21.某顺序存储的表格中有90000个元素，已按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字的值皆不相同。用顺序查找法查找时，平均比较次数约为（）A．25000B．30000C．45000D．9000032.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为()。A.(n-1)/2B.n/2C.(n+1)/2D.n42’.对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找到表中任一元素的平均查找长度为（）。A．n/2B．（n+1）/2C．（n－1）/2D．n/453.下面关于二

3、分查找的叙述正确的是()A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序且表中数据必须是整型，实型或字符型C.表必须有序，而且只能从小到大排列D.表必须有序，且表只能以顺序方式存储64.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数为（）A.37/12B.35/12C.39/12D.43/127先看一个具体的情况，假设：n=11分析折半查找的平均查找长度639141025781112判定树1223333444412485.适用于折半查找的表的存储方式及元素排列要求为()A．链接方式存储，元素无序B．链接方式存储，

4、元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序96.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时,（）次比较后查找成功。A.1B.2C.4D.8107.具有12个关键字的有序表，折半查找的平均查找长度（）A.3.1B.4C.2.5D.5118.当采用分块查找时，数据的组织方式为()A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D.数据分成若干块，每块（除最

5、后一块外）中数据个数需相同129.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()A．（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，120，110，130）D.(100，80，60，90，120，130，110)1310.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作()型调整以使其平衡。A.LLB.LRC.RLD.RR14如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构

6、，使之恢复平衡。我们称调整平衡过程为平衡旋转。现分别介绍这四种平衡旋转。平衡旋转可以归纳为四类：LL平衡旋转RR平衡旋转LR平衡旋转RL平衡旋转15若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。(以B为旋转轴）ABCABC若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转。(以B为旋转轴）2）RR平衡旋转：ABCABC1）LL平衡旋转：16若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。(以插入的结点C为旋转轴）4）RL平衡旋转：ABCABCABC若在A的左子树

7、的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。(以插入的结点C为旋转轴）ABCABCABC3）LR平衡旋转：这种调整规则可以保证二叉排序树的次序不变171．B-树的定义B-树是一种平衡的多路查找树：18在m阶的B-树，或为空树，或为满足下列特性的m叉树：（1）树中每个结点至多有m棵子树；（2）若根结点不是叶子结点，则至少有两棵子树；（3）除根之外的所有非终端结点至少有m