3.6 练习¶
3.6.1 知识巩固¶
1. 生活场景中的数据关系¶
请根据数据之间的关系，为下面三个场景选择“线性结构、树形结构、网状结构”中的一种，并说明理由：
- 同学们排成一列，每人只关心自己前面和后面的人；
- 学校按“学校 → 年级 → 班级”分层管理；
- 城市道路连接多个路口，一个路口可以通向多个其他路口，也可能形成环路。
参考答案
-
是线性结构。除排在最前和最后的人外，每个人都只与前面和后面各一人相邻，关系沿一条线展开。
-
是树形结构。每个班级属于一个年级，每个年级又属于学校，关系从上到下分层展开。
-
是网状结构。一个路口可以连接多个路口，路线之间还能形成环，不能排成单一顺序或严格层级。
判断结构时应先观察元素之间的关系，而不是先考虑它在内存中占多少空间。
2. 逻辑顺序怎样存进内存¶
为了保存逻辑顺序 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。这也说明逻辑结构和物理结构是观察同一组数据的两个不同角度。
3. 作业记录中的数据类型与结构¶
某学习小组按座位顺序记录 4 名同学是否交了作业，得到：
[true, false, true, true]
- 每个元素适合使用哪种基本数据类型？
- 这 4 个元素按座位顺序排成一列，使用了什么逻辑结构？
- 如果以后改为记录每人的作业分数
[90, 0, 85, 100]，改变的是数据的“内容类型”还是“组织方式”？说明理由。
参考答案
-
每个元素只表示“是”或“否”，适合使用布尔类型
bool。 -
这些元素按座位顺序排列，形成线性结构，可以用数组保存。
-
改变的是内容类型：元素由布尔值变成了整数。组织方式没有改变， 这些数据仍然按座位顺序排成一列，仍可使用数组这一线性结构。
基本数据类型描述“存的是什么”，数据结构描述“数据怎样组织”。
3.6.2 编程练习¶
1. 统计二进制表示中的 1¶
给定非负整数 n，请统计它的二进制表示中共有多少个 1。
要求使用位运算完成，不把二进制表示转换成字符串，也不使用直接统计 1 的内置函数。
解题提示
- n & 1 可以取出 n 的最右边一位，用它判断这一位是否为 1
- 右移一位表示丢掉当前最右边的二进制位；多数语言使用运算符 >>
- 完成逐位检查并右移的方法后，再观察：n & (n - 1) 会把 n 中最右边的一个 1 变成 0