配列で作るスタック 問題14
練習モードは行番号つきで順に解く形式、本番形式は公開問題と同じ体裁の1問です。
大域の配列 stack と変数 top でスタックを表す。手続 push は値を積み、関数 pop は最後に積んだ値を取り出して返す。関数 test は、取り出した値を順に並べた整数を返す。配列の要素番号は 1 から始まる。
次のプログラムを test() で呼び出す。
〔プログラム〕
| 1 | 大域: 整数型の配列: stack ← {3 個の 0} |
| 2 | 大域: 整数型: top ← 0 |
| 3 | |
| 4 | ○push(整数型: x) |
| 5 | top ← top ＋ 1 |
| 6 | stack[top] ← x |
| 7 | |
| 8 | ○整数型: pop() |
| 9 | 整数型: v ← stack[top] |
| 10 | top ← top － 1 |
| 11 | return v |
| 12 | |
| 13 | ○整数型: test() |
| 14 | 整数型: r |
| 15 | push(9) |
| 16 | push(5) |
| 17 | r ← pop() |
| 18 | push(6) |
| 19 | r ← r × 10 ＋ pop() |
| 20 | r ← r × 10 ＋ pop() |
| 21 | return r |
ヒント1：トレース表の枠を見る
この列で表を作り、文を1つ実行するたびに1行足していきます。
| # | 行 | したこと | stack | top | r | x | v |
|---|
ヒント2：最初の6ステップを見る
続きを同じ要領で書いていきます。太字は、その文で値が変わった変数です。
| # | 行 | したこと | 手続 | stack | top | r | x | v |
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 宣言 | (main) | {0, 0, 0} | — | — | — | — |
| 2 | 2 | 宣言 | (main) | {0, 0, 0} | 0 | — | — | — |
| 3 | 14 | 宣言 | test | {0, 0, 0} | 0 | 未定義 | — | — |
| 4 | 5 | 代入 | push | {0, 0, 0} | 1 | — | 9 | — |
| 5 | 6 | 代入 | push | {9, 0, 0} | 1 | — | 9 | — |
| 6 | 15 | 呼出し | test | {9, 0, 0} | 1 | 未定義 | — | — |
設問1
6行目を3回目に実行した直後の、変数 stack の値はどれか。
正解：イ {9, 6, 0}
- 6行目は全部で3回実行されます。
- 実行した直後の stack は、順に {9, 0, 0} → {9, 5, 0} → {9, 6, 0} です。
- 3回目の直後なので、答えは {9, 6, 0} です。
設問2
10行目を3回目に実行した直後の、変数 top の値はどれか。
正解：ア 0
- 10行目は全部で3回実行されます。
- 実行した直後の top は、順に 1 → 1 → 0 です。
- 3回目の直後なので、答えは 0 です。
設問3
test() を呼び出したときの戻り値はどれか。
正解：エ 569
- 呼出しは全部で4回行われます。
- 奥の呼出しから順に 5 → 6 → 9 → 569 を返し、最後に返る 569 が答えです。
本番形式
問 次の記述中の［ ａ ］に入れる正しい答えを，解答群の中から選べ。
大域の配列 stack と変数 top でスタックを表す。手続 push は値を積み，関数 pop は最後に積んだ値を取り出して返す。関数 test は，取り出した値を順に並べた整数を返す。配列の要素番号は 1 から始まる。
関数 test を test() として呼び出すと，戻り値は［ ａ ］となる。
〔プログラム〕
| 大域: 整数型の配列: stack ← {3 個の 0} |
| 大域: 整数型: top ← 0 |
| ○push(整数型: x) |
| top ← top ＋ 1 |
| stack[top] ← x |
| ○整数型: pop() |
| 整数型: v ← stack[top] |
| top ← top － 1 |
| return v |
| ○整数型: test() |
| 整数型: r |
| push(9) |
| push(5) |
| r ← pop() |
| push(6) |
| r ← r × 10 ＋ pop() |
| r ← r × 10 ＋ pop() |
| return r |
解答群
正解：オ 569
- 呼出しは全部で4回行われます。
- 奥の呼出しから順に 5 → 6 → 9 → 569 を返し、最後に返る 569 が答えです。
解説
スタックは「最後に積んだ値から先に取り出す」入れ物です。top は、いちばん上の値が入っている要素番号です。 9、5 を積んで 1 つ取り出し、6 を積んでから 2 つ取り出します。取り出した順に並べると 569 です。
行番号つきのプログラム
| 1 | 大域: 整数型の配列: stack ← {3 個の 0} |
| 2 | 大域: 整数型: top ← 0 |
| 3 | |
| 4 | ○push(整数型: x) |
| 5 | top ← top ＋ 1 |
| 6 | stack[top] ← x |
| 7 | |
| 8 | ○整数型: pop() |
| 9 | 整数型: v ← stack[top] |
| 10 | top ← top － 1 |
| 11 | return v |
| 12 | |
| 13 | ○整数型: test() |
| 14 | 整数型: r |
| 15 | push(9) |
| 16 | push(5) |
| 17 | r ← pop() |
| 18 | push(6) |
| 19 | r ← r × 10 ＋ pop() |
| 20 | r ← r × 10 ＋ pop() |
| 21 | return r |
トレース表（全ステップ）
太字は、その文で値が変わった変数です。設問が指している行は黄色、その回は濃い黄色、変数は青い列で示します。
| # | 行 | したこと | 手続 | stack | top | r | x | v |
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 宣言 | (main) | {0, 0, 0} | — | — | — | — |
| 2 | 2 | 宣言 | (main) | {0, 0, 0} | 0 | — | — | — |
| 3 | 14 | 宣言 | test | {0, 0, 0} | 0 | 未定義 | — | — |
| 4 | 5 | 代入 | push | {0, 0, 0} | 1 | — | 9 | — |
| 5 | 6 | 代入 | push | {9, 0, 0} | 1 | — | 9 | — |
| 6 | 15 | 呼出し | test | {9, 0, 0} | 1 | 未定義 | — | — |
| 7 | 5 | 代入 | push | {9, 0, 0} | 2 | — | 5 | — |
| 8 | 6 | 代入 | push | {9, 5, 0} | 2 | — | 5 | — |
| 9 | 16 | 呼出し | test | {9, 5, 0} | 2 | 未定義 | — | — |
| 10 | 9 | 宣言 | pop | {9, 5, 0} | 2 | — | — | 5 |
| 11 | 10 | 代入 | pop | {9, 5, 0} | 1 | — | — | 5 |
| 12 | 11 | 戻る（5） | pop | {9, 5, 0} | 1 | — | — | 5 |
| 13 | 17 | 代入 | test | {9, 5, 0} | 1 | 5 | — | — |
| 14 | 5 | 代入 | push | {9, 5, 0} | 2 | — | 6 | — |
| 15 | 6 | 代入 | push | {9, 6, 0} | 2 | — | 6 | — |
| 16 | 18 | 呼出し | test | {9, 6, 0} | 2 | 5 | — | — |
| 17 | 9 | 宣言 | pop | {9, 6, 0} | 2 | — | — | 6 |
| 18 | 10 | 代入 | pop | {9, 6, 0} | 1 | — | — | 6 |
| 19 | 11 | 戻る（6） | pop | {9, 6, 0} | 1 | — | — | 6 |
| 20 | 19 | 代入 | test | {9, 6, 0} | 1 | 56 | — | — |
| 21 | 9 | 宣言 | pop | {9, 6, 0} | 1 | — | — | 9 |
| 22 | 10 | 代入 | pop | {9, 6, 0} | 0 | — | — | 9 |
| 23 | 11 | 戻る（9） | pop | {9, 6, 0} | 0 | — | — | 9 |
| 24 | 20 | 代入 | test | {9, 6, 0} | 0 | 569 | — | — |
| 25 | 21 | 戻る（569） | test | {9, 6, 0} | 0 | 569 | — | — |