天津理工大学数据结构期末考试复习试卷.pdf

一 单项选择题一 单项选择题 每小题每小题2 2分 共分 共3030分分 1 程序段 s i 0 do i i 1 s s i while inext s s next p next B s next p next p next s C p next s p next s next D p next s next p next s 3 假设以数组 A m 存放循环队列的元素 其头尾指针分别为 front 和 rear 则当前 队列中的元素个数为 A A rear front m m B rear front 1 C front rear m m D rear front m 4 对 N 个元素的表做顺序查找时 若查找每个元素的概率相同 则平均查找长度为 A A N 1 2 B N 2 C N D 1 N N 2 5 在图采用邻接表存储时 求最小生成树的 Prim 算法的时间复杂度为 B B A O n B O n e C O n 2 D O n3 6 设森林 F 对应的二叉树为 B 它有 m 个结点 B 的根为 p p 的右子树结点个数为 n 则森林 F 中第一棵树的结点个数是 A A A m n B m n 1 C n 1 D m n 7 在有向图 G 的拓扑序列中 若顶点 Vi 在顶点 Vj 之前 则下列情形不可能出现的 是 D D A G 中有弧 B G 中有一条从 Vi 到 Vj 的路径 C G 中没有弧 D G 中有一条从 Vj 到 Vi 的路径 8 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反 则该二叉树一定满 足 C C A 所有的结点均无左孩子 B 所有的结点均无右孩子 C 只有一个叶子结点 D 是任意一棵二叉树 9 下面关于二分查找的叙述正确的是 D D A 表必须有序 表可以顺序方式存储 也可以链表方式存储 B 表必须有序且表中数据必须是整型 实型或字符型 C 表必须有序 而且只能从小到大排列 D 表必须有序 且表只能以顺序方式存储 10 要连通具有 n 个顶点的有向图 至少需要 B 条边 A n l B n C n l D 2n 11 下列排序算法中 其中 D D 是稳定的 A 堆排序 冒泡排序 B 快速排序 堆排序 C 直接选择排序 归并排序 D 归并排序 冒泡排序 11 设 abcdef 以所给的次序进栈 若在进栈操作时 允许退栈操作 则得不到的序 列为 D A fedcba B bcafed C dcefba D cabdef 12 下列数据中 C 是非线性数据结构 A 栈 B 队列 C 完全二叉树 D 堆 13 一组记录的关键码为 46 79 56 38 40 84 则利用快速排序的方法 以 第一个记录为基准得到的一次划分结果为 C 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 14 下列叙述中 不符合 m 阶 B 树定义要求的是 D A 根节点最多有 m 棵子树 B 所有叶结点都在同一层上 C 各结点内关键字均升序或降序排列 D 叶结点之间通过指针链接 15 设 A 是 n n 的对称矩阵 将 A 的对角线及对角线上方的元素以列为主的次序存 放在一维数组 B 1 n n 1 2 中 对上述任一元素 aij 1 i j n 且 i j 在 B 中 的位置为 B A i i l 2 j B j j l 2 i C j j l 2 i 1 D i i l 2 j 1 二 二 计算计算分析分析题题 共 共4040分分 1 10 分 设用于通讯的电文仅由 8 个字母组成 他们在电文中出现的频率分别为 0 30 0 07 0 10 0 03 0 20 0 06 0 22 0 02 1 试设计哈夫曼树及其编码 2 若使用 0 7 的二进制表示形式是另一种编码方案 给出两种编码的对照表 带 权路径长度 WPL 值并比较两种方案的优缺点 2 5 分 设散列表的长度为 15 散列函数 H K K 13 给定的关键字序列为 20 16 29 82 37 02 06 28 55 39 23 10 试写出用线性探测法解决冲突时 所构造的散列表 并求出在等概率情况下 查找成功时的平均查找长度 3 10 分 根据下面的无向加权图 1 写出它的邻接矩阵 2 按 Prim 算法求其最小生成树 4 10 分 设记录关键字集合 K 28 17 85 96 75 8 42 65 4 1 写出对 K 进行 二路归并 且按关键字递增次序排序时 各趟排序的结果 2 将 K 建成一个完全二叉树形式的最小堆 5 5 分 依次删除下面 AVL 树中关键字 g 和 m 画出调整过程 如果需要的话 画出最终结果 标出每个节点的平衡因子 三三 算法设计题算法设计题 共 共3 30 0分分 1 6 分 下面程序段的功能是实现二叉搜索树的递归查找算法 请在划线处填 上正确的语句 bool Find BTreeNode BST ElemType 查找失败 else if item BST data item BST data 查找成功 return else if itemdata return Find item else return Find item if 2 4 分 下面程序段的功能是实现冒泡排序算法 请在划线处填上正确的语 句 void bubble int r n for i 1 i n 1 i for exchange 0 j 0 jr j 1 temp r j 1 r j temp exchange 1 if exchange 0 return 3 20 分 已知 A B 和 C 为三个有序链表 编写算法实现从 A 表中删除 B 表和 C 表中共有的数据元素 函数名 Difference L 功能 从 A 表中删除 B 表和 C 表中共有的数据元素 不负责释放内存 参数 LinkList La LinkList Lb LinkLis