数据结构第九章查找作业及答案Word格式文档下载.docx

1、&设一哈希表表长 M为100，用除留余数法构造哈希函数，即 H（ K） =K MOIP （ P=M ,为 使函数具有较好性能，P应选 o9、 在各种查找方法中，平均查找长度与结点个数无关的是 o10、 对线性表进行二分查找时，要求线性表必须以 方式存储，且结点按关键字 _排列。11在分块查找方法中，首先查找索引，然后再查找相应的 o12. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为 次；当使用监视哨时，若查找失败，则比较关键字的次数为 _ o13.在有序表A1.12中，采用二分查找算法查等于 A12的元素，所比较的元素下标依次为 o14.在有序表A1.20中，按二分查找方法

2、进行查找，查找长度为 5的元素个数是 o15.已知二叉排序树的左右子树均不为空，则 上所有结点的值均小于它的根结点值， 上所有结点的值均大于它的根结点的值。16. 中序遍历二叉排序树得到的序列是 序列（填有序或无序）。17.从有序表（10 , 16, 25, 40, 61, 28, 80, 93）中依次二分查找40和61元素时，其查找长度分别为 和 、单项选择题1在表长为n的链表中进行顺序查找，它的平均查找长度为（ ）A.ASL=n ; B . ASL=（n+l）/2 ;C . ASL= n + 1 ; D . ASLlog 2 （n+l）l2折半查找有序表（4, 6, 10, 12, 20,

3、 30, 50, 70, 88, 100）。若查找表中元素 58，则它将依次与表中（ ）比较大小，查找结果是失败。A.20, 70, 30, 50 B . 30, 88, 70, 50 C . 20, 50 D . 30, 88, 50 3对22个记录的有序表作折半查找，当查找失败时，至少需要比较（ ）次关键字。A. 3 B . 4 C . 5 D . 64.链表适用于（）查找A.顺序 B .二分法 C .顺序，也能二分法 D .随机5.折半搜索与二叉搜索树的时间性能（ ）。A.相同 B. 完全不同 C. 有时不相同 D. 数量级都是0（ log 2n）6. 散列表的地址区间为0-17,散列函

4、数为H（K）=K mod 17。采用线性探测法处理冲突，并将 关键字序列26, 25, 72, 38, 8, 18, 59依次存储到散列表中。元素59存放在散列表中的 地址是（ ）OA. 8 B. 9 C. 10 D. 117.当采用分快查找时，数据的组织方式为 （） 。A.数据分成若干块，每块内数据有序B数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数 据组成索引块C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D.数据分成若干块，每块（除最后一块外）中数据个数需相同8.散列函数有一个共同的性质，即函数值应当以 （） 取其值域的每个值。A.

5、最大概率 B. 最小概率 C. 平均概率 D. 同等概率9.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进 行多少次探测？（）A. k-1 次 B. k 次 C. k+1 次 D. k （k+1） /2 次10. 哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存 入哈希表中，至少要进行（）次探测。A. k B. k+1 C. k（k+1）/2 D.1+k（k+1）/211. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作（） 型调整以使其平衡。A. LL

6、B. LR C. RL D. RR12.二叉查找树的查找效率与二叉树的（） 有关，在（ ）时其查找效率最低（1）树型 D. 结点的位置 呈单枝树 D. 结点太复杂。中，用折半查找算法查找关键: A. 高度 B. 结点的多少 C.（2）: A. 结点太多 B. 完全二叉树 C.13、顺序表 （ 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ） 码值 11，所需的关键码比较次数为（ ）A） 2 B） 3 C） 4 D） 514、对包含 n 个元素的哈希表进行查找，平均查找长度为（ ）A） O（log 2n） B） O（n） C） O（nlog 2n） D） 不直接

