数据结构图,查找,内排序的练习及答案.pdf

数据结构课后练习数据结构课后练习 习题要求 此次练习不要求上交 只是帮助大家掌握知识点 便于复习 第八章第八章 图图 一 单项选择题 20 分 1 带权有向图 G 用邻接矩阵 A 存储 则 Vi 的入度等于 A 中 D A 第 i 行非 的元素只和 B 第 i 列非 的元素之和 C 第 i 行非 且非 0 的元素之和 D 第 i 列非 且非 0 的元素个数 2 无向图的邻接矩阵是一个 A A 对称矩阵 B 零矩阵 C 上三角阵 D 对角矩阵 3 在一个无向图中 所有顶点的度之和等于边数的 C 倍 A 1 2 B 1 C 2 D 4 4 一个有 n 个顶点的无向图最多有 C 条边 A n B n n 1 C n n 1 2 D 2n 5 对于一个具有 n 个顶点的无向图 若采用邻接矩阵表示 则该矩阵大小是 D A n B 2 1 n C n 1 D 2 n 6 一个有向图 G 的邻接表存储如右图所示 现按深 度优先搜索遍历 从 V1 出发 所得到的顶点序 列是 B A 1 2 3 4 5 B 1 2 3 5 4 C 1 2 4 5 3 D 1 2 5 3 4 7 对右图所示的无向图 从顶点 V1 开始进行深度 优先遍历 可得到顶点访问序列 A 提示 可先画出邻居表图再遍历 A 1 2 4 3 5 7 6 B 1 2 4 3 5 6 7 C 1 2 4 5 6 3 7 D 1 2 3 4 5 6 7 8 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点 则该图一定是 B A 完全图 B 连通图 C 有回路 D 一棵树 9 任何一个无向连通图 B 最小生成树 提示 注意最小生成树的定义 此题易错 A 只有一棵 B 一棵或多棵 C 一定有多棵 D 可能不存在 11 若图的邻接矩阵中主对角线上的元素全是 0 其余元素全是 1 则可以断定该图一定是 D A 无向图 B 不是带权图 C 有向图 D 完全图 二 填空题 1 有 n 个结点的无向图最多有 n n 1 2 条边 2 有 n 个顶点的强连通有向图 G 至少有 n 1 条弧 3 对于一个具有 n 个顶点和 e 条边的无向图 若采用邻接表表示 则表头数组的大小为 n 所有邻接表中的结点总数是 2e 4 对于 n 个顶点的无向图 采用邻接矩阵表示 求图中边数的方法是 邻接矩阵中 1 的个 数除以 2 判断任意两个顶点 i 和 j 是否有边相连的方法是 A i j 是否为 1 求任 意一个顶点的度的方法是 计算该行或该列中 1 的个数 5 对于 n 个顶点的有向图 采用邻接矩阵表示 求图中边数的方法是 邻接矩阵中 1 的个 数 判断任意两个顶点 i 和 j 是否有边相连的方法是 A i j 是否为 1 求任意一个 顶点的度的方法是 出度为该行中 1 的个数 入度为该列中 1 的个数 顶点的度等于出度和 入的之和 6 对于 n 个顶点的无向图 采用邻接表表示 求图中边数的方法是 邻接表中结点的个数 除头结点外 除以 2 判断任意两个顶点 i 和 j 是否有边相连的方法是 从 i 表头结点开 头的链表中是否包含 j 结点 求任意一个顶点的度的方法是 以 i 表头结点开头的链 表中结点个数 7 连通分量是无向图中的 极大 连通子图 8 一个连通图的 生成树 是一个极小连通子图 四 分析题 有一个带权图 其邻接矩阵的数组表示如右图 试完成下列要求 1 写出该图上从顶点 1 触发进行深度优先遍历 的顶点序列 并据此判断该图是否为连通图 2 画出该图的带权邻接表 3 画出按 Kruskal 算法构造最小生成树 森林 的示意图 解答 1 从顶点 1 出发的一个深度优先遍历的顶点序 列为 1 2 3 8 7 4 5 6 据此判断该图不是连通图 2 该图的带权邻接表如下图所示 特别注意 带权图要将权值放到结点中 3 按 Kruskal 算法构造的生成森林为 特别注意 下面的答案没有给过程 考试时应写 过程 如果过程正确将按步骤给分 如果没有过程 结果错误扣全部分数 第九章第九章 查找查找 1 只能在顺序存储结构上才能实现的查找方法是 B 特别重要 A 顺序查找 B 二分查找 C 树型查找 D 散列查找 2 在数据元素有序 元素个数较多而且固定不变的情况下 宜采用 A A 二分查找 B 分块查找 C 二叉排序树查找 D 顺序查找 3 有一个长度为 12 的有序表 按二分查找法对该表进行查找 在表内各元素等概率情况下 查找成功所需的平均比较次数为 B 提示 可借助二分查找判定树 A 35 12 B 37 12 C 39 12 D 43 12 4 有一个有序表 R 1 13 1 3 9 12 32 41 45 62 75 77 82 95 100 当采用二分查找法查找值 为 82 的结点时 经 C 次比较后查找成功 提示 二分查找判定树 A 1 B 2 C 4 D 8 5 如右图所示的一棵二叉排序树 其查找不成功不成功的平均查找长度 是 A 提示 加方框结点表示不成功 A 12 7 B 28 7 C 15 6 D 21 6 6 采用分块查找时 若线性表有 625 个元素 查找每个元素的概 率相同 假设采用顺序查找来确定结点所在的块 则每块分为 B 个结点最佳 A 9 B 25 C 6 D 625 7 设有 n 个关键字 散列查找法的平均查找长度是 A A O 1 B O n C O n 2 log D O 2 n 三 分析题 1 教材 P272 的 9 2 解答 请参考相关课件 2 对于关键字序列 30 15 21 40 25 26 36 37 若装填因子为 0 8 采用线性探查法解决散列冲 突 完成以下各题 提示 表长 关键字个数 装填因子 1 设计散列函数 2 画出散列表 3 计算查找成功和查找失败的平均查找长度 解答 1 由于装填因子为 0 8 关键字个数 n 8 所以表长 m 8 0 8 10 用除留余数法 由于表长为 10 则 p 7 散列函数为 H key key mod 7 2 此处给出最后结果 中间过程必须计算 否则不给全分 3 写出完整的算式给全分 只有结果的只给 1 3 分数 查找成功的平均查找长度 ASLsucc 1 1 1 3 1 1 2 6 8 16 8 2 查找失败的平均查找长度 ASLunsucc 9 8 7 6 5 4 3 2 1 1 10 46 10 4 6 第十章第十章 内排序内排序 以关键字序列 256 301 751 129 937 863 742 694 076 438 为例 分别写出执 行以下排序算法的各趟排序结束时 关键字序列的状态 1 直接插入排序 2 希尔排序 3 冒泡排序 冒泡排序 4 快速排序 快速排序 5 直接选择