数据结构基础期末复习例题-北京尧图网络

Min-heap {7, 9, 14, 19, 25, 20, 16, 21}; result after inserting 2. 译最小堆 {7, 9, 14, 19, 25, 20, 16, 21}插入 2 后的最小堆解 {2, 7, 14, 9, 25, 20, 16, 21, 19}。2 置于末端后上滤与 19、9、7 依次交换2 升至根这道题考察的是最小堆Min-heap的插入操作以及随之而来的上滤Percolate Up / Bubble Up过程。题目Min-heap {7, 9, 14, 19, 25, 20, 16, 21}; result after inserting 2.最小堆 {7, 9, 14, 19, 25, 20, 16, 21}插入 2 后的最小堆答案{2, 7, 14, 9, 25, 20, 16, 21, 19}详细解题步骤第一步将新元素插入到堆的末尾在最小堆中插入新元素时首先将其放在数组的最后一个位置即作为完全二叉树的最后一个叶子节点。原堆有 8 个元素插入 2 后2 被放在索引为 8第 9 个位置的地方。此时堆的数组状态为{7, 9, 14, 19, 25, 20, 16, 21, 2}第二步执行上滤Percolate Up操作由于新插入的元素 2 可能破坏最小堆的性质即父节点必须小于或等于子节点我们需要将它与它的父节点进行比较。如果父节点比它大则交换位置直到满足堆的性质或到达根节点。第 1 次比较与交换2 所在的位置是索引 8。它的父节点索引是(8-1)/2 3。索引 3 处的元素是19。因为2 19所以 2 与 19 交换。当前数组状态{7, 9, 14, 2, 25, 20, 16, 21, 19}第 2 次比较与交换2 现在在索引 3。它的父节点索引是(3-1)/2 1。索引 1 处的元素是9。因为2 9所以 2 与 9 交换。当前数组状态{7, 2, 14, 9, 25, 20, 16, 21, 19}第 3 次比较与交换2 现在在索引 1。它的父节点索引是(1-1)/2 0。索引 0 处的元素是7即根节点。因为2 7所以 2 与 7 交换。当前数组状态{2, 7, 14, 9, 25, 20, 16, 21, 19}结束条件2 现在位于索引 0根节点没有父节点了上滤过程结束。最终结果经过上述步骤插入 2 并调整后的最小堆为{2, 7, 14, 9, 25, 20, 16, 21, 19}Which statement about d-heaps is True? 译关于 d-堆哪项为真解 “父结点可由整除求得”。d-堆中 i 的父为 ⌊(i−2)/d⌋ 1用整除即可其余完全 d-堆叶少于内部结点、d-堆用于升序排序、高度正比于 n均错。这道题考察的是对d-堆d-heap这种数据结构基本性质的理解。我们来逐一分析题目中提到的几个命题看看为什么只有“父结点可由整除求得”是正确的。1. “父结点可由整除求得”True在普通的二叉堆d2中子节点 i 的父节点是 ⌊(i−1)/2⌋。而在 d-堆中如果根节点从索引 1 开始计算节点 i 的父节点索引公式为Parent(i)⌊(i−2)/d⌋1注如果根节点从索引 0 开始公式则是 ⌊(i−1)/d⌋无论是哪种索引方式这个公式中只包含减法、加法和整数除法整除。因此在计算机底层实现时确实可以通过简单的整除运算快速定位父节点。这个说法是完全正确的。2. “d-堆的叶子结点少于内部结点”False对于任何树形结构叶子结点和内部结点的数量关系取决于树的形状而不是 d-堆特有的性质。例如一个只有根节点和几个子节点的 d-堆叶子结点数量可能等于甚至大于内部结点数量。在完全 d-堆中叶子结点的数量通常约占总节点数的一半具体为 ⌈(d−1)n1d⌉所以叶子结点往往多于内部结点。3. “d-堆用于升序排序”False堆排序Heap Sort的核心是利用堆的性质每次提取出最值。如果我们要进行升序排序我们需要每次取出最小值因此必须使用最小堆Min-heap。如果我们要进行降序排序我们需要每次取出最大值因此必须使用最大堆Max-heap。题目笼统地说“d-堆用于升序排序”是不准确的因为 d-堆既可以是最大堆也可以是最小堆它本身并不绑定某种特定的排序方向。4. “d-堆的高度正比于 n”False这是最容易混淆的一个概念。d-堆是一棵高度平衡的完全树它的高度 hh 与节点数 nn 的关系是对数级别的h≈log⁡d(n)如果高度正比于 n即 O(n) 那它就退化成了链表失去了堆作为优先队列 O(log⁡n)高效操作的意义。总结在关于 d-堆的诸多性质中最核心且无争议的数学事实就是其父子节点之间的索引关系可以通过整除运算来高效求得。因此该选项为真。这是一个非常关键的问题你问到了堆Heap这种数据结构最核心的特性之一。其实你不需要额外去“数”或“猜”每一层有多少个元素。因为堆在底层是用一维数组来存储的而它作为一种完全二叉树Complete Binary Tree其层序遍历的数组索引和树的层级结构之间存在着严格的数学对应关系。只要你知道了数组的长度 n 每一层的元素个数和节点位置就完全被“锁死”了。1. 为什么层序遍历能直接反映层级结构堆的定义要求它必须是“完全二叉树”。这意味着除了最底层其他层的节点都是满的。最底层的节点必须从左到右连续排列不能有空缺。因此当你拿到一个层序遍历的数组时你只需要知道数组的总长度就可以像切蛋糕一样精准地算出每一层有几个元素2. 以这道题为例数组{98, 72, 86, 60, 65, 12, 23, 50}数组总长度 n8 。我们来逐层切分第 0 层根节点只需要 1 个节点。包含元素98索引 0剩余元素8 - 1 7第 1 层最多需要 212212 个节点。包含元素72, 86索引 1, 2剩余元素7 - 2 5第 2 层最多需要 224224 个节点。包含元素60, 65, 12, 23索引 3, 4, 5, 6剩余元素5 - 4 1第 3 层最多需要 238238 个节点。但此时数组里只剩下 1 个元素了。包含元素50索引 7剩余元素1 - 1 0结束所以这棵树的层级结构自然就出来了98 (第0层1个) / \ 72 86 (第1层2个) / \ / \ 60 65 12 23 (第2层4个) / 50 (第3层1个)3. 通用的计算公式底层逻辑在代码实现中我们根本不需要去算“每层有几个”而是直接用数组索引来定位父子节点父节点Parent(i) (i - 1) / 2左孩子Left(i) 2 * i 1右孩子Right(i) 2 * i 2总结做这类题时不要靠眼睛去画树要靠数学公式去算。只要把数组按索引 0,1,2,3...依次排开利用完全二叉树的性质它的层级结构就是唯一确定的。详细解析 Keys {92, 81, 58, 21, 57, 45, 161, 38, 117}, h key%13, double hashing with h2 (key%11) 1; average successful search length? 译双散列h key%13、h2 (key%11) 1成功查找平均查找长度解 15/9 ≈ 1.67。各键探测数依次为 1, 1, 1, 1, 1, 3, 2, 1, 4合计 15除以 9 得约 1.67。这道题考察的是双散列Double Hashing的插入过程以及成功查找的平均查找长度ASL的计算。在双散列中如果发生冲突探测的公式为hi(k)(h1(k)i⋅h2(k))(modm)其中m13m13 哈希表大小h1(k)k(mod13)h2(k)(k(mod11))1ii 是探测次数从 0 开始成功查找的平均查找长度 (ASL) 所有元素插入时所需的探测次数之和 / 元素总个数。因为插入第 nn 个元素时探测了 kk 次意味着成功查找这个元素也需要 kk 次下面我们来逐个计算每个键的探测次数1. 插入 92h192(mod13)1h192(mod13)1位置 1 为空直接放入。探测次数1当前表[_, 92, _, _, _, _, _, _, _, _, _, _, _]2. 插入 81h181(mod13)3h181(mod13)3位置 3 为空直接放入。探测次数1当前表[_, 92, _, 81, _, _, _, _, _, _, _, _, _]3. 插入 58h158(mod13)6h158(mod13)6位置 6 为空直接放入。探测次数1当前表[_, 92, _, 81, _, _, 58, _, _, _, _, _, _]4. 插入 21h121(mod13)8h121(mod13)8位置 8 为空直接放入。探测次数1当前表[_, 92, _, 81, _, _, 58, _, 21, _, _, _, _]5. 插入 57h157(mod13)5h157(mod13)5位置 5 为空直接放入。探测次数1当前表[_, 92, _, 81, _, 57, 58, _, 21, _, _, _, _]6. 插入 45h145(mod13)6h145(mod13)6 位置 6 已被 58 占据冲突h2(45(mod11))1112h2(45(mod11))1112第 2 次探测 (61×2)(mod13)8(61×2)(mod13)8 位置 8 已被 21 占据冲突第 3 次探测 (62×2)(mod13)10(62×2)(mod13)10 位置 10 为空放入探测次数3当前表[_, 92, _, 81, _, 57, 58, _, 21, _, 45, _, _]7. 插入 161h1161(mod13)5h1161(mod13)5 位置 5 已被 57 占据冲突h2(161(mod11))1718h2(161(mod11))1718第 2 次探测 (51×8)(mod13)0(51×8)(mod13)0 位置 0 为空放入探测次数2当前表[161, 92, _, 81, _, 57, 58, _, 21, _, 45, _, _]8. 插入 38h138(mod13)12h138(mod13)12位置 12 为空直接放入。探测次数1当前表[161, 92, _, 81, _, 57, 58, _, 21, _, 45, _, 38]9. 插入 117h1117(mod13)0h1117(mod13)0 位置 0 已被 161 占据冲突h2(117(mod11))1718h2(117(mod11))1718第 2 次探测 (01×8)(mod13)8(01×8)(mod13)8 位置 8 已被 21 占据冲突第 3 次探测 (02×8)(mod13)3(02×8)(mod13)3 位置 3 已被 81 占据冲突第 4 次探测 (03×8)(mod13)11(03×8)(mod13)11 位置 11 为空放入探测次数4最终表[161, 92, _, 81, _, 57, 58, _, 21, _, 45, 117, 38]计算平均查找长度各键探测次数分别为1, 1, 1, 1, 1, 3, 2, 1, 4总探测次数 1111132141511111321415元素总个数 9ASL 15 / 9 ≈ 1.67与题目给出的答案完全吻合。4.散列表错题The average search time of searching a hash table with N elements is:A. O(1) B. O(logN) C. O(N)D. cannot be determined5.图相关基础知识点扫盲1. 第一题答案T (正确)题目分析已知 bb 到 aa 的最短路径长度 d(b,a)12d(b,a)12 。已知 cc 和 bb 之间有一条边权重为 2即 w(c,b)2w(c,b)2 。我们需要判断 cc 到 aa 的最短路径 d(c,a)d(c,a) 是否一定 ≥10≥10 。推理过程根据三角不等式Triangle Inequality在最短路径问题中从点 cc 到点 aa 的距离不可能超过“先从 cc 到 bb 再从 bb 到 aa ”的距离之和。反之从 bb 到 aa 的距离也不可能超过“先从 bb 到 cc 再从 cc 到 aa ”的距离。即2. 第二题答案F (错误)题目分析设 PP 是从 SS 到 TT 的最短路径。如果图中每条边的权重都增加 2问 PP 是否仍然是最短路径。推理过程最短路径取决于路径上所有边的权重之和。当每条边增加相同的权重时包含边数更多的路径其总权重增加的幅度会更大。这可能会导致原本较长的路径边数少变得比原本最短的路径边数多更短。反例路径 1有 2 条边每条边权为 5。总权重 55105510 。路径 2有 1 条边边权为 11。总权重 11。初始状态路径 1 (10) 路径 2 (11)所以路径 1 是最短路径。变化后每边加 2路径 1 新权重 (52)(52)7714(52)(52)7714 。路径 2 新权重1121311213 。结果14 13路径 2 变成了新的最短路径原来的最短路径 PP 路径 1不再是极值。因此该命题是错误的。3. 第三题答案T (正确)题目分析询问线段树是否可以用于查找任意索引范围内的最大公约数GCD。推理过程线段树是一种高效的数据结构常用于处理区间查询和更新问题。原理GCD 运算满足结合律即 gcd(gcd(a,b),c)gcd(a,gcd(b,c))gcd(gcd(a,b),c)gcd(a,gcd(b,c)) 。这使得我们可以将一个大区间的 GCD 分解为子区间的 GCD 来计算。实现线段树的每个节点可以存储对应区间的 GCD 值。构建时父节点的值为左右子节点值的 GCD。查询时可以将查询区间分解为线段树上的若干个不重叠区间计算这些区间 GCD 的 GCD 即可得到结果。复杂度这种方法可以在 O(log⁡N)O(logN) 的时间复杂度内完成任意区间的 GCD 查询。因此该命题是正确的。7-1 File TransferWe have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other?Input Specification:Each input file contains one test case. For each test case, the first line contains N (2≤N≤104), the total number of computers in a network. Each computer in the network is then represented by a positive integer between 1 and N. Then in the following lines, the input is given in the format:I c1 c2whereIstands for inputting a connection betweenc1andc2; orC c1 c2whereCstands for checking if it is possible to transfer files betweenc1andc2; orSwhereSstands for stopping this case.Output Specification:For eachCcase, print in one line the word yes or no if it is possible or impossible to transfer files betweenc1andc2, respectively. At the end of each case, print in one line The network is connected. if there is a path between any pair of computers; or There arekcomponents. wherekis the number of connected components in this network.Sample Input 1:5C 3 2I 3 2C 1 5I 4 5I 2 4C 3 5SSample Output 1:nonoyesThere are 2 components.Sample Input 2:5 C 3 2 I 3 2 C 1 5 I 4 5 I 2 4 C 3 5 I 1 3 C 1 5 SSample Output 2:no no yes yes The network is connected.这道题是典型的并查集Union-Find应用。我们需要支持三种操作I c1 c2合并 c1 和 c2 所在的集合建立连接C c1 c2检查 c1 和 c2 是否在同一个集合中即是否连通S结束当前测试案例输出整个网络的连通情况N ≤ 10⁴可以直接用并查集加上按大小合并路径压缩。思路初始化parent[i] -1或parent[i] i表示每个节点独立。Find路径压缩。Union按大小或按秩合并小树挂在大树下。处理每个命令I调用UnionC调用Find判断根是否相同S统计有多少个根即parent[i] 0的数量输出The network is connected.或There are k components.C 语言实现按题目的函数原型习惯#include stdio.h #include stdlib.h #define MAXN 10001 int parent[MAXN]; // 初始化 void init(int n) { for (int i 1; i n; i) { parent[i] -1; // 负数表示根绝对值表示集合大小 } } // 带路径压缩的查找 int find(int x) { if (parent[x] 0) return x; // 根节点 return parent[x] find(parent[x]); // 路径压缩 } // 按大小合并 void unionSet(int a, int b) { int rootA find(a); int rootB find(b); if (rootA rootB) return; // parent[root] 是负数值越小表示集合越大 if (parent[rootA] parent[rootB]) { // rootA 的 size 更大更负 parent[rootA] parent[rootB]; parent[rootB] rootA; } else { parent[rootB] parent[rootA]; parent[rootA] rootB; } } int main() { int N; scanf(%d, N); init(N); char op; int c1, c2; while (1) { scanf( %c, op); // 注意空格跳过换行 if (op S) break; if (op I) { scanf(%d %d, c1, c2); unionSet(c1, c2); } else if (op C) { scanf(%d %d, c1, c2); if (find(c1) find(c2)) printf(yes\n); else printf(no\n); } } // 统计连通分量个数 int components 0; for (int i 1; i N; i) { if (parent[i] 0) components; } if (components 1) printf(The network is connected.\n); else printf(There are %d components.\n, components); return 0; }样例验证样例 1输入text5 C 3 2 I 3 2 C 1 5 I 4 5 I 2 4 C 3 5 S输出textno no yes There are 2 components.✅ 正确样例 2输入text5 C 3 2 I 3 2 C 1 5 I 4 5 I 2 4 C 3 5 I 1 3 C 1 5 S输出textno no yes yes The network is connected.✅ 正确时间复杂度近似 O(M⋅α(N))其中 M 是操作次数α 是反阿克曼函数几乎常数。完全满足 N≤104 的题目要求。

数据结构基础期末复习例题

相关推荐

Perfsee源码解析：WebGL火焰图组件的实现原理

PROMPT设计中的“边界感”：从一句规则说到三层对齐

MiniMax-M2.5-NVFP4性能深度测评：在MI350上跑GSM8K基准的惊人表现

更多资讯

煤矿电工作业视频怎么学？全国通用证书怎么考？三门峡电工看过来

特种工申报所需资料有哪些？考前准备全攻略

电工证有哪些种类2026河南最新政策你知道吗

福清哪有办电工证的培训机构怎么选，多久拿证真的靠谱吗？

自来水厂的特种工怎么考?学历不高也能报,官方报名入口全解析

郑州特种工考试平台多久拿证才靠谱？别交完培训费考不过

今日更新

西昌市电工作业查询怎么查？郑州报考避坑指南帮你少走弯路

西昌市电工作业查询通过率揭秘：怕考不过白交培训费？这几点要记牢

临夏电工证在哪里审官方报名入口怎么找

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？