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

《数据结构》（C语言版）第9章查找计算机与信息工程学院于江德复习提要查找方法比较式查找法计算式查找法基于树的查找法基于线性表的查找法分块（或索引顺序表）查找法折半（或二分）查找法顺序查找法对存储结构和关键字排列方式没有特殊要求只适合顺序存储的有序表另建一个索引表，分块有序，块间可用折半查找，块内顺序查找二叉排序树平衡二叉树（AVL）B-树B+树——哈希法/散列法/杂凑法在记录存储位置与关键字之间建立确定的关系——哈希函数左子树上所有节点的值根节点的值右子树上所有节点的值左、右子树深度之差的绝对值不超过1的二叉排序树一种平衡的多路查找树，m叉树B-树的变型树，关键字信息全部在叶子结点中，其它结点是其索引31.某顺序存储的表格中有90000个元素，已按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字的值皆不相同。用顺序查找法查找时，平均比较次数约为（）A．25000B．30000C．45000D．9000042.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为()。A.(n-1)/2B.n/2C.(n+1)/2D.n52’.对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找到表中任一元素的平均查找长度为（）。A．n/2B．（n+1）/2C．（n－1）/2D．n/463.下面关于二分查找的叙述正确的是()A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序且表中数据必须是整型，实型或字符型C.表必须有序，而且只能从小到大排列D.表必须有序，且表只能以顺序方式存储74.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数为（）A.37/12B.35/12C.39/12D.43/12先看一个具体的情况，假设：n=11分析折半查找的平均查找长度639141025781112判定树i1234567891011Ci1223333444412495.适用于折半查找的表的存储方式及元素排列要求为()A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序106.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时,（）次比较后查找成功。A.1B.2C.4D.8117.具有12个关键字的有序表，折半查找的平均查找长度（）A.3.1B.4C.2.5D.5128.当采用分块查找时，数据的组织方式为()A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D.数据分成若干块，每块（除最后一块外）中数据个数需相同139.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()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)1410.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作()型调整以使其平衡。A.LLB.LRC.RLD.RR15如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。现分别介绍这四种平衡旋转。平衡旋转可以归纳为四类：LL平衡旋转RR平衡旋转LR平衡旋转RL平衡旋转16若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。(以B为旋转轴）ABCABC若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转。(以B为旋转轴）2）RR平衡旋转：ABCABC1）LL平衡旋转：17若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。(以插入的结点C为旋转轴）4）RL平衡旋转：ABCABCABC若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。(以插入的结点C为旋转轴）ABCABCABC3）LR平衡旋转：这种调整规则可以保证二叉排序树的次序不变181．B-树的定义B-树是一种平衡的多路查找树：root5015718438202643566278899619在m阶的B-树，或为空树，或为满足下列特性的m叉树：（1）树中每个结点至多有m棵子树；（2）若根结点不是叶子结点，则至少有两棵子树；（3）除根之外的所有非终端结点至少有m/2棵子树；（4）所有的非终端结点结构如下：（n,A0,K1,R1,A1,K2,R2,A2,………,Kn,Rn,An）多叉树的特性20其中，每个非终端结点含有：关键字个数nn个关键字Ki（1≤i≤n）nmn个指向记录的指针Ri（1≤i≤n）n+1个指向子树的指针Ai（0≤i≤n）;（5）所有的叶子结点都出现在同一层次上，并且不带任何信息。多叉树的特性11.m阶B-树是一棵(B)A.m叉排序树B.m叉平衡排序树C.m-1叉平衡排序树D.m+1叉平衡排序树2212.散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（D）方法是散列文件的关键。A.散列函数B.除余法中的质数C.冲突处理D.散列函数和冲突处理2313.下面关于哈希(Hash，杂凑)查找的说法正确的是(C)A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小B．除留余数法是所有哈希函数中最好的C．不存在特别好与坏的哈希函数，要视情况而定D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可2414.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=keyMOD13,散列地址为1的链中有（D）个记录。A．1B.2C.3D.42515.关于杂凑查找说法不正确的有几个(B)（1）采用链地址法解决冲突时，查找一个元素的时间是相同的（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的（3）用链地址法解决冲突易引起聚集现象（4）再哈希法不易产生聚集A.1B.2C.3D.42616.设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是(D)A．8B．3C．5D．92717.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？(D)A．k-1次B.k次C.k+1次D.k（k+1）/2次2818.散列表的地址区间为0-17,散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。（1）元素59存放在散列表中的地址是（D）。A．8B.9C.10D.11（2）存放元素59需要搜索的次数是（C）。A．2B.3C.4D.52919.已知一个线性表（38，25，74，63，52，48），假定采用散列函数h(key)=key%7计算散列地址，并散列存储在散列表A[0…6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为（C）A．1.5B.1.7C.2.0D.2.330参考答案1、CC（2‘、B）DAD6、CABCC你的问题？Thanks！