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

基本情報H24春 問7の解説

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


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

1.問題
2.解説


1.問題

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


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

2.解説

 「公式を導き出す」-「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のポインタが必要になります。
 ・・・と考えていくと、データの個数に比例した参照回数が発生することが分かります。

 よって答えはエです。
Prev Up Next  Top
このページのトップへ


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

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

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