作成日 2013/10/19 最終更新日 2013/10/19
基本情報H24春 問7の解説
基本情報H24春 問7の解説をします。
分野:テクノロジ系
大分類:基礎理論
中分類:アルゴリズムとプログラミング
小分類:データ構造
多数のデータが単方向リスト構造で格納されている。このリスト構造には,先頭ポインタとは別に,末尾のデータを指し示す末尾ポインタがある。次の操作のうち,ポインタを参照する回数が最も多いのはどれか。
ア リストの先頭にデータを挿入する。
イ リストの先頭のデータを削除する。
ウ リストの末尾にデータを挿入する。
エ リストの末尾のデータを削除する。
「公式を導き出す 」-「2.簡単な例で考えてみる 」で説明した方法で解いてみます。
と言っても、公式(データ個数と参照回数の関係式)を出す必要はないので、参照回数がデータの個数にどう関係するかを考えるだけにとどめます。
まず、問題文で与えられているデータ構造を図にします。
注:絶対に図は書きましょう。
ここで、「管理データ」ですが、これは先頭のアドレスと末尾のアドレスを保持しているデータとします。
◆アについて、参照回数を考えます。「データ1」の前に「データ0」を追加します。その場合の最終結果は以下の通りです。
最初のデータ構造から、このデータ構造にするためには、以下の手順を踏む必要があります。
(1)データ1のポインタ(管理データが持っている)をデータ0に保持させる
(2)データ0のポインタを管理データに保持させる
ということで、ポインタの参照回数は2回 です(データ0とデータ1のポインタ)。多分。
多分と付けたのは、データ1のポインタは単にそれを値として使っているだけなので、参照と言わないかもしれないということです。
そうすると参照回数は1回(データ0)だけです。
まあ、「1」回とか「2」回という回数よりも、データの個数に関係しないということが重要です。
◆イについて、参照回数を考えます。「データ1」を削除します。その場合の最終結果は以下の通りです。
最初のデータ構造から、このデータ構造にするためには、以下の手順を踏む必要があります。
(1)データ1のポインタ(管理データが持っている)を取得する
(2)データ1のポインタを使って、データ2の先頭ポインタ(データ1が持っている)を取得する
(3)データ2のポインタを管理データに保持させる
ということで、ポインタの参照回数は2回 です(データ1とデータ2のポインタ)。
これも、もしかしたら「1」回が正しいかもしれませんが、回数よりも、データの個数に関係しないということが重要です。
◆ウについて、参照回数を考えます。「データn+1」を「データn」の後ろに追加します。その場合の最終結果は以下の通りです。
最初のデータ構造から、このデータ構造にするためには、以下の手順を踏む必要があります。
(1)データnのポインタ(管理データが持っている)を取得し、その中に「データn+1」のポインタを設定する
(2)データn+1のポインタを管理データに設定させる
ということで、ポインタの参照回数は2回 です(データnとデータn+1のポインタ)。
これも、もしかしたら「1」回が正しいかもしれませんが、回数よりも、データの個数に関係しないということが重要です。
◆エについて、参照回数を考えます。「データn」を削除します。その場合の最終結果は以下の通りです。
最初のデータ構造から、このデータ構造にするためには、以下の手順を踏む必要があります。
(1)データn-1のポインタ(データn-2が持っている)を取得し、その中の「データn」のポインタを設定解除する
(2)データn-1のポインタを管理データに設定させる
なのですが、問題なのは(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.の登録商標または商標です。
その他、社名および商品名、システム名称などは、一般に各社の商標または登録商標です。
このホームページの作成者はこれらの会社とはいっさい関係がありません。