基本情報技術者試験 科目B アルゴリズムとプログラミング 練習問題 セット2
アルゴリズムとプログラミングの15問を本番のペースの75分で解きます。時間制限なしでも練習できます。目標は9問正解です。
- 問題数
- 15
- 時間
- 75分
- 目標
- 9 (60%)
- 分野
- アルゴリズムとプログラミング
- モード
- 時間制限あり・なし
- 利用
- 試験パス
このテストにはJavaScriptが必要です。問題は次のとおりです。
次のプログラムを実行したときに出力される値はどれか。
整数型: x ← 4096 整数型: s ← 0 while (x > 0) s ← s + x mod 10 x ← x ÷ 10 の商 endwhile sを出力する関数 maxIndex は、要素数1以上の整数型の配列 a で最大値が入っている要素番号を返す。最大値が複数あるときは、最も小さい要素番号を返す。プログラム中の〔 a 〕に入れる正しい答えはどれか。ここで、配列の要素番号は1から始まる。
○整数型: maxIndex(整数型の配列: a) 整数型: k ← 1 整数型: i for (i を 2 から aの要素数 まで 1 ずつ増やす) if (〔 a 〕) k ← i endif endfor return k関数 digits を digits(13) として呼び出したときの戻り値はどれか。
○整数型の配列: digits(整数型: n) 整数型の配列: r ← {} do rの末尾 に n mod 2 を追加する n ← n ÷ 2 の商 while (n > 0) return r手続 sortAsc は、整数型の配列 a を選択ソートで昇順に整列する。i 番目の位置には、a[i] から末尾までの最小値を入れる。プログラム中の〔 a 〕に入れる正しい答えはどれか。ここで、配列の要素番号は1から始まる。
○sortAsc(整数型の配列: a) 整数型: i, j, m for (i を 1 から aの要素数 - 1 まで 1 ずつ増やす) m ← i for (j を 〔 a 〕 から aの要素数 まで 1 ずつ増やす) if (a[j] < a[m]) m ← j endif endfor a[i] と a[m] の値を入れ替える endfor関数 g を g(5) として呼び出したとき、g が呼び出される回数はどれか。ここで、最初の呼出し g(5) も1回と数える。
○整数型: g(整数型: n) if (n ≦ 1) return n endif return g(n - 1) + g(n - 2)次のプログラムを実行したとき、出力される値を出力順に並べたものはどれか。
整数型: a ← 4 整数型: b ← 7 整数型: c ← 2 a ← b - c b ← a × c c ← b mod a aを出力する bを出力する cを出力する手続 hanoi は、ハノイの塔の円盤の移し方を、移動元の柱の番号 × 10 + 移動先の柱の番号 の形で一つずつ出力する。hanoi(3, 1, 3, 2) として呼び出したとき、出力される値の個数はどれか。
○hanoi(整数型: n, 整数型: from, 整数型: to, 整数型: via) if (n > 0) hanoi(n - 1, from, via, to) from × 10 + to を出力する hanoi(n - 1, via, to, from) endif関数 indexOf は、文字型の配列 t の中に文字型の配列 p と同じ並びが最初に現れる位置(先頭の要素番号)を返し、現れなければ -1 を返す。プログラム中の〔 a 〕に入れる正しい答えはどれか。ここで、t の要素数は p の要素数以上とし、配列の要素番号は1から始まる。
○整数型: indexOf(文字型の配列: t, 文字型の配列: p) 整数型: i, j 論理型: ok for (i を 1 から 〔 a 〕 まで 1 ずつ増やす) ok ← true for (j を 1 から pの要素数 まで 1 ずつ増やす) if (t[i + j - 1] ≠ p[j]) ok ← false endif endfor if (ok) return i endif endfor return -1関数 balanced は、"(" と ")" だけから成る文字型の配列 s のかっこが正しく対応していれば true を、そうでなければ false を返す。クラス Stack はスタックを表す。Stack() は空のスタックを生成し、メソッド push(x) は x を格納し、pop() は最後に格納した要素を取り出して返し、size() は格納されている要素の個数を返す。プログラム中の〔 a 〕に入れる正しい答えはどれか。ここで、配列の要素番号は1から始まる。
○論理型: balanced(文字型の配列: s) Stack: st ← Stack() 整数型: i for (i を 1 から sの要素数 まで 1 ずつ増やす) if (s[i] = "(") st.push(s[i]) else if (〔 a 〕) return false endif st.pop() /* 戻り値は使用しない */ endif endfor return st.size() = 0クラス ListElement は単方向リストの要素を表し、メンバ変数 val(整数型)に要素の値を、next(ListElement 型)に次の要素の参照を格納する。次の要素がないとき next は未定義である。ListElement(v) は、val が v で next が未定義の要素を生成する。手続 insertAfter は、単方向リストの要素 p の直後に、値が v の新しい要素を挿入する。プログラム中の〔 a 〕と〔 b 〕に入れる正しい答えの組合せはどれか。
○insertAfter(ListElement: p, 整数型: v) ListElement: e ← ListElement(v) 〔 a 〕 〔 b 〕2分木を配列 t で表す。要素番号 k の節の左の子は要素番号 2 × k、右の子は 2 × k + 1 にあり、値が0の要素には節がない。大域変数 t = {8, 3, 10, 1, 6, 0, 14} のとき、手続 walk を walk(1) として呼び出したときの出力はどれか。ここで、配列の要素番号は1から始まる。
大域: 整数型の配列: t ← {8, 3, 10, 1, 6, 0, 14} ○walk(整数型: k) if (k ≦ tの要素数) if (t[k] ≠ 0) walk(2 × k) t[k]を出力する walk(2 × k + 1) endif endif2分木を配列 t で表す。要素番号 k の節の左の子は 2 × k、右の子は 2 × k + 1 にあり、値が0の要素や要素番号が t の要素数を超える位置には節がない。関数 height は、k を根とする部分木の高さ(根から最も遠い節までの節の個数)を返し、関数 hmax は二つの引数のうち大きいほうを返す。プログラム中の〔 a 〕に入れる正しい答えはどれか。ここで、配列の要素番号は1から始まる。
大域: 整数型の配列: t ← {8, 3, 10, 1, 6, 0, 14, 0, 0, 4, 7} ○整数型: hmax(整数型: x, 整数型: y) if (x > y) return x endif return y ○整数型: height(整数型: k) if (k > tの要素数) return 0 endif if (t[k] = 0) return 0 endif return 〔 a 〕関数 doubling を doubling(100) として呼び出したとき、αの行が実行される回数はどれか。
○整数型: doubling(整数型: n) 整数型: i ← 1 while (i < n) i ← i × 2 /*** α ***/ endwhile return iクラス Point は平面上の点を表し、メンバ変数 x と y(いずれも整数型)をもつ。Point(a, b) は x が a、y が b のインスタンスを生成する。Point 型の変数には、インスタンスそのものではなくインスタンスの参照が格納される。次のプログラムを実行したとき、出力される値を出力順に並べたものはどれか。
Point: p ← Point(1, 2) Point: q ← p Point: r ← Point(1, 2) q.x ← 5 r.y ← 7 p.xを出力する p.yを出力する次のプログラムは、2分法で x × x = 2 の正の解を含む範囲を狭めていく。出力される値を出力順に並べたものはどれか。
実数型: lo ← 1 実数型: hi ← 2 実数型: mid 整数型: k for (k を 1 から 3 まで 1 ずつ増やす) mid ← (lo + hi) ÷ 2 if (mid × mid < 2) lo ← mid else hi ← mid endif endfor loを出力する hiを出力する
このセットの出題内容
- 変数・制御構造2問
- 配列1問
- 数値計算2問
- 探索・整列1問
- 再帰2問
- 文字列処理1問
- スタック・キュー1問
- リスト構造1問
- 木・グラフ2問
- 計算量1問
- オブジェクト指向1問
この試験のほかの練習
IPA(独立行政法人情報処理推進機構)とは関係のない独自の練習です。問題はすべて当サイトのオリジナルで、IPAのサンプル問題、公開問題、過去問題ではありません。