# 練習問題

## 知識の確認

### 日常の場面におけるデータの関係

データ同士の関係に基づき、次の各場面に当てはまるものを「線形構造、木構造、ネットワーク構造」から一つ選び、理由を説明してください。

<!-- numbered-subquestions -->

1. 生徒たちが一列に並び、それぞれが自分の前と後ろの人だけを気にしています。
2. 学校が「学校 → 学年 → 学級」という階層で管理されています。
3. 市街地の道路が複数の交差点を結んでいます。一つの交差点から複数の別の交差点へ進め、環状の経路ができる場合もあります。

??? success "解答例"

    1. 線形構造です。先頭と末尾以外の人は、前後に一人ずつ隣接し、関係が一本の線に沿って続きます。

    2. 木構造です。各学級は一つの学年に属し、各学年は学校に属します。関係が上から下へ階層的に広がります。

    3. ネットワーク構造です。一つの交差点が複数の交差点につながり、経路が環を作ることもあるため、単一の順序や厳密な階層には並べられません。

        構造を判断するときは、メモリ上の領域の大きさより先に、要素同士の関係を観察します。

### 論理的な順序をメモリに格納するには

論理的な順序 `A → B → C` を保存するために、次の二つの簡略化したメモリ配置を考えます。

- 案 1：`A、B、C` を、それぞれ番号 `20、21、22` のメモリの区画に置きます。
- 案 2：`A、B、C` を、それぞれ番号 `20、7、31` のメモリの区画に置き、`A` に `B` の位置、`B` に `C` の位置を記録します。

<!-- numbered-subquestions -->

1. どちらが連続した領域への格納で、どちらが分散した領域への格納ですか。
2. それぞれ、配列と連結リストのどちらに近いですか。
3. 案 2 では区画の番号が大小順になっていないのに、なぜ `A → B → C` の論理的な順序を表せるのでしょうか。

??? success "解答例"

    1. 案 1 は連続したメモリの区画を使うため、連続した領域への格納です。案 2 はノードが別々の位置に分散するため、分散した領域への格納です。

    2. 案 1 は配列、案 2 は連結リストに近い方式です。

    3. 論理的な順序は、メモリの区画番号の大小ではなく、ノード間に記録した接続関係で決まります。
        `A` が記録する位置から `B` を、さらに `B` が記録する位置から `C` を見つけられるため、`A、B、C` の順にアクセスできます。

        このことからも、論理構造と物理構造は、同じデータを異なる二つの観点から捉えたものだと分かります。

### 宿題の記録に使うデータ型と構造

ある学習グループで、4 人の生徒が宿題を提出したかどうかを座席順に記録したところ、次のようになりました。

`[true, false, true, true]`

<!-- numbered-subquestions -->

1. 各要素には、どの基本データ型が適していますか。
2. 4 個の要素が座席順に一列に並ぶことで、どの論理構造を使っていますか。
3. 後で各自の宿題の点数 `[90, 0, 85, 100]` を記録するように変えた場合、変わるのはデータの「内容の型」と「組織化の方法」のどちらですか。理由を説明してください。

??? success "解答例"

    1. 各要素は「はい」か「いいえ」だけを表すため、真偽値型 `bool` が適しています。

    2. 要素は座席順に並ぶ線形構造で、配列に保存できます。

    3. 変わるのは内容の型です。要素が真偽値から整数になります。組織化の方法は変わらず、
        データは引き続き座席順に一列に並び、配列という線形構造を使えます。

        基本データ型は「何を格納するか」を表し、データ構造は「データをどう組織化するか」を表します。

## プログラミング演習

### 二進表現に含まれる 1 の数

非負整数 `n` が与えられます。その二進表現に含まれる 1 の総数を数えてください。

ビット演算を使って解いてください。二進表現を文字列に変換したり、1 の数を直接数える組み込み関数を使ったりしてはいけません。

??? tip "解くためのヒント"

    1. n & 1 で n の右端のビットを取り出し、そのビットが 1 かどうかを調べられます
    2. 右に 1 ビットシフトすると、現在の右端のビットが捨てられます。多くの言語では演算子 >> を使います
    3. 各ビットを調べて右シフトする方法を完成させてから、n & (n - 1) が n の右端の 1 を 0 に変えることを確かめてみましょう

[LeetCode](https://leetcode.com/problems/number-of-1-bits/){ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }