跳转至
纸质书已发行，详情请见这里

# 3.6 练习

## 3.6.1 知识巩固

### 1. 生活场景中的数据关系

请根据数据之间的关系，为下面三个场景选择“线性结构、树形结构、网状结构”中的一种，并说明理由：

1. 同学们排成一列，每人只关心自己前面和后面的人；
2. 学校按“学校 → 年级 → 班级”分层管理；
3. 城市道路连接多个路口，一个路口可以通向多个其他路口，也可能形成环路。

参考答案

1. 是线性结构。除排在最前和最后的人外，每个人都只与前面和后面各一人相邻，关系沿一条线展开。

2. 是树形结构。每个班级属于一个年级，每个年级又属于学校，关系从上到下分层展开。

3. 是网状结构。一个路口可以连接多个路口，路线之间还能形成环，不能排成单一顺序或严格层级。

   判断结构时应先观察元素之间的关系，而不是先考虑它在内存中占多少空间。

### 2. 逻辑顺序怎样存进内存

为了保存逻辑顺序 `A → B → C`，现有两种简化的内存安排：

- 方案甲：`A、B、C` 分别放在编号为 `20、21、22` 的内存格中；
- 方案乙：`A、B、C` 分别放在编号为 `20、7、31` 的内存格中，并由 `A` 记录 `B` 的位置、`B` 记录 `C` 的位置。

1. 哪个方案属于连续空间存储？哪个属于分散空间存储？
2. 两个方案分别更接近数组还是链表？
3. 方案乙的内存格编号没有按大小排列，为什么仍能表示 `A → B → C` 的逻辑顺序？

参考答案

1. 方案甲使用连续的内存格，属于连续空间存储；方案乙的节点分散在不同位置，属于分散空间存储。

2. 方案甲更接近数组，方案乙更接近链表。

3. 逻辑顺序由节点之间记录的连接关系决定，而不是由内存格编号的大小决定。 从 `A` 记录的位置可以找到 `B`，再从 `B` 记录的位置找到 `C`，所以仍能依次访问 `A、B、C`。

   这也说明逻辑结构和物理结构是观察同一组数据的两个不同角度。

### 3. 作业记录中的数据类型与结构

某学习小组按座位顺序记录 4 名同学是否交了作业，得到：

`[true, false, true, true]`

1. 每个元素适合使用哪种基本数据类型？
2. 这 4 个元素按座位顺序排成一列，使用了什么逻辑结构？
3. 如果以后改为记录每人的作业分数 `[90, 0, 85, 100]`，改变的是数据的“内容类型”还是“组织方式”？说明理由。

参考答案

1. 每个元素只表示“是”或“否”，适合使用布尔类型 `bool`。

2. 这些元素按座位顺序排列，形成线性结构，可以用数组保存。

3. 改变的是内容类型：元素由布尔值变成了整数。组织方式没有改变， 这些数据仍然按座位顺序排成一列，仍可使用数组这一线性结构。

   基本数据类型描述“存的是什么”，数据结构描述“数据怎样组织”。

## 3.6.2 编程练习

### 1. 统计二进制表示中的 1

给定非负整数 `n`，请统计它的二进制表示中共有多少个 1。

要求使用位运算完成，不把二进制表示转换成字符串，也不使用直接统计 1 的内置函数。

解题提示

1. n & 1 可以取出 n 的最右边一位，用它判断这一位是否为 1
2. 右移一位表示丢掉当前最右边的二进制位；多数语言使用运算符 >>
3. 完成逐位检查并右移的方法后，再观察：n & (n - 1) 会把 n 中最右边的一个 1 变成 0

LeetCode 题目解析

##### 欢迎在评论区留下你的见解、问题或建议