数据结构模拟复习题二

1 一 选择题一 选择题 1 在数据结构中 从逻辑上可以把数据结构分成 D A 动态结构和静态结构 B 紧凑结构和非紧凑结构 C 内部结构和外部结构 D 线性结构和非线性结构 2 算法分析的两个主要方面是 C A 数据复杂性和程序复杂性 B 可读性和文档性 C 时间复杂度和空间复杂度 D 正确性和简单性 3 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变 平均要移动 B 个元素 A 8 B 63 5 C 63 D 7 4 设一数列 a b c d e f 通过栈结构不可能排成的顺序数列为 B A c b e f d a B a e d f b c C b d c e a f D d e c f b a 5 设有一个二维数组 A 10 15 数组按行存放 假设 A 0 0 存放位置在 644 每个元素占一个空间 则 A 4 5 在 C 位置 实际求得是 a 5 6 Loc aij Loc aLoc aij Loc a11 11 i 1 n j 1 l i 1 n j 1 l 或 或 644 4 0 15 5644 4 0 15 5 A 672 B 626 C 709 D 724 6 设二叉树根结点的层次为 1 所有含有 63 个结点的二叉树中 最小高度是 A A 6 B 5 C 4 D 7 取整 LOG2 N 1 7 设结点 x 和结点 y 是二叉树 T 中的任意两个结点 若在前序序列中 x 在 y 之前 而在后序序列中 x 在 y 之后 则 x 和 y 的关系是 D A x 是 y 的左兄弟 B x 是 y 的右兄弟 C y 是 x 的祖先 D y 是 x 的孩子 8 具有 n 个顶点的无向完全图的边数为 A A n n 1 2 B n n 1 C n2 D n2 1 9 请指出在顺序表 2 5 7 10 14 15 18 23 35 41 52 中 用折半查找法查找关键码 12 需做 B 次关键码比较 A 5 B 4 C 3 D 2 10 对有 n 个记录的表作快速排序 在最坏情况下 算法的时间复杂度是 B A O n B O n2 C O nlog2n D O n3 11 设有字符序列 Q H C Y P A M S R D F X 问新序列 F H C D P A M Q R S Y X 是下列哪个排序算法一趟扫描的结果 D A 起泡排序 B 初始步长为 4 的 shell 的排序 C 二路归并排序 D 以第一个元素为分界元素的快速排序 12 线性表 在 B 情况下适用于使用链式结构实现 需经常修改 中的结点值 需不断对 进行删除插入 中含有大量的结点 中结点结构复杂 13 把一棵树转换为二叉树后 这棵二叉树的形态是 D 唯一的 有多种 但根结点都没有左孩子 有多种 有多种 但根结点都没有右孩子 14 在一个无向图中 所有顶点的度数之和等于图的边数的 C 倍 A 1 2 B 1 C 2 D 4 15 用邻接表表示图进行广度优先遍历时 通常是采用 B 来实现算法的 2 A 栈 B 队列 C 树 D 图 16 设一棵完全二叉树有 700 个结点 则共有 350 个叶子结点 17 中序遍历的递归算法平均空间复杂度为 0 N 18 用普里姆 Prim 算法求具有 n 个顶点 e 条边的图的最小生成树的时间复杂度为 O n2 用克鲁斯卡尔 Kruskal 算法的时间复杂度是 O eloge 19 设有一稠密图 G 则 G 采用 邻接矩阵 存储较省空间 二 主观题二 主观题 1 3 分 设有一对称矩阵 A n n 按行优先次序存放在一维数组 S m 中 在 S 中只存放 A 的下三角元素 请写出计算矩阵元素 A i j 在数组 S 中下标的公式 k i i 1 2 j 1 i j 下三角时 2 6 分 试写出如图 1 所示的二叉树分别按先序 中序 后序遍历时得到的结点序列 先序 A B D G H J K E C F I M 中序 G D J H K B E A C F M I 后序 G J K H D E B M I F C A 3 6 分 已知二维数组表示的图的邻接矩阵如下图 2 所示 试分别画出自顶点 1 出发进行遍历所得的深度优先生成树和广度优先生成树 深度优先生成树 V1 V7 V3 V4 V5 V6 V2 V10 V9 V8 广度优先生成树 V1 V7 V9 V3 V10 V5 V4 V8 V6 V2 4 6 分 根据图 3 给出的邻接矩阵 按普里姆算法逐步写出图的最小生成树 0 4 3 4 0 5 5 9 3 5 0 5 5 5 5 0 7 6 5 4 9 7 0 3 6 3 0 2 5 2 0 6 5 4 6 0 图 1图 3 图 2 3 深度优先生成树 V1 V7 V3 V4 V5 V6 V2 V10 V9 V8 广度优先生成树 V1 V7 V9 V3 V10 V5 V4 V8 V6 V2 5 6 分 字符 a b c d e f g 的权值分别是 4 7 8 2 5 16 30 构造并画出一棵哈夫曼树 左子树根结点的权小于等于右子树根结点的权 并写出 a b c d e f g 的 Huffman 编码 6 6 分 应用希尔排序算法 对键值序列 49 38 65 97 76 13 27 49 从小到大进行排序 试写出每趟排序的结果 设增量序列为 4 2 1 7 6 分 用序列 46 68 45 139 70 58 101 10 88 94 建立一个二叉排序树 画出该树 并写出在等概率情况下查找成功的平均查找长度 8 6 分 根据图 4 写出从 C 点开始按深度优先遍历该图的结果 并根据邻接表存