平成28年春期試験午後問題 問8
問8 データ構造及びアルゴリズム
次のプログラムの説明及びプログラムを読んで，設問1，2に答えよ。
携帯端末上で稼働する簡易メモ帳の機能のうち，メモの編集処理(メモの追加・削除・変更・移動)を行う部分のプログラムである。図1は，簡易メモ帳に4件のメモ "Aoki"，"Imai"，"Uno"及び"Endo"を登録した場合の表示例である。
〔プログラムの説明〕 
携帯端末上で稼働する簡易メモ帳の機能のうち，メモの編集処理(メモの追加・削除・変更・移動)を行う部分のプログラムである。図1は，簡易メモ帳に4件のメモ "Aoki"，"Imai"，"Uno"及び"Endo"を登録した場合の表示例である。
- メモは，画面に表示可能な1バイトで表現できる文字から成る文字列である。各メモは，文字列の前に，文字列の長さ(0～255)を1バイトの符号なし2進整数の形式で付け加えて格納する。例えば，メモ"Hello!"は，次の形式で格納する(以下，文字列の長さは10進数で表記し，その値に下線を付けて表す)。
- メモの格納と管理のために，2個の配列 Memo[]，Data[] と，4個の変数 MemoCnt，MemoMax，DataLen，Datamax を使用する。
各メモは，配列 Data[] の先頭から順に，1要素に1バイトずつ(1)で示した形式で格納し，その格納位置の情報を配列 Memo[] に設定して管理する。
MemoMax は格納できるメモの最大件数(配列 Memo[] の要素数)，MemoCnt は現在 格納されているメモの件数である。
DataMax は格納できる最大文字数(配列 Data[] の要素数)，DataLen は現在格納されている文字数である(文字数には，文字列の長さの情報を含む)。 - 簡易メモ帳の画面には，配列 Memo[] の要素番号の昇順に，それが指すメモを取り出して，メモを表示する。図1の表示例は，図3(後出)の状態に対応している。
- メモの編集処理を行うための関数の概要は，次の①～⑤のとおりである。これらの関数が呼ばれるとき，引数の内容や配列の空き状態などは事前に検査済みで，正しく実行できるものとする。
なお，以降の図に示す実行例では，MemoMax＝5，DataMax＝25としている。
- 関数: resetMemo()
全てのメモを消去する。MemoCnt と DataLen に0を設定することによって，Memo[] と Data[] の全要素を"空き"の状態にする。
resetMemo()を実行した後の配列・変数の状態を，図2に示す。以降の図で，網掛け部分 は，その配列要素が"空き"であることを表す。
- 関数: addMemo(整数型: TextLen，文字列型: text)
1件のメモを追加する。長さ textLen の文字列 text をData[] の最初の空き要素以降に格納し，その格納位置の情報を Memo[] に設定する。図2の状態から，- addMemo(4，"Aoki")
- addMemo(4，"Imal")
- addMemo(3，"Uno")
- addMemo(4，"Endo")
- 関数: deleteMemo(整数型: pos)
1件のメモを削除する。Memo[] の要素番号 pos＋1 以降の内容をそれぞれ一つ前の要素に移し，MemoCnt から1を減じることによって，Memo[pos] が指すメモを削除する(表示の対象から除く)。Data[] 中の参照されなくなったメモは，そのまま残す。図3の状態から，deleteMemo(O) を実行した後の配列・変数の状態を，図4に示す。以降の図で，斜線部分
は，参照されなくなったメモであることを表す。
- 関数: changeMemo(整数型: pos，整数型: textLen，文字列型: text)
1件のメモの内容を変更する。長さ textLen の文字列 text を Data[] の 最初の空き要素以降に格納し，その格納位置の情報を Memo[pos] に 設定することによって，Memo[pos] が指すメモの内容を変更する。Data[] 中の参照されなくなったメモは，そのまま残す。図4の状態から changeMemo(2，3，"Abe") を 実行した後の配列・変数の状態を，図5に示す。
- 関数: moveMemo(整数型: fromPos，整数型: toPos)
1件のメモを移動する。Memo[] の要素の並び順を変えて，Memo[fromPos] の 内容を Memo[toPos] の位置に移動する。fromPos＜toPos の場合は，Memo[fromPos] の値を取り出し，Memo[fromPos＋1]～Memo[toPos] の内容を前方に1要素分ずらし，取り出した値を Memo[toPos] に設定するという操作を行う。fromPos＞toPos の場合も，これと同様の操作を行う。図5の状態から moveMemo(2，0) を実行した後の配列・変数の状態を，図6に示す。
広告
設問1
プログラム中の に入れる正しい答えを，解答群の中から選べ。
a，b に関する解答群
- DataLen
- DataLen ＋ 1
- DataLen ＋ textLen
- DataLen ＋ textLen ＋ 1
- textLen
- textLen ＋ 1
c に関する解答群
- MemoCnt － pos
- pos － 1
- pos
- pos ＋ 1
d に関する解答群
- fromPos，i ≧ toPos－1，－1
- fromPos，i ≧ toPos＋1，－1
- toPos，i ≦ fromPos－1，1
- toPos，i ≦ fromPos＋1，1
解答選択欄
- a:
- b:
- c:
- d:
- a=ア
- b=ウ
- c=エ
- d=イ
解説
〔aについて〕具体例として図3の状態に addMemo(3, "Oka") を実行した場合を考えてみましょう。
文字列の追加される位置は Data[] の最初の空き要素以降、すなわち現在格納されている文字データの直後になります。Data[] に格納されている文字数は DataLen が保持しているので、追加する文字列の開始位置は、文字列追加前の DataLen の値と等しくなります。よって Memo[MemoCnt] に代入されるのは DataLen の値です。
上記の例でも、Memo[4] に 追加前の DataLen の値である 19 が格納されています。
〔bについて〕
addMemo() を実行すると、Data[] には"文字列の長さを表す数字"＋追加文字列が追記されるので DataLen は textLen + 1 だけ増えることになります。しかし、addMemo() および changeMemo() では、Data[] に"文字列の長さを表す数字"を加える処理をした直後に DataLen を 1 増やしているので、bで増やすのは追加した文字列の長さ分だけになります。
∴b＝ウ：DataLen + textLen
〔cについて〕
deleteMemo() は削除位置 pos を引数にとり、削除する要素の位置まで Memo[] の要素を前詰めすることによって該当するメモを削除しています。
Memo[i - 1] ← Memo[i]
i ← i + 1
のループ処理で行っており、i はこの繰り返し処理の初期値になっています。上図の deleteMemo(0) の例における1回目の前詰め処理は Memo[0] ← Memo[1] ですので、これを満たすような i の初期値を考えると 1 であればよいとわかります。つまり pos で指定された位置＋1を i に設定すれば、期待通りの処理が行われることになります。よってcには pos + 1 が入ります。i ← i + 1
∴c＝エ：pos + 1
〔dについて〕
dを含む部分は fromPos ＞ toPos のときに行われる処理です。図6は正に fromPos ＞ toPos である moveMemo(2, 0) の実行後の状態です。
図5の状態から図6の状態に Memo[] を変化させるには、Memo[2]の内容を変数に格納した後、Memo[2] ← Memo[1]、Memo[1] ← Memo[0] という操作を行わなくてはなりません。
Memo[i] ← Memo[i - 1]
moveMemo(2, 0) の場合は、Memo[2] ← Memo[1]、Memo[1] ← Memo[0] という順で処理が行われるので i = 2、i = 1 という2回のループになります。これを満たすためには、i の初期値が 2 であり、i を 1 ずつ減らしながら、i が 1 になるまで繰り返すことになります。moveMemo() の引数とループ条件の関係を考えると、2＝fromPos、1＝toPos＋1 ですから、dには fromPos, i≧toPos+1, -1 が入ります。∴d＝イ：fromPos, i≧toPos+1, -1
広告
設問2
次の記述中の に入れる正しい答えを，解答群の中から選べ。
このメモの管理方法では，削除されたメモや変更前のメモは，Data[] 中に参照されない状態で残っている。その結果，DataLen の値は一方的に増加し，やがて Data[] 中の空き要素が枯渇する。次に示す関数 clearGarbage()は，Data[] 中の参照されなくなったメモを取り除き，空き要素を増やすための関数である。
プログラムの配列・変数が図6に示す状態のときに，clearGarbage() を実行すると，実行が終了した時点で，Memo[1] の値はe，Memo[2] の値はf，DataLen の値はgとなる。
このメモの管理方法では，削除されたメモや変更前のメモは，Data[] 中に参照されない状態で残っている。その結果，DataLen の値は一方的に増加し，やがて Data[] 中の空き要素が枯渇する。次に示す関数 clearGarbage()は，Data[] 中の参照されなくなったメモを取り除き，空き要素を増やすための関数である。
e，f，g に関する解答群
- 0
- 3
- 4
- 5
- 7
- 9
- 10
- 12
- 13
- 23
解答選択欄
- e:
- f:
- g:
- e=ウ
- f=カ
- g=ケ
解説
プログラムをトレースしていくことで答えを導きます。clearGarbage() の対象となる図6は以下の状態です。- DataLen ← 0
- DataLen を 0 で初期化
- (分岐) MemoCnt = 0
- MemoCnt は 3 なので、false と判定される
- m:0, m＜3, 1
- m を 0 から 2 まで 1 ずつ増やしながら繰り返す
- d ← Memo[0]
- d に 19 が格納される
- Memo[0] ← DataLen
- Memo[0] に 0 が格納される
- i:0, i≦Data[19], 1
- i を 0 から 3 まで 1 ずつ増やしながら繰り返す
- temp[Datalen] ← Data[d + i]
DataLen = DataLen + 1 - temp[0] に Data[19] を格納して、DataLen を 1 増やす
temp[1] に Data[20] を格納して、DataLen を 1 増やす
temp[2] に Data[21] を格納して、DataLen を 1 増やす
temp[3] に Data[22] を格納して、DataLen を 1 増やす
DataLen は 4 になる
- d ← Memo[1]
- d に 5 が格納される
- Memo[1] ← DataLen
- Memo[1] に 4 が格納される
- i:0, i≦Data[5], 1
- i を 0 から 4 まで 1 ずつ増やしながら繰り返す
- temp[Datalen] ← Data[d + i]
DataLen = DataLen + 1 - temp[4] に Data[5] を格納して、DataLen を 1 増やす
temp[5] に Data[6] を格納して、DataLen を 1 増やす
temp[6] に Data[7] を格納して、DataLen を 1 増やす
temp[7] に Data[8] を格納して、DataLen を 1 増やす
temp[8] に Data[9] を格納して、DataLen を 1 増やす
DataLen は 9 になる
- d ← Memo[2]
- d に 10 が格納される
- Memo[2] ← DataLen
- Memo[2] に 9 が格納される
- i:0, i≦Data[10], 1
- i を 0 から 3 まで 1 ずつ増やしながら繰り返す
- temp[Datalen] ← Data[d + i]
DataLen = DataLen + 1 - temp[9] に Data[10] を格納して、DataLen を 1 増やす
temp[10] に Data[11] を格納して、DataLen を 1 増やす
temp[11] に Data[12] を格納して、DataLen を 1 増やす
temp[12] に Data[13] を格納して、DataLen を 1 増やす
DataLen は 13 になる
∴e＝ウ：4
f＝カ：9
g＝ケ：13
広告
広告