2011年 数据结构期末考试 试卷+答案.pdf

华南农业大学期末考试试卷及参考答案华南农业大学期末考试试卷及参考答案 2011 学年第一学期学年第一学期 考试科目 数据结构考试科目 数据结构 考试类型 闭卷 考试时间 考试类型 闭卷 考试时间 120 分钟分钟 班级班级 学号学号 姓名姓名 考试须知 考试须知 1 答案必须写在 答题卡 上 写在试卷上不得分 答案必须写在 答题卡 上 写在试卷上不得分 2 考试结束时 只回收答题卡 不回收试卷 考试结束时 只回收答题卡 不回收试卷 3 必须在答题卡上正确填写班级 学号 姓名等内容 否则没有考试成绩必须在答题卡上正确填写班级 学号 姓名等内容 否则没有考试成绩 一 选择题 每小题一 选择题 每小题 2 分 共分 共 20 分 分 1 有 n 个顶点的有向图最多有 条边 B A n B n n 1 C n n 1 D n2 2 任何一个无向连通图 B 最小生成树 A 只有一棵 B 有一棵或多棵 C 一定有多棵 D 可能不存在 3 如果从无向图的任一顶点出发进行一次深度优先遍历即可访问所有顶点 则该图 一定是 B A 完全图 B 连通图 C 有回路 D 一棵树 4 有一个有序表位 1 3 9 12 32 41 45 62 75 77 82 95 99 当采用二分查找法 查找关键字为 82 的元素时 C 次比较后查找成功 A 1 B 2 C 4 D 8 5 对一组数据 84 47 25 15 21 排序 数据的排列次序在排序的过程中的变 化为 1 84 47 25 15 21 2 15 47 25 84 21 3 15 21 25 84 47 4 15 21 25 47 84 则采用的排序是 A A 选择排序 B 冒泡排序 C 快速排序 D 插入排序 6 数据序列 8 9 10 4 5 6 20 1 2 只能是下列排序算法中的 的两 趟排序后的结果 C A 选择排序 B 冒泡排序 C 插入排序 D 堆排序 7 在平衡二叉树中插入一个结点后造成了不平衡 设最低的不平衡结点为 A 并已 知插入结点后 A 的左孩子的平衡因子为 0 右孩子的平衡因子为 1 则应作 型 调整以使其平衡 C A LL B LR C RL D RR 8 快速排序算法的时间复杂性为 O nlog2n 但在 情况下 该算法效率近似为 O n 2 A A 初始序列有序或基本有序 B 初始序列无序 C 经排序后的子序列有序或基本有序 D 经排序后的子序列无序 9 在以下排序算法中 关键字比较的次数与记录的初始排列次序无关的是 D A 希尔排序 B 冒泡排序 C 插入排序 D 直接选择排序 10 就平均性能而言 目前最好的内排序方法是 排序法 D A 冒泡排序 B 希尔排序 C 堆排序 D 快速排序 二 是非判断题 每小题二 是非判断题 每小题 1 分 共分 共 5 分 分 1 排序的稳定性是指排序算法中的比较次数保持不变 且算法能够终止 2 拓扑排序算法把一个无向图中的顶点排成一个有序序列 3 排序的时间开销主要取决与算法执行中的比较次数 4 带权连通无向图不仅可能有多棵生成树 其最小生成树也可能有多棵 T 5 归并排序辅助存储为 O 1 三 应用题 共三 应用题 共 45 分 分 1 已知无向带权连通图 G V E 的邻接表如下所示 请画出该图 并使用 Prim 或 Kruskal 算法求出该图的最小生成树 其中边结点的 3 个域为 顶点号 边上的权值 指针 V1 V2 V3 V4 V5 2 对长度为 8 的有序表 给出折半查找的判定树 给出等概率情况下的平均查找长 度 3 使用哈希函数 H key key mod 7 把一个整数值转换成哈希表下标 现将 19 24 10 17 15 38 18 40 依次插入到长度为 10 的哈希表中 使用线性探测法解决冲突 请 构造哈希表并计算查找成功时的平均查找长度 ASL 3 设有一组关键字 9 01 23 14 55 20 84 27 采用哈希函数 H key key mod 7 表长为10 用开放定址法的二次探测再散列方法Hi H key di mod 10 di 1 2 12 22 22 32 解决冲突 要求 对该关键字序列构造哈希表 并计 算查找成功的平均查找长度 212316418 11232522 1162244 11834510 222410 1 2 3 4 5 4 关键字序列为 19 14 23 1 68 20 84 27 55 11 10 79 哈希函数为 H key key mod 13 采用链地址法处理冲突 给定哈希表的长度为 13 0 12 要求画出关键字序 列在哈希表中的存储状态 并计算在等概率情况下 查找成功的平均查找长度 5 一组记录关键码为 49 38 65 97 76 13 27 49 使用快速排序 写出 以第一个记录为基准的一次划分过程 6 设记录的关键字集合 K 23 9 39 5 68 12 62 48 33 给定的增量序 列 D 4 2 1 请写出对 K 按 SHELL 方法 排序各趟排序结束时的结果 7 判断下列序列是否是堆 可以是小堆 也可以是大堆 若不是堆 请将它们调整 为堆 1 100 85 98 77 80 60 82 40 20 10 66 2 100 98 85 82 80 77 66 60 40 20 10 3 100 85 40 77 80 60 66 98 82 10 20 4 10 20 40 60 66 77 80 82 85 98 100 8 已知序列 503 87 512 61 908 170 897 用二叉树的形式画出采用堆排序算法对该 序列作升序排列时的每一趟结果 包括所建立的初始堆 9 依次把结点 16 3 7 11 9 26 18 14 15 插入到初始状态为空的平衡二叉排序树中 使得在每次插入后保持该树仍然是平衡二叉排序树 要求画出每次每次插入后所形成的 平衡二叉排序树 10 在学生的课程安排中 有些课程必须在学完其先修课程才能开始 如软件工程专 业的学生必须学习的课程之间的一个关系如下表所示 课程编号 课程名称 先修课程 C1 程序设计基础 无 C2 离散数学 C1 C3 数据结构 C1 C2 C4 汇编语言 C1 C5 语言的设计和分析 C3 C4 C6 计算机原理 C11 C7 编译原理 C3 C5 C8 操作系统 C3 C6 C9 高等数学 无 C10 线性代数 C9 C11 普通物理 C9 C12 数值分析 C1 C9 C10 1 要求用AOV网将上表中课程以及课程之间的优先关系表示出来 2 假设每次只安排一门课程 请给出一个包含所有课程的合理安排序列 使到 在开始任一门课程之前其先修课程已经完成 参考答案 参考答案 1 2 AVL 1 2 2 4 3 1 4 8 21 8 2 62 3 散列地址 0 1 2 3 4 5 6 7 8 9 关键字 15 24 10 19 17 38 18 40 比较次数 1 1 2 1 4 5 5 5 哈希表 a ASLsucc 24 8 3 3 要求 对该关键字序列构造哈希表 并计算查找成功的平均查找长度 0 1 2 3 4 5 6 7 8 9 14 1 9 23 27 55 20 84 ASL 1 1 2 1 1 2 3 3 8 14 8 1 75 4 ASL 1 6 2 4 3 4 12 1 75 3 1 0 7 5 6 24 12 1 2 3 4 5 18 16 2 4 22 10 1 2 3 4 5 12 2 4 10 5 1 27 38 65 97 76 13 49 2 27 38 97 76 13 65 49 3 27 38 13 97 76 65 49 4 27 38 13 76 97 65 49 5 27 38 13 49 76 97 65 49 6 设记录的关键字集合 K 23 9 39 5 68 12 62 48 33 给定的增量序 列 D 4 2 1 请写出对 K 按 SHELL 方法 排序各趟排序结束时的结果 1 23 9 39 5 33 12 62 48 68 2 23 5 33 9 39 12 62 48 68 3 5 9 12 23 33 39 48 62 68 7 1 是大堆 2 是大堆 4 是小堆 3 不是堆 调成大堆 100 98 66 85 80 60 40 77 82 10 20 8 9 10 C1 C2 C3 C4 C5 C7 C9 C10 C11 C6 C12 C8 或或C9 C10 C11 C6 C1 C12 C4 C2 C3 C5 C7 C8 或 四 程序填空题 共四 程序填空题 共 30 分 每空分 每空 2 分 注意 每空只填一个 语句 分 注意 每空只填一个 语句 1 归并过程 已知两个有序的顺序表 La 和 Lb 将其合并成一个有序的顺序表 Lc 顺序表定义如下 typedef struct ElemType elem int length int listsize SqList void MergeList Sq SqList La SqList Lb SqList pa La elem pb Lb elem Lc listsize Lc length La length Lb length pc Lc elem ElemType malloc Lc listsize sizeof ElemType if Lc elem exit OVERFLOW 存储分配失败 pa last La elem La length 1 pb last Lb elem Lb length 1 while 1 归并 if 2 pc pa else pc pb while pa pa last 3 while pb data 8 return OK InOrderTraverse 其中栈 Stack 数据结构的基本操作如下 InitStack Stack 构造一个空栈 S StackEmpty Stack S 若 S 为空栈返回 TRUE 否则返回 FALSE StackLength Stack S 返回栈 S 的元素个数 Push Stack 插入元素 e 作为栈 S 的栈顶元素 Pop Stack 删除栈 S 的栈顶元素 并用 e 返回其值 假定上述操作已经实现 直接调用即可 3 对顺序表进行希尔排序 顺序表的定义如下 define MAXLENGTH 10000 typedef struct int r MAXLENGTH 顺序表中存储元素的数组 从下标 1 开始使用 int length 顺序表的元素个数 SqList void ShellInsert SqList for 9 i L length i if L r i 0 10 L r j dk L r j 11 ShellInsert void ShellSort SqList k t k ShellInsert L dlta k 一趟增量为 dlta k 的插入排序 ShellSort 4 图的广度优先遍历 void BFSTraverse Graph G Status Visit int v 按广度优先非递归遍历图 G 使用辅助队列 Q 和访问标志数组 visited 数组元 素的值设为 FALSE 表示对应该结点未访问 设为 TRUE 则为已经访问 QElemType v w Queue Q QElemType u for v 0 v G vexnum v visited v FALSE InitQueue Q 置空的辅助队列 Q for v 0 v 0 w NextAdjVex G u w FirstAdjVex G u 取结点 u 的第一个相邻结点 NextAdjVex G u w 取 u 的下一个相邻结点 if visited w visited w TRUE Visit w 15 if while if BFSTraverse 其中队列 Queue 数据结构的基本操作如下 InitQueue Queue 构造一个空队列 Q QueueEmpty Queue Q 若 Q 为空队列返回 T