基本情報科目B対策（4章さまざまなデータ構造）

こんにちは、ECF Techブログ担当の平良です。

本記事は「基本情報技術者試験　科目B対策講座」の一部です。講座記事のすべてをご覧になりたい方は、下のリンクからご確認ください。

はじめに本教材は基本情報技術者試験（科目B）の学習を目的とした教材です。試験合格のための学習にお役立て頂ければ幸いです。想定読者基本情報技術者試験(科目A)を学習中、もしくは学習済の方アルゴリズムやプログラミングの知識(科目A程度)をお...

本章では、さまざまなデータ構造を扱った練習問題を掲載しています。学習の一助にお役立てください。

4-1 オブジェクト指向プログラミング
- 4-1-1 オブジェクト指向の基本
4-2 様々なデータ構造
4-3 木構造
さいごに

4-1 オブジェクト指向プログラミング

4-1-1 オブジェクト指向の基本

問題

[オリジナル問題]

商品情報をオブジェクト指向で処理するプログラムです。出力結果のとおりとなるように、プログラム中の空欄①～④を埋めてください。空欄の語句は解答群から選んでください。

クラス Item は商品情報を表します。クラス Item の説明は下表のとおりです。

メンバ変数	型	説明
name	文字型	商品名
price	整数型	商品価格

コンストラクタ	説明
Item()	商品情報を生成する

メソッド	戻り値	説明
show()	なし	メンバ変数の情報を`name:price`の形式で出力する

〔プログラム〕

Item: ringo ←  ①
ringo. ② ← "りんご"
ringo. ③ ← 150
ringo. ④

〔出力結果〕

りんご:150

〔解答群〕
ア　show()　　イ　name　　ウ　price　　エ　Item()

基礎知識

オブジェクト指向プログラミングの基本的な考え方を示します。

クラスを元にオブジェクトを生成します。
オブジェクトを生成するためにはコンストラクタを呼び出します。
オブジェクトは、クラスに定義されたメンバ変数とメソッドを持ちます。
生成したオブジェクトは、変数に代入できます。
変数を使って、オブジェクトの持つメンバ変数を参照したり、メソッドを呼び出したりできます。

ヒント1

空欄①について
空欄①はオブジェクトを生成し、変数ringoに代入する処理です。オブジェクトを生成するためには、コンストラクタを呼び出します。

空欄②③について
メンバ変数はオブジェクトの持つ情報です。メンバ変数を参照する場合は変数名.メンバ変数名とします。

空欄④について
メソッドはオブジェクトができる動作です。メソッドを呼び出す際は、変数名.メソッド名(引数)とします。

解答解説

〔解答〕
①：Item()
②：ringo.name ← "りんご"
③：ringo.price ← 150
④：ringo.show()

〔解説〕
プログラムは次の順番で処理を行っています。

Itemオブジェクトの生成。
メンバ変数nameの値を設定
メンバ変数priceの値を設定
メソッドを呼び出して、メンバ変数の内容を出力

空欄①はオブジェクトを生成するためのコンストラクタ呼び出しItem()になります。生成されたオブジェクトは変数ringoに代入されます。

生成したオブジェクトのメンバ変数を設定します。オブジェクトは変数ringoを使って参照できますので、商品名nameと価格priceを設定するために、

ringo.name ← "りんご"
ringo.price ← 150
としています。

最後にringo.show()でshowメソッドを呼び出して、メンバ変数の内容を出力します。

4-2 様々なデータ構造

4-2-1 キュー

問題

[オリジナル問題]
キューを操作するプログラムです。文中のを埋めてください。

クラスQueueはキューを表すクラスです。クラスQueueの内容は下表のとおりです。

コンストラクタ	説明
Queue()	キューを生成します

メソッド	戻り値	説明
enqueue(整数型: data)	なし	整数 data をキューに追加します
dequeue()	整数型	キューから値を取り出し、戻り値として返します

プログラムを実行した時、8行目の処理で出力される数値はである。

〔プログラム〕

Queue: queue ← Queue()
queue.enqueue(5)
queue.enqueue(3)
queue.enqueue(8)
queue.dequeue() の戻り値を出力
queue.dequeue() の戻り値を出力
queue.enqueue(6)
queue.dequeue() の戻り値を出力

基礎知識

キューは筒状に値を格納するデータ構造です。キューに入れられた値は順番にならび、入れられた順に取り出すことができます。

解答解説

〔解答〕
8

〔解説〕
キューは値が入ってきた順番に値を取り出すことができるデータ構造です。各命令実行後のキューの状態、出力内容を表に示します。

最後のqueue.dequeue() の戻り値を出力で出力されるのは、8となります。

4-2-2 優先度付きキュー

[出典：基本情報技術者試験科目B サンプル問題問8]

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

優先度付きキューを操作するプログラムである。優先度付きキューとは扱う要索に優先度を付けたキューであり、要素を取り出す際には優先度の高いものから順番に取り出される。クラス PrioQueue は優先度付きキューを表すクラスである。クラス PrioQueue の説明を図に示す。ここで、優先度は整数型の値1,2,3のいずれかであり、小さい値ほど優先度が高いものとする。
手続prioSched を呼び出したとき、出力はの順となる。

〔プログラム〕

〇prioSched()
  PrioQueue: prioQueue ← PrioQueue()
  prioQueue.enqueue("A", 1)
  prioQueue.enqueue("B", 2)
  prioQueue.enqueue("C", 2)
  prioQueue.enqueue("D", 3)
  prioQueue.dequeue()  /*戻り値は使用しない*/
  prioQueue.dequeue()  /*戻り値は使用しない*/
  priolueue.enqueue("D", 3)
  prioQueue.enqueue("B", 2)
  prioQueue.dequeue()  /*戻り値は使用しない*/
  prioQueue.dequeue()  /*戻り値は使用しない*/
  prioQueue.enqueue("C", 2)
  prioQueue.enqueue("A", 1)
  while(prioQueue.size() が 0 と等しくない)
    prioQueue.dequeue() の戻り値を出力
  endwhile

解答群
ア　"A", "B", "C", "D"
イ　"A", "B", "D", "D"
ウ　"A", "C", "C", "D"
エ　"A", "C", "D", "D"

ヒント1

キューの状態を書きながらトレースしましょう。プログラムの最初のdequeueまでの状態を示します。

プログラム	キューの状態
`prioQueue.enqueue("A", 1)`	`A-1`
`prioQueue.enqueue("B", 2)`	`A-1`,`B-2`
`prioQueue.enqueue("C", 2)`	`A-1`,`B-2`,`C-2`
`prioQueue.enqueue("D", 3)`	`A-1`,`B-2`,`C-2`,`D-3`
`prioQueue.dequeue()`	`B-2`,`C-2`,`D-3`

以降、優先度にも注意しながらトレースを進めましょう。

解答解説

〔解答〕
エ

〔解説〕
3行目のenqueueからwhile文の手前までのプログラムをトレースすると、次のようになります。

プログラム	キューの状態
`prioQueue.enqueue("A", 1)`	`A-1`
`prioQueue.enqueue("B", 2)`	`A-1`,`B-2`
`prioQueue.enqueue("C", 2)`	`A-1`,`B-2`,`C-2`
`prioQueue.enqueue("D", 3)`	`A-1`,`B-2`,`C-2`,`D-3`
`prioQueue.dequeue()`	`B-2`,`C-2`,`D-3`
`prioQueue.dequeue()`	`C-2`,`D-3`
`prioQueue.enqueue("D", 3)`	`C-2`,`D-3`,`D-3`
`prioQueue.enqueue("B", 2)`	`C-2`,`D-3`,`D-3`,`B-2`
`prioQueue.dequeue()`	`D-3`,`D-3`,`B-2`
`prioQueue.dequeue()`	`D-3`,`D-3`
`prioQueue.enqueue("C", 2)`	`D-3`,`D-3`,`C-2`
`prioQueue.enqueue("A", 1)`	`D-3`,`D-3`,`C-2`,`A-1`

以降、while文による出力です。while文ではキューが空になるまでdequeueを呼び出し、戻り値を出力します。この時点でキューの状態は

D-3,D-3,C-2,A-1

です。ここから優先度1のものから出力し、優先度が同じ場合は左にあるもの(先にenqueueされたもの)から出力します。したがって、ACDDとなります。

4-2-3 スタック

[オリジナル問題]
スタックを操作するプログラムです。文中のを埋めてください。

クラスStackはスタックを表すクラスです。クラスStackの内容は下表のとおりです。

コンストラクタ	説明
Stack()	スタックを生成する。

メソッド	戻り値	説明
push(整数型: data)	なし	整数 data をスタックに追加します
pop()	整数型	スタックから値を取り出し、戻り値として返します

プログラムの出力結果を順に並べるとである。

〔プログラム〕

Stack: stack ← Stack()
stack.push(5)
stack.push(3)
stack.push(8)
stack.pop() の戻り値を出力
stack.push(6)
stack.pop() の戻り値を出力
stack.pop() の戻り値を出力

基礎知識

スタックは下のように値を積み重ねて格納するデータ構造です。スタックに入れられた値は、入れられた順とは逆順に値を取り出すことができます。値を入れる操作をプッシュ、値を取り出す操作をポップと言います。

解答解説

〔解答〕
8,6,3

〔解説〕
プログラムの各処理とスタックの状態を示します。

したがって、出力順は8,6,3となります。

4-2-4 配列でスタックを表現する

問題

[オリジナル問題]

正の整数を扱えるスタック構造を表現するプログラムです。空欄①～③を埋めてください。

大域の配列stackと変数top、および下記２つの関数でスタックを実現します。配列の初期値は-1で、値が入っていないことを表します。

関数 push はスタックに値を1つ追加します。スタックがいっぱいの場合は「スタックがいっぱいです。」を出力します。

関数 pop はスタックから値を1つ取り出し、戻り値として返します。スタックが空の場合は「スタックが空です。」を出力し、-1を戻り値として返します。

〔プログラム〕

大域:
整数型の配列: stack ← {-1,-1,-1,-1,-1}
整数型: top ← 0 /* 次に取り出すべき要素 */

〇push(整数型: data)
  if (top＝stackの要素数)
    "スタックがいっぱいです。"を出力
  else
      ①  
    stack[top] ← data
  endif

〇整数型: pop()
  整数型: ret
  if ( ② ) 
    "スタックが空です。"を出力
    return -1
  else
       ③
    top ← top - 1
    return ret
  endif

ヒント1

配列stackは、下図のように大きい要素番号を上に積み上げられた値として扱っています。

空欄①
変数topの初期値は0です。配列の要素番号は1から始まります。

空欄②
初回で関数 pop を呼び出したと想定するとわかりやすいかもしれません。

空欄③
topの更新処理があるため、一旦取り出す値を退避しています。

解答解説

〔解答〕
①：top ← top + 1
②：top=0
③：ret ← stack[top]

〔解説〕
プログラムの動作の様子を、次の呼び出しプログラムを使って説明します。

push(7)
pop()

配列stackは初期状態で下図左のようになっています。変数topが0の時は、配列が空であることがわかります。
push(7)で関数 push を呼び出します。topを1つ加算してから、値を設定する必要があります。(下図中央)
pop()で関数 pop を呼び出します。スタックの一番上にある値を一旦退避し、topをつ減算、最後の退避した値を返します。(下図右)

空欄①について
変数topは次に取り出す要素を表しています。プッシュをするためには、その次の要素（空き要素）に移動し、値を設定する必要があるため、先にtop ← top + 1の処理を実行する必要があります。

空欄②について
top=0であればスタックが空であることを判定できます。変数topの初期値が0であることからもわかります。

空欄③について
ポップ操作をした後はtopを1つ減らす必要がありますが、return文は関数の最後に実行しなければいけないため、

return stack[top]
top ← top - 1

とは書けません。そのため、戻り値となる値を一旦変数retに代入(ret ← stack[top])し、その後topを1減算しています。最後に退避した値を戻り値として返します。

4-2-5 単方向リスト

問題

[オリジナル問題]

クラスListElementは単方向リストの要素を表します。クラスListElementのメンバ変数の説明を下に示します。

メンバ変数	型	説明
val	文字型	要素の値
next	ListElement	次の要素の参照次の要素が無い時の状態は未定義

関数 showNode は、単方向リストをすべてたどり、各ListElementのメンバ変数 val の値を出力する関数です。プログラム中の空欄①を埋めてください。

〔プログラム〕

大域: ListElement: listHead

〇showNode()
  ListElement: nextNode
  nextNode ← listHead
  while(nextNode が "未定義" でない)
    nextNode.val の値を出力
    nextNode ← ①

基礎知識

単方向リストは下図のようなデータ構造を持ちます。本問題では、リストの各要素をListElementのオブジェクトを使って表しています。リストの内容をすべて出力するには、各要素のもつ次要素の参照を使用します。

ヒント1

リストの各要素をたどるには、各オブジェクトのメンバ変数 next を活用します。

解答解説

〔解答〕
①：nextNode ← nextNode.next

〔解説〕

プログラムの初期状態が次のようになっているものとして、プログラムをトレースしてみましょう。

5行目の処理nextNode ← listHeadにより、変数nextNodeはlistHeadと同じ最初の要素を指します（下図）。この状態で7行目の処理である、nextNode.val の値を出力が行われますので、5が出力されます。

空欄①を含む8行目の処理で行いたいのは、変数nextNodeが次の要素を指すようにすることです（下図）。

この時点で次の要素の参照を持っているのは nextNodeのメンバ変数next なので、nextNode ← nextNode.nextとすることで、下のようになり、次の要素を参照できるようになります。

4-2-6 単方向リストの操作

問題

[出典：基本情報技術者試験科目B サンプル問題問10]

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

手続 delNodeは、単方向リストから、引数 pos で指定された位置の要素を削除する手続である。引数 pos は、リストの要素数以下の正の整数とする。リストの先頭の位置を1とする。
クラス ListElement は、単方向リストの要素を表す。クラス ListELement のメンバ変数の説明を表に示す。ListElement 型の変数はクラス ListElement のインスタンスの参照を格納するものとする。大域変数 listHead には、リストの先頭要素の参照があらかじめ格納されている。

〔プログラム〕

大域: ListElement: listHead // リストの先頭要素が格納されている

〇delNode(整数型: pos)  /* posは、リストの要素数以下の正の整数 */
ListElement: prev
整数型：i
if (posが 1 と等しい)
  listHead ← listHead.next
else
  prev ← listHead
  /* posが2と等しいときは繰返し処理を実行しない */
  for (i を 2 から pos-1 まで 1 ずつ増やす)
    prev ← prev.next
  endfor
  prev.next ← 【  】
endif

解答群
ア　listHead　　　　　　イ　listHead.next
ウ　listHead.next.next　　エ　prev
オ　prev.next　　　　　　カ　prev.next.next

ヒント1

削除対象の1つ前の要素が、削除対象の要素を参照しないようにすることで実現します。ただし、リストが途切れないようにする必要がありますので、前の要素は削除対象の次の要素を指すようにします。つまり、下図のような処理を行う必要があります。

解答解説

〔解答〕
カ

〔解説〕
正確なトレース力が問われる問題です。下図のような単方向リストを例に考えてみましょう。

上の図のように、引数posには3が与えられたものとします。6行目のif文の条件式posが 1 と等しいはfalseになりますので、else部分の処理が行われることになります。

9行目の処理はprev ← listHeadなので、変数listHeadとprevは同じ要素を指します（下図）。

11行目からfor文が開始します。(i を 2 から pos-1 まで 1 ずつ増やす)とあります。引数posは3なので、pos-1の部分は2です。iを2から2まで1ずつ増やすと読み替えることができます。したがって、for文内の処理は1回行われます。

for文内の処理はprev ← prev.nextですので、1回実行すると下図のようになります。

forループはこれで終了。次に空欄を含む14行目を実行することで、下図のオレンジ色の矢印のようにすることが目的です。こうすることで、引数で指定された削除対象の要素が、リストからはずれ、削除したことになります。

ここで選択肢を検証します。空欄の行はprev.next ← 【　　】となっています。prev.nextは下図の青吹き出し部分で、ここに何を代入するかが問われています。一方、各選択肢が示す参照はオレンジ色の吹き出しが示す矢印です。

正解は カprev.next.next となります。カの参照をprev.nextに代入することで、prev.nextはカと同じ要素を指すことになり、目的の状態を実現することができます（下図）。

4-3 木構造

まずは木構造を扱う上で欠かせない、再帰の考え方を問う例題です。

4-3-1 再帰プログラム

問題

[出典：基本情報技術者試験科目B サンプル問題問7]

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

関数 factorial は非負の整数 n を引数にとり、その階乗を返す関数である。非負の整数 n の階は n が 0 のときに 1 になり、それ以外の場合は 1 から n までの整数を全て掛け合わせた数となる。

〔プログラム〕

〇整数型: factorial(整数型: n)
  if (n = 0)
    return 1
  endif
  return【　　】

解答群
ア（n ー 1）✕ factorial(n)　　イ　factorial(n ー 1)
ウ　n　　　　　　　　　　　　エ　n ✕（n ー 1）
オ　n ✕ factorial(1)　　　　　カ　n ✕ factorial(n ー 1)

基礎知識

関数 factorial は自分自身を呼び出す関数です。このような関数を再帰関数と言います。

ヒント1

この関数で 4! を求める場合は、次のような考え方で動作しています。
4! は 4 ✕ 3! と等しいです。
3! は 3 ✕ 2! と等しいです。
2! は 2 ✕ 1! と等しいです。
1! は 1 です。

解答解説

〔解答〕
カ

〔解説〕
関数factorialで 4! を求めることを考えます。4!を求めるにはfactorial(4)のように呼び出します。以降の動作をトレースすると、

factorial(4)の処理

if (n = 0)：nは4なので、if文に入らずreturn n ✕ factorial(n ー 1)が実行されます。factorial(n ー 1)は factorial(3) となります。

factorial(3)の処理

if (n = 0)：nは3なので、if文に入らずreturn n ✕ factorial(n ー 1)が実行されます。factorial(n ー 1)は factorial(2) となります。

factorial(2)の処理

if (n = 0)：nは2なので、if文に入らずreturn n ✕ factorial(n ー 1)が実行されます。factorial(n ー 1)は factorial(1) となります。

factorial(1)の処理

if (n = 0)：nは1なので、if文に入らずreturn n ✕ factorial(n ー 1)が実行されます。factorial(n ー 1)は factorial(0) となります。

factorial(0)の処理

if (n = 0)：nは0なので、if文に入りreturn 1が実行されます。

factorial(1)の処理つづき

factorial(0)の戻り値は1、nは1なので、return n ✕ factorial(n ー 1)はreturn 1✕1となり、1を戻り値として返します。

factorial(2)の処理つづき

factorial(1)の戻り値は1、nは2なので、return n ✕ factorial(n ー 1)はreturn 2✕1となり、2を戻り値として返します。

factorial(3)の処理つづき

factorial(2)の戻り値は2、nは3なので、return n ✕ factorial(n ー 1)はreturn 3✕2となり、6を戻り値として返します。

factorial(4)の処理つづき

factorial(3)の戻り値は6、nは4なので、return n ✕ factorial(n ー 1)はreturn 4✕6となり、24を戻り値として返します。

となります。

