基本情報H24春　問7の解説

作成日　2013/10/19
最終更新日　2013/10/19

　基本情報H24春　問7の解説をします。

分野：テクノロジ系
大分類：基礎理論
中分類：アルゴリズムとプログラミング
小分類：データ構造

1.問題

　多数のデータが単方向リスト構造で格納されている。このリスト構造には，先頭ポインタとは別に，末尾のデータを指し示す末尾ポインタがある。次の操作のうち，ポインタを参照する回数が最も多いのはどれか。

ア　リストの先頭にデータを挿入する。
イ　リストの先頭のデータを削除する。
ウ　リストの末尾にデータを挿入する。
エ　リストの末尾のデータを削除する。

このページのトップへ

2.解説

　「公式を導き出す」-「2.簡単な例で考えてみる」で説明した方法で解いてみます。
　と言っても、公式（データ個数と参照回数の関係式）を出す必要はないので、参照回数がデータの個数にどう関係するかを考えるだけにとどめます。

　まず、問題文で与えられているデータ構造を図にします。
注：絶対に図は書きましょう。

　ここで、「管理データ」ですが、これは先頭のアドレスと末尾のアドレスを保持しているデータとします。

◆アについて、参照回数を考えます。「データ1」の前に「データ0」を追加します。その場合の最終結果は以下の通りです。

　最初のデータ構造から、このデータ構造にするためには、以下の手順を踏む必要があります。
　　（１）データ1のポインタ（管理データが持っている）をデータ0に保持させる
　　（２）データ0のポインタを管理データに保持させる
　ということで、ポインタの参照回数は2回です（データ0とデータ1のポインタ）。多分。
　多分と付けたのは、データ1のポインタは単にそれを値として使っているだけなので、参照と言わないかもしれないということです。
　そうすると参照回数は1回（データ0）だけです。
　まあ、「1」回とか「2」回という回数よりも、データの個数に関係しないということが重要です。

◆イについて、参照回数を考えます。「データ1」を削除します。その場合の最終結果は以下の通りです。

　最初のデータ構造から、このデータ構造にするためには、以下の手順を踏む必要があります。
　　（１）データ1のポインタ（管理データが持っている）を取得する
　　（２）データ1のポインタを使って、データ2の先頭ポインタ（データ1が持っている）を取得する
　　（３）データ2のポインタを管理データに保持させる
　ということで、ポインタの参照回数は2回です（データ1とデータ2のポインタ）。
　これも、もしかしたら「1」回が正しいかもしれませんが、回数よりも、データの個数に関係しないということが重要です。

◆ウについて、参照回数を考えます。「データn+1」を「データn」の後ろに追加します。その場合の最終結果は以下の通りです。

　最初のデータ構造から、このデータ構造にするためには、以下の手順を踏む必要があります。
　　（１）データnのポインタ（管理データが持っている）を取得し、その中に「データn+1」のポインタを設定する
　　（２）データn+1のポインタを管理データに設定させる
　ということで、ポインタの参照回数は2回です（データnとデータn+1のポインタ）。
　これも、もしかしたら「1」回が正しいかもしれませんが、回数よりも、データの個数に関係しないということが重要です。

◆エについて、参照回数を考えます。「データn」を削除します。その場合の最終結果は以下の通りです。

　最初のデータ構造から、このデータ構造にするためには、以下の手順を踏む必要があります。
　　（１）データn-1のポインタ（データn-2が持っている）を取得し、その中の「データn」のポインタを設定解除する
　　（２）データn-1のポインタを管理データに設定させる
　なのですが、問題なのは（１）です。
　データn-1のポインタを取得するためには、データn-2のポインタが必要になります。
　データn-2のポインタを取得するためには、データn-3のポインタが必要になります。
　・・・と考えていくと、データの個数に比例した参照回数が発生することが分かります。

　よって答えはエです。

このページのトップへ

このページの利用によって発生した、いかなる損害について、このホームページの作成者は責任を負いません。
このページの間違いや嘘を見つけた方、このページに書いて欲しい情報がある方はメールをお願いします。

Microsoft 、Windows 、Visual Basic および Excel は米国Microsoft Corporationの米国およびその他の国における登録商標または商標です。
ここではExcel® をエクセル、Visual Basic® for Applications をVBAと表記する場合があります。
Mac 、Mac OS 、Mac OS X は米国Apple Computer,Inc.の登録商標または商標です。
その他、社名および商品名、システム名称などは、一般に各社の商標または登録商標です。

このホームページの作成者はこれらの会社とはいっさい関係がありません。