数据结构考试题

04 级 1 一种抽象数据类型包括数据对象 数据关系和 三部分 A 数据类型 B 基本操作 C 数据抽象 D 类型说明 2 在 运算中 使用顺序表比链表好 A 插入 B 删除 C 根据序号查找 D 根据元素值查找 3 设有一个二维数组 A 10 20 按行存放于一个连续的存储空间中 A 0 0 的存储地址 是 200 每个数组元素占 1 个存储字 则 A 6 2 的地址为 A 226 B 322 C 341 D 342 4 设单链表中结点的结构为 data next 已知指针 p 所指结点不是尾结点 若在 p 之后 插入结点 s 则应执行下列哪一个操作 A s next p p next s B p next s s next p C s next p next p s D s next p next p next s 5 已知单链表 A 长度为 m 单链表 B 长度为 n 若将 B 联接在 A 的末尾 其时间复杂度 应为多少 A OA B O n C O m D O m n 6 若让元素 1 2 3 依次进栈 则出栈次序不可能出现 种情况 A 3 2 1 B 2 1 3 C 3 1 2 D 1 3 2 7 设循环队列的结构是 const int MaxSize 100 typedef int DataType typedef struct DataType data MaxSize int front rear Queue 若有一个 Queue 类型的队列 Q 则判断队列满的条件应是语句 A Q front Q rear B Q front Q rear MaxSize C Q front Q rear MaxSize D Q front Q rear 1 MaxSize 8 具有 n n 0 个结点的完全二叉树的深度为 A log2 n B log2 n C log2 n 1 D log2 n 1 9 用邻接表表示的图进行广度优先遍历时 通常是采用 来实现算法的 A 栈 B 队列 C 树 D 图 10 已知图的邻接表如下所示 根据算法 则从顶点 0 出发按深度优先遍历的结点序列是 A 0 1 3 2 B 0 2 3 1 C 0 3 2 1 D 0 1 2 3 11 要进行有序表的折半查找 则线性表 A 必须以顺序方式存储 B 既可以以顺序方式 也可以以链表方式存储 C 必须以顺序方式存储且数据元素已按值递增或递减的次序排好 D 必须以链表方式存储且数据元素已按值递增或递减的次序排好 12 把一棵树转换为二叉树后 这棵二叉树的形态是 A 唯一的 且根结点没有右孩子 B 有多种 但根结点都没有右孩子 C 唯一的 且根结点可能有右孩子 D 有多种 且根结点可能有右孩子 13 从未排序序列中挑选元素 并将其依次插入已排序序列 初始时为空 的一端的方法 称为 A 选择排序 B 希尔排序 C 插入排序 D 归并排序 14 下列关键字序列中 是堆 A 16 72 31 23 94 53 B 94 23 31 72 16 53 C 16 53 23 94 31 72 D 16 23 53 31 94 72 15 若一组记录的排序码为 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 二 填空题 二 填空题 1 5 题每空题每空 1 分 分 6 9 题每空题每空 3 分 共分 共 20 分 分 1 具有头结点的循环单链表 L 为空的条件是 注 结点结构为 LNode data next 2 队列是一种限定在表的一端插入 在另一端删除的线性表 它的特点是 3 设有一个顺序栈 S 元素 s1 s2 s3 s4 s5 s6 依次进栈 如果 6 个元素的出栈顺序为 s2 s3 s4 s6 s5 s1 则顺序栈的容量至少应为 4 具有 12 个结点的完全二叉树有 个度为 2 的结点 5 有向图 G 用邻接矩阵存储 其第 i 行的非零元素个数等于顶点 i 的 6 若一棵二叉树的先序序列是 BEFCGDH 中序序列是 FEBGCHD 则它的后序序列是 7 给定一组数据对象的排序码为 46 79 56 38 40 84 则利用堆排序方法建立的初始 堆 小顶堆 为 8 如图所示的树 其对应二叉树的先序序列为 9 对下图的无向带权图 设顶点次序为 a b c d e f g h 1 写出按普里姆算法求其最小生成树的边的次序 2 写出按克鲁斯卡尔算法求其最小生成树的边的次序 三 应用题 共三 应用题 共 51 分 分 1 8 分 已知主串 s ABCAABBABCABAACB 模式串 t ABCABAA 1 写出模式串 t 的 next 函数值 j1234567 串 tABCABAA Next j 2 利用模式串 t 的 next 函数值 画出 kmp 算法匹配的全过程 确定模式串在主串中位 置 2 10 分 假设用于通信的电文由字符集 a b c d e f g h 中的字母构成 这 8 个字母在电 文中出现的频率分别为 0 07 0 19 0 02 0 06 0 32 0 03 0 21 0 10 1 构造哈夫曼树 并求出其带权路径长度 WPL 2 为这 8 个字母设计哈夫曼编码 3 13 分 对于如下图所示的 AOE 网 1 求出各个事件的最早发生时间和最晚发生时间 事件V0V1V2V3V4V5V6V7V8V9 Ve vi Vl vi 2 计算各个活动的最早开始时间和最迟开始时间 活动a1a2a3a4a5a6a7a8a9a10a11a12a13a14a15 E ai L ai 3 找出关键活动 关键路径 并回答完成整个工程最少需要的时间是多少 4 10 分 假定对有序表 3 4 5 7 24 30 42 54 63 72 87 95 进行折 半查 找 试回答下列问题 1 画出描述折半查找过程的判定树 2 若查找元素 54 需依次与哪些元素比较 3 若查找元素 90 需依次与哪些元素比较 4 假定每个元素的查找概率相等 求查找成功时的平均查找长度 5 10 分 试利用 Dijkstra 算法求图中从顶点 a 到其他各顶点间的最短路径 写出执行算 法过程中各步的状态 四 算法分析与设计 共四 算法分析与设计 共 14 分 分 1 8 分 1 说明在中序线索二叉树中找指定结点的后继的思想 2 完成以下算法 BiTree InSucc BiTree p 已知 p 是指向中序线索二叉树上某个结点的指针 本函数返回 p 的后继的指针 If p rtag 1 return while q ltag 0 return InSucc 2 6 分 设在一个带表头结点的单链表中所有元素结点的数据值按递增顺序排列 试完 成下列函数 删除表中所有大于 min 小于 max 的元素 若存在 Typedef struct LNode ElemType data struct LNode next LNode LinkList void rangeDelete LinkList L ElemType min ElemType max LNode pr p pr L p L next 请完成 05 级 1 一种抽象数据类型包括数据对象 数据关系和 三部分 A 数据类型 B 基本操作C 数据抽象 D 类型说明 2 在 运算中 使用顺序表比链表好 A 插入 B 删除 C 根据序号查找 D 根据元素值查找 3 如下陈述中正确的是 A 串是一种特殊的线性表 B 串的长度必须大于零 C 串中元素只能是字母 D 空串就是空格串 4 设单链表中结点的结构为 data next 已知指针 p 所指结点不是尾结点 若在 p 之 后插入结点 s 则应执行下列哪一个操作 A s next p p next s B p next s s next p C s next p next p s D s next p next p next s 5 5 已知单链表 A 长度为 m 单链表 B 长度为 n 若将 B 联接在 A 的末尾 其时间复杂度应 为多少 A O A B O n C O m D O m n 6 若让元素 1 2 3 依次进栈 则出栈次序不可能出现 种情况 A 3 2 1B 2 1 3 C 3 1 2D 1 3 2 7 设循环队列的结构是 constconst intint MaxSize 100 typedeftypedef intint DataType typedeftypedef structstruct DataType data MaxSize intint front rear Queue 若有一个 Queue 类型的队列 Q 则判断队列满的条件应是语句 A Q front Q rear B Q front Q rear MaxSize C Q front Q rear MaxSize D Q front Q rear 1 MaxSize 8 具有 n n 0 个结点的完全二叉树的深度为 A log2 n B log2 n C log2 n 1 D log2 n 1 9 用邻接表表示的图进行广度优先遍历时 通常是采用 来实现算法的 A 栈 B 队列 C 树 D 图 10 已知图的邻接表如下所示 根据算法 则从顶点 0 出发按深度优先遍历的结点序列是 A 0 1 3 2 B 0 2 3 1 C 0 3 2 1 D 0 1 2 3 11 把一棵树转换为二叉树后 这棵二叉树的形态是 A A 唯一的 且根结点没有右孩子 B B 有多种 但根结点都没有右孩子 C C 唯一的 且根结点可能有右孩子 D D 有多种 且根结点可能有右孩子 12 算法分析的目的是 A 找出数据结构的合理性 B 研究算法中的输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易懂性和文档性 二 填空题 二 填空题 1 5 题每空题每空 1 分 分 6 7 题每空题每空 3 分 共分 共 14 分 分 1 具有头结点的循环单链表 L 为空的条件是 注 结点结构为 LNode data next 2 队列是一种限定在表的一端插入 在另一端删除的线性表 它的特点是 3 在串 S structure 中 以 t 为首字符的子串有 个 4 具有 12 个结点的完全二叉树有 个度为 2 的结点 5 有向图 G 用邻接矩阵存储 其第 i 行的非零元素个数等于顶点 i 的 6 若一棵二叉树的先序序列是 BEFCGDH 中序序列是 FEBGCHD 则它的后序序列是 7 对下图的无向带权图 设顶点次序为 a b c d e f g h 1 写出按普里姆算法求其最小生成树的边的次序 2 写出按克鲁斯卡尔算法求其最小生成树的边的次序 三 是非题三 是非题 每题每题 1 分 共分 共 7 分分 1 线性的数据结构可以顺序存储 也可以链式存储 非线性的数据结构只能链式 存储 2 栈和队列逻辑上都是线性表 3 顺序表中所有结点的类型必须相同 4 单链表从任何一个结点出发 都能访问到所有结点 5 二叉树按某种顺序线索化后 任一结点均有指向其前驱和后继的线索 6 二叉树中所有结点个数是 2k 1 1 其中 k 是树的深度 7 用二叉链表法存储包含 n 个结点的二叉树 结点的 2n 个指针区域中有 n 1 个为 空指针 四 应用题 共四 应用题 共 49 分 分 1 10 分 假设用于通信的电文由字符集 a b c d e f g h 中的字母构成 这 8 个字母在电 文中出现的频率分别为 0 07 0 19 0 02 0 06 0 32 0 03 0 21 0 10 1 构造哈夫曼树 并求出其带权路径长度 WPL 2 为这 8 个字母设计哈夫曼编码 2 12 分 试利用 Dijkstra 算法求图中从顶点 a 到其它各顶点的最短路径 写出执行算 法过程中各步的状态 3 13 分 对于如下图所示的 AOE 网 v v0 0 v v1 1 v v2 2 v v3 3 v v4 4 v v6 6 v v5 5 v v7 7 v v8 8 v v9 9 a a1 1 5 5 a a2 2 7 7 a a3 3 3 3 a a4 4 6 6 a a5 5 3 3 a a6 6 4 4 a a7 7 5 5 a a8 8 4 4 a a9 9 6 6 a a1 10 0 5 5 a a1 11 1 8 8 a a1 12 2 2 2 a a1 13 3 8 8 a a1 14 4 9 9 a a1 15 5 3 3 1 求出各个事件的最早发生时间和最晚发生时间 2 计算各个活动的最早开始时间和最迟开始时间 3 找出关键活动 关键路径 回答完成整个工程最少需要的时间是多少 4 4 分 画出和下列二叉树相应的森林 5 10 分 列出下图中全部可能的拓扑有序序列 并指出应用算法 Topological Sort 求 得的是哪一个序列 采用邻接表存储结构 顶点按 顺序存储 五 算法分析与设计 共五 算法分析与设计 共 18 分 分 1 1 用两种不同的表示法画出网 G