基本情報技術者 2016年 春期 午後 問08
次のプログラムの説明及びプログラムを読んで、設問1，2に答えよ。
携帯端末上で稼働する簡易メモ帳の機能のうち、メモの編集処理（メモの追加・削除・変更・移動）を行う部分のプログラムである。図1は、簡易メモ帳に4件のメモ“Aoki”、“Imai”、“Uno”及び“Endo”を登録した場合の表示例である。
〔プログラムの説明〕
(1) メモは、画面に表示可能な1バイトで表現できる文字から成る文字列である。各メモは、文字列の前に、文字列の長さ（0〜255）を1バイトの符号なし2進整数の形式で付け加えて格納する。例えば、メモ“Hello!”は、次の形式で格納する（以下、文字列の長さは10進数で表記し、その値に下線を付けて表す）。
(2) メモの格納と管理のために、2個の配列Memo[]、Data[]と、4個の変数MemoCnt、MemoMax、DataLen、DataMaxを使用する。
各メモは、配列Data[]の先頭から順に、1要素に1バイトずつ(1)で示した形式で格納し、その格納位置の情報を配列Memo[]に設定して管理する。
MemoMaxは格納できるメモの最大件数（配列Memo[]の要素数）、MemoCntは現在格納されているメモの件数である。
DataMaxは格納できる最大文字数（配列Data[]の要素数）、DataLenは現在格納されている文字数である（文字数には、文字列の長さの情報を含む）。
(3) 簡易メモ帳の画面には、配列Memo[]の要素番号の昇順に、それが指すメモを取り出して、メモを表示する。図1の表示例は、図3（後出）の状態に対応している。
(4) メモの編集処理を行うための関数の概要は、次の①〜⑤のとおりである。これらの関数が呼ばれるとき、引数の内容や配列の空き状態などは事前に検査済みで、正しく実行できるものとする。
なお、以降の図に示す実行例では、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, "Imai")
addMemo(3, "Uno")
addMemo(4, "Endo")
をこの順に実行した後の配列・変数の状態を、図3に示す。
③ 関数：deleteMemo(整数型：pos)
1件のメモを削除する。Memo[]の要素番号pos+1以降の内容をそれぞれ一つ前の要素に移し、MemoCntから1を減じることによって、Memo[pos]が指すメモを削除する（表示の対象から除く）。Data[]中の参照されなくなったメモは、そのまま残す。図3の状態から、deleteMemo(0)を実行した後の配列・変数の状態を、図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：イ
解説
解答の導き方
このプログラムでは、Data[]にメモの文字列を順番に保存し、Memo[]には各メモがData[]のどこから始まるかを記録します。配列とは、番号の付いた箱が並んだ保存場所です。この番号を添字といいます。
DataLenは、Data[]の先頭から現在使っている要素数です。そのため、次のメモを追加するときの先頭位置としても使えます。メモを削除したり並べ替えたりしても、Data[]にある文字列自体は移動しません。
a、b：addMemo
追加前のDataLenを とします。関数の処理を順に追うと、次のようになります。
- Memo[MemoCnt]に、追加するメモの先頭位置を記録します。この時点での先頭位置はDataLenなので、aはDataLenです。解答群ではアに当たります。
- Data[DataLen]に文字列の長さを入れます。
- DataLenを1増やします。これで、文字列を格納する位置を指します。
- 文字列の各文字をData[DataLen + i]に入れます。
- 文字列の長さの情報1要素と、文字列のtextLen要素を使ったので、格納後のDataLenは、いまのDataLenにtextLenを加えた値になります。したがってbはDataLen + textLenで、解答群ではウです。
DataLenを増やす前の値を とすると、長さの情報はData[]に入り、文字列はData[]からData[]までに入ります。格納後のDataLenは です。
図3の例でも、メモの先頭位置は順に0、5、10、14です。最初のメモ“Aoki”は、長さの情報1要素と文字列4文字で合計5要素を使うため、次のメモはData[]の添字5から始まります。
c：deleteMemo
説明には、削除する位置の次の要素から内容を一つずつ前へ移すとあります。削除位置がposなら、最初に移動するのはMemo[pos + 1]です。その値をMemo[pos]に入れ、その後も同じように一つずつ前へずらします。
したがって、ループの開始値はpos + 1です。cは解答群のエに当たります。
図3の状態でdeleteMemo(0)を実行する場合、iは1から始まります。
その後、MemoCntを1減らします。Data[]の内容は削除せず、Memo[]から指されなくなるだけです。図4では、削除後もData[]の先頭にあったメモが残っています。
d：moveMemo
図5の状態からmoveMemo(2, 0)を実行する場合を考えます。移動元のMemo[2]の値19を、まずmに保存します。その後、移動元より前にある値を後ろへずらし、最後にMemo[0]に19を入れます。
移動元の位置から移動先の次の位置まで、添字を1ずつ減らしながら移動します。つまり、iはfromPosから始まり、iがtoPos + 1以上の間、1ずつ減らします。よってdは解答群のイです。
実際には、iが2のときMemo[2]にMemo[1]の値10を入れ、iが1のときMemo[1]にMemo[0]の値5を入れます。最後にMemo[0]に保存しておいた19を入れます。図6のMemo[]は、19、5、10の順になります。
誤りやすいポイント
- DataLenに文字列の長さの情報も含めること
文字列だけでなく、その前に置く長さの情報もData[]の1要素を使います。追加後のDataLenは、追加前よりtextLenだけでなく1多く増えます。 - aとbで使うDataLenのタイミングが異なること
aでは、文字列の長さの情報を格納する前のDataLenを使います。bでは、その情報を格納してDataLenを1増やした後の値を使います。 - 削除する位置posと、最初に移動する位置を混同すること
Memo[pos]に入れるのは、その次のMemo[pos + 1]の値です。したがって、ループはpos + 1から始まります。 - 移動方向に応じたループの向きを取り違えること
移動元が移動先より後ろにある場合は、添字を大きい方から小さい方へたどります。先に小さい方から書き換えると、まだ必要な値を上書きしてしまうためです。
FAQ
Q: メモを削除したのに、Data[]の内容が残っているのはなぜですか？
A: 削除処理はMemo[]の並びを変えて、対象のメモを表示対象から外す処理だからです。Data[]の内容は消さず、Memo[]から指されなくなります。
A: 削除処理はMemo[]の並びを変えて、対象のメモを表示対象から外す処理だからです。Data[]の内容は消さず、Memo[]から指されなくなります。
Q: changeMemoで既存の文字列を書き換えず、DataLenの位置から新たに保存するのはなぜですか？
A: 元の文字列の長さと新しい文字列の長さが異なる場合もあるためです。新しい内容を空き領域に保存し、その先頭位置をMemo[pos]に設定します。
A: 元の文字列の長さと新しい文字列の長さが異なる場合もあるためです。新しい内容を空き領域に保存し、その先頭位置をMemo[pos]に設定します。
Q: moveMemoではData[]の内容も移動しますか？
A: 移動するのはMemo[]の並びだけです。Memo[]がData[]の格納位置を示しているので、Memo[]の順序を変えると表示順が変わります。
A: 移動するのはMemo[]の並びだけです。Memo[]がData[]の格納位置を示しているので、Memo[]の順序を変えると表示順が変わります。
関連キーワード: 配列、添字、データ長、データの格納位置、逐次格納
設問2：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
このメモの管理方法では、削除されたメモや変更前のメモは、Data[]中に参照されない状態で残っている。その結果、DataLenの値は一方的に増加し、やがてData[]中の空き要素が枯渇する。次に示す関数clearGarbage()は、Data[]中の参照されなくなったメモを取り除き、空き要素を増やすための関数である。
プログラムの配列・変数が図6に示す状態のときに、clearGarbage()を実行すると、実行が終了した時点で、Memo[1]の値はe、Memo[2]の値はf、DataLenの値はgとなる。
解答群
ア：0
イ：3
ウ：4
エ：5
オ：7
カ：9
キ：10
ク：12
ケ：13
コ：23
模範解答
e：ウ、f：カ、g：ケ
解説
解答の導き方
clearGarbage()は、Data[]に残っているデータのうち、Memo[]から参照されているメモだけを一時配列temp[]にコピーし、Data[]の先頭に詰め直す処理です。参照とは、ある位置のデータを使うために、その位置を指し示すことです。
図6では、MemoCntは3です。したがって、Memo[]の0番目から2番目までを順に調べます。配列の位置を表す番号を添字といいます。
まずDataLenを0にします。次に、mを0から順に増やしながら、Memo[m]が指すメモをtemp[]にコピーします。コピー後の位置がMemo[m]に記録されます。
順に処理を追います。
- mが0のとき、処理前のMemo[0]は19です。Data[19]には文字列の長さ3が入っています。長さの情報もメモの一部なので、長さを表す1要素と文字列の3要素、合わせて4要素をコピーします。temp[0]～temp[3]にコピーされ、DataLenは4になります。Memo[0]は新しい先頭位置の0に更新されます。
- mが1のとき、処理前のMemo[1]は5です。Data[5]にある長さは4なので、長さの情報を含む5要素をコピーします。コピー先はtemp[4]～temp[8]で、DataLenは9になります。Memo[1]は4に更新されます。
- mが2のとき、処理前のMemo[2]は10です。Data[10]にある長さは3なので、4要素をコピーします。コピー先はtemp[9]～temp[12]で、DataLenは13になります。Memo[2]は9に更新されます。
ここで、プログラムの「i ≤ Data[d]」が重要です。Data[d]に入っている長さが3なら、iは0、1、2、3の4回分になります。文字列だけでなく、その先頭にある長さの情報もコピーするためです。
コピーが終わると、temp[0]～temp[12]の内容をData[0]～Data[12]に移します。DataLenには、3件のメモを詰め直した後の要素数である13が残ります。
したがって、Memo[1]の値は4、Memo[2]の値は9、DataLenの値は13です。
誤りやすいポイント
-
文字列の長さだけをコピーする
各メモには、文字列の前に長さの情報も格納されています。長さが3のメモは、3要素ではなく4要素をコピーします。 -
Data[]に並んだ順にコピーする
メモをコピーする順番は、Data[]上の位置順ではなく、Memo[]の添字の順です。図6ではMemo[]が指す順に、位置19、5、10のメモをコピーします。 -
削除済み・変更前のメモもコピーする
clearGarbage()はMemo[]から指されているメモだけをコピーします。Data[]にデータが残っていても、参照されていないものはコピーしません。 -
DataLenをコピーした文字列の文字数だけと考える
DataLenは、長さの情報も含めて格納した要素数です。そのため、今回の値は文字列の長さの合計ではなく13になります。
FAQ
Q: Memo[]の値を、コピーのたびに更新しても問題ありませんか？
A: 問題ありません。各回で、まずコピー元の位置をdに保存し、その後にMemo[m]を新しい位置へ更新しています。次の回で使う別のMemo[m]の値は、まだ更新されていません。
A: 問題ありません。各回で、まずコピー元の位置をdに保存し、その後にMemo[m]を新しい位置へ更新しています。次の回で使う別のMemo[m]の値は、まだ更新されていません。
Q: なぜ一時配列temp[]にコピーしてからData[]へ移すのですか？
A: Data[]の中で直接データを詰め直すと、まだ読み取っていないメモのデータを上書きするおそれがあるためです。先にtemp[]へすべてコピーしておけば、その心配を避けられます。
A: Data[]の中で直接データを詰め直すと、まだ読み取っていないメモのデータを上書きするおそれがあるためです。先にtemp[]へすべてコピーしておけば、その心配を避けられます。
Q: DataLenを0にした後も、元のメモの位置が分かるのはなぜですか？
A: DataLenは、これから詰め直したデータの末尾を表す値として使われます。元の位置はMemo[]に残っており、各メモをコピーするときに、その位置をdへ取り出しています。
A: DataLenは、これから詰め直したデータの末尾を表す値として使われます。元の位置はMemo[]に残っており、各メモをコピーするときに、その位置をdへ取り出しています。
関連キーワード: 配列、添字、参照、一時配列、データ再配置
