基本情報技術者試験 科目B アルゴリズムとプログラミング 練習問題 セット3
アルゴリズムとプログラミングの15問を本番のペースの75分で解きます。時間制限なしでも練習できます。目標は9問正解です。
- 問題数
- 15
- 時間
- 75分
- 目標
- 9 (60%)
- 分野
- アルゴリズムとプログラミング
- モード
- 時間制限あり・なし
- 利用
- 試験パス
このテストにはJavaScriptが必要です。問題は次のとおりです。
関数 halvings は、1以上の整数 n を受け取り、n を2で割って小数点以下を切り捨てる操作を、n が1になるまで繰り返したときの操作の回数を返す。例えば halvings(9) は、9、4、2、1 と3回の操作で1になるので3を返す。プログラム中の〔 a 〕に入れる正しい答えはどれか。
○整数型: halvings(整数型: n) 整数型: count ← 0 while (〔 a 〕) n ← n ÷ 2 の商 count ← count + 1 endwhile return count次のプログラムを実行したときに出力される値はどれか。ここで、二次元配列の要素番号は行番号、列番号の順に指定し、内側の { } が1行分の内容を表す。
整数型の二次元配列: m ← {{2, 0, 1}, {3, 5, 4}, {6, 7, 8}} 整数型: i, j, s ← 0 for (i を 1 から 3 まで 1 ずつ増やす) for (j を 1 から 3 まで 1 ずつ増やす) if (i < j) s ← s + m[i, j] endif endfor endfor sを出力する関数 gcd を gcd(84, 36) として呼び出したときの戻り値はどれか。
○整数型: gcd(整数型: a, 整数型: b) 整数型: r while (b ≠ 0) r ← a mod b a ← b b ← r endwhile return a関数 find は、昇順に整列された整数型の配列 data から target を2分探索で探し、見つかればその要素番号を、見つからなければ -1 を返す。プログラム中の〔 a 〕に入れる正しい答えはどれか。ここで、配列の要素番号は1から始まる。
○整数型: find(整数型の配列: data, 整数型: target) 整数型: low ← 1 整数型: high ← dataの要素数 整数型: mid while (low ≦ high) mid ← (low + high) ÷ 2 の商 if (data[mid] = target) return mid elseif (data[mid] < target) 〔 a 〕 else high ← mid - 1 endif endwhile return -1関数 countSort は、1以上 k 以下の整数だけから成る配列 a を、値ごとの個数を数える方法で昇順に並べた配列を返す。プログラム中の〔 a 〕に入れる正しい答えはどれか。ここで、配列の要素番号は1から始まる。
○整数型の配列: countSort(整数型の配列: a, 整数型: k) 整数型の配列: c ← {k個の0} 整数型の配列: r ← {} 整数型: i, j for (i を 1 から aの要素数 まで 1 ずつ増やす) c[a[i]] ← c[a[i]] + 1 endfor for (i を 1 から k まで 1 ずつ増やす) for (j を 1 から 〔 a 〕 まで 1 ずつ増やす) rの末尾 に i を追加する endfor endfor return r次のプログラムを実行したときに出力される配列はどれか。ここで、配列の要素番号は1から始まる。
整数型の配列: a ← {2, 5, 1, 4} 整数型: i for (i を 4 から 2 まで 1 ずつ減らす) a[i] ← a[i] + a[i - 1] endfor aを出力する手続 p を p(3) として呼び出したとき、出力される値を出力順に並べたものはどれか。
○p(整数型: n) if (n > 0) nを出力する p(n - 1) nを出力する endif関数 words は、文字型の配列 s に含まれる単語の数を返す。単語は空白以外の文字が1文字以上続いたもので、単語の間には空白が1文字以上ある。s = {" ", "w", "e", " ", " ", "g", "o", " ", "u", "p"} として呼び出したときの戻り値はどれか。ここで、" " は空白1文字を表し、配列の要素番号は1から始まる。
○整数型: words(文字型の配列: s) 整数型: i, c ← 0 論理型: inWord ← false for (i を 1 から sの要素数 まで 1 ずつ増やす) if (s[i] = " ") inWord ← false elseif (not inWord) c ← c + 1 inWord ← true endif endfor return c関数 squeeze は、要素数1以上の文字型の配列 s で、空白が2文字以上続く部分を空白1文字にまとめた配列を返す。例えば {"a", " ", " ", "b"} は {"a", " ", "b"} になる。プログラム中の〔 a 〕に入れる正しい答えはどれか。ここで、" " は空白1文字を表し、配列の要素番号は1から始まる。
○文字型の配列: squeeze(文字型の配列: s) 文字型の配列: r ← {} 整数型: i rの末尾 に s[1] を追加する for (i を 2 から sの要素数 まで 1 ずつ増やす) if (s[i] ≠ " " or 〔 a 〕) rの末尾 に s[i] を追加する endif endfor return r関数 deepest は、"(" と ")" が正しく対応した文字型の配列 s で、かっこが最も深く重なったときの深さを返す。クラス Stack はスタックを表す。Stack() は空のスタックを生成し、メソッド push(x) は x を格納し、pop() は最後に格納した要素を取り出して返し、size() は格納されている要素の個数を返す。deepest({"(", "(", ")", "(", "(", ")", ")", ")"}) として呼び出したときの戻り値はどれか。ここで、配列の要素番号は1から始まる。
○整数型: deepest(文字型の配列: s) Stack: st ← Stack() 整数型: i, best ← 0 for (i を 1 から sの要素数 まで 1 ずつ増やす) if (s[i] = "(") st.push(i) if (st.size() > best) best ← st.size() endif else st.pop() /* 戻り値は使用しない */ endif endfor return bestクラス ListElement は単方向リストの要素を表し、メンバ変数 val(整数型)に要素の値を、next(ListElement 型)に次の要素の参照を格納する。次の要素がないとき next は未定義である。ListElement(v) は、val が v で next が未定義の要素を生成する。手続 reverse は、大域変数 listHead が先頭を指す単方向リストの並びを逆にする。プログラム中の〔 a 〕に入れる正しい答えはどれか。
大域: ListElement: listHead ○reverse() ListElement: prev, cur, nxt prev ← 未定義の値 cur ← listHead while (cur が 未定義でない) nxt ← cur.next 〔 a 〕 prev ← cur cur ← nxt endwhile listHead ← prev重み付き有向グラフの辺を、出発点 from、到着点 to、重み w の三つの配列で表す。頂点1から各頂点への最短距離を求めるため、すべての辺について距離を短くできるか調べる操作を3回繰り返す。99はまだ到達していないことを表す。次のプログラムを実行したときに出力される配列はどれか。ここで、配列の要素番号は1から始まる。
整数型の配列: from ← {3, 2, 1, 1, 2} 整数型の配列: to ← {4, 4, 2, 3, 3} 整数型の配列: w ← {6, 5, 4, 1, 2} 整数型の配列: d ← {0, 99, 99, 99} 整数型: k, e for (k を 1 から 3 まで 1 ずつ増やす) for (e を 1 から fromの要素数 まで 1 ずつ増やす) if (d[from[e]] + w[e] < d[to[e]]) d[to[e]] ← d[from[e]] + w[e] endif endfor endfor dを出力する関数 pairs を pairs(n) として呼び出したとき、αの行が実行される回数を n で表したものはどれか。ここで、n は1以上とする。
○整数型: pairs(整数型: n) 整数型: i, j, cnt ← 0 for (i を 1 から n まで 1 ずつ増やす) for (j を 1 から i - 1 まで 1 ずつ増やす) cnt ← cnt + 1 /*** α ***/ endfor endfor return cntクラス Item は商品を表し、メンバ変数 price(単価、整数型)と qty(数量、整数型)をもつ。Item(p, q) は price が p、qty が q のインスタンスを生成する。次のプログラムは、数量が5以上の商品を1割引きにして合計金額を求める。出力される値はどれか。ここで、配列の要素番号は1から始まる。
Itemの配列: cart ← {Item(300, 2), Item(120, 5), Item(800, 1)} 整数型: i, total ← 0 for (i を 1 から cartの要素数 まで 1 ずつ増やす) if (cart[i].qty ≧ 5) total ← total + (cart[i].price × cart[i].qty × 9 ÷ 10 の商) else total ← total + cart[i].price × cart[i].qty endif endfor totalを出力する関数 moving は、整数型の配列 a の連続する3要素ごとの平均(移動平均)を並べた配列を返す。moving({4, 8, 6, 10, 2}) として呼び出したときの戻り値はどれか。ここで、配列の要素番号は1から始まる。
○実数型の配列: moving(整数型の配列: a) 実数型の配列: r ← {} 整数型: i, s for (i を 3 から aの要素数 まで 1 ずつ増やす) s ← a[i - 2] + a[i - 1] + a[i] rの末尾 に s ÷ 3 を追加する endfor return r
このセットの出題内容
- 変数・制御構造1問
- 配列2問
- 数値計算2問
- 探索・整列2問
- 再帰1問
- 文字列処理2問
- スタック・キュー1問
- リスト構造1問
- 木・グラフ1問
- 計算量1問
- オブジェクト指向1問
この試験のほかの練習
IPA(独立行政法人情報処理推進機構)とは関係のない独自の練習です。問題はすべて当サイトのオリジナルで、IPAのサンプル問題、公開問題、過去問題ではありません。