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

⇄問題文と設問を画面2分割で開く⇱問題PDF

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

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

 携帯端末上で稼働する簡易メモ帳の機能のうち,メモの編集処理(メモの追加・削除・変更・移動)を行う部分のプログラムである。図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としている。
  1. 関数: resetMemo()
     全てのメモを消去する。MemoCnt と DataLen に0を設定することによって,Memo[] と Data[] の全要素を"空き"の状態にする。
     resetMemo()を実行した後の配列・変数の状態を,図2に示す。以降の図で,網掛け部分 は,その配列要素が"空き"であることを表す。
  2. 関数: addMemo(整数型: TextLen,文字列型: text)
     1件のメモを追加する。長さ textLen の文字列 text をData[] の最初の空き要素以降に格納し,その格納位置の情報を Memo[] に設定する。図2の状態から,
    • addMemo(4,"Aoki")
    • addMemo(4,"Imal")
    • addMemo(3,"Uno")
    • addMemo(4,"Endo")
    をこの順に実行した後の配列・変数の状態を,図3に示す。
  3. 関数: deleteMemo(整数型: pos)
     1件のメモを削除する。Memo[] の要素番号 pos+1 以降の内容をそれぞれ一つ前の要素に移し,MemoCnt から1を減じることによって,Memo[pos] が指すメモを削除する(表示の対象から除く)。Data[] 中の参照されなくなったメモは,そのまま残す。図3の状態から,deleteMemo(O) を実行した後の配列・変数の状態を,図4に示す。以降の図で,斜線部分は,参照されなくなったメモであることを表す。
  4. 関数: changeMemo(整数型: pos,整数型: textLen,文字列型: text)
     1件のメモの内容を変更する。長さ textLen の文字列 text を Data[] の 最初の空き要素以降に格納し,その格納位置の情報を Memo[pos] に 設定することによって,Memo[pos] が指すメモの内容を変更する。Data[] 中の参照されなくなったメモは,そのまま残す。図4の状態から changeMemo(2,3,"Abe") を 実行した後の配列・変数の状態を,図5に示す。
  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") を実行した場合を考えてみましょう。
pm08_11.png/image-size:426×240
Memo[] はメモごとの開始位置を保持する配列です。そして MemoCnt は、現在のメモの件数を保持しているので、aの格納先である Memo[MemoCnt] は、新たに追加される文字列の開始位置を格納する要素になります。上記の例では Memo[MemoCnt] は Memo[4] になります。

文字列の追加される位置は Data[] の最初の空き要素以降、すなわち現在格納されている文字データの直後になります。Data[] に格納されている文字数は DataLen が保持しているので、追加する文字列の開始位置は、文字列追加前の DataLen の値と等しくなります。よって Memo[MemoCnt] に代入されるのは DataLen の値です。

上記の例でも、Memo[4] に 追加前の DataLen の値である 19 が格納されています。
pm08_12.png/image-size:426×240
a=ア:DataLen

bについて〕
addMemo() を実行すると、Data[] には"文字列の長さを表す数字"+追加文字列が追記されるので DataLen は textLen + 1 だけ増えることになります。しかし、addMemo() および changeMemo() では、Data[] に"文字列の長さを表す数字"を加える処理をした直後に DataLen を 1 増やしているので、bで増やすのは追加した文字列の長さ分だけになります。
pm08_13.png/image-size:333×260
したがってbには DataLen + textLen が入ります。

b=ウ:DataLen + textLen

cについて〕
deleteMemo() は削除位置 pos を引数にとり、削除する要素の位置まで Memo[] の要素を前詰めすることによって該当するメモを削除しています。
pm08_14.png/image-size:393×116
上記の例では、MemoCnt を 1 減らすとともに、Memo[0] ← Memo[1]、Memo[1] ← Memo[2]、Memo[2] ← Memo[3] という順で処理が行われます。DeleteMemo 内では、これを
Memo[i - 1] ← Memo[i]
i ← i + 1
のループ処理で行っており、i はこの繰り返し処理の初期値になっています。上図の deleteMemo(0) の例における1回目の前詰め処理は Memo[0] ← Memo[1] ですので、これを満たすような i の初期値を考えると 1 であればよいとわかります。つまり pos で指定された位置+1を i に設定すれば、期待通りの処理が行われることになります。よってcには pos + 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] という操作を行わなくてはなりません。
pm08_15.png/image-size:393×115
プログラム中ではこの繰り返し処理を以下の文で行っています。
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[] 中の参照されなくなったメモを取り除き,空き要素を増やすための関数である。
pm08_10.png/image-size:250×319
 プログラムの配列・変数が図6に示す状態のときに,clearGarbage() を実行すると,実行が終了した時点で,Memo[1] の値はe,Memo[2] の値はf,DataLen の値はgとなる。
e,f,g に関する解答群
  • 0
  • 3
  • 4
  • 5
  • 7
  • 9
  • 10
  • 12
  • 23

解答選択欄

  • e:
  • f:
  • g:

解答

  • e=
  • f=
  • g=

解説

プログラムをトレースしていくことで答えを導きます。clearGarbage() の対象となる図6は以下の状態です。
pm08_8.png/image-size:393×116
DataLen ← 0
DataLen を 0 で初期化
(分岐) MemoCnt = 0
MemoCnt は 3 なので、false と判定される
m:0, m<3, 1
m を 0 から 2 まで 1 ずつ増やしながら繰り返す
//m = 0 のループ
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 になる
pm08_16.png/image-size:397×167
//m = 1 のループ
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 になる
pm08_17.png/image-size:397×167
//m = 2 のループ
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 になる
pm08_18.png/image-size:397×167
最後に temp[] の内容を Data[] にコピーして処理終了です。
pm08_19.png/image-size:397×167
図6の状態に対して clearGarbage() を実行すると、Memo[1] は 4 に、Memo[2] は 9 に、DataLen は 13 になります。

e=ウ:4
 f=カ:9
 g=ケ:13

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

問1 問2 問3 問4 問5 問6 問7 問8 問9 問10 問11 問12 問13 採点講評
© 2010-2024 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop