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

PR広告

平成30年度秋 基本情報技術者試験午後 問8 データ構造及びアルゴリズム|合格率アップ!動画解説!

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

 整数式を受け取って、その値を返すプログラムである。例えば、例1に示す整数式を受け取ると、その値50を返す。

  例1: 2 × (34 - ( 5 + 67 ) ÷ 8)

〔プログラムの説明〕

(1) 整数式は、文字の列で与えられる。整数式は、次のもので構成される。

 ・符号のない数字。0~9の並び

 ・演算子: +, -, ×, ÷

 ・括弧: (, )

(2) 引数 Expression[ ] で整数式を、引数 ExpLen で整数式の文字数を、それぞれ受け取る。

(3) プログラム中の破線で囲んだ解析処理の部分では、受け取った整数式を解析し、計算に必要な情報を配列及び変数に設定する。

(4) プログラム中の破線で囲んだ計算処理の部分では、(3)で設定した情報を用いて、整数式の値を計算する。整数式の値は、Value[0] に得られる。

(5) 各配列の添字は、0から始まる。各配列の要素数は、十分に大きいものとする。

(6) 受け取った整数式に誤りはないものとする。また、計算の過程で、あふれやゼロ除算は発生しないものとする。

〔プログラム〕

 ○整数型関数: compute(文字型: Expression[], 整数型: ExpLen)

 ○文字型: Operator[100]

 ○整数型: OpCnt, Priority[100], Value[100]

 ○文字型: chr

 ○整数型: i, ip, nest

  解析処理(詳細は〔プログラム(解析処理部分)の説明〕に示す)

  計算処理(詳細は〔プログラム(計算処理部分)の説明〕に示す)

 ・return Value[0]

〔プログラム(解析処理部分)の説明〕

(1) Expression[ ] で渡された整数式を解析し、計算に必要な情報を配列 Operator[ ]、Priority[ ]、Value[ ] 及び変数 OpCnt に設定する。関数 int() は、引数の数字が表す値を整数型で返す。

(2) 例1の整数式について、プログラム(解析処理の部分)を実行した直後の各配列及び変数の状態を、図1に示す。

平成30年度秋 基本情報技術者試験午後 過去問8 データ構造及びアルゴリズム

図1 プログラム(解析処理の部分)を実行した直後の状態

〔プログラム(解析処理の部分)〕

  ・OpCnt ← 0

  ・Value[0] ← 0

  ・nest ← 0

  ■ i:0, i < ExpLen, 1

  |・chr ← Expression[i]

  |▲ ('0' ≦ chr) and (chr ≦ '9') /* 数字0〜9か? */

  ||・Value[OpCnt] ← 10 × Value[OpCnt] + int(chr)

  |▼

  |▲ (chr = '+') or (chr = '-') or (chr = '×') or (chr = '÷')

  ||・Operator[OpCnt] ← chr

  ||▲ (chr = '+') or (chr = '-')

①→|||・Priority[OpCnt] ← nest + 1

  |||--

②→|||・Priority[OpCnt] ← nest + 2

  ||▼

  ||・OpCnt ← OpCnt + 1

  ||・Value[OpCnt] ← 0

  |▼

  |▲ chr = '('

③→||・nest ← nest + 10

  |▼

  |▲ chr = ')'

④→||・nest ← nest - 10

  |▼

  ■

〔プログラム(計算処理の部分)の説明〕

(1) 整数式の値を計算していく。図1に示す各配列及び変数の状態から、プログラム(計算処理の部分)の最外側の繰返しを1回実行した直後の各配列及び変数の状態を、図2に示す。

平成30年度秋 基本情報技術者試験午後 過去問8 データ構造及びアルゴリズム

図2 プログラム(計算処理の部分)の最そとがわの繰返しを1回実行した直後の状態

  ■ OpCnt > 0

⑤→|・ ip ← 0

⑥→|■ i: 1, i < OpCnt, 1

⑦→||▲ Priority[ip] < Priority[i]

  |||・ip ← i

  ||▼

  |■

  |・chr ← Operator[ip]

  |▲ chr = '+'

  ||・Value[ip] ← Value[ip] + Value[ip + 1]

  |▼

  |chr = '-'

  ||・Value[ip] ← Value[ip] - Value[ip + 1]

  |▼

  |chr = '×'

  ||・Value[ip] ← Value[ip] × Value[ip + 1]

  |▼

  |chr = '÷'

  ||・Value[ip] ← Value[ip] ÷ Value[ip + 1]

  |▼

  |■ i: ip + 1, i < OpCnt, 1

  ||・Value[i] ← Value[i + 1]

  ||・Operator[i - 1] ← Operator[i]

  ||・Priority[i - 1] ← Priority[i]

  |■

  |・OpCnt ← OpCnt - 1

  ■

