配列で作るスタック 問題27
大域の配列 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 ← ［ ａ ］ |
| 11 | return v |
| 12 | |
| 13 | ○整数型: test() |
| 14 | 整数型: r |
| 15 | push(7) |
| 16 | push(4) |
| 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 | — | 7 | — |
| 5 | 6 | 代入 | push | {7, 0, 0} | 1 | — | 7 | — |
| 6 | 15 | 呼出し | test | {7, 0, 0} | 1 | 未定義 | — | — |
設問1
test() を呼び出すと戻り値は 467 になる。プログラム中の ［ ａ ］ に入れる正しい答えはどれか。
正解：ウ top － 1
- それぞれの選択肢を空欄に入れて、実際に動かした結果は次のとおりです。
- 「v － 1」→ 途中で止まる（配列の範囲外です（要素番号 4、要素数 3））
- 「top － 2」→ 途中で止まる（配列の範囲外です（要素番号 -1、要素数 3））
- 「top － 1」→ 戻り値は 467（正解）
- 「top ＋ 1」→ 途中で止まる（配列の範囲外です（要素番号 4、要素数 3））
設問2
6行目を3回目に実行した直後の、変数 stack の値はどれか。
正解：ア {7, 6, 0}
- 6行目は全部で3回実行されます。
- 実行した直後の stack は、順に {7, 0, 0} → {7, 4, 0} → {7, 6, 0} です。
- 3回目の直後なので、答えは {7, 6, 0} です。
設問3
10行目を2回目に実行した直後の、変数 top の値はどれか。
正解：イ 1
- 10行目は全部で3回実行されます。
- 実行した直後の top は、順に 1 → 1 → 0 です。
- 2回目の直後なので、答えは 1 です。
本番形式
問 次の記述中の［ ａ ］に入れる正しい答えを，解答群の中から選べ。
大域の配列 stack と変数 top でスタックを表す。手続 push は値を積み，関数 pop は最後に積んだ値を取り出して返す。関数 test は，取り出した値を順に並べた整数を返す。配列の要素番号は 1 から始まる。
関数 test を test() として呼び出したとき，プログラム中の α の行を3回目に実行した直後の変数 stack の値は［ ａ ］となる。
〔プログラム〕
| 大域: 整数型の配列: 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(7) |
| push(4) |
| r ← pop() |
| push(6) |
| r ← r × 10 ＋ pop() |
| r ← r × 10 ＋ pop() |
| return r |
解答群
正解：イ {7, 6, 0}
- 6行目は全部で3回実行されます。
- 実行した直後の stack は、順に {7, 0, 0} → {7, 4, 0} → {7, 6, 0} です。
- 3回目の直後なので、答えは {7, 6, 0} です。
α の行は，下のトレース表（行番号つき）では 6 行目です。
解説
スタックは「最後に積んだ値から先に取り出す」入れ物です。top は、いちばん上の値が入っている要素番号です。 7、4 を積んで 1 つ取り出し、6 を積んでから 2 つ取り出します。取り出した順に並べると 467 です。
行番号つきのプログラム
| 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(7) |
| 16 | push(4) |
| 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 | — | 7 | — |
| 5 | 6 | 代入 | push | {7, 0, 0} | 1 | — | 7 | — |
| 6 | 15 | 呼出し | test | {7, 0, 0} | 1 | 未定義 | — | — |
| 7 | 5 | 代入 | push | {7, 0, 0} | 2 | — | 4 | — |
| 8 | 6 | 代入 | push | {7, 4, 0} | 2 | — | 4 | — |
| 9 | 16 | 呼出し | test | {7, 4, 0} | 2 | 未定義 | — | — |
| 10 | 9 | 宣言 | pop | {7, 4, 0} | 2 | — | — | 4 |
| 11 | 10 | 代入 | pop | {7, 4, 0} | 1 | — | — | 4 |
| 12 | 11 | 戻る（4） | pop | {7, 4, 0} | 1 | — | — | 4 |
| 13 | 17 | 代入 | test | {7, 4, 0} | 1 | 4 | — | — |
| 14 | 5 | 代入 | push | {7, 4, 0} | 2 | — | 6 | — |
| 15 | 6 | 代入 | push | {7, 6, 0} | 2 | — | 6 | — |
| 16 | 18 | 呼出し | test | {7, 6, 0} | 2 | 4 | — | — |
| 17 | 9 | 宣言 | pop | {7, 6, 0} | 2 | — | — | 6 |
| 18 | 10 | 代入 | pop | {7, 6, 0} | 1 | — | — | 6 |
| 19 | 11 | 戻る（6） | pop | {7, 6, 0} | 1 | — | — | 6 |
| 20 | 19 | 代入 | test | {7, 6, 0} | 1 | 46 | — | — |
| 21 | 9 | 宣言 | pop | {7, 6, 0} | 1 | — | — | 7 |
| 22 | 10 | 代入 | pop | {7, 6, 0} | 0 | — | — | 7 |
| 23 | 11 | 戻る（7） | pop | {7, 6, 0} | 0 | — | — | 7 |
| 24 | 20 | 代入 | test | {7, 6, 0} | 0 | 467 | — | — |
| 25 | 21 | 戻る（467） | test | {7, 6, 0} | 0 | 467 | — | — |