第 8 章
习题
1 、 填空题
1、采用折半查找算法搜索一个线性表时， 此线性表必须是 存储的 表。
2、在具有 20 个元素的有序表上进行二分查找，则比较一次查找成功的结点
数为 ，比较两次查找成功的结点数为 ，比较三次查找成功的结点
数为 ，比较四次查找成功的结点数为 ，比较五次查找成功的结点
数为 ，平均查找长度为 。
3、静态查找表的三种不同实现各有优缺点。其中， 查找效率最低但 限制最少。 查找效率最高但限制最强。而 查找则介于上述二者之间。
4、索引顺序表的主表被分成若干块，各块之间 ，块内无序。
5 、设散列表的长度为 m， 初始状态为空， 用线性探查法解决冲突， 将 n（ n<m ）个不同的关键字插入散列表，如果这 n 个关键字的散列地址全都相同， 则总的探测次数为 。
6 、对两棵具有相同关键字集合而形状不同的二叉排序树， 遍
历它们得到的序列的顺序是一样的。 2 、 选择题
1、顺序查找适合于（ ）存储结构的查找表。
A． 压缩 B． 散列 C． 索引 D． 顺序或链式
2 、 设 有 序 表 的 关 键 字 序 列 为 {1 ，4 ，6， 10， 18 ，35 ，42 ，53 ，67 ，71 ，78 ，84 ，92 ，99}，当用二分查找查 找关键字为 84 的结点时，经（ ）次比较后查找成功。
A． 2 B． 3 C． 4 D． 12
3、与其他查找方法相比，散列查找法的特点是（ ）。
A． 通过关键字比较进行查找
B． 通过关键字计算记录存储地址进行查找
C． 通过关键字计算记录存储地址，并进行一定的比较进行查找
D． 通过关键字比较进行查找，并计算记录存储地址
4 、在散列函数 H（k）=k%m 中，一般来讲，m 应取（ ）.
A． 奇数 B． 偶数 C． 素数 D． 充分大的数
5 、散列表的地址区间为 0～16，散列函数为 H1（ K ）=K%17，采用线性探 测法解决冲突，将关键字序列 26 ，25 ，72 ，38， 1， 18 ，59 依次存储到散列表 中。元素 59 存放在散列表中的地址为（ ）。
A． 8 B. 9 C. 10 D. 11
6、设有 100 个元素，用折半查找法进行查找时，最大、最小比较次数分别是 ( )。
A． 7， 1 B． 6， 1 C． 5， 1 D． 8， 1
3 、 判断题
1 、在有序的顺序表和有序的链表上，均可以使用折半查找法来提高查找速 度。 ( )
2、对于同一组待输入的关键字集合，虽然各关键字的输入顺序不同，但得到的 二叉排序树是相同。()
3、散列法中的冲突指的是具有不同关键字的元素对应于相同的存储地址。 ( )
4 、 将 一 新 结 点 插 入 二 叉 排 序 树 中 ， 该 结 点 一 定 成 为 叶 子 结 点 。 ( )
5 、任意一棵二叉排序树的平均查找时间都小于用顺序查找算法搜索同一结点顺 序表的平均查找时间。 ( )
四、应用题
1、画出对长度为 11 的有序表进行二分查找的判定树，并求其等概率时查找 成功的平均查找长度。
2 、给定表{19， 14，22 ，66，21 ，83， 10}，试按元素在表中的次序将它们 插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树。
3 、 已 知 散 列 函 数 为 H （ k ） =k % 13 ， 关 键 值 序 列 为 19， 14 ，23 ，01 ，68 ，20 ，84 ，27 ，55， 11， 10 ，79 ，处理冲突的方法为线性 探测法，散列表长度为 13 ，试画出该散列表并计算等概率情况下查找成功和失
败时的平均查找长度。
五、算法设计题
1 、编写递归的二分查找算法。
2 、试设计一算法，求出指定结点在给定的二叉排序树中所在的层次。
3、编写算法，判断一个用二叉链表存储的二叉树是否为二叉排序树。
评论0