习题讲解-7-查找

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,集合（查找）,1,1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( C )。【北京航空航天大学 】,A (n-1)/2 B. n/2 C. (n+1)/2 D. n,2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A ) 【南京理工大学】,A（N+1）/2 B. N/2 C. N D. （1+N）*N /2,3顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（ D）,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（C ）。 在此假定N为线性表中结点数，且每次查找都是成功的。【长沙铁道学院】,A.N+1 B.2log2N C.logN D.N/2 E.Nlog2N F.N2,2,4. 下面关于二分查找的叙述正确的是 (D) 【南京理工大学 】,A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列,B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储,5. 对线性表进行二分查找时，要求线性表必须（ B ）【燕山大学 2001 】,A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序,6适用于折半查找的表的存储方式及元素排列要求为( D ) 【南京理工大学 1997】,A链接方式存储，元素无序 B链接方式存储，元素有序,C顺序方式存储，元素无序 D顺序方式存储，元素有序,7. 用二分（对半）查找表的元素的速度比用顺序法( D ) 【南京理工大学 1998】,必然快 B. 必然慢 C. 相等 D. 不能确定,3,8当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( C ),A必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 【南京理工大学 1997】,9. 具有12个关键字的有序表，折半查找的平均查找长度（ A ）【中山大学 1998】,A. 3.1 B. 4 C. 2.5 D. 5,10. 折半查找的时间复杂性为（ D ）【中山大学 1999 】,A. O（n2） B. O（n） C. O（nlogn） D. O（logn）,11当采用分快查找时，数据的组织方式为 ( B ) 【南京理工大学 1996】,A数据分成若干块，每块内数据有序,B数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块,C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块,D. 数据分成若干块，每块（除最后一块外）中数据个数需相同,4,12. 二叉查找树的查找效率与二叉树的( C )有关, 在 (C )时其查找效率最低【武汉交通科技大学1996 】,(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置,(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。,13. 要进行顺序查找，则线性表（ C）；要进行折半查询，则线性表（D ）；若表中元素个数为n, 则顺序查找的平均比较次数为（G ）；折半查找的平均比较次数为（H）。【北方交通大学 】,A. 必须以顺序方式存储； B. 必须以链式方式存储；C. 既可以以顺序方式存储，也可以链式方式存储；D. 必须以顺序方式存储，且数据已按递增或递减顺序排好；,A.n B.n/2 E.log2n F.nlog2n G.(n+1)/2 H.log2(n+1),14在等概率情况下,线性表的顺序查找的平均查找长度ASL为( E ),有序表的折半查找的ASL为( B ),对静态树表,在最坏情况下,ASL为( E ),而当它是一棵平衡树时,ASL为 ( B ),在平衡树上删除一个结点后可以通过旋转使其平衡,在最坏情况下需( B )次旋转。供选择的答案：【上海海运学院】,A. O(1) B. O( log2n ) C. O(log,2,n),2,) D.O(nlog,2,n) E. O(n),5,15. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败,它们的平均查找长度是(B) ,对于查找成功,他们的平均查找长度是(A)供选择的答案: 【上海海运学院 1997 】,A. 相同的 B.不同的,16如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( A)查找法。 【西安电子科技大学 2001】,A. 分快查找 B. 顺序查找 C. 折半查找,17. 既希望较快的查找又便于线性表动态变化的查找方法是 (C ) 【北方交通大学 2000 】,A顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找,18分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(C ) 【合肥工业大学2000】,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),19. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0, 右孩子的平衡因子为1,则应作( C ) 型调整以使其平衡。【合肥工业大学 】,A. LL B. LR C. RL D. RR,6,28. 下面关于哈希(Hash，杂凑)查找的说法正确的是( C ) 【南京理工大学 1998 】,A哈希函数构造的越复杂越好，因为这样随机性好，冲突小,B除留余数法是所有哈希函数中最好的,C不存在特别好与坏的哈希函数，要视情况而定,D若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可,29. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (A) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为 (C) 【南京理工大学 1999 】,（1） A17 B. 13 C. 16 D. 任意,（2） A0至17 B. 1至17 C. 0至16 D. 1至16,7,31. 设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( D ) 【南京理工大学 2001 】,A8 B3 C5 D9,根据哈希函数，求出元素的存储位置，称为散列,二次探测再散列 H= (H(key)+D)MOD M, D=123.线性探测再散列 D = 1,2,-1,2,.2,2,-2,2,二次探测再散列,32. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( D ),Ak-1次 B. k次 C. k+1次 D. k（k+1）/2次,【中国科技大学 1998 】【中科院计算所1998 】,33. 哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行( C )次探测。【西安电子科技大学 1998 】,A k B. k+1 C. k(k+1)/2 D.1+k(k+1)/2,8,35. 散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。 【北方交通大学 2001 】,（1）元素59存放在散列表中的地址是（ D ）。,A 8 B. 9 C. 10 D. 11,（2）存放元素59需要搜索的次数是（C ）。,A 2 B. 3 C. 4 D. 5,36. 将10个元素散列到100000个单元的哈希表中，则（ C ）产生冲突。【北京邮电大学 2001 】,A. 一定会 B. 一定不会 C. 仍可能会,9,4HASH方法的平均查找路长决定于什么？ 是否与结点个数N有关？ 处理冲突的方法主要有哪些？【中国人民大学 2000 】,哈希方法的平均查找路长主要取决于负载因子（表中实有元素数与表长之比），它反映了哈希表的装满程度，该值一般取0.650.9。,8. 设哈希表a 、b分别用向量a0.9,b0.9表示 ，哈希函数均为H（key）=key MOD 7,处理冲突使用开放定址法，Hi=H(key)+DiMOD 10,在哈希表a中Di用线性探测再散列法，在哈希表b中Di用二次探测再散列法,试将关键字19,24, 10,17,15,38,18,40分别填入哈希表a,b中,并分别计算出它们的平均查找长度ASL。【北京工业大学 1998】,10,散列表存储中解决碰撞的基本方法：, 开放定址法 形成地址序列的公式是：Hi=（H（key）+di）% m，其中m是表长，di是增量。根据di取法不同，又分为三种：,adi =1，2，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。,bdi =12，-12，22，-22， ，,k2（km/2） 称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j为整数）的素数时才有可能。,cdi =伪随机数序列，称为随机探测再散列。, 再散列法 Hi=RHi（key） i=1，2，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。, 链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用H0.m-1表示，分量初始值为空指针。凡散列地址为i（0im-1）的记录均插在以Hi为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而中的散列表称闭散列表，含义是元素个数受表长限制。, 建立公共溢出区 设H0.m-1为基本表，凡关键字为同义词的记录，都填入溢出区O0.m-1。,11,12,62. 如图2所示是一棵正在进行插入运算的AVL树，关键码70的插入使它失去平衡，按照AVL树的插入方法，需要对它的结构进行调整以恢复平衡。【北京大学 1997 】,请画出调整后的AVL树。,假设AVL树用llink-rlink法存储，t是指向根结点的指针，请用Pascal(或C)语句表示出这个调整过程。,（说明：不必写出完整的程序，只需用几个语句表示出在本题中所给出的具体情况下调整过程中指针的变化。在调整过程中还有两个指针变量p和q可以使用。）,13,