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

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