🎓 大学定期試験・院試対策
データ構造とアルゴリズム過去問・一問一答
- 収録問題
- 50問
- カテゴリ
- 4分野
あなたの達成率
完了率 0%0 / 50問 正解済み
収録問題一覧
✓ 正解済み ✕ 前回不正解
計算量とオーダー記法11問
- cs-algo-001・易あるアルゴリズムの時間計算量が で表されるとき、これをオーダー記法で表したものはどれか。
- cs-algo-002・標準入力サイズ n が十分大きいとき、計算量を増加の小さい順に正しく並べたものはどれか。
- cs-algo-003・標準時間計算量が のアルゴリズムを、1秒間に 回の基本操作を実行できるコンピュータで、n=50 の入力に対して実行する。基本操作の回数を 回とし、 を とみなして近似したとき、実行時間はおよそどれくらいか。
- cs-algo-004・標準漸化式 （c は正の定数、）で表される時間計算量のオーダーはどれか。
- cs-algo-005・標準円盤が6枚のハノイの塔を、最小の移動回数で解くときの移動回数はいくつか。
- cs-algo-006・易時間計算量が のアルゴリズムで、入力サイズ n を2倍にすると、実行時間はおよそ何倍になるか。ここで、n は十分大きいものとする。
- cs-algo-007・標準擬似コード「for i = 1 to n { for j = 1 to i { S } }」で、基本操作 S が実行される回数を表す式はどれか。
- cs-algo-008・標準実行時間が に比例するアルゴリズムと、 に比例するアルゴリズムのオーダーの関係として、適切なものはどれか。
- cs-algo-009・易100個のデータが格納された配列から、線形探索で目的のデータを探す。目的のデータは配列のどの位置にも等しい確率で存在するとき、探索が成功するまでの平均比較回数はいくつか。
- cs-algo-010・難n 都市の巡回セールスマン問題を、出発都市を固定してすべての巡回路を列挙して解くとき、調べる巡回路の数のオーダーとして適切なものはどれか。
- cs-algo-045・難関数 f を「n が0または1のとき1を返し、n が2以上のとき f(n−1) + f(n−2) を返す」と再帰的に定義する。f(5) を計算するとき、最初の呼出しも含めて f は何回呼び出されるか。
リスト・スタック・キュー・木構造12問
- cs-algo-011・標準空のスタック S と空のキュー Q に対して、push(S, 3) → push(S, 8) → enqueue(Q, pop(S)) → push(S, 5) → enqueue(Q, 1) → enqueue(Q, pop(S)) → dequeue(Q) の操作を順に実行した。最後の dequeue(Q) で取り出される値はどれか。
- cs-algo-012・標準すべての葉の深さが等しく、葉以外の節点がすべて2つの子をもつ2分木がある。根から葉までの辺の数（高さ）が4であるとき、節点の総数はいくつか。
- cs-algo-013・難大きさ N の配列 A[0]〜A[N−1] を循環させて使うキューで、先頭要素の添字を front、格納されている要素数を count とする。キューが満杯でないとき、次に enqueue する要素を格納する添字はどれか。
- cs-algo-014・易単方向の連結リストの特徴として、適切なものはどれか。
- cs-algo-015・易2分探索木を中間順（通りがけ順）に走査して節点の値を出力すると、値はどのような順に並ぶか。
- cs-algo-016・難2分探索木から、左右両方に子をもつ節点を削除する。2分探索木の性質を保つための置き換え方として、適切なものはどれか。
- cs-algo-017・標準2分ヒープを配列 A[0], A[1], … に格納するとき、A[i] の節点の左の子と右の子の添字の組合せとして適切なものはどれか。ここで、添字は0から始まり、根は A[0] とする。
- cs-algo-018・標準n 個の要素をもつ2分ヒープ（最大ヒープ）に、新しい要素を1つ挿入するときの最悪時間計算量はどれか。
- cs-algo-019・標準根が A で、A の左の子が B、右の子が C、B の左の子が D、右の子が E、C の右の子が F である2分木がある。この木を前順（行きがけ順）で走査したときの訪問順はどれか。
- cs-algo-020・標準逆ポーランド記法で書かれた式「6 2 3 + × 4 −」を、スタックを用いて評価した結果はどれか。
- cs-algo-044・標準空の2分探索木に、すでに昇順に整列された n 個のデータを先頭から順に挿入して木を作った。この木で値を探索するときの最悪時間計算量はどれか。
- cs-algo-049・易プログラムで関数を呼び出すとき、戻り先のアドレスや局所変数を保存しておくのに使われるデータ構造はどれか。
探索・ソートアルゴリズム13問
- cs-algo-021・標準昇順に整列された配列 D[0]〜D[10] = [3, 9, 14, 21, 27, 33, 40, 46, 52, 61, 75] から、2分探索で値46を探す。left=0, right=10 から始め、mid = ⌊(left + right)/2⌋ の要素と比較し、D[mid] が46より小さければ left = mid + 1、大きければ right = mid − 1 とする。比較される要素の値を順に並べたものはどれか。
- cs-algo-022・易2分探索法を適用するための前提条件として、適切なものはどれか。
- cs-algo-023・標準2000個の整列済みデータから2分探索で値を探すとき、比較回数の最大値はいくつか。
- cs-algo-024・標準配列を整列するマージソートの、クイックソートと比べたときの長所として、適切なものはどれか。
- cs-algo-025・標準配列の先頭の要素を常にピボットとするクイックソートで、時間計算量が最悪の になるのは、どのような入力のときか。
- cs-algo-026・標準配列 [6, 2, 7, 3, 1] を、隣り合う要素を左端から順に比較し、左の方が大きければ交換するバブルソートで昇順に整列する。1回目の走査（左端から右端までの比較と交換）を終えた直後の配列はどれか。
- cs-algo-027・標準ほぼ整列済みのデータに対して特に高速に動作し、完全に整列済みのデータであれば比較回数が n−1 回で済む整列アルゴリズムはどれか。
- cs-algo-028・難要素どうしの比較だけを用いて n 個の要素を整列するアルゴリズムについて、最悪の場合の比較回数の下限として正しいものはどれか。
- cs-algo-029・標準0〜k の範囲の整数だけからなる n 個のデータを、値ごとの出現回数を数えて整列する計数ソート（分布数え上げソート）の時間計算量はどれか。
- cs-algo-030・易アルゴリズムの設計手法である分割統治法の説明として、適切なものはどれか。
- cs-algo-041・標準ハッシュ表による探索で、適切なハッシュ関数を用いて衝突が少ない場合の平均時間計算量と、すべてのキーが同じハッシュ値になった最悪の場合の時間計算量の組合せとして、適切なものはどれか。ここで、衝突はチェイン法で処理し、n はデータ数とする。
- cs-algo-042・標準配列に対するヒープソートの特徴として、適切なものはどれか。
- cs-algo-043・易整列アルゴリズムが「安定である」とは、どういう意味か。
グラフアルゴリズム・動的計画法14問
- cs-algo-031・易グラフの幅優先探索を実装するとき、次に訪問する頂点を管理するのに用いるデータ構造として、適切なものはどれか。
- cs-algo-032・難頂点 S, A, B, C, T と、重み付きの無向辺 S−A(4), S−B(1), B−A(2), A−C(1), B−C(5), C−T(3), A−T(6) からなるグラフがある（括弧内は辺の重み）。ダイクストラ法で求めた S から T への最短距離はいくつか。
- cs-algo-033・標準ダイクストラ法を用いて単一始点最短経路問題を正しく解くための条件として、適切なものはどれか。
- cs-algo-034・標準貪欲法（グリーディ法）によって、常に最適解が得られる問題として適切なものはどれか。
- cs-algo-035・難容量5kgのナップサックに、次の4つの品物から選んで詰める。品物は分割できない。A：重さ2kg・価値30、B：重さ3kg・価値40、C：重さ4kg・価値50、D：重さ1kg・価値15。詰めた品物の価値の合計の最大値はいくらか。
- cs-algo-036・標準フィボナッチ数 F(n) = F(n−1) + F(n−2) を定義どおりの単純な再帰で計算すると、計算量は指数時間になる。計算済みの値を表に記録して再利用する方法に変えたときの時間計算量はどれか。ここで、加算は定数時間で行えるものとする。
- cs-algo-037・難行列 （2×10）、（10×5）、（5×20）の積 を計算する。p×q 行列と q×r 行列の積に必要なスカラーの乗算回数を pqr とするとき、計算順序を最適に選んだ場合の乗算回数の合計はいくつか。
- cs-algo-038・標準バックトラック法の説明として、適切なものはどれか。
- cs-algo-039・標準クラスカル法で、重み付き無向グラフの最小全域木を求める手順として適切なものはどれか。
- cs-algo-040・標準頂点1〜6と、辺 1−2, 1−3, 2−4, 2−5, 3−6, 5−6 からなる無向グラフがある。頂点1から深さ優先探索を行い、未訪問の隣接頂点が複数あるときは番号の小さい順に選ぶ。頂点を訪問する順序はどれか。
- cs-algo-046・難最大化問題を分枝限定法で解くとき、ある部分問題の探索を打ち切ってよいのは、どのような場合か。
- cs-algo-047・難頂点数 V、辺数 E のグラフに対するダイクストラ法で、暫定距離が最小の頂点を取り出す処理に2分ヒープを用いたときの時間計算量はどれか。
- cs-algo-048・標準有向グラフの頂点を、すべての辺が前から後ろへ向かうように一列に並べるトポロジカルソートが可能であるための条件はどれか。
- cs-algo-050・標準品物の数が n、ナップサックの容量が整数 W の0-1ナップサック問題を、「最初の i 個の品物から選び、重さの合計が w 以下のときの価値の最大値」を表に記録する動的計画法で解く。このときの時間計算量はどれか。