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

《数据结构》（C语言版）第9章 查找 复习提要 1. ?某顺序存储的表格中有90000个元素，已按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字的值皆不相同。用顺序查找法查找时，平均比较次数约为（ ） A．25000 B．30000 C．45000 D．90000 2. ?若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。 A. (n-1)/2 B. n/2 C. (n+1)/2 D. n 2’. ?对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找到表中任一元素的平均查找长度为（ ）。 A．n/2 B．（n+1）/2 C．（n－1）/2 D．n/4 3. ?下面关于二分查找的叙述正确的是 ( ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储 4. ?有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数为（ ） A. 37/12 B. 35/12 C. 39/12 D. 43/12 5. ?适用于折半查找的表的存储方式及元素排列要求为( ) A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 6. ?有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时,（ ）次比较后查找成功。 A. 1 B. 2 C. 4 D. 8 7. ?具有12个关键字的有序表，折半查找的平均查找长度（ ） A. 3.1 B. 4 C. 2.5 D. 5 8.当采用分块查找时，数据的组织方式为 ( ) A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 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) 10. ?在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。 A. LL B. LR C. RL D. RR 1）LL平衡旋转： 3）LR平衡旋转： 11. m阶B-树是一棵( B ) A. m叉排序树 B. m叉平衡排序树 C. m-1叉平衡排序树 D. m+1叉平衡排序树 12.散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（ D ）方法是散列文件的关键。 A. 散列函数 B. 除余法中的质数 C. 冲突处理 D. 散列函数和冲突处理 13.?下面关于哈希(Hash，杂凑)查找的说法正确的是( C ) A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B．除留余数法是所有哈希函数中最好的 C．不存在特别好与坏的哈希函数，要视情况而定 D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可 14. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key