設問1

プログラム(解析処理の部分)に関する次の記述中の に入れる正しい答えを、解答群の中から選べ。

 プログラム(解析処理の部分)の行①~④で用いている定数について考察する。

 まず、行③及び④の処理では、定数として10を用いているが、この定数は10である必要はない。このプログラムにおいては、定数がaであれば常に正しい演算順序が保証される。

 また、行①及び②の処理では、定数として1及び2を用いているが、次に示すように書き換えることが可能である。ここで、priLow 及び priHigh は整数の定数を表し、その値は priLow<priHigh とする。

 ①→  ・Priority[OpCnt] ← nest+priLow

 ②→  ・Priority[OpCnt] ← nest+priHigh

 このように表現したとき、行③及び④の処理では、nest の値を増減する定数がbのときに限リ正しい演算順序が保証されることになる。

a に関する解答群

ア 1以上

イ 2以上

ウ 11以下

エ 12以下

b に関する解答群

ア priHigh以上

イ priHigh+1以上

ウ priHigh-priLow以上

エ priHigh-priLow+1以上

設問2

優先順位の等しい演算子が複数個含まれている整数式の、演算の実行順序について考察する。プログラムに関する次の記述中の に入れる正しい答えを、解答群の中から選べ。ここで、c1~c3に入れる答えは、cに関する解答群の中から組合せとして正しいものを選ぶものとする。

 プログラム(計算処理の部分)では、優先順位の等しい演算子が複数個含まれている場合、演算を左から順に実行するようになっている。このプログラムでは、演算を左から順に実行するか右から順に実行するかは、行c1の内容がc2c3かで決まる。

 演算の実行順序によって、計算結果が異なることがある。例えば、次の四つの整数式のケースを考える。

  ケース1:(12+3+1)×4×2

  ケース2:(12+3+1)÷4÷2

  ケース3:(12-3-1)×4×2

  ケース4:(12-3-1)÷4÷2

 これらのケースのうち、演算を左から実行しても右から実行しでも、プログラムによる計算結果が等しくなるのは、ケースdである。

c に関する解答群

c1 c2 c3
・ip ← 0 ・ip ← OpCnt - 1
i:1, i < OpCnt, 1 i:OpCnt, i > 0, -1
i:1, i < OpCnt, 1 i:OpCnt-1, i > 0, -1
Priority[ip] < Priority[i] Priority[ip] ≦ Priority[i]

d に関する解答群

ア 1

イ 1及び2

ウ 1及び3

エ 1及び4

設問3

プログラムの動作に関する次の記述中の に入れる正しい答えを、解答群の中から選べ。

 符号付き整定数(数字の並びの先頭に符号+又は-を付けた定数)を含む整数式を考える。符号付き整定数は、例2のように括弧で囲んで記述する。ただし、符号付き整定数の直前の文字が演算子でない場合は、例3のように括弧で囲まなくてもよい。

  例2: (+2) × ((-3) + (-4))

  例3: +2 × (-3 + (-4))

 符号付き整定数を含む整数式 2 × (-1) についてプログラム(解析処理の部分)を実行した結果を、図3に示す。

 このように、符号付き整定数を含む整数式を受け取ったとき、プログラムはe

注記 網掛け部分(値が格納されているとは限らない)は表示していない

平成30年度秋 基本情報技術者試験午後 過去問8 データ構造及びアルゴリズム

図3 整数式 2 × (-1) についてプログラム(解析処理の部分)を実行した結果

e に関する解答群

ア 整数式が符号付き整定数で始まる場合に、正しい値を返さない

イ 整数式中に符号 - の付いた符号付き整定数がある場合に、正しい値を返さない

ウ 整数式中に二つ以上の符号付き整定数が含まれる場合に、正しい値を返さない

エ 正しい値を返す

f, g に関する解答群

ア -1

イ 0

ウ 1

エ 2

設問1 解説