整理して図に示します。図中の吹き出しは、各呼び出しの戻り値です。たとえばfactorial(3)の呼び出しは6であることを示しています。

図に示すとおり、

factorial(4)内でfactorial(3)が呼び出され
factorial(3)内でfactorial(2)が呼び出され

といった処理が続きます。factorial(0)まで行って始めて戻り値が確定し、以降factorial(1)、factorial(2)の順で戻り値が決まっていきます。最終的にfactorial(4)の戻り値として24が求められるしくみです。

再帰は、木構造を扱うプログラムでよく用いられる考え方です。木構造のアルゴリズムに入る前に理解を深めておきましょう。

4-3-2 木構造の理解

問題

[オリジナル問題]

プログラムは、下図の2分木をたどり節の値を表示するプログラムです。出力結果を答えてください。

配列treeは下図の二分木構造を表しています。例えば、配列treeの要素番号1の配列は、節番号1の子の節番号から成る配列です。節番号1の子は左が2、右が3なので配列{2, 3}と表現されます。また、子の節がない場合は{}と表現されます。

〔プログラム〕

整数型の二次元配列: tree ← {{2,3},{4,5},{},{},{}}
整数型: node ← 1
node ← tree[node][1]
node ← tree[node][2]
nodeの値を出力

基礎知識

木構造はその名のとおり、下図に示す木のような形をしたデータ構造です。値を持つ部分は 節(またはノード) と呼ばれています。節は場所によって別の呼び名があり、枝分かれの大元となる節を 根(またはルート) 、枝分かれの先端に位置し、別の節を持たない節を 葉(またはリーフ) とも呼びます。

木構造のうち、節からの枝分かれが最大２つになっているものを二分木と言います。

解答解説

〔解答〕
5

〔解説〕
変数nodeは二分木の節を参照する変数です。初期値は1が代入されていますので、下図のように一番上の節を示しています。

3行目の処理は、node ← tree[node][1]となっています。変数nodeは1なので、tree[1][1]の値2が、nodeに新たに代入されます。二分木の左側の枝に参照が移動したというイメージです（下図）。

4行目の処理は、node ← tree[node][2]となっています。変数nodeは2なので、tree[2][2]の値5が、nodeに新たに代入されます。二分木の右側の枝に参照が移動したというイメージです（下図）。

したがって、最後の出力処理では5が出力されることになります。

本問題で二分木をたどっていくイメージをつかんでおきましょう。節の多い二分木になると、二分木をたどる処理に再帰を活用します。

4-3-3 木構造の走査

問題

[出典：基本情報技術者試験科目B サンプル問題問9]

次の記述中のに入れる正しい答えを、解答群の中から選べ。ここで、配列の要素番号を1から始まる。

手続 order は、図の2分木の、引数で指定した節を根とする部分木をたどりながら、全ての節番号を出力する。大域の配列treeが図の2分木を表している。配列 tree の要素は、対応するの節の子の節番号を、左の子、右の子の順に格納した配列である。例えば、配列 tree の要素番号 1 の要素は、節番号 1 の子の節番号から成る配列であり、左の子の番号2、右の子の番号3を配列 {2, 3}として格納する。
手続order をorder(1)として呼び出すと、の順に出力される。

〔プログラム〕

　大域: 整数型配列の配列: tree ← {{2, 3}, {4, 5}, {6, 7}, {8, 9},
                                {10, 11}, {12, 13}, {14}, {}, {}, {},
                                 {}, {}, {}, {}}  // {}は要素数0の配列

　〇order(整数型：n)
  if (tree[n]の要素数 が 2 と等しい)
    order(tree[n][1])
    nを出力
    order(tree[n][2])
  elseif(tree[n]の要素数 が 1 と等しい)
    order(tree[n][1])
    nを出力
  else
    nを出力
  endif

解答群
ア　1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
イ　1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 13, 7, 14
ウ　8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7
エ　8, 9, 4, 10, 11, 5, 2, 12, 13, 6, 14, 7, 3, 1