《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 算法》数据结构章节的配套练习对应 ru/docs/chapter_data_structure/exercises.md中文版见 docs/chapter_data_structure/exercises.md为主线逐题拆解三组知识巩固题与一道编程练习题。读完本文你将掌握线性结构 / 树形结构 / 网状结构的判别方法理解数组与链表在内存中的存储差异厘清基本数据类型存什么与数据结构怎么组织的本质区别并能独立用位运算实现二进制 1 的计数。每道题都配有仓库源码级佐证便于你在 codes 目录中对照验证。练习背后的知识基石练习看似是独立的判断题实际考察的是数据结构章节的两条主线知识它们分别来自数据结构分类从逻辑结构线性 / 非线性与物理结构连续空间 / 分散空间两个维度审视数据结构基本数据类型处理器可直接处理的类型byte/short/int/long、float/double、char、bool它们以二进制形式存储。理解这两篇文档是做对练习的前提逻辑结构刻画元素之间的关系物理结构刻画数据在内存中的实际存放方式而基本数据类型只决定单元格里存的是什么东西。知识巩固一生活场景中的数据关系请根据数据之间的关系为下面三个场景选择线性结构、树形结构、网状结构中的一种并说明理由同学们排成一列每人只关心自己前面和后面的人学校按学校 → 年级 → 班级分层管理城市道路连接多个路口一个路口可以通向多个其他路口也可能形成环路。参考答案与解析场景 1线性结构。除排在最前和最后的人外每个人都只与前面和后面各一人相邻关系沿一条线展开。这正是一对一的线性关系——数组中相邻元素、链表中相邻节点都属于此类。场景 2树形结构。每个班级属于一个年级每个年级又属于学校关系从上到下分层展开形成一对多的层级。树、堆以及哈希表逻辑上都属于树形结构。场景 3网状结构。一个路口可以连接多个路口路线之间还能形成环不能排成单一顺序或严格层级体现多对多关系典型代表是图。判断结构时应先观察元素之间的关系而不是先考虑它在内存中占多少空间。这一点很关键逻辑结构与物理结构是观察同一组数据的两个不同角度内存占用属于物理层面不应参与逻辑分类。在 数据结构分类文档 中这一分类体系被明确为线性结构数组、链表、栈、队列、哈希表一对一→ 非线性结构 → 树形结构树、堆一对多与网状结构图多对多。知识巩固二逻辑顺序怎样存进内存为了保存逻辑顺序A → B → C现有两种简化的内存安排方案甲A、B、C分别放在编号为20、21、22的内存格中方案乙A、B、C分别放在编号为20、7、31的内存格中并由A记录B的位置、B记录C的位置。问 1哪个方案属于连续空间存储哪个属于分散空间存储方案甲使用连续的内存格20、21、22属于连续空间存储方案乙的节点分散在不同位置20、7、31属于分散空间存储。问 2两个方案分别更接近数组还是链表方案甲更接近数组——元素紧挨在一起靠地址偏移直接访问方案乙更接近链表——每个节点额外保存指向下一个节点的引用指针。问 3方案乙的内存格编号没有按大小排列为什么仍能表示A → B → C的逻辑顺序逻辑顺序由节点之间记录的连接关系决定而不是由内存格编号的大小决定。从A记录的位置可以找到B再从B记录的位置找到C所以仍能依次访问A、B、C。这也印证了逻辑结构和物理结构是观察同一组数据的两个不同角度。源码印证数组与链表的两种物理实现上述抽象的两种方案在仓库中都有完整的 C 语言实现可作为对照实验的实物数组连续空间array.c 演示了连续内存下的典型操作。其中insertL35-L42要把目标索引及其后的所有元素整体后移一位removeItemL46-L51则前移一位——这正是紧挨着放必须付出的代价插入 / 删除平均时间复杂度为 O(n)。链表分散空间linked_list.c 中的insertL10-L14只改两条指针P-next n1; n0-next P;即完成 O(1) 插入accessL30-L37则必须从表头逐节点head head-next前进访问第 i 个节点是 O(n)。把两个文件并排阅读连续 vs 分散带来的访问速度与增删成本差异会非常直观。仓库中所有数据结构栈、队列、哈希表、树、图等最终都建立在数组、链表或二者的组合之上——这一点在 数据结构分类文档 中有明确归纳。知识巩固三作业记录中的数据类型与结构某学习小组按座位顺序记录 4 名同学是否交了作业得到[true, false, true, true]问 1每个元素适合使用哪种基本数据类型每个元素只表示是或否适合使用布尔类型bool。在 基本数据类型文档 中bool正是用于表示是 / 否判断的类型虽然逻辑上 1 个比特0 或 1就够了但现代 CPU 以字节为最小寻址单位因此内存中通常占 1 字节。问 2这 4 个元素按座位顺序排成一列使用了什么逻辑结构元素按座位顺序排列形成线性结构可以用数组保存——数组中相邻下标即对应相邻座位。问 3如果以后改为记录每人的作业分数[90, 0, 85, 100]改变的是数据的内容类型还是组织方式改变的是内容类型元素由布尔值变成了整数。组织方式没有改变——这些数据仍然按座位顺序排成一列仍可使用数组这一线性结构。关键结论存什么与怎么组织是两回事基本数据类型描述存的是什么数据结构描述数据怎样组织。这正是 基本数据类型文档 的核心论点同一个数组结构可以承载int、float、char、bool等不同类型的数据。仓库中 basic_data_types.md 给出了 Python、C、Java、Go、Swift、Rust、C 等多种语言的对照代码例如 Java 中int[] numbers new int[5]与boolean[] bools new boolean[5]结构相同、内容类型不同。补充一点类型细节该文档有完整取值表Java 中bool默认值falseint占 4 字节可表示 2³² 个数byte占 1 字节而 Python 的int大小任意、float为 64 位双精度、无独立char类型C/C 的基本类型大小不固定取决于平台数据模型。练习中内容类型的选择因此与具体语言强相关但组织方式数组、链表、树、图在所有语言中是一致的抽象。编程练习统计二进制表示中的 1给定非负整数n请统计它的二进制表示中共有多少个 1。要求使用位运算完成不把二进制表示转换成字符串也不使用直接统计 1 的内置函数。这是一道经典的汉明重量Hamming weight问题考察的是对位运算的直觉。原练习给出了三个递进式提示下面逐一展开。提示 1用n 1探测最低位n 1取出n的最右边一位结果为 1 说明最低位是 1结果为 0 说明最低位是 0。于是每轮可以数一位。提示 2用右移逐位推进右移一位多数语言写作 1表示丢掉当前最右边的二进制位。把探测最低位和右移一位循环 n 的位数次就能数完每一位def count_ones_shift(n: int) - int: count 0 while n 0: count n 1 # 探测最低位是否为 1 n 1 # 丢掉最低位 return count时间复杂度 O(log n)循环次数等于二进制位数不依赖字符串与内置计数函数完全满足题目约束。提示 3用n (n - 1)优化完成逐位检查的版本后观察一个技巧n (n - 1)会把n中最右边的一个 1 变成 0。例如n 12二进制1100n - 1 111011二者按位与得10008——最右侧的 1 被消掉了。每执行一次就消掉一个 1循环次数等于 1 的个数而非二进制位数def count_ones_optimized(n: int) - int: count 0 while n 0: n n - 1 # 消掉最右边的 1 count 1 return count同样可用 C / Java 实现int版本循环次数最多为 32long最多为 64。复杂度对比与边界情况方案循环次数适用场景逐位检查n 1 1二进制位数如 32实现直观利于理解位运算消 1 法n (n - 1)1 的个数稀疏二进制表示下更快边界情况n 0时两种写法都直接返回 0题目限定非负整数因此无需处理负数补码的符号位问题。如果按提示走完仍想验证正确性可对n 0、n 1、n 7三个 1、n 2^31 - 131 个 1等样本做断言测试。小结本章练习用四个问题把数据结构章节最核心的认知模型串了起来逻辑结构看关系一对一 → 线性一对多 → 树形多对多 → 网状分类文档物理结构看存放连续空间数组 vs 分散空间链表对应仓库中 array.c 与 linked_list.c 的实现差异数据类型 vs 数据结构前者回答存什么后者回答怎么组织basic_data_types.md位运算实战n 1、、n (n - 1)三个运算符即可完成二进制 1 计数从 O(log n) 优化到 O(个数)。想继续深入可以接着阅读同章节的 数据结构的分类与物理实现、基本数据类型以及下一章 数组 与 链表 的完整讲义配套多语言代码位于 codes 目录可一键运行对照。【免费下载链接】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），仅供参考 《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 算法》数据结构章节的配套练习对应 ru/docs/chapter_data_structure/exercises.md中文版见 docs/chapter_data_structure/exercises.md为主线逐题拆解三组知识巩固题与一道编程练习题。读完本文你将掌握线性结构 / 树形结构 / 网状结构的判别方法理解数组与链表在内存中的存储差异厘清基本数据类型存什么与数据结构怎么组织的本质区别并能独立用位运算实现二进制 1 的计数。每道题都配有仓库源码级佐证便于你在 codes 目录中对照验证。练习背后的知识基石练习看似是独立的判断题实际考察的是数据结构章节的两条主线知识它们分别来自数据结构分类从逻辑结构线性 / 非线性与物理结构连续空间 / 分散空间两个维度审视数据结构基本数据类型处理器可直接处理的类型byte/short/int/long、float/double、char、bool它们以二进制形式存储。理解这两篇文档是做对练习的前提逻辑结构刻画元素之间的关系物理结构刻画数据在内存中的实际存放方式而基本数据类型只决定单元格里存的是什么东西。知识巩固一生活场景中的数据关系请根据数据之间的关系为下面三个场景选择线性结构、树形结构、网状结构中的一种并说明理由同学们排成一列每人只关心自己前面和后面的人学校按学校 → 年级 → 班级分层管理城市道路连接多个路口一个路口可以通向多个其他路口也可能形成环路。参考答案与解析场景 1线性结构。除排在最前和最后的人外每个人都只与前面和后面各一人相邻关系沿一条线展开。这正是一对一的线性关系——数组中相邻元素、链表中相邻节点都属于此类。场景 2树形结构。每个班级属于一个年级每个年级又属于学校关系从上到下分层展开形成一对多的层级。树、堆以及哈希表逻辑上都属于树形结构。场景 3网状结构。一个路口可以连接多个路口路线之间还能形成环不能排成单一顺序或严格层级体现多对多关系典型代表是图。判断结构时应先观察元素之间的关系而不是先考虑它在内存中占多少空间。这一点很关键逻辑结构与物理结构是观察同一组数据的两个不同角度内存占用属于物理层面不应参与逻辑分类。在 数据结构分类文档 中这一分类体系被明确为线性结构数组、链表、栈、队列、哈希表一对一→ 非线性结构 → 树形结构树、堆一对多与网状结构图多对多。知识巩固二逻辑顺序怎样存进内存为了保存逻辑顺序A → B → C现有两种简化的内存安排方案甲A、B、C分别放在编号为20、21、22的内存格中方案乙A、B、C分别放在编号为20、7、31的内存格中并由A记录B的位置、B记录C的位置。问 1哪个方案属于连续空间存储哪个属于分散空间存储方案甲使用连续的内存格20、21、22属于连续空间存储方案乙的节点分散在不同位置20、7、31属于分散空间存储。问 2两个方案分别更接近数组还是链表方案甲更接近数组——元素紧挨在一起靠地址偏移直接访问方案乙更接近链表——每个节点额外保存指向下一个节点的引用指针。问 3方案乙的内存格编号没有按大小排列为什么仍能表示A → B → C的逻辑顺序逻辑顺序由节点之间记录的连接关系决定而不是由内存格编号的大小决定。从A记录的位置可以找到B再从B记录的位置找到C所以仍能依次访问A、B、C。这也印证了逻辑结构和物理结构是观察同一组数据的两个不同角度。源码印证数组与链表的两种物理实现上述抽象的两种方案在仓库中都有完整的 C 语言实现可作为对照实验的实物数组连续空间array.c 演示了连续内存下的典型操作。其中insertL35-L42要把目标索引及其后的所有元素整体后移一位removeItemL46-L51则前移一位——这正是紧挨着放必须付出的代价插入 / 删除平均时间复杂度为 O(n)。链表分散空间linked_list.c 中的insertL10-L14只改两条指针P-next n1; n0-next P;即完成 O(1) 插入accessL30-L37则必须从表头逐节点head head-next前进访问第 i 个节点是 O(n)。把两个文件并排阅读连续 vs 分散带来的访问速度与增删成本差异会非常直观。仓库中所有数据结构栈、队列、哈希表、树、图等最终都建立在数组、链表或二者的组合之上——这一点在 数据结构分类文档 中有明确归纳。知识巩固三作业记录中的数据类型与结构某学习小组按座位顺序记录 4 名同学是否交了作业得到[true, false, true, true]问 1每个元素适合使用哪种基本数据类型每个元素只表示是或否适合使用布尔类型bool。在 基本数据类型文档 中bool正是用于表示是 / 否判断的类型虽然逻辑上 1 个比特0 或 1就够了但现代 CPU 以字节为最小寻址单位因此内存中通常占 1 字节。问 2这 4 个元素按座位顺序排成一列使用了什么逻辑结构元素按座位顺序排列形成线性结构可以用数组保存——数组中相邻下标即对应相邻座位。问 3如果以后改为记录每人的作业分数[90, 0, 85, 100]改变的是数据的内容类型还是组织方式改变的是内容类型元素由布尔值变成了整数。组织方式没有改变——这些数据仍然按座位顺序排成一列仍可使用数组这一线性结构。关键结论存什么与怎么组织是两回事基本数据类型描述存的是什么数据结构描述数据怎样组织。这正是 基本数据类型文档 的核心论点同一个数组结构可以承载int、float、char、bool等不同类型的数据。仓库中 basic_data_types.md 给出了 Python、C、Java、Go、Swift、Rust、C 等多种语言的对照代码例如 Java 中int[] numbers new int[5]与boolean[] bools new boolean[5]结构相同、内容类型不同。补充一点类型细节该文档有完整取值表Java 中bool默认值falseint占 4 字节可表示 2³² 个数byte占 1 字节而 Python 的int大小任意、float为 64 位双精度、无独立char类型C/C 的基本类型大小不固定取决于平台数据模型。练习中内容类型的选择因此与具体语言强相关但组织方式数组、链表、树、图在所有语言中是一致的抽象。编程练习统计二进制表示中的 1给定非负整数n请统计它的二进制表示中共有多少个 1。要求使用位运算完成不把二进制表示转换成字符串也不使用直接统计 1 的内置函数。这是一道经典的汉明重量Hamming weight问题考察的是对位运算的直觉。原练习给出了三个递进式提示下面逐一展开。提示 1用n 1探测最低位n 1取出n的最右边一位结果为 1 说明最低位是 1结果为 0 说明最低位是 0。于是每轮可以数一位。提示 2用右移逐位推进右移一位多数语言写作 1表示丢掉当前最右边的二进制位。把探测最低位和右移一位循环 n 的位数次就能数完每一位def count_ones_shift(n: int) - int: count 0 while n 0: count n 1 # 探测最低位是否为 1 n 1 # 丢掉最低位 return count时间复杂度 O(log n)循环次数等于二进制位数不依赖字符串与内置计数函数完全满足题目约束。提示 3用n (n - 1)优化完成逐位检查的版本后观察一个技巧n (n - 1)会把n中最右边的一个 1 变成 0。例如n 12二进制1100n - 1 111011二者按位与得10008——最右侧的 1 被消掉了。每执行一次就消掉一个 1循环次数等于 1 的个数而非二进制位数def count_ones_optimized(n: int) - int: count 0 while n 0: n n - 1 # 消掉最右边的 1 count 1 return count同样可用 C / Java 实现int版本循环次数最多为 32long最多为 64。复杂度对比与边界情况方案循环次数适用场景逐位检查n 1 1二进制位数如 32实现直观利于理解位运算消 1 法n (n - 1)1 的个数稀疏二进制表示下更快边界情况n 0时两种写法都直接返回 0题目限定非负整数因此无需处理负数补码的符号位问题。如果按提示走完仍想验证正确性可对n 0、n 1、n 7三个 1、n 2^31 - 131 个 1等样本做断言测试。小结本章练习用四个问题把数据结构章节最核心的认知模型串了起来逻辑结构看关系一对一 → 线性一对多 → 树形多对多 → 网状分类文档物理结构看存放连续空间数组 vs 分散空间链表对应仓库中 array.c 与 linked_list.c 的实现差异数据类型 vs 数据结构前者回答存什么后者回答怎么组织basic_data_types.md位运算实战n 1、、n (n - 1)三个运算符即可完成二进制 1 计数从 O(log n) 优化到 O(个数)。想继续深入可以接着阅读同章节的 数据结构的分类与物理实现、基本数据类型以及下一章 数组 与 链表 的完整讲义配套多语言代码位于 codes 目录可一键运行对照。【免费下载链接】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），仅供参考