7、依赖于 n 15、若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度 ASL为（）。A （n-1）/2 B. n/2 C. （n+1）/2 D. n16.下面关于二分查找的叙述正确的是 （ ）A.表必须有序，表可以顺序方式存储，也可以链表方式存储C. 表必须有序，而且只能从小到大排列B.表必须有序且表中数据必须是整型，实型或字符型D. 表必须有序，且表只能以顺序方式存储17.对线性表进行二分查找时，要求线性表必须（ ）A.以顺序方式存储 B.以顺序方式存储，且数据元素有序C.以链接方式存储 D.以链接方式存储，且数据元素有序18适用于折半查

8、找的表的存储方式及元素排列要求为 （ ）A 链接方式存储，元素无序 B 链接方式存储，元素有序C.顺序方式存储，元素无序 D 顺序方式存储，元素有序19. 用二分（对半）查找表的元素的速度比用顺序法 （ ）A 必然快 B. 必然慢 C. 相等 D. 不能确定20当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但 前者比后者的查找速度 （ ）A.必疋快 B. 不一疋C. 在大部分情况下要快 D.取决于表递增还是递减21. 具有 12 个关键字的有序表，折半查找的平均查找长度（）A. 3.1 B. 4 C. 2.5D. 522. 折半查找的时间复杂性为（A. O（n2）

9、B. O （n）C. O （ nlogn ） D. O（logn ）23设顺序线性表的长度为 30，分成 5块，每块 6 个元素，如果采用分块查找，则其平均查 找长度为（ D ）。（A） 6 （B） 11 （C） 5 （D） 6.524. 二叉排序树的查找效率与二叉树的 （ ） 有关。A. 高度 B. 结点的多少 C. 树型 D. 结点的位置25 在等概率情况下,一棵平衡树的ASL为（）。A. 0（1） B. 0（ Iog2n ） C. O（log2n）2） D.O（nlog2n）26. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是 （）A.（100, 80, 90, 6

10、0 , 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）27.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A,并已知A的左28.下列二叉排序树中，满足平衡二叉树定义的是（ ）。A.根结点至多有m棵子树B所有叶子都在同一层次上C.非叶结点至少有m/2 （m为偶数）或m/2+1 （m为奇数）棵子树D.根结点中的数据是有序的30.下面关于m阶B树说法正确的是（）每个结点至少有两棵非

11、空子树； 树中每个结点至多有 m 1个关键字；所有叶子在同一层上；当插入一个数据项引起B树结点分裂后，树长高一层A. B. C. D. 31、 下面关于B和B+树的叙述中，不正确的是（）A. B树和B+W都是平衡的多叉树。 B. B 树和B+W都可用于文件的索引结构C. B树和B+树都能有效地支持顺序检索。 D. B树和B+树都能有效地支持随机检索32、 下列叙述中，不符合 m阶B树定义要求的是（）A .根节点最多有m棵子树 B.所有叶结点都在同一层上C .各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接33、 设散列表中有m个存储单元，散列函数H（key）= key % p，则p最

12、好选择（ ）（A）小于等于m的最大奇数 （B）小于等于m的最大素数（C）小于等于m的最大偶数 （D）小于等于m的最大合数34、适于对动态查找表进行高效率查找的组织结构是（ ）。A.有序表 B 分块有序表 C 二叉排序树 D 线性链表三、判断题1.查找相同结点的效率折半查找总比顺序查找高。 （ ）2.索引顺序表的特点是块内可无序，块间要有序。3. 在采用线性探测法处理冲突的散列表中，所有同义词在表中一定相邻。4. 在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过 1。（ ）5. 若查找表的长度为n,则顺序查找法的平均查找长度为（n+1）12。6. 折半搜索适用于有序表，包括有序的顺序表和

13、有序的链表。7.采用线性探测法处理散列时的冲突,当从哈希表删除一个记录时,不应将这个记录的所在位置置空,因为这会影响以后的查找。8. 在散列检索中,“比较”操作一般也是不可避免的。9.在m阶B-树中每个结点上至少有 个关键字，最多有m个关键字。10. 负载因子 （ 装填因子 ） 是散列表的一个重要参数,它反映散列表的装满程度。11.散列法的平均查找长度不随表中结点数目的增加而增加， 随负载因子的增大而增大。12.哈希表的结点中只包含数据元素自身的信息，不包含任何指针。13.若散列表的负载因子a 1,则可避免冲突的产生。14. 用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。15.

