数据结构专升本模拟题及参考答案汇总

作业题 一 作业题 一 一 单项选择题一 单项选择题 1 从逻辑上可以把数据结构分为 两大类 A 动态结构 静态结构 B 顺序结构 链式结构 C 线性结构 非线性结构 D 初等结构 构造型结构 2 链表不具有的特点是 A 插入 删除不需要移动元素 B 可随机访问任一元素 C 不必事先估计存储空间 D 所需空间与线性长度成正比 3 下面程序段的时间复杂度的量级为 For i 1 i n i For j 1 j I j For k 1 k2 则该二叉树的高度为 4 采用分块查找时 若线性表中共有 625 个元素 查找每个元素的概率相同 假设采用顺序查找来确定 结点所在的块时 每块应分 个结点最佳 5 设 G 为具有 N 个顶点的无向连通图 则 G 中至少有 条边 6 哈夫曼树 Huffman Tree 又称 它是 n 个带权叶子结点构成的所有二叉树中 带权路径 长度 WPL 7 树的先序遍历过程如下 若树为空 则进行空操作 若树非空 则访问树的 依次先序遍历树 的 三 应用题三 应用题 1 给定权值集合 1 4 2 6 9 构造相应的哈夫曼树 并计算它的带权路径长度 2 对关键字序列 10 6 3 2 5 4 构造一棵平衡二叉 排序 树并画图 要求画出建树过程 3 设有一个有序文件 其中各记录的关键字为 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 当用折半查找算法查找关键字为 3 8 19 时 其比较次数分别为多少 4 对有五个结点 A B C D E 的图的邻接矩阵 050 010 20060 0 10301000 1 画出逻辑图 2 画出图的十字链表存储 3 基于邻接矩阵写出图的深度 广度优先遍历序列 4 计算图的关键路径 作业题 三 作业题 三 一 单项选择题一 单项选择题 1 串的长度是指 A 串中所含不同字母的个数 B 串中所含非空格字符的个数 C 串中所含不同字符的个数 D 串中所含字符的个数 2 设有数组 A i j 数组的每个元素长度为 3 字节 i 的值为 1 到 8 j 的值为 1 到 10 数组从内存 首地址 BA 开始顺序存放 当用以列为主存放时 元素 A 5 8 的存储首地址为 A BA 141 B BA 180 C BA 222 D BA 225 3 算法分析的两个主要方面是 A 空间复杂性和时间复杂性 B 正确性和简明性 C 可读性和文档性 D 数据复杂性和程序复杂性 4 算法分析的目的是 A 找出数据结构的合理性 B 研究算法中的输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易懂性和文档性 5 下面程序段的时间复杂性的量极为 Int fun int n int i 1 s 1 While s n S I Return I A O n 2 B O lbn C O n D O 6 线性表是 A 一个有限序列 可以为空 B 一个有限序列 不能为空 C 一个无限序列 可以为空 D 一个无限序列 不能为空 7 带头结点的单链表 L 为空的判定条件是 A L NULL B L next NULL C L next L D L NULL 8 在一个长度为 n 的线性表中 删除值为 x 的元素时需要比较元素和移动元素的总次数为 A n 1 2 B n 2 C n D n 1 9 一个顺序存储线性表的第一个元素的存储地址是 90 每个元素的长度是 2 则第 6 个元素的存储地址 是 A 98 B 100 C 102 D 106 10 如果某链表中最常用的操作是取第 i 个结点及其前驱 则采用 存储方式最节省时间 A 单链表 B 双向链表 C 单循环链表 D 顺序表 二 填空题二 填空题 1 高度为 2 的二叉树的结点数至少有 个 高度为 3 的二叉树的结点数至少有 个 2 在顺序表 8 11 15 19 25 26 30 33 42 48 50 中 用折半查找关键字值 20 需做的关键字比较次 数为 3 在有 n 个顶点的无向图中 每个顶点的度最大可达 4 已知广义表 A a b c d e f 则广义表运算 head tail tail A 5 数组 Array 是 n n 1 个 的有序组合 数组中的数据是按顺序存储在一块 的存储单元中 6 采用顺序存储结构表示三元组表 Triple Table 来实现对稀疏矩阵的一种压缩存储形式 就称为 简称 表 7 运算是矩阵运算中最基本的一项 它是将一个 m x n 的矩阵变成另外一个 n x m 的矩阵 同 时使原来矩阵中元素的行和列的位置互换而值保持不变 三 应用题三 应用题 1 对于下图所示的二叉树 画出二叉链表存储结构图 2 请画出下图所示的树所对应的二叉树 3 已知一个无向图如下图所示 要求分别用 Prim 和 Kruskal 算法生成最小树 假设以 为起点 试画 出构造过程 4 已知完全二叉树的第 8 层有 8 个结点 则其叶子结点是多少 5 画出如图所示中树的二叉树的表示形式 A BCD E 作业题 四 作业题 四 一 单项选择题一 单项选择题 1 将两个各有 n 个元素的有序表归并成一个有序表 其最少得比较次数是 A n B 2n 1 C 2n D n 1 2 一个有 n 个顶点的无向连通图 它所包含的连通分量个数为 A 0B 1 C nD n 1 3 数据文件的基本操作中最重要的操作是 A 插入B 删除 C 修改D 检索 4 对关键码序列 28 16 32 12 60 2 5 72 快速排序 从小到大一次划分结果为 A 2 5 12 16 26 60 32 72 B 5 16 2 12 28 60 32 72 C 2 16 12 5 28 60 32 72 D 5 16 2 12 28 32 60 72 5 如果只想得到 1000 个元素组成的序列中第 5 个最小元素之前的部分排序的序列 用 方法最 快 A 堆排序 B 快速排序 C 插入排序D 归并排序 6 算法分析的目的是 A 找出数据结构的合理性 B 研究算法中的输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易懂性和文档性 7 二叉树的第 I 层上最多含有结点数为 A 2I B 2I 1 1 C 2I 1 D 2I 1 8 循环队列存储在数组 A 中 长度为 m 则入队时的操作为 A rear rear 1 B rear rear 1 mod m 1 C rear rear 1 mod m D rear rear 1 mod m 1 9 广义表满足Head A Tail A 则A为 A B C D 10 在一棵度为3的树中 度为3的结点数为2个 度为2的结点数为1个 度为1的结点数为2个 则度为0 的结点数为 个 A 3 B 4 C 5 D 6 二 填空题二 填空题 1 在一个循环队列中 队首指针指向队首元素的 2 数组中每一个数据通常称为 用下标区分 其中下标的个数由数组的 决定 3 一个图的 表示法是唯一的 而 表示法是不唯一的 4 在一个 10 阶的 B 树上 每个数根结点中所含的关键字数目最多允许 个 最少允许 个 5 对关键字序列 52 80 63 44 48 91 进行一趟快速排序之后的得到结果为 10 高度为 1 的平衡二叉树的结点数至少有 个 高度为 2 的平衡二叉树的结点数至少有 个 三三 判断判断 1 顺序存储结构属于静态结构 链式结构属于动态结构 2 即使对不含相同元素的同一输入序列进行两组不同的 合法的入栈和出栈组合操作 所得的输出序 列也一定相同 3 带权无向图的最小生成树必是唯一的 4 B 树和 B 树都可用于文件的索引结构 5 在用堆排序算法排序时 如果要进行增序排序 则需要采用 大根堆 四 应用题四 应用题 1 模式串 p abaabcac 的 next 函数值序列为多少 2 设二维数组 A 5 6 的每个元素占 4 个字节 已知 LOC a0 0 1000 A 共占多少个字节 A 的终端 结点 a4 5 的起始地址为多少 按行和按列优先存储时 a2 5 的起始地址分别为多少 3 设 a b c d e 五个字符的编码分别为 1 2 3 4 5 并设标识符依以下次序出现 ac bd aa be ab ad cd bc ae ce 要求用哈希 Hash 方法将它们存入具有 10 个位置的表中 1 将上述关键字 标识符 构造一个哈希函数 使得发生冲突尽可能地少 2 线性探测再散列法 解决冲突 写出上述各关键字在表中位置 4 给定一个关键字序列 24 19 32 43 38 6 13 22 请写出快速排序第一趟的结果 堆排序时 所建的初始堆 归并排序的全过程 然后回答上述三中排序方法中那一种方法使用的辅助空间最少 在 最坏情况下那种方法的时间复杂度最差 作业题 五 作业题 五 一 单项选择题一 单项选择题 1 一组记录的关键码为 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 2 广义表 A a b c d e f g 则下面式子的值为 GetHead GetTail GetHead GetTail GetTail A A g B d C c D d 3 对于有 n 个结点的二叉树 其高度为 A nlog2n B log2n C log2n 1 D 不确定 4 如图所示 给出由7个顶点组成的无向图 从顶点1出发 对它进行深度优先搜索得到的顶点序列是 A 1 3 5 4 2 6 7B 1 3 4 7 6 2 5 C 1 5 3 4 2 7 6D 1 2 4 7 6 5 3 5 采用邻接表存储的图 其深度优先遍历类似于二叉树的 A 中序遍历B 先序遍历 C 后序遍历 D 按层次遍历 6 已知有向图G V E 其中V V1 V2 V3 V4 V5 V6 V7 E G的拓扑序列是 A V1 V3 V4 V6 V2 V5 V7B V1 V3 V2 V6 V4 V5 V7 C V1 V3 V4 V5 V2 V6 V7D V1 V2 V5 V3 V4 V6 V7 7 顺序查找法适用于查找顺序存储或链式存储的线性表 平均比较次数为 在此假定N为线性 表中结点数 且每次查找都是成功的 A N 1B 2log2N C log2ND N 8 下面关于m阶B树说法正确的是 每个结点至少有两棵非空子树 树中每个结点至多有m一1个关键字 所有叶子在同一层上 当插入一个数据项引起B树结点分裂后 树长高一层 A B C D 9 已知一个线性表 38 25 74 63 52 48 假定采用h k k 7计算Hash地址进行散列存储 若 利用链地址法处理冲突 则在该Hash表上进行查找的平均查找长度为 A 1 0B 7 6 C 4 3D 3 2 10 在排序算法的实施过程中 使用辅助存储空间为O 1 的有 A 简单排序法B 快速排序法 C 归并排序法D 基数排序法 二 填空题二 填空题 1 n n 大于 1 个结点的各棵树中 其中深度最大的那棵树的深度是 n 它共有 个叶子结点和 个非叶子结点 2 设一棵后序线索树的高是 50 结点 x 是树中的一个结点 其双亲是结点 y y 的右子树高度是 60 x 是 y 的左孩子 则确定 x 的后继最多需经过 中间结点 不含后继及 x 本身 3 高度为 2 第 2 层为叶子 的 3 阶 B 树中 最多有 个关键字 4 分别采用堆排序 快速排序 冒泡排序和归并排序 对初态为无序的表 则平均情况下最省时间的是 算法 5 简单选择排序和起泡排序中比较次数与序列初态无关的算法有 6 串的链式存储结构是将存储区域分成一系列大小相同的结点 每个结点有两个域 域和 域 其中 域用于用于存放数据 域用于存放下一个结点的指针 三 判断三 判断 1 顺序存储的线性表可以随机存取 2 即使对不含相同元素的同一输入序列进行两组不同的 合法的入栈和出栈组合操作 所得的输出序 列也一定相同 3 十字链表是无向图的一种存储结构 4 折半查找方法适用于排列连续顺序文件的查找 5 在执行某个排序算法过程中 出现了排序码朝着最终排序序列位置相反方向移动 则该算法是不稳 定的 四 应用题四 应用题 1 用十字链表表示一个有k个非零元素的m x n的稀疏矩阵 则其总的结点数为多少 2 G V E 是一个带有权的连通图 则 1 请回答什么是G的最小生成树 2 G为下图所示 请找出G的所有最小生成树 3 请分别叙述在一个连续顺序文件中采用顺序查找法 折半查找法和分块查找法查找一个记录 该文 件中记录应该满足什么条件 4 设待排序文件之排序码为 88 33 22 55 99 11 66 采用顺序存储 请用直接选择排序算法 对上述文件进行排序 用图示说明排序过程 作业题一参考答案 作业题一参考答案 一 单项选择题一 单项选择题 1 C 2 B 3 D 4 C 5 B 6 B 7 A 8 C 9 D 10 D 二 填空题二 填空题 1 非零元很少 2 操作受限 或限定仅在表尾进行插入和限定仅在表头进行删除操作或限制存取点或特殊 先进先出 或后进后出 3 简单选择排序 4 O n2 O e O n 5 邻阵矩阵 邻接表 三 算法三 算法 答 int count 0 void onechild Btree t if t NULL onechild t lchild onechild t rchild if t lchild NULL 四 应用题四 应用题 1 答 2 答 1 2 3 4 1 G C 3 A D 3 A D 1 C 2 FG 1 C 2 FG 5 6 3 答 由于地址空间为10 且从100开始 故散列函数选为H key key 7 100 用线性探测再散列解决冲突 ASLsucc 27 10 4 答 成功查找平均比较查找长度为 n 1 n log2 n 1 1 作业题二参考答案 作业题二参考答案 一 单项选择题一 单项选择题 1 C 2 C 3 B 4 C 5 D 6 C 7 C 8 B 9 A 10 C 二 填空题二 填空题 1 2n0 1 2 6 261 3 log2k 1 4 25 5 N 1 6 最优二叉树 最小的二叉树 7 根结点 各子树 三 应用题三 应用题 1 2 FG 4 2 FG 3 A D 4 B 5 E 6 1 C 1 C 2 FG 3 A D 4 B 5 1 C 答 不唯一 型对即可 此树的带权路径长度 WPL 9 1 6 2 4 3 1 2 4 45 2 答 1 插入 10 2 插入 6 3 插入 3 4 5 插入 2 6 插入 5 7 插入 4 8 3 答 当关键字为3时 比较次数为4 当关键字为8时 比较次数为1 当关键字为 19 时 查找不成功 4 答 2 略 3 深度优先遍历序列 ABCDE 广度优先遍历序列 ABCED 4 关键路径 A B 长 100 4 12 6 3 7 13 9 22 调整 1010 6 10 6 调整 10 6 3 10 6 3 2 10 6 3 2 5 10 6 3 25 6 5 3 24 10 作业题三参考答案 作业题三参考答案 一 单项选择题一 单项选择题 1 D 2 B 3 A 4 C 5 D 6 A 7 B 8 C 9 B 10 D 二 填空题二 填空题 1 2 3 2 4 3 n 1 4 e 5 相同类型数据 地址连续 6 三元组顺序表 三元组 7 矩阵转置 三 应用题三 应用题 1 答 二叉链表 2 2 答 3 答 Prim算法构造最小生成树的步骤如24题所示 为节省篇幅 这里仅用Kruskal算法 构造最小生成 树过程如下 下图也可选 2 4 代替 3 4 5 6 代替 1 5 即 4 答 由完全二叉树的定义可知 除最后一层外 其他各层的结点是满的 设该完全二叉树有d层 则 B C D E A 除最后一层外各层的结点个数分别为 1 2 4 8 16 32 即第i层的结点个数为2i 1 这里第8 层有8个结点 显然第8 层是最后的一层 那么第7层的结点个数为27 1 64个 其中的4个结点有8个叶子 结点 余下的为叶子结点 个数为64 4 60 所以该完全二叉树的叶子结点个数为60 8 68个 5 答 对应的二叉树形式如图所示 作业题四参考答案 作业题四参考答案 一 单项选择题一 单项选择题 1 A 2 B 3 D 4 B 5 D 6 C 7 C 8 C 9 B 10 D 二 填空题二 填空题 1 答 前一个位置 2 答 数组元素 数组元素 维数 3 答 邻阵矩阵 邻接表 4 答 9 4 5 答 48 44 52 64 80 91 6 1 2 三 判断三 判断 1 答 2 答 3 答 4 答 5 答 四 应用题四 应用题 1 答 模式p的next函数值如下 2 答 A共120个字节 a4 5的起始地址为 1116 按行优先存储时 a2 5的起始地址为 1068 按列优先存储时 a2 5的起始地址为 1108 3 答 1 哈希函数H key 关键字各字符编码之和 MOD 7 2 4 答 一趟快速排序 22 19 13 6 24 38 43 32 初始大堆 43 38 32 22 24 6 13 19 二路并归 第一趟 19 24 32 43 6 38 13 22 第二趟 19 24 32 43 6 13 22 38 第三趟 6 1