3.6 練習問題¶
3.6.1 知識の確認¶
1. 日常の場面におけるデータの関係¶
データ同士の関係に基づき、次の各場面に当てはまるものを「線形構造、木構造、ネットワーク構造」から一つ選び、理由を説明してください。
- 生徒たちが一列に並び、それぞれが自分の前と後ろの人だけを気にしています。
- 学校が「学校 → 学年 → 学級」という階層で管理されています。
- 市街地の道路が複数の交差点を結んでいます。一つの交差点から複数の別の交差点へ進め、環状の経路ができる場合もあります。
解答例
-
線形構造です。先頭と末尾以外の人は、前後に一人ずつ隣接し、関係が一本の線に沿って続きます。
-
木構造です。各学級は一つの学年に属し、各学年は学校に属します。関係が上から下へ階層的に広がります。
-
ネットワーク構造です。一つの交差点が複数の交差点につながり、経路が環を作ることもあるため、単一の順序や厳密な階層には並べられません。
構造を判断するときは、メモリ上の領域の大きさより先に、要素同士の関係を観察します。
2. 論理的な順序をメモリに格納するには¶
論理的な順序 A → B → C を保存するために、次の二つの簡略化したメモリ配置を考えます。
- 案 1：
A、B、Cを、それぞれ番号20、21、22のメモリの区画に置きます。 - 案 2：
A、B、Cを、それぞれ番号20、7、31のメモリの区画に置き、AにBの位置、BにCの位置を記録します。
- どちらが連続した領域への格納で、どちらが分散した領域への格納ですか。
- それぞれ、配列と連結リストのどちらに近いですか。
- 案 2 では区画の番号が大小順になっていないのに、なぜ
A → B → Cの論理的な順序を表せるのでしょうか。
解答例
-
案 1 は連続したメモリの区画を使うため、連続した領域への格納です。案 2 はノードが別々の位置に分散するため、分散した領域への格納です。
-
案 1 は配列、案 2 は連結リストに近い方式です。
-
論理的な順序は、メモリの区画番号の大小ではなく、ノード間に記録した接続関係で決まります。
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 かどうかを調べられます
- 右に 1 ビットシフトすると、現在の右端のビットが捨てられます。多くの言語では演算子 >> を使います
- 各ビットを調べて右シフトする方法を完成させてから、n & (n - 1) が n の右端の 1 を 0 に変えることを確かめてみましょう