hello-algo/ja/docs/chapter_data_structure/exercises.md

練習問題

知識の確認

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

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

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 の位置を記録します。

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]

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{ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }