基本情報技術者過去問題平成25年春期午後問8(データ構造及びアルゴリズム)

基本情報技術者過去問題平成25年春期午後問8

問8　データ構造及びアルゴリズム

　次のプログラムの説明及びプログラムを読んで，設問1，2に答えよ。

　ある食料品店では，従来の特売方法に加えて，新たに選択型特売を始めることになった。選択型特売とは，例えば3種類の商品中から合計3個(3商品を各1個，同一商品を3個など)を選択して購入すれば値引きをするという特売方法である。
　このプログラムは，レジ用プログラムの一部として，選択型特売の値引き処理をする。プログラムの実行は，顧客がレジに持ち込んだ商品のバーコードを全て読み込んで，購入する商品が確定した時点で行うものとする。

〔プログラムの説明〕

顧客がレジに持ち込んだ商品の情報(以下，購入情報という)及び1種類の選択型特売についての商品の情報(以下，特売情報という)は，次のように宣言された大域の変数及び配列で他のレジ用プログラムと受け渡す。配列の添字は，1から始まる。
購入情報の内容は，次のとおりである。図1は，購入情報のデータ例である。
1. 購入[]は，ptr，品番，品名，単価，数量，金額 のメンバーから成る1レコードを1要素とする構造型の配列である。
2. 購入[]には，購入する商品の情報が，バーコードを読み込んだ順に添字 1 の要素から格納されている。同一品番の商品の情報は，1 レコードにまとめられており，品番の重複はない。
3. 購入[]中の ptr は，レコードを品番の昇順にたどるポインタであり，次に大きい品番をもつレコードが格納されている要素の添字が入っている。最も大きい品番をもつレコードの ptr 値は 0 である。
4. ptr 起点は，最も小さい品番をもつレコードが格納されている購入[]の要素の添字を示す。
5. 購入行数は，購入[]中に格納されたレコード件数を示す。
特売情報の内容は，次のとおりである。
1. 特売は，品番，品名，単価，数量 のメンバーから成る構造型の変数である。品番，品名，単価 には，特売を一つの商品とみなして付けた品番，特売の名称，値引き額が,それぞれ格納されている。
2. 対象[]は，品番，数量 のメンバーから成る1レコードを1要素とする構造型の配列である。品番には，特売対象の商品の品番が格納されている。対象[]には，要素が品番の昇順に添字1から格納されている。
3. 対象行数は，対象[]中に格納されたレコード件数を示す。
4. 指定数量は，特売対象の商品を合計何個購入する必要があるかを示す。
5. 対象[]中及び特売中の数量には，初期値0が格納されている。
6. 図2には，特売情報のデータ例として，次の特売例を示してある。
処理は，検索部，計算部，更新部から成り，この順に実行する。
1. 検索部では，対象[]中の各品番が購入[]中にあれば，購入[]中の該当するレコードの数量の値を，対象[]中の数量に格納する。
2. 計算部では，対象[]中の各数量の値の合計を指定数量で割った商を，特売中の数量に格納する。
3. 更新部では，特売中の数量の値が1以上であれば，購入[]に特売のレコードを追加し，購入情報を更新する。
メンバーの参照は，例えば，購入[3]の品番を参照するときは，購入[3].品番と記述する。
図1及び図2のデータ例を用いてプログラムを実行した結果は，図3及び図4のとおりである。図3及び図4中の網掛け部分は，実行によって内容が変更された箇所であることを示す。

設問1

プログラム中の　に入れる正しい答えを，解答群の中から選べ。

a，b に関する解答群

K ← K ＋ 1
K ← ptr 起点
K ← 購入[K].ptr
T ← 1
T ← T ＋ 1

c，d に関する解答群

K
Kp
購入[K] .ptr
購入[Kp].ptr
購入[購入行数].ptr
購入行数

解答選択欄

解答

a=ウ
b=オ
c=カ
d=ア

解説

まず購入情報で使われている ptr について確認しておきます。

問題文(2)③より、ptr とは、購入情報のレコードを品番の昇順にたどるためのポインタであることがわかります。例えば図1の場合、品番を昇順にたどるためには下記の順番で購入[]のレコードを読む必要があります。

　2行目→1行目→4行目→5行目→3行目

これは ptr を使用することで下記のように表現できます。

　ptr起点(=2)→購入[2].ptr(=1)→購入[1].ptr(=4)→購入[4].ptr(=5)→購入[5].ptr(=3)

ptr起点には最も品番の値が小さなレコードの位置が入っており、各要素の ptr には次に大きい品番の値を持ったレコードの位置が格納されていることになります。

〔a，bについて〕
空欄を含むループ文は、問題文(4)①に説明があるように、対象[]中の各品番が購入[]中にあれば、購入[]中の該当するレコードの数量の値を、対象[]中の数量に格納する処理です。

このループの中では以下の命令で対象レコードの数量を更新しています。

対象[T].数量 ← 購入[K].数量

この命令が実行されるのは、購入レコードの品番と対象レコードの品番が一致したときです。両者が一致した以上、現在の購入レコードの品番が他の対象レコードの品番と一致することはないので、購入レコードを次に進める必要があります。また、他の購入レコードの品番が現在の対象レコードの品番と一致することはないので、対象レコードも次に進める必要があります。例えば、品番222で一致したときを考えると、品番の重複はないので他の購入レコードの品番が222であることはありませんし、品番222の購入レコードが別の対象レコードに重複一致することもありません。したがって、両方のレコードを次に進める必要があります。

購入[K]の次のレコードの位置は"購入[K].ptr"、対象[T]の次のレコードの位置は"T+1"なので、KとTを各値で更新することになります。よって、「ウ」と「オ」が[a]と[b]に入る処理となります。

どちらがどの空欄に入るかは2つ目の[a][b]を見て判断することになります。[a]が実行される条件を見ると、「購入レコードの品番＜対象レコードの品番」の場合となっています。この場合は、購入レコードを進めることで現在の対象レコードに一致する可能性があるので、購入レコードだけを先に進めることになります。

逆に「購入レコードの品番＞対象レコードの品番」の場合には、対象レコードだけを先に進めることになります。

したがって[a]には「K ← 購入[K].ptr」が、[b]には「T ← T ＋ 1」が入ります。

∴a＝ウ：K ← 購入[K].ptr
　b＝オ：T ← T ＋ 1

〔c，dについて〕
更新部では特売のレコードを購入情報に挿入するとともに、購入情報内のポインタによる連結を適切に更新する処理を行っています。この問題では以下のループ処理で、変数 Kp および K に何を求めているのかを考えることが肝となっています。

(K > 0) and (購入[K].品番 < 特売.品番)
・Kp ← K
・K ← 購入[K].ptr

このループ処理は購入[K].品番が特売の品番以上となったとき、若しくは購入レコードの末尾に達したときに終了します。このとき、K には購入レコードのうち、特売.品番の次に大きな品番を持つレコードの位置、Kp には購入レコードのうち、特売.品番の次に小さな品番を持つレコードの位置が格納されていることになります。つまり、下記の関係が成り立ちます。

　購入[Kp].品番 < 特売.品番 < 購入[K]の品番

この2つは、特売レコードの前後に位置することになるレコードです（ループが末尾に達したときはK＝0なので、後ろのレコードはない）。

購入[Kp] は特売レコードの一つ前のレコードですので、購入[Kp].ptr を特売のレコードを参照するポインタに更新しなければなりません。特売のレコードは購入情報の末尾に挿入されるので、[c]には「購入行数」が入ります。また、Kp が 0 であるときは購入レコードの中に特売.品番よりも小さな品番を持つレコードが存在しなかったということですから、prt起点に特売のレコードを参照するためのポインタ、すなわち「購入行数」を設定することになります。

