2012计算机本科数据结构与算法单选题题库4.xls

TitleAnswerAAnswerBAnswerCAnswerDAnswer 1 顺序存储的表中有90000个元素 已按关键字 值升序排列 假设对每个元素进行查找的概率相 同 且每个元素的关键字值皆不相同 用顺序查 找法查找时 需平均比较的次数为 A 25000B 30000C 45000D 90000C 2 分块查找方法将表分为多块 并要求 A 块内有 序 B 块间有 序 C 链式存 储 D 链式存 储 B 3 设有一组关键字 19 14 23 1 6 20 4 27 5 11 10 9 用散列函数H key key 13 构造散列表 用拉链法解决冲突 散列地址为1 的链中记录个数为 A 1B 2 C 3D 4C 4 一个有序表为 1 3 9 12 32 41 45 62 75 77 82 95 100 当采用折半查找方法 查找值32时 查找成功需要的比较次数是 A 2 B 3C 4D 8 B 5 某索引顺序表共有元素395个 平均分成5块 若先对索引表采用顺序查找 再对块中元素进行 顺序查找 则在等概率情况下 分块查找成功的 平均查找长度是 A 43B 79C 198D 200A 6 在含有10个关键字的3阶B 树中进行查找 至 多访问的结点个数为 A 2B 3C 4 D 5B 7 设散列表长m 14 散列函数H K K 11 已 知 表 中 已 有 4 个 结 点 r 15 4 r 38 5 r 61 6 r 84 7 其他地址为空 如用二次探 测再散列处理冲突 关键字为49的结点地址是 A 8B 3C 5D 9D 8对于哈希函数H key key MOD 13 被称为同义 词的关键字是 A 35和41 B 23和39 C 15和44 D 25和51 D 9 从二叉排序树中查找一个元素时 其时间复 杂度大致为 A O n B O 1 C O log2n D O n2 C 10 若在查找的同时对表进行增 删工作 这种 查找称为 A 内 查 找 B 外查找 C 静态查 找 D 动态查 找 D 11 当在一个有序的顺序表上查找一个数据时 既可用折半查找 也可用顺序查找 但前者比后 者的查找速度 A 必定快 B 不一定 C 在大部 分 情 况 下 要快 D 取决于 表 递 增 还 是递减 C 12 折半查找有序表 4 6 10 12 20 30 50 70 88 100 若查找表中元素58 则它 将依次与表中 比较大小 查找结果是失 败 A 20 70 30 50 B 30 88 70 50 C 20 50 D 30 88 50 A 13 分别以下列序列构造二叉排序树 与用其它 三个序列所构造的结果不同的是 A 100 80 90 60 120 110 130 B 100 60 80 90 120 110 130 C 100 120 110 130 80 60 90 D 100 80 60 90 120 130 110 B 14 下面关于哈希查找的说法 正确的是 A 哈希函 数 构 造 的 越 复 杂 越 好 因 为 这 样 随 机 性 好 冲 突小 B 除留余 数 法 是 所 有 哈 希 函 数 中 最 好 的 C 不 存 在 特 别 好 与 坏 的 哈 希 函 数 要 视 情 况 而定 D 哈希表 的 平 均 查 找 长 度 有 时 也 和 记 录 总 数 有 关 C 15 在平衡二叉树中插入一个结点后造成了不平 衡 设最低的不平衡结点为A 并已知A的左孩子 的平衡因子为0右孩子的平衡因子为1 则应作 型调整以使其平衡 A LL B LRC RL D RRC 16 用二分 对半 查找表的元素的速度比用顺 序法 A 必然快 B 必然慢 C 相等D 不能确 定 D 17 具有12个关键字的有序表 折半查找的平均 查找长度 A 3 1 B 4C 2 5D 5 A 18 哈希查找中k个关键字具有同一哈希值 若 用线性探测法将这k个关键字对应的记录存入哈 希表中 至少要进行 次探测 A k B k 1C k k 1 2 D 1 k k 1 2 C 19 m阶B 树是一棵 A m叉排 序树 B m叉平 衡排序树 C m 1叉 平 衡 排 序 树 D m 1 叉 平 衡 排 序 树 B 20 下面关于m阶B树说法正确的是 每个结点至少有两棵非空子树 树中每 个 结 点 至 多 有 m 一 1 个 关 键 字 所有叶子在同一层上 当插入一个数据项引起B树结点分裂后 树长高 一层 A B C D B 21 从未排序序列中依次取出元素与已排序序列 中的元素进行比较 将其放入已排序序列的正确 位置上的方法 这种排序方法称为 A 插入排 序 B 归并排 序 C 冒泡排 序 D 选择排 序 A 22 从未排序序列中挑选元素 并将其依次放入 已排序序列 初始时为空 的一端的方法 称为 A 归并排 序 B 冒 泡 排 序 C 插入排 序 D 选 择 排 序 D 23 对n个不同的关键字由小到大进行冒泡排序 在下列 情况下比较的次数最多 A 从小到 大 排 列 好 的 B 从大到 小 排 列 好 的 C 元素无 序 D 元素基 本有序 B 24 对n个不同的排序码进行冒泡排序 在元素 无序的情况下比较的次数最多为 A n n 1 2 B n 1 C n D n 1 A 25 若 一 组 记 录 的 排 序 码 为 46 79 56 38 40 84 则利用快速排序的方法 以第一个记录为基准得到的一次划分结果为 A 38 40 46 56 79 84 B 40 38 46 56 79 84 C 40 38 46 79 56 84 D 40 38 46 84 56 79 B 26 下列关键字序列中 是堆 A 16 72 31 23 94 53 B 94 23 31 72 16 53 C 16 23 53 31 94 72 D 16 53 23 94 31 72 C 27 堆的形状是一棵 A 二叉排 序树 B 完全二 叉树 C 满二叉 树 D 平衡二 叉树 B 28 下述几种排序方法中 要求内存最大的是 A 归并排 序 B 希尔排 序 C 快速排 序 D 堆排序 A 29 下述几种排序方法中 是稳定的排 序方法 A 希尔排 序 B 快速排 序 C 归并排 序 D 堆排序 C 30 下列排序算法中 不能保证每趟排 序至少能将一个元素放到其最终的位置上 A 希尔排 序 B 快 速 排 序 C 冒 泡 排 序 D 堆排序A 31 若一组记录的排序码为 46 79 56 38 40 84 则利用堆排序的方法建立的初始堆为 A 79 46 56 38 40 84 B 84 79 56 46 40 38 C 84 56 79 40 46 38 D 84 79 56 38 40 46 D 32 某内排序方法的稳定性是指 A 该 排 序 算 法 不 允 许 有 相 同 的 关 键 字 记录 B 该排序 算 法 允 许 有 相 同 的 关 键 字 记 录 C 平均时 间 为 0 n log n 的 排序方法 D 前 面 三个都 不 正确 D 33 比较次数与排序的初始状态无关的排序方法 是 A 直接插 入排序 B 起泡排 序 C 快速排 序 D 简单选 择排序 D 34 数据序列 8 9 10 4 5 6 20 1 2 只能是下列排序算法中的 的两趟排序后 的结果 A 选择排 序 B 冒泡排 序 C 插入排 序 D 堆排序 C 35 对一组数据 84 47 25 15 21 排序 数据的排列次序在排序的过程中的变化为 1 84 47 25 15 21 2 15 47 25 84 21 3 15 21 25 84 47 4 15 21 25 47 84 则采用的排序是 A 选择B 冒泡C 快速D 插入A 36 对序列 15 9 7 8 20 1 4 进行排序 进行一趟后数据的排列变为 4 9 1 8 20 7 15 则采用的是 排序 A 选择B 快速C 希尔 D 冒泡C 37 下列排序算法中 算法可能会出现 下面情况 在最后一趟开始之前 所有元素都不 在其最终的位置上 A 堆排序 B 冒泡排 序 C 快 速 排序 D 插入排 序 D 38 直接插入排序在最好情况下的时间复杂度为 A O logn B O n C O n logn D O n2 B 39 若 用 冒 泡 排 序 方 法 对 序 列 10 14 26 29 41 52 从大到小排序 需进行 次比较 A 3B 10C 15D 25C 40 对序列 15 9 7 8 20 1 4 用希 尔排序方法排序 经一趟后序列变为 15 l 4 8 20 9 7 则该次采用的增量是 A 1 B 4 C 3 D 200B 41 稳定的排序方法是 A 直接插 入 排 序 和 快速排序 B 折 半 插 入 排 序 和 起泡排序 C 简 单 选 择 排 序 和 四 路 归 并 排序 D 树 形 选 择 排 序 和 shell排序 B 42 用直接插入排序方法对下面四个序列进行排 序 由小到大 元素比较次数最少的是 A 94 32 40 90 80 46 21 69 B 32 40 21 46 69 94 90 80 C 21 32 46 40 80 69 90 94 D 90 69 80 46 21 32 94 40 C 43 对下列关键字序列用快速排序法进行排序时 速度最快的情形是 A 21 25 5 17 9 23 3 0 B 25 23 30 17 21 5 9 C 21 9 1 7 30 25 2 3 5 D 5 9 17 2 1 23 25 3 0 A 44 有一组数据 15 9 7 8 20 1 7 4 用堆排序的筛选方法建立的初始堆为 A 1 4 8 9 20 7 15 7 B 1 7 15 7 4 8 20 9 C 1 4 7 8 20 15 7 9 D A B C 均不对 C 45 就排序算法所用的辅助空间而言 堆排序 快速排序 归并排序的关系是 A 堆排序 快 速 排 序 归 并排序 B 堆 排 序 归 并 排序 快 速排序 C 堆 排 序 归并排 序 快速 排序 D 堆 排 序 快速排 序 归并 排序 A 46 已知N元整型数组a存放N个学生的成绩 已按 由大到小排序 以下算法是用对分 折半 查找 方法统计成绩大于或等于X分的学生人数 请填 空使之完善 define N 学生人数 int uprx int a N int x 函数返回大 于等于X分的学生人数 int head 1 mid rear N do mid head rear 2 if x a mid 1 else 2 while 3 if a head x return head 1 return head 第 1 个 空 填 A rear mid 1 B rear mi d 1 C head mid 1 D head mi d 1 A 47 已知N元整型数组a存放N个学生的成绩 已按 由大到小排序 以下算法是用对分 折半 查找 方法统计成绩大于或等于X分的学生人数 请填 空使之完善 define N 学生人数 int uprx int a N int x 函数返回大 于等于X分的学生人数 int head 1 mid rear N do mid head rear 2 if x a mid 1 else 2 while 3 if a head x return head 1 return head 第 2 个空填 A rear mid 1 B rear mi d 1 C head mid 1 D head mi d 1 D