プログラム(解析処理の部分)に関する次の記述中の に入れる正しい答えを、解答群の中から選べ。

 プログラム(解析処理の部分)の行①~④で用いている定数について考察する。

 まず、行③及び④の処理では、定数として10を用いているが、この定数は10である必要はない。このプログラムにおいては、定数がaであれば常に正しい演算順序が保証される。

 また、行①及び②の処理では、定数として1及び2を用いているが、次に示すように書き換えることが可能である。ここで、priLow 及び priHigh は整数の定数を表し、その値は priLow<priHigh とする。

 ①→  ・Priority[OpCnt] ← nest+priLow

 ②→  ・Priority[OpCnt] ← nest+priHigh

 このように表現したとき、行③及び④の処理では、nest の値を増減する定数がbのときに限リ正しい演算順序が保証されることになる。

a に関する解答群

ア 1以上

イ 2以上

ウ 11以下

エ 12以下

b に関する解答群

ア priHigh以上

イ priHigh+1以上

ウ priHigh-priLow以上

エ priHigh-priLow+1以上

平成30年度秋 基本情報技術者試験午後 過去問8 データ構造及びアルゴリズム

平成30年度秋 基本情報技術者試験午後 過去問8 データ構造及びアルゴリズム

平成30年度秋 基本情報技術者試験午後 過去問8 データ構造及びアルゴリズム

平成30年度秋 基本情報技術者試験午後 過去問8 データ構造及びアルゴリズム

設問2 解説

優先順位の等しい演算子が複数個含まれている整数式の、演算の実行順序について考察する。プログラムに関する次の記述中の に入れる正しい答えを、解答群の中から選べ。ここで、c1~c3に入れる答えは、cに関する解答群の中から組合せとして正しいものを選ぶものとする。

 プログラム(計算処理の部分)では、優先順位の等しい演算子が複数個含まれている場合、演算を左から順に実行するようになっている。このプログラムでは、演算を左から順に実行するか右から順に実行するかは、行c1の内容がc2c3かで決まる。

 演算の実行順序によって、計算結果が異なることがある。例えば、次の四つの整数式のケースを考える。

  ケース1:(12+3+1)×4×2

  ケース2:(12+3+1)÷4÷2

  ケース3:(12-3-1)×4×2

  ケース4:(12-3-1)÷4÷2

 これらのケースのうち、演算を左から実行しても右から実行しでも、プログラムによる計算結果が等しくなるのは、ケースdである。

c に関する解答群

c1 c2 c3
・ip ← 0 ・ip ← OpCnt - 1
i:1, i < OpCnt, 1 i:OpCnt, i > 0, -1
i:1, i < OpCnt, 1 i:OpCnt-1, i > 0, -1
Priority[ip] < Priority[i] Priority[ip] ≦ Priority[i]

d に関する解答群

ア 1

イ 1及び2

ウ 1及び3

エ 1及び4

平成30年度秋 基本情報技術者試験午後 過去問8 データ構造及びアルゴリズム

平成30年度秋 基本情報技術者試験午後 過去問8 データ構造及びアルゴリズム

設問3 解説

プログラムの動作に関する次の記述中の に入れる正しい答えを、解答群の中から選べ。

 符号付き整定数(数字の並びの先頭に符号+又は-を付けた定数)を含む整数式を考える。符号付き整定数は、例2のように括弧で囲んで記述する。ただし、符号付き整定数の直前の文字が演算子でない場合は、例3のように括弧で囲まなくてもよい。

  例2: (+2) × ((-3) + (-4))

  例3: +2 × (-3 + (-4))

 符号付き整定数を含む整数式 2 × (-1) についてプログラム(解析処理の部分)を実行した結果を、図3に示す。

 このように、符号付き整定数を含む整数式を受け取ったとき、プログラムはe

注記 網掛け部分(値が格納されているとは限らない)は表示していない

平成30年度秋 基本情報技術者試験午後 過去問8 データ構造及びアルゴリズム

図3 整数式 2 × (-1) についてプログラム(解析処理の部分)を実行した結果

e に関する解答群

ア 整数式が符号付き整定数で始まる場合に、正しい値を返さない

イ 整数式中に符号 - の付いた符号付き整定数がある場合に、正しい値を返さない

ウ 整数式中に二つ以上の符号付き整定数が含まれる場合に、正しい値を返さない

エ 正しい値を返す

f, g に関する解答群

ア -1

イ 0

ウ 1

エ 2

平成30年度秋 基本情報技術者試験午後 過去問8 データ構造及びアルゴリズム

PR広告

フェイスブックコメント

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

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

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

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

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

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

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

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

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