数据结构复习题及答案.pdf

数据结构练习题数据结构练习题 习题习题 1 绪论绪论 1 1 单项选择题单项选择题 1 数据结构是一门研究非数值计算的程序设计问题中 数据元素的 C 数据信息在 计算机中的 A 以及一组相关的运算等的课程 A 操作对象 计算方法 逻辑结构 数据映象 A 存储结构 关系 运算 算法 2 数据结构 DS Data Struct 可以被形式地定义为 DS D R 其中 D 是 B 的有 限集合 R 是 D 上的 D 有限集合 A 算法 数据元素 数据操作 数据对象 A 操作 映象 存储 关系 3 在数据结构中 从逻辑上可以把数据结构分成 C A 动态结构和静态结构 紧凑结构和非紧凑结构 线性结构和非线性结构 内部结构和外部结构 4 算法分析的目的是 C 算法分析的两个主要方面是 A A 找出数据结构的合理性 B 研究算法中的输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易懂性和文档性 A 空间复杂性和时间复杂性 B 正确性和简明性 C 可读性和文档性 D 数据复杂性和程序复杂性 5 计算机算法指的是 C 它必具备输入 输出和 B 等五个特性 A 计算方法 B 排序方法 C 解决问题的有限运算序列 D 调度方法 A 可行性 可移植性和可扩充性 B 可行性 确定性和有穷性 C 确定性 有穷性和稳定性 D 易读性 稳定性和安全性 1 2 填空题 将正确的答案填在相应的空中 填空题 将正确的答案填在相应的空中 1 数据逻辑结构包括线性结构 树形结构和图形结构三种类型 树形结构和图形结构 合称为非线性结构 2 在线性结构中 第一个结点没有前驱结点 其余每个结点有且只有 1 个前驱结点 最后一个结点没有后续结点 其余每个结点有且只有 1 个后续结点 3 在树形结构中 树根结点没有前驱结点 其余每个结点有且只有 1 个直接前驱结点 叶子结点没有后续结点 其余每个结点的直接后续结点可以任意多个 4 在图形结构中 每个结点的前驱结点数和后续结点数可以任意多个 5 线性结构中元素之间存在一对一关系 树形结构中元素之间存在一对多关系 图形 结构中元素之间存在多对多关系 6 算法的五个重要特性是有穷性 确定性 可行性 输入 输出 7 分析下面算法 程序段 给出最大语句频度 n2 该算法的时间复杂度是 O n2 for i 0 i n i for j 0 j n j A i j 0 8 分析下面算法 程序段 给出最大语句频度 n n 1 2 该算法的时间复杂度是 O n2 for i 0 i n i for j 0 j i j A i j 0 9 分析下面算法 程序段 给出最大语句频度 n3 该算法的时间复杂度是 O n3 s 0 for i 0 i n i for j 0 j n j for k 0 k n k s s B i j k sum s 10 分析下面算法 程序段 给出最大语句频度 该算法的时间复杂度是O n 1 2 i s 0 while s n i s i s s i 11 分析下面算法 程序段 给出最大语句频度 log2n 该算法的时间复杂度是 O log2n i 1 while ixi va elem i 1 va elem i va elem i 1 x 2 试写一算法 实现顺序表的就地逆置 即利用原表的存储空间将线性表 a1 a2 an 逆置为 an an 1 a1 void reverse int a int i j tmp for i 0 j size 1 i j i j tmp a i a i a j a j tmp 3 已知线性表中的元素以值递增有序排列 并以单链表作存储结构 试写一算法 删 除表中所有大于 x 且小于 y 的元素 若表中存在这样的元素 同时释放被删除结点空间 void del LinkList L elemtype a elemtype b p L q p next while q L q q next while q L 0 3 1 4 v1 v2 v3 v6 v5 v4 v1 v2 v5 v4 v3 v6 5 求矩阵第 i 列非零元素之和 6 将矩阵第 i 行全部置为零 7 n 8 9 9 对每个顶点查找其邻接点的过程 O e e 为图中的边数 O e 1 2 3 4 5 6 5 4 3 2 2 3 3 5 6 a b d f c e 遍历图的顺序不同 DFS 采用栈存储访问过的结点 BFS 采用队列存储访问过 的结点 10 邻接矩阵 邻接表 11 一个结点可能有若干个前驱 也可能有若干个后继 12 2 13 唯一 7 3 1 2 1 2 3 1 5 2 3 6 4 1 5 2 6 3 4 1 5 6 2 3 4 5 6 1 2 3 4 5 1 6 2 3 4 5 1 2 6 3 4 5 1 2 3 6 4 4 5 1 该 AOE 图为 W 3 W 7 W 9 W 6 W 5 4 3 2 3 3 a b d f c e 1 5 6 2 4 3 b a d c e 11 15 13 14 12 f 6 12 4 9 5 10 6 1 5 4 3 7 2 1 6 8 9 7 5 4 3 2 6 5 2 4 1 4 1 9 4 7 2 2 完成整个计划需要 18 天 3 关键路径为 V1 V2 V5 V7 V9 和 V1 V2 V5 V8 V9 习题习题 8 8 查找查找 8 1 单项选择题单项选择题 1 顺序查找法适合于存储结构为 的线性表 A 散列存储 B 顺序存储或链接存储 C 压缩存储 D 索引存储 2 对线性表进行二分查找时 要求线性表必须 A 以顺序方式存储 B 以链接方式存储 C 以顺序方式存储 且结点按关键字有序排序 D 以链接方式存储 且结点按关键字有序排序 3 采用顺序查找方法查找长度为 n 的线性表时 每个元素的平均查找长度为 A n B n 2 C n 1 2 D n 1 2 4 采用二分查找方法查找长度为 n 的线性表时 每个元素的平均查找长度为 A O n2 B O nlog2n C O n D O log2n 5 二分查找和二叉排序树的时间性能 A 相同 B 不相同 6 有一个有序表为 1 3 9 12 32 41 45 62 75 77 82 95 100 当二分查 找值 82 为的结点时 次比较后查找成功 A 1 B 2 C 4 D 8 7 设哈希表长 m 14 哈希函数 H key key 11 表中已有 4 个结点 addr 15 4 addr 38 5 addr 61 6 addr 84 7 如用二次探测再散列处理冲突 关键字为 49 的结点的地址是 A 8 B 3 C 5 D 9 8 有一个长度为 12 的有序表 按二分查找法对该表进行查找 在表内各元素等概率情 况下查找成功所需的平均比较次数为 A 35 12 B 37 12 C 39 12 D 43 12 9 对于静态表的顺序查找法 若在表头设置岗哨 则正确的查找方式为 A 从第 0 个元素往后查找该数据元素 B 从第 1 个元素往后查找该数据元素 C 从第 n 个元素往开始前查找该数据元素 D 与查找顺序无关 10 解决散列法中出现的冲突问题常采用的方法是 A 数字分析法 除余法 平方取中法 B 数字分析法 除余法 线性探测法 C 数字分析法 线性探测法 多重散列法 D 线性探测法 多重散列法 链地址法 11 采用线性探测法解决冲突问题 所产生的一系列后继散列地址 A 必须大于等于原散列地址 B 必须小于等于原散列地址 C 可以大于或小于但不能等于原散列地址 D 地址大小没有具体限制 12 对于查找表的查找过程中 若被查找的数据元素不存在 则把该数据元素插入到集 合中 这种方式主要适合于 A 静态查找表 B 动态查找表 C 静态查找表与动态查找表 D 两种表都不适合 13 散列表的平均查找长度 A 与处理冲突方法有关而与表的长度无关 B 与处理冲突方法无关而与表的长度有关 C 与处理冲突方法有关而与表的长度有关 D 与处理冲突方法无关而与表的长度无关 8 2 填空题 将正确的答案填在相应的空中 填空题 将正确的答案填在相应的空中 1 顺序查找法的平均查找长度为 折半查找法的平均查找长度为 哈希表查找 法采用链接法处理冲突时的平均查找长度为 2 在各种查找方法中 平均查找长度与结点个数 n 无关的查找方法是 3 折半查找的存储结构仅限于 且是 4 假设在有序线性表 A 1 20 上进行折半查找 则比较一次查找成功的结点数为 则比较二次查找成功的结点数为 则比较三次查找成功的结点数为 则比较四次查 找成功的结点数为 则比较五次查找成功的结点数为 平均查找长度为 5 对于长度为 n 的线性表 若进行顺序查找 则时间复杂度为 若采用折半法查 找 则时间复杂度为 6 已知有序表为 12 18 24 35 47 50 62 83 90 115 134 当用折半查找 90 时 需进行 次查找可确定成功 查找 47 时 需进行 次查找成功 查找 100 时 需进行 次查找才能确定不成功 7 二叉排序树的查找长度不仅与 有关 也与二叉排序树的 有关 8 一个无序序列可以通过构造一棵 树而变成一个有序树 构造树的过程即为对 无序序列进行排序的过程 9 平衡二叉排序树上任一结点的平衡因子只可能是 或 10 法构造的哈希函数肯定不会发生冲突 11 在散列函数 H key key p 中 p 应取 12 在散列存储中 装填因子 的值越大 则 的值越小 则 8 3 综合练习题综合练习题 1 画出对长度为 10 的有序表进行折半查找的判定树 并求其等概率时查找成功的平均 查找长度 4 选取哈稀函数 H k 3k MOD 11 用开放定址法处理冲突 di i 7k MOD 10 1 I 1 2 3 试在 0 10 的散列地址空间中对关键字序列 22 41 53 46 30 13 01 67 造哈希表 并求等概率情况下查找成功时的平均查找长度 5 已知一组关键字 49 38 65 97 76 13 27 44 82 35 50 画出由此生成 的二叉排序树 并写出对其进行中序遍历的结果序列 习题答案习题答案 8 1 1 B 2 C 3 C 4 D 5 B 6 C 7 D 8 B 9 C 10 D 11 C 12 B 13 C 8 2 1 n 1 2 n 1 log2 n 1 n 1 1 为装填因子 2 哈希表查找法 3 顺序存储结构 有序的 4 1 2 4 8 5 3 7 依题意 构造一棵有序二叉树 共 12 个结点 第一层 1 个结点 第二层 2 个结点 第三 层 4 个结点 第四层 5 个结点 则 ASL 1 1 2 2 3 4 4 5 12 37 12 5 O n O log2n 6 2 4 3 7 结点个数 n 生成过程 8 二叉排序树 9 0 1 1 10 直接定址 11 素数 12 存取元素时发生冲突的可能性就越大 存取元素时发生冲突的可能性就越小 习题习题 9 9 排序排序 9 1 单项选择题 1 在所有排序方法中 关键字比较的次数与记录的初始排列次序无关的是 A 希尔排序 B 起泡排序 C 插入排序 D 选择排序 2 设有 1000 个无序的元素 希望用最快的速度挑选出其中前 10 个最大的元素 最好 选用 排序法 A 起泡排序 B 快速排序 C 堆排序 D 基数排序 3 在待排序的元素序列基本有序的前提下 效率最高的排序方法是 A 插入排序 B 选择排序 C 快速排序 D 归并排序 4 一组记录的排序码为 46 79 56 38 40 84 则利用堆排序的方法建立的初始 堆为 A 79 46 56 38 40 80 B 38 46 56 79 40 84 C 84 79 56 46 40 38 D 84 56 79 40 46 38 5 一组记录的关键码为 46 79 56 38 40 84 则利用快速排序的方法 以第一 个记录为基准得到的一次划分结果为 A 38 40 46 56 79 84 B 40 38 46 79 56 84 C 40 38 46 56 79 84 D 40 38 46 84 56 79 6 一组记录的排序码为 25 48 16 35 79 82 23 40 36 72 其中含有 5 个 长度为 2 的有序表 按归并排序的方法对该序列进行一趟归并后的结果为 A 16 25 35 48 23 40 79 82 36 72 B 16 25 35 48 79 82 23 36 40 72 C 16 25 48 35 79 82 23 36 40 72 D 16 25 35 48 79 23 36 40 72 82 7 排序方法中 从未排序序列中依次取出元素与已排序序列 初始时为空 中的元素 进行比较 将其放入已排序序列的正确位置上的方法 称为 A 希尔排序 B 起泡排序 C 插入排序 D 选择排序 8 排序方法中 从未排序序列中挑选元素 并将其依次放入已排序序列 初始时为空 的一端的方法 称为 A 希尔排序 B 归并排序 C 插入排序 D 选择排序 9 用某种排序方法对线性表 25 84 21 47 15 27 68 35 20 进行排序时 元素序列的变化情况如下 25 84 21 47 15 27 68 35 20 20 15 21 25 47 27 68 35 84 15 20 21 25 35 27 47 68 84 15 20 21 25 27 35 47 68 84 则所采用的排序方法是 A 选择排序 B 希尔排序 C 归并排序 D 快速排序 10 下述几种排序方法中 平均查找长度最小的是 A 插入排序 B 选择排序 C 快速排序 D 归并排序 11 下述几种排序方法中 要求内存量最大的是 A 插入排序 B 选择排序 C 快速排序 D 归并排序 12 快速排序方法在 情况下最不利于发挥其长处 A 要排序的数据量太大 B 要排序的数据中含有多个相同值 C 要排序的数据已基本有序 D 要排序的数据个数为奇数 9 2 填空题填空题 将正确的答案填在相应的空中 将正确的答案填在相应的空中 1 在对一组记录 54 38 96 23 15 72 60 45 83 进行直接插入排序时 当 把第 7 个记录 60 插入到有序表时 为寻找插入位置需比较 2 在利用快速排序方法对一组记录 54 38 96 23 15 72 60 45 83 进行快 速排序时 递归调用而使用的栈所能达到的最大深度为 共需递归调用的次数为 其中第二次递归调用是对 一组记录进行快速排序 3 在堆排序 快速排序和归并排序中 若只从存储空间考虑 则应首先选取 方法 其次选取 方法 最后选取 方法 若只从排序结果的稳定性考虑 则应选取 方法 若只从平均情况下排序最快考虑 则应选取 方法 若只从最坏情况下排序最快并且要节 省内存考虑 则应选取 方法 4 在插入排序 希尔排序 选择排序 快速排序 堆排序 归并排序和基数排序中 排序是不稳定