[d]は特売のレコードの ptr に設定される値ですから、上記の関係より「K」を設定するのが適切です。

∴c＝カ：購入行数
　d＝ア：K

設問2

次の記述中の　に入れる正しい答えを，解答群の中から選べ。

　商品のバーコードを読み込む段階で，その時点までに読み込んだ商品の金額の小計を，値引きを反映した金額で表示したい。そこで，商品のバーコードを読み込んだときに選択型特売に該当する商品ならば，都度このプログラムを実行するように修正したい。また，読込み済み商品の購入の取消しにも対応したい。ここで，対象[]中及び特売中の数量には，初期値 0 を格納してプログラムを呼び出す。
　この方法では，特売のレコードを購入[]に書き込むとき，既に購入[]中にその特売のレコードが存在していることがある。また，値引きが成立していた特売のレコード中の数量が 0 になったとき，その特売のレコードの削除が必要になることがある。
　特売のレコードの取扱いは，表1に示す処理に分けられる。

　処理①～④のうち，eは、特売のレコードの更新処理であり，fは特売のレコードの削除処理である。
　そこで，プログラムの修正方法として，検索部と計算部は変更せず，更新部を次のように変更することにした。

プログラムの中の　の部分を，次の条件式で置き換える。
プログラムの末尾に，次の処理を追加する。

　なお，更新処理では，更新前と更新後の特売のレコード中の数量が同じになる場合でも処理を行う。また，削除処理では，該当する特売のレコードを格納していた配列の要素はそのまま残し，ポインタの付替えによってレコードを無効にする。

e，f に関する解答群

処理①
処理②
処理③
処理④

g に関する解答群

K
Kp
購入[K].ptr
購入[Kp].ptr
購入[購入行数].ptr
購入行数

解答選択欄

解答

e=イ
f=ア
g=ウ

解説

〔eについて〕
特売のレコードを更新するときは、既に購入情報に特売のレコードが存在しており、特売.数量が0よりも大きいときです。例えば、図3の状態でB社緑茶500mlを3本追加購入すると、特売のレコード「B社お茶3本100円引き」の数量を2から3に更新する必要があります。したがって処理②が該当します。

∴e＝イ：処理②

〔fについて〕
特売のレコードを削除するときは、既に購入情報に特売のレコードが存在しており、特売.数量が0（値引き適用なし）になったときです。問題文にも下記のように記載されています。

「値引きが成立していた特売のレコード中の数量が 0 になったとき，その特売のレコードの削除が必要になることがある。」

したがって処理①が該当します。

∴f＝ア：処理①

〔gについて〕
空欄を含む処理は、特売.数量が0であることを実行条件としています。表1を参照すると、特売.数量=0 のときの処理は以下のように場合分けできます。

特売のレコードが存在する: 特売のレコードを削除する
特売のレコードが存在しない: 何もしない

何もしない場合は特に処理を記述する必要はないはずなので、本部分は特売のレコードを削除する処理であると判断できます。

購入情報に特売のレコードが存在しないことが前提であるときは、更新部冒頭のループ処理で求められる Kp および K は、特売のレコードの前後となるレコード位置を示していましたが、購入情報に特売のレコードが存在している場合には、特売のレコードに達した時点で継続条件の「購入[K].品番 < 特売.品番」が偽となりループから抜けることになるので、Kp および K には以下の値が格納されていることになります。

Kp: 特売のレコードの1つ前のレコードの位置（変更前と同じ）
K: 特売のレコードの位置

削除処理はポインタの付替えによって行うとあるので、特売のレコードをポインタの連結から外すためには、購入[K](特売のレコード)の ptr を購入[Kp]の ptr に付け替えることになります。したがって、[g]には「購入[K].ptr」が入ります。

∴g＝ウ：購入[K].ptr

平成25年春期午後問題一覧

問1　問2　問3　問4　問5　問6　問7　問8　問9　問10　問11　問12　問13　採点講評