数据结构期末考试试卷(A卷)

第 1 页 共 12 页 数据结构期末考试试卷 数据结构期末考试试卷 A A 卷 卷 第一学期 开课单位 软件学院 考试形式 闭 开卷 允许带 入 场 科目 数据结构 班级 软件工程 姓名 学号 题序一二三四五六七八九总 分 得分 评卷人 I I 基本概念部分 共基本概念部分 共 6060 分 分 1 下图所示是单链表结点的插入过程 在 fence 结点后面插入一个 值为 10 的 ltmp 结点 已知 fence next 是指向 fence 的后继结点 请把这一插入过程用代码表示出来 6 分 这一过程的代码 这一过程的代码 ltmp next fence next fence next ltmp 第 2 页 共 12 页 2 下图所示是双链表结点的删除过程 在 fence 结点后面删除一个 值为 23 的结点 已知 fence next 是指向 fence 的后继结点 fence prev 是指向 fence 的前驱结点 ltmp 是一个值为 NULL 的链 表结点指针 请把这一删除过程用代码表示出来 8 分 这一过程的代码 这一过程的代码 ltmp fence next fence next ltmp next ltmp next prev fence 3 画出下图中的 BST 加上值 5 以后的形状 6 分 第 3 页 共 12 页 4 画出下图所示图的相邻矩阵表示 假设下面的表格是一个二维数组 请 在表格中填入正确的数值 8 分 123456 110202 21035 3315 42051110 515113 第 4 页 共 12 页 62103 5 给出下图从顶点 1 开始的 DFS 树 8 分 深度优先搜索 DFS 从底到高 从小到大 广度优先搜索 BFS 直接在下面的顶点中画出来即可 直接在下面的顶点中画出来即可 6 给出下图从顶点 3 开始使用 Prim 普里姆 算法时的最小支撑树 最小生成树 8 分 3 0 2 1 54 3 0 2 1 54 第 5 页 共 12 页 直接在下面的顶点中画出来即可 直接在下面的顶点中画出来即可 7 起泡排序函数的算法如下 8 分 void bubsort int A int n int tmp 2 1 3 4 5 6 第 6 页 共 12 页 for int i 0 i n i for int j i 1 j A j tmp A i A i A j A j tmp 外层循环 打印一下中间结果 for int k 0 k n k printf d A k printf n 对数组 intint A 9 12 3 7 90 15 应用上面的排序算法进行排序的部分中间打印结果如下 请补充使之完整 第0次外层循环的中间结果 3 12 9 7 90 15 第第1 1次外层循环的中间结果次外层循环的中间结果 3 3 7 7 1212 9 9 9090 1515 第第2 2次外层循环的中间结果次外层循环的中间结果 3 3 7 7 9 9 1212 9090 1515 第第3 3次外层循环的中间结果次外层循环的中间结果 3 3 7 7 9 9 1212 9090 1515 第第4 4次外层循环的中间结果次外层循环的中间结果 3 3 7 7 9 9 1212 1515 9090 第5次外层循环的中间结果 3 7 9 12 15 90 8 给出从下图的最大值堆中删除最大元素后得到的堆 8 分 7 6 31 5 24 第 7 页 共 12 页 或 6 5 3 4 2 1 II II 算法填空部分 每空一条语句或表达式 填在本大题后面的标算法填空部分 每空一条语句或表达式 填在本大题后面的标 号线上 每空号线上 每空 2 2 分 共分 共 3030 分 分 1 假设有两个链表值都是从小到大排序的 下面的函数能把把它们 合并成一个有序的表 合并两个有序的单链表为一个新的有序的单链表 传入参数为两个有序的单链表 返回合并后的有序表 template List merge List l1 List l2 l1 setStart l2 setStart List l new LList Elem e1 e2 按顺序把两个表中的元素放入新表中 while l1 getValue e1 l1 next else l append e2 l2 next 第 8 页 共 12 页 end if else end while 如果表 l1 不为空 则把剩余的元素都放入新表中 while l1 getValue e1 1 append e1 l1 next 如果表 l2 不为空 则把剩余的元素都放入新表中 while l2 getValue e2 l append e2 l2 next 返回新生成的表 return 1 1 List 1 错 2 回文 palindrome 是指一个字符串从前面读和从后面读都一样 仅使用若干栈和队列 栈和队列的 ADT 函数以及若干个 int 类型和 char 类型的变量 下面的算法能判断一个字符串是否为回文 算法 的返回结果为 true 或 false bool isPal char buf 声明一个空栈和一个空队列 Queue q Stack s char cq cs 初始化栈和队列 s new AStack BUFLEN q new AQueue BUFLEN 把字符串中的字符一个一个分别入栈和入队 for int i 0 ipush buf i q enqueue buf i 第 9 页 共 12 页 出栈出队 比较 while q dequeue cq return true 3 下面是一个递归函数 search 传入参数为一棵二叉树和一个值 K 如果值 K 出现在树中则返回 true 否则返回 false template bool search BinNode rt int K template bool search BinNode rt int K if rt NULL return false else if KEComp eq K rt val return true else return false 错 search rt left K search rt right K 4 下面是一个递归函数 smallcount 传入一棵二叉检索树和值 K 返回值小于或等于 K 的结点数目 template int smallcount BinNode root Key K template int smallcount BinNode root Key K if root NULL return 0 0 false else if KEComp lt K root val return smallcount root left K else return smallcount root right K 错 第 10 页 共 12 页 1 smallcount root left K smallcount root right K 注 返回值 如果是 int 型则返回 0 或 1 如果是 bool 型则返回 false 或 true 5 写一个算法以确定有 n 个顶点的无向图是否包含回路 代码已经 给出 其中空位的地方需要你来补上 判断是否存在环的方法 检查所有可能的连通分量 define UNVISITED 0 define VISITED 1 bool isExistRing Graph G bool br false for int v 0 v vn 考虑图的所有顶点 if UNVISITED G getmark v br br LookRing G 0 1 return br 从顶点 pre 开始 利用深度优先搜索 在同一个连通分量类 如果找到了一个曾经被访问过的顶点 即说明此无向图存在环 bool LookRing Graph G int v int pre bool br false G setmark vG setmark v VISITED VISITED 设置该顶点被访问 for int w G first v w e G e w G next v w if VISITED G getmark W if w pre br true 存在环 else br br LookRing G w v 对每一个可能边再找 return br 第 11 页 共 12 页 l2 getValue e2 l append e1 l q enqueue buf i s pop cs true false search rt left K search rt right K 0 1 smallcount root left K smallcount root right K v n G getMark v G setMark v VISITED G e G getMark w 综合问题求解 共综合问题求解 共 1010 分 分 1 编写一个函数 以一棵树为输入 返回树的结点数目 函数原型 如下 10 分 tem