14、在平衡二叉树中，向某个平衡因子不为零的结点的子树中插入一新结点，一定会引起平 衡旋转。16.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右 孩子的值。17.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。18.对大小均为 n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找 成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。19.任一查找树 （二叉分类树 ）的平均查找时间都小于用顺序查找法查找同样结点的线性表的 平均查找时间。20. 在二叉树排序树中插入一个新结点，总是插入到叶结点下面。21. 顺序查找法适

15、用于存储结构为顺序或链接存储的线性表。四、简答题1.对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性 查找的速度快，这种说法对吗？2.假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答 下列问题：（1） 画出描述折半查找过程的判定树；（2） 若查找元素 54，需依次与哪些元素比较？（3） 若查找元素 90，需依次与哪些元素比较？（4） 假定每个元素的查找概率相等，求查找成功时的平均查找长度。3.设哈希（Hash）表的地址范围为017,哈希函数为：H（ K）= K MOD 16K 为关键字，用线性探测法再散列法处理冲

16、突，输入关键字序列：（ 10, 24, 32, 17, 31 , 30, 46, 47, 40, 63, 49）造出Hash表，试回答下列问题：（1） 画出哈希表的示意图；（ 2） 若查找关键字 63，需要依次与哪些关键字进行比较？（ 3） 若查找关键字 60，需要依次与哪些关键字比较？（ 4 ） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。4、设哈希表长度为11,哈希函数H（ K） = （ K的第一字母在字母表中的序号） M0D1,1若输 入顺序为（D, BA TN M Cl，I，K, X，TA）,处理冲突方法为线性探测再散列或链地址法， 要求构造哈希表 并求出等概率情况下查找

17、成功平均查找长度。5、输入一个正整数序列 100 50 302 450 66 200 30 260 建立一棵二叉排序树 要求： 画出该二叉排序树； 画出删除结点 302 后的二叉排序树。6、 设有一组关键字：19 O1 23 14 55 2O 84 27 68 采用哈希函数：H（key） =key mod 7 采用开放地址法的线性探测再散列方法解决冲突。要求：在Os 11的散列地址空间中对该关键字序列构造哈希表。7、已知如下所示长度为 12 的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec ）（1） 试按表中元素的

18、顺序依次插入一棵初始为空的二叉排序树， 画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。（2） 若对表中元素先进行排序构成有序表， 求在等概率的情况下对此有序表进行折半查找时查 找成功的平均查找长度。（3）按表中元素顺序构造一棵平衡二叉排序树， 并求其在等概率的情况下查找成功的平均查找 长度。8、用开放地址法的二次探测再散列方法 Hi=（H（key）+di） mod10（di=1 2,2 2,3 2, ,） 解决冲突 要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。9、选取散列函数 H（key）=（3*key ）%11，用线性探测法处理冲突，对下列关键

19、码序列构造 一个散列地址空间为 010,表长为11的散列表，22 , 41, 53, 08, 46, 30, 01, 31, 66五、算法设计题1. 已知 11 个元素的有序表为（ 05 13 19 21 37 56 64 75 80 88 92 ）, 请写出折半查找的算法程序，查找关键字为 key 的数据元素。2. 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。 且树中结点的关键字均不同。3.已知一个含有 1000 个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表 设计方案，要求它在等概率情况下查找成功的平均查找长度不超过 3。4.已知某哈希表的装载因子小于 1，哈希函数 H（key） 为关键字（标识符）的第一个字母在字 母表中的序号， 处理冲突的方法为线性探测开放定址法。 试编写一个按第一个字母的顺序 输出哈希表中所有关键字的算法。