《Hello 算法》数据结构篇练习精讲：线性/树形/网状结构判断与位运算实战

《Hello 算法》数据结构篇练习精讲线性/树形/网状结构判断与位运算实战【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇聚焦《Hello 算法》数据结构章节的配套练习docs/chapter_data_structure/exercises.md围绕两个核心问题展开如何根据元素间关系判断数据结构的逻辑类型线性、树形、网状以及如何理解逻辑结构与物理结构这对贯穿全书的基础概念文末再结合位运算完成一道计数二进制位 1 的编程练习。读完后你将掌握结构判定的方法论、连续/分散空间存储的本质区别以及n (n - 1)这类经典位技巧的推导过程。一、知识巩固三个生活场景中的结构判定本章练习的第一组题目生活场景中的数据结构给出三个场景要求从线性结构、树形结构、网状结构中选出正确类型并说明理由同学们排成一列每人只关心自己前面和后面的人学校按学校 → 年级 → 班级分层管理城市道路连接多个路口一个路口可以通向多个其他路口也可能形成环路。参考答案与判断依据线性结构。除排在最前和最后的人外每个人都只与前面和后面各一人相邻关系沿一条线展开。树形结构。每个班级属于一个年级每个年级又属于学校关系从上到下分层展开。网状结构。一个路口可以连接多个路口路线之间还能形成环不能排成单一顺序或严格层级。这里最值得记住的是参考回答末尾的方法论判断结构时应先观察元素之间的关系而不是先考虑它在内存中占多少空间。这一点在 数据结构分类 一节中有完整的理论支撑逻辑结构描述数据元素之间的逻辑关系按元素间关系可细分为线性一对一、树形一对多、网状多对多三类对应下图的分类体系可以对照着理解场景 1 的前面/后面各一人正是一对一线性关系场景 2 的学校 → 年级 → 班级是一对多的树形关系场景 3 的路口网络允许多对多且成环只有网状结构图能表达。二、逻辑顺序怎样存进内存连续存储与分散存储第二组题目把逻辑结构落到内存层面为了保存逻辑顺序A → B → C有两种简化的内存安排方案甲A、B、C分别放在编号为20、21、22的内存格中方案乙A、B、C分别放在编号为20、7、31的内存格中并由A记录B的位置、B记录C的位置。三道小问及其参考答案哪个方案属于连续空间存储哪个属于分散空间存储方案甲使用连续的内存格属于连续空间存储方案乙的节点分散在不同位置属于分散空间存储。两个方案分别更接近数组还是链表方案甲更接近数组方案乙更接近链表。方案乙的内存格编号没有按大小排列为什么仍能表示A → B → C的逻辑顺序逻辑顺序由节点之间记录的连接关系决定而不是由内存格编号的大小决定。从A记录的位置可以找到B再从B记录的位置找到C所以仍能依次访问A、B、C。第三问的答案点出了练习的核心结论逻辑结构和物理结构是观察同一组数据的两个不同角度。这与 数据结构分类 中物理结构反映了数据在计算机内存中的存储方式可分为连续空间存储数组和分散空间存储链表的论述完全对应从源码结构看仓库中数组与链表的参考实现也印证了这一分类array.py 中insert函数通过把索引index及之后的元素整体向后移动一位来插入元素正是连续存储的物理特征——编号相邻、整体搬移而 linked_list.py 中的链表节点则各自持有指向后继节点的指针元素在内存中的实际位置与逻辑顺序无关对应方案乙的分散 记录连接关系。顺带补充一个练习未展开但值得注意的点物理结构从底层决定了数据的访问、更新、增删方式连续存储和分散存储在时间与空间效率上呈互补关系——这也是练习中哪个更像数组/链表这类问题的判断底气所在。三、数据类型与数据结构[true, false, true, true]的三重追问第三组题目给出一个贴近实际的记录某学习小组按座位顺序记录 4 名同学是否交了作业得到[true, false, true, true]。三道小问分别考察数据类型、逻辑结构、内容类型 vs 组织方式的区分每个元素适合使用哪种基本数据类型每个元素只表示是或否适合使用布尔类型bool。这 4 个元素按座位顺序排成一列使用了什么逻辑结构这些元素按座位顺序排列形成线性结构可以用数组保存。如果以后改为记录每人的作业分数[90, 0, 85, 100]改变的是数据的内容类型还是组织方式改变的是内容类型元素由布尔值变成了整数。组织方式没有改变这些数据仍然按座位顺序排成一列仍可使用数组这一线性结构。参考答案的点睛句是基本数据类型描述存的是什么数据结构描述数据怎样组织。这一区分在 基本数据类型 一节中有完整论述——bool的取值范围就是false与true通常以 1 字节存储CPU 以 1 字节作为最小寻址内存单元而数组作为线性结构其元素是bool、int还是char与结构本身无关。该节同时提供了多语言Python、Java、C 等用同一数组结构存放不同类型元素的对照示例可以延伸阅读。四、编程练习统计二进制表示中的 1最后是一道编程题统计二进制表示中的 1给定非负整数n统计它的二进制表示中共有多少个 1。要求使用位运算完成不把二进制表示转换成字符串也不使用直接统计 1 的内置函数。解题提示的展开原文档给出的三条提示是n 1可以取出n的最右边一位用它判断这一位是否为 1右移一位表示丢掉当前最右边的二进制位多数语言使用运算符完成逐位检查并右移的方法后再观察n (n - 1)会把n中最右边的一个 1 变成 0。前两条提示对应最直观的逐位检查法循环执行取最低位 → 判 1 → 右移直到n变为 0代码如下以 Python 为例各语言位运算符、语义一致def count_bits(n: int) - int: 方法一逐位检查时间复杂度 O(log n) count 0 while n 0: count n 1 # 取出最低位为 1 则计数加一 n n 1 # 右移一位丢掉已检查的最低位 return count第三条提示指向更高效的去 1 法n (n - 1)会精确地把n最右边的那个 1 变 0因为减 1 会使该位借位清零、其后各位全变为 1与n做与运算后这些位全部被消掉。于是循环次数恰好等于 1 的个数低 1 位数越多的输入反而越快def count_bits_fast(n: int) - int: 方法二每次消去最右边的 1循环次数等于 1 的个数 count 0 while n 0: n n (n - 1) # 消去最低位的 1 count 1 return count这道题与本章的关联在于它训练的是对数字在内存中如何被编码与操作的手感。数字编码选读 一节解释了整数以补码形式存储、硬件以加法为核心设计电路的背景而位运算正是直接操作这些二进制位的最低层手段——n (n - 1)能成立前提正是你对补码下减 1 触发借位的行为有正确直觉。五、小结与延伸本练习文件 exercises.md 的五个题目共同覆盖了数据结构一章的三条主线逻辑结构判定先看元素间关系一对一/一对多/多对多再谈结构名称逻辑结构与物理结构分离逻辑顺序由连接关系决定内存编号的连续与否只影响访问与增删的效率特征数组 vs 链表数据类型与数据结构正交bool/int描述存的是什么数组等线性结构描述数据怎样组织。完成练习后建议按章节顺序回到 数据结构分类 与 基本数据类型 复核概念并参考 本章小结 中的 QA如哈希表为何同时包含线性与非线性结构进一步巩固后续章节中 数组 的insert/remove实现与链表节点实现可以作为连续 vs 分散存储的源码级对照阅读材料。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考