総視聴再生時間43万分以上(2017年5月13日現在)の動画で基本情報技術者試験の過去問&キーワード解説!スキマ時間に動画!〜これじょIT〜

PR広告

平成28年度春 基本情報技術者試験午後 過去問8 データ構造及びアルゴリズム 設問2 合格率アップ!動画付き解説

TOP :

問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としている。

関数: resetMemo()

 全てのメモを消去する。MemoCnt と DataLen に0を設定することによって、Memo[] と Data[] の全要素を"空き"の状態にする。

 resetMemo()を実行した後の配列・変数の状態を、図2に示す。以降の図で、網掛け部分 は、その配列要素が"空き"であることを表す。

平成28年度春応用情報技術者試験午問8 データ構造及びアルゴリズム 合格率アップ!動画解説!

関数: addMemo(整数型: TextLen, 文字列型: text)

 1件のメモを追加する。長さ textLen の文字列 text をData[] の最初の空き要素以降に格納し、その格納位置の情報を Memo[] に設定する。図2の状態から、

addMemo(4, "Aoki")

addMemo(4, "Imal")

addMemo(3, "Uno")

addMemo(4, "Endo")

をこの順に実行した後の配列・変数の状態を、図3に示す。

平成28年度春応用情報技術者試験午問8 データ構造及びアルゴリズム 合格率アップ!動画解説!

関数: deleteMemo(整数型: pos)

 1件のメモを削除する。Memo[] の要素番号 pos+1 以降の内容をそれぞれ一つ前の要素に移し、MemoCnt から1を減じることによって、Memo[pos] が指すメモを削除する(表示の対象から除く)。Data[] 中の参照されなくなったメモは、そのまま残す。図3の状態から、deleteMemo(O) を実行した後の配列・変数の状態を、図4に示す。以降の図で、斜線部分は、参照されなくなったメモであることを表す。

平成28年度春応用情報技術者試験午問8 データ構造及びアルゴリズム 合格率アップ!動画解説!

関数: changeMemo(整数型: pos, 整数型: textLen, 文字列型: text)

 1件のメモの内容を変更する。長さ textLen の文字列 text を Data[] の 最初の空き要素以降に格納し、その格納位置の情報を Memo[pos] に 設定することによって、Memo[pos] が指すメモの内容を変更する。Data[] 中の参照されなくなったメモは、そのまま残す。図4の状態から changeMemo(2, 3, "Abe") を 実行した後の配列・変数の状態を、図5に示す。

平成28年度春応用情報技術者試験午問8 データ構造及びアルゴリズム 合格率アップ!動画解説!

関数: 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に示す。

平成28年度春応用情報技術者試験午問8 データ構造及びアルゴリズム 合格率アップ!動画解説!

[プログラム]

○大域 整数型: MemoCnt, MemoMax, Memo[MemoMax]

○大域 整数型: DataLen, DataMax

○大域 8ビット論理型: Data[DataMax]

○関数: resetMemo()

・MemoCnt ← 0
・DataLen ← 0

○関数: addMemo(整数型: textLen, 文字列型: text)

○整数型: i

・Memo[MemoCnt] ← a
・MoemoCnt ← MemoCnt + 1
・Data[DataLen] ← textLen
・DataLen ← DataLen + 1
■ i:0, i < textLen, 1
| ・Data[DataLen + i] ← text[i]
■
・DataLen ← b

○関数: deleteMemo(整数型: pos)

○整数型: i

・i ← c
■ i < MemoCnt
| ・Memo[i - 1] ← Memo[i]
| ・i ← i + 1
■
・MemoCnt ← MemoCnt - 1

○関数: changeMemo(整数型: pos, 整数型: textLen, 文字列型: text)

○整数型: i

・Memo[pos] ← DataLen
・Data[DataLen] ← textLen
・DataLen ← DataLen + 1
■ i:0, i < textLen, 1
| ・Data[DataLen + i] ← text[i]
■
・DataLen ← b

○関数: moveMemo(整数型: fromPos, 整数型: to Pos)

○整数型: i, m

・m ← Memo[fromPos]
▲ fromPos < toPos
|■ i: fromPos, i ≦ toPos -1, 1
|| ・Memo[i] ← Memo[i + 1}
|■
▼
▲ fromPos > toPos
|■ i: d
|| ・Memo[i] ← Memo[i -1]
|■
▼
・Memo[toPos] ← m

設問2

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

 このメモの管理方法では、削除されたメモや変更前のメモは、Data[] 中に参照されない状態で残っている。その結果、DataLen の値は一方的に増加し、やがて Data[] 中の空き要素が枯渇する。次に示す関数 clearGarbage()は、Data[] 中の参照されなくなったメモを取り除き、空き要素を増やすための関数である。

○関数: clearGarbage()

○整数型: d, i, m
○8ビット論理型: temp[DataMax]

・DataLen ← 0
▲ MemoCnt = 0
| ・return
▼
■ m: 0, m < MemoCnt, 1
| ・d ← Memo[m]
| ・Memo[m] ← DataLen
|■ i: 0, i ≦ Data[d], 1
|| ・temp[DataLen] ← Data[d + i]
|| ・DataLen ← DataLen + 1
|■
■
■ d: 0, d < DataLen, 1
| ・Data[d] ← temp[d]
■

 プログラムの配列・変数が図6に示す状態のときに、clearGarbage() を実行すると、実行が終了した時点で、Memo[1] の値はe、Memo[2] の値はf、DataLen の値はgとなる。

解答群

  1. 0
  2. 3
  3. 4
  4. 5
  5. 7
  6. 9
  7. 10
  8. 12
  9. 13
  10. 23

解説

図6は下記の通り

平成28年度春応用情報技術者試験午問8 データ構造及びアルゴリズム 合格率アップ!動画解説!

このプログラムが実行されると

Memo[] = {19,5,10}

Data[] = {4,A,o,k,i,4,I,m,a,i,3,U,n,o,4,E,n,d,o,3,A,b,e}

※斜体は削除されている

Memo[] = {0,4,9}

Data[] = {3,A,b,e,4,I,m,a,i,3,U,n,o}

となります。従って

Memo[1] = 4 なので、eには「ウ 4」

Memo[2] = 9 なので、fには「カ 9」

DataLen = 13 なので、gには「ク 13」

がそれぞれ入ります。

プログラムの値の動きは動画を準備します!

平成28年度春 基本情報技術者試験午後 目次

TOP :

タグ: ,

PR広告

フェイスブックコメント

平成28年度秋 基本情報技術者試験 午後 テキスト・動画解説

平成28年度秋 基本情報技術者試験 午前 テキスト・動画解説

平成28年度春 基本情報技術者試験 午後 テキスト・動画解説

平成28年度春 基本情報技術者試験 午前 テキスト・動画解説

平成27年度秋 基本情報技術者試験 午後 テキスト・動画解説

平成27年度春 基本情報技術者試験 午後 テキスト・動画解説

平成27年度春 基本情報技術者試験 午前 テキスト・動画解説

平成26年度秋 基本情報技術者試験 午前 テキスト・動画解説

平成26年度春 基本情報技術者試験 午前 テキスト・動画解説