数据结构第九章复习题

第九章 查找 一、 选择题 1.若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找 一个记录，其平均查找长度 ASL 为( )。 A (n-1)/2 B. n/2 C. (n+1)/2 D. n 2. 下面关于二分查找的叙述正确的是 ( ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且 只能从小到大排列 B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表 只能以顺序方式存储 3. 用二分（对半）查找表的元素的速度比用顺序法( ) A必然快 B. 必然慢 C. 相等 D. 不能确定 4. 具有 12 个关键字的有序表，折半查找的平均查找长度（ ） A. 3.1 B. 4 C. 2.5 D. 5 5当采用分块查找时，数据的组织方式为 ( ) A数据分成若干块，每块内数据有序 B数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小） 的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 6. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 7. 对大小均为 n 的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失 败,它们的平均查找长度是(1) ,对于查找成功,他们的平均查找长度是(2)供选择 的答案: A. 相同的 B.不同的 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 11. 下面关于 m 阶 B-树说法正确的是( ) 每个结点至少有两棵非空子树； 树中每个结点至多有 m 一 1 个关键字; 所有叶子在同一层上; 当插入一个数据项引起 B 树结点分裂后，树 长高一层。 A B. C. D. 12. m 阶 B-树是一棵( ) A. m 叉排序树 B. m 叉平衡排序树 C. m-1 叉平衡排序树 D. m+1 叉平衡排序 树 15. 设有一组记录的关键字为19，14，23，1，68，20，84，27，55，11，10，79，用链 地址法构造散列表，散列函数为 H（key）=key MOD 13,散列地址为 1 的链中有（ ） 个记录。 A1 B. 2 C. 3 D. 4 16. 关于哈希查找说法不正确的有几个( ) （1）采用链地址法解决冲突时，查找一个元素的时间是相同的 （2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是 相同的 （3）用链地址法解决冲突易引起聚集现象 （4）再哈希法不易产生聚集 A. 1 B. 2 C. 3 D. 4 17. 设哈希表长为 14，哈希函数是 H(key)=key%11,表中已有数据的关键字为 15，38，61，84 共四个，现要将关键字为 49 的结点加到表中，用二次探测再散列 法解决冲突，则放入的位置是( ) A8 B3 C5 D9 18. 假定哈希查找中 k 个关键字具有同一哈希值，若用线性探测法把这 k 个关键字存入散 列表中，至少要进行多少次探测？( ) Ak-1 次 B. k 次 C. k+1 次 D. k（k+1）/2 次 19. 好的哈希函数有一个共同的性质，即函数值应当以( )取其值域的每个值。 A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 20. 将 10 个元素散列到 100000 个单元的哈希表中，则（ ）产生冲突。 A. 一定会 B. 一定不会 C. 仍可能会 二、 判断题 1采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所 在位置置空，因为这会影响以后的查找。 （ ） 2在散列检索中， “比较”操作一般也是不可避免的。 （ ） 3Hash 表的平均查找长度与处理冲突的方法无关。 （ ） 4. 散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。 （ ） 5. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元 素个数有关，而且与每块中元素个数有关。 （ ） 6. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（ ） 7 最佳二叉树是 AVL 树（平衡二叉树） 。 （ ） 8在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。 （ ） 9二叉树中除叶结点外, 任一结点 X，其左子树根结点的值小于该结点（X）的值；其右 子树根结点的值该结点（X）的值,则此二叉树一定是二叉排序树。 （ ） 10有 n 个数存放在一维数组 A1n中，在进行顺序查找时，这 n 个数的排列有序或无 序其平均查找长度不同。 （ ） 11. N 个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。 （ ） 12. 在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二 排序叉树相同。 （ ） 13. B-树中所有结点的平衡因子都为零。 （ ） 14. 在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋 转。 （ ） 三、填空题 1. 顺序查找 n 个元素的顺序表，若查找成功，则比较关键字的次数最多为 _ _次；当使 用监视哨时，若查找失败，则比较关键字的次数为_ _。 2在有序表 A112中，采用二分查找算法查等于 A12的元素，所比较的元素下标依次 为_。 3. 在有序表 A120中，按二分查找方法进行查找，查找长度为 5 的元素个数是 _ 4. 高度为 4（含叶子结点层）的 3 阶 b-树中，最多有_个关键字。 5. 在一棵 m 阶 B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原 有的关键字的个数是_;若在某结点中删除一个关键字而导致结点合并,则该结 点中原有的关键字的个数是_。 6. 在哈希函数 H（key）=key%p 中，p 值最好取_。 8. 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序 树检索时，平均比较次数为_。 9. 如果关键码按值排序，而后用二分法依次检索这些关键码，并把检索中遇到的在二叉树 中没有出现的关键码依次插入到二叉排序树中，则对这样的二叉排序树检索时，平均 比较次数为_。 （提示：此时二叉排序树与折半查找的二叉判定树一样了） 10. 平衡因子的定义是_ _ 11. 查找是非数值程序设计的一个重要技术问题，基本上分成_(1)_查找，_(2)_查找 和_(3)_查找。处理哈希冲突的方法有_(4)_、_(5)_、_(6)_和_(7)_。 12. 具有 N 个关键字的 B 树的查找路径长度不会大于_。在一棵有 N 个结点的非 平衡二叉树中进行查找，平均时间复杂度的上限（即最坏情况平均时间复杂度）为 _ 13. 高度为 5（除叶子层之外）的三阶 B-树至少有_个结点。 14. 可以唯一的标识一个记录的关键字称为_。 15. 动态查找表和静态查找表的重要区别在于前者包含有_和_运算， 而后者不包含这两种运算。 16. 已知 N 元整型数组 a 存放 N 个学生的成绩，已按由大到小排序，以下算法是用对分 （折半）查找方法统计成绩大于或等于 X 分的学生人数，请填空使之完善。( 提示：这 时需要找的是最后一个大于等于 X 的下标，若查找成功其下标若为 m，则有 m 个学生成 绩大于或等于 X，若查找不成功，若这时 low 所指向的值小于 X，则有 low-1 个学生成绩 大于或等于 X，注意这时表中可能不止一个数值为 X 的值，这时我们要查找的是下标最 大的) #define N /*学生人数*/ int uprx(int aN,int x ) /*函数返回大于等于 X 分的学生人数*/ int low=1,mid,high=N; do mid=(low+high)/2; if(x=amid) _(1)_ else _(2)_; while(_(3)_); if (alowx) return low-1; return low; 四、应用题 1. 名词解释： 哈希表 叙述 B-树定义，主要用途是什么？ 平衡二叉树（AVL 树） 平衡因子 平均查找长度（ASL） 3. 设有一组关键字9,01,23,14,55,20,84,27，采用哈希函数：H（key）=key mod 7 ， 表长为 10，用开放地址法的二次探测再散列方法解决冲突 Hi=(H(key)+di) mod 10(di=12,22,32,)。要求：对该关键字序列构造哈希表，并确定其装填因子，查找成功 所需的平均探查次数。 4. 设一组数据为1,14,27,29,55,68,10,11,23，现采用的哈希函数是 H(key)=key MOD 13， 即关键字对 13 取模，冲突用链地址法解决，设哈希表的大小为 13(012)，试画出 插入上述数据后的哈希表。 7. 设有一棵空的阶 B-树，依次插入关键字 30,20,10,40,80,58,47,50,29,22,56,98,99，请画出该树。 9. 已知 2 棵 2-3 B-树如下（省略外结点）： （1）对树（a）,请分别画出先后插入 26，85 两个新结点后的树形； （2）对树（b）,请分别画出先后删除 53，37 两个结点后的树形。 4524 10312 5061 7030 37 53 90 (a) 4524 103 5361 9037 70 （b） 10. 输入一个正整数序列（53,17,12,66,58,70,87,25,56,60） ，试完成下列各题。 （1） 按次序构造一棵二叉排序树 BS。 （2） 依此二叉排序树，如何得到一个从大到小的有序序列？ （3） 假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度 （4） 画出在此二叉排序树中删除“66”后的树结构。 11. 给定关键词输入序列CAP,AQU,PIS,ARI,TAU,GEM,CAN,LIB,VIR,LEO,SCO，假定关键 词比较按英文字典序，试画出从一棵空树开始，依上述顺序（