日本語
メニュー

データ構造とアルゴリズム

計算量(オーダー記法)、配列と連結リスト、スタックとキュー、ハッシュテーブル、二分探索、各種ソートの手順と安定性、二分探索木とヒープ、グラフの探索と最短経路、再帰・動的計画法・貪欲法を3択問題で学べます。キャッシュやGPUとの関係も扱います。

10問練習するこの分野からランダムに10問・約5分 この分野を解くこの分野の問題をすべて、ランダムな順で出題します 苦手問題直近で間違えた問題だけを解き直します

擬似言語の実行・トレースツール →

ソートの動きを見るツール →

ダイクストラ法の計算ツール →

二分探索木・ヒープの可視化ツール →

ハッシュ表の計算ツール →

計算量(オーダー)の比較ツール →

逆ポーランド記法の変換ツール →

データ構造とアルゴリズムの要点

同じ問題を解くプログラムでも、使うデータ構造とアルゴリズムによって、データが増えたときの速さは桁違いに変わります。計算量のオーダーで手間の増え方を見積もり、データの使い方に合った構造を選ぶことが、速いプログラムの出発点です。

配列と連結リスト、スタックとキュー、ハッシュテーブル、二分探索木とヒープ、グラフの表し方といった基本のデータ構造と、二分探索、バブル・選択・挿入・マージ・クイック・ヒープなどのソート、幅優先探索・深さ優先探索・ダイクストラ法、再帰・動的計画法・貪欲法を、手順を1つずつたどる計算問題を中心に学びます。基本情報技術者試験・応用情報技術者試験のアルゴリズム分野の学習にも役立ちます。さらに、キャッシュに合ったデータの並べ方やGPUでの並列ソートなど、ハードウェアの性能との関係も扱います。

データ構造とアルゴリズムの問題一覧（40問）
  1. 要素数 n の配列で、異なる2つの要素の組をすべて1回ずつ比べる処理(i 番目の要素を、それより後ろにあるすべての要素と比べることを、i を1つずつ進めて繰り返す二重ループ)の計算量はどれか。
  2. 計算量が O(n²) のプログラムで、データ数が1,000のときに処理時間が0.5秒だった。データ数を4,000にすると、処理時間はおよそ何秒になるか。
  3. 異なる100個の値が入った配列から、先頭から順に1つずつ比べる線形探索で目的の値を探す。目的の値は必ず配列の中にあり、どの位置にある確率も等しいとき、比較の回数の平均はいくらか。
  4. 配列と比べたときの連結リスト(各要素が次の要素の位置を指すポインタを持つリスト)の特徴として正しいものはどれか。
  5. 空のスタックに対して、push 1、push 2、pop、push 3、push 4、pop、pop の順に操作した。pop で取り出された値を順に並べたものはどれか。
  6. 空のキューに A、B、C の順に要素を入れ、1つ取り出し、D を入れて1つ取り出し、E を入れて1つ取り出した。取り出された要素を順に並べたものはどれか。
  7. 逆ポーランド記法(後置記法)で書かれた式「3 4 + 2 * 5 −」を、数が来たらスタックに積み、演算子が来たら2つの値を取り出して計算し、結果を積む方法で評価した。結果はいくらか。ここで、演算子の左側の値は先に積まれた方の値とする。
  8. ハッシュテーブル(ハッシュ表)における衝突(コリジョン)の説明として正しいものはどれか。
  9. 大きさ7のハッシュテーブル(位置0〜6)に、ハッシュ関数 h(k) = k mod 7 でキー10、17、24、3をこの順に格納する。衝突したときは、位置を1つずつ後ろへずらして(6の次は0)空いている位置を探す線形探査法を使う。キー3が格納される位置はどれか。
  10. ハッシュテーブルの衝突を処理する方法として、チェイン法(同じ位置の要素を連結リストでつなぐ)とオープンアドレス法(表の中の空いている別の位置を探す)を比べた説明として正しいものはどれか。負荷率は、格納した要素数を表の大きさで割った値とする。
  11. 配列の中央の要素と比べて、探す範囲を半分ずつに絞っていく二分探索を使うための前提条件として正しいものはどれか。
  12. 昇順に整列された異なる1,000個の値から二分探索で値を探す。1回の比較で「一致・より小さい・より大きい」が分かるものとすると、見つかる場合も見つからない場合も含めて、比較の回数は最大で何回か。
  13. 昇順に並んだ配列 a[0]〜a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60 から、二分探索で38を探す。探す範囲を下端 lo = 0、上端 hi = 9 から始め、中央の位置を (lo + hi) ÷ 2 の切り捨てとする。38と比べられる要素の値を順に並べたものはどれか。
  14. 配列 5, 3, 8, 1, 4 をバブルソートで昇順に並べる。先頭から隣どうしを比べ、左の方が大きければ交換する操作を末尾まで1回行った(1パス)後の配列はどれか。
  15. 配列 29, 10, 14, 37, 13 を選択ソート(未整列の部分から最小値を探し、未整列の部分の先頭と交換する)で昇順に並べる。この操作を2回行った後の配列はどれか。
  16. 要素数10の配列を挿入ソートで昇順に並べる。2番目以降の要素を順に取り出し、左隣から順に比べて、取り出した値以下の要素が見つかるか先頭に達するまで比べる。最初から昇順に並んでいる場合と、降順に並んでいる場合の比較の回数の組はどれか。
  17. 最悪の場合でも計算量が O(n log n) で、作業用の配列などの追加の記憶領域をほとんど使わずに並べ替えられるソートはどれか。
  18. (名前, 点数) のデータ (A, 80)、(B, 70)、(C, 80)、(D, 70) がこの順に並んでいる。点数の昇順に安定ソートで並べ替えたときの名前の順はどれか。
  19. クイックソートの計算量が O(n²) になる典型的な場合はどれか。
  20. マージソートで、昇順に整列済みの2つの列 1, 4, 7, 9 と 2, 3, 8, 10 を、先頭どうしを比べて小さい方を出力することを繰り返して1つの列にまとめる(マージする)。片方の列が空になったら、残りは比べずにそのまま出力する。比較の回数は何回か。
  21. 二分ヒープを、根を a[0] とする配列 a[0], a[1], a[2], … に、上の段から順に左から詰めて格納する。a[4] の子と親はどれか。
  22. 親の値が子の値以上になる最大ヒープを、根を a[0] とする配列で表している。ヒープ 50, 30, 40, 10, 20, 35 に45を追加する。末尾に置いてから、親より大きい間は親と交換する操作を行った後の配列はどれか。
  23. 二分探索木を中間順(通りがけ順。左の部分木、その節、右の部分木の順に訪れる)でたどったとき、訪れた節の値はどのように並ぶか。値はすべて異なるものとする。
  24. 空の二分探索木に、50, 30, 70, 20, 40, 60, 80 の順に値を挿入した。この木を後行順(帰りがけ順。左の部分木、右の部分木、その節の順に訪れる)でたどったときの順はどれか。
  25. 空の二分探索木に、1, 2, 3, …, 1000 の順に値を挿入した(つり合いをとる操作はしない)。この木で1000を探すとき、根から比べ始めて、見つかるまでに比べる節の数はいくつか。
  26. データベースやファイルシステムの索引に、二分探索木ではなくB木(B+木を含む)がよく使われる主な理由はどれか。
  27. 頂点が100万個、辺が300万本ほどの道路網のように、頂点の数に比べて辺の少ない(疎な)グラフをメモリに記憶する方法として適切なものはどれか。
  28. 辺に重みのないグラフで、出発点から各頂点までの最短の辺の数を求めたい。適した探索の方法と、そのとき使うデータ構造の組はどれか。
  29. 辺に向きのないグラフで、各頂点の隣の頂点が次のとおりである。A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E。頂点 A から再帰的な深さ優先探索を行う。隣の頂点はここに書いた順に調べ、まだ訪れていない頂点が見つかったらすぐにその頂点へ進む。頂点を訪れる順はどれか。
  30. 辺に向きのないグラフで、辺の重み(距離)が S−A: 4、S−B: 1、A−B: 2、A−C: 1、B−C: 5、C−T: 3、A−T: 6 である。ダイクストラ法で S から T までの最短経路を求めたとき、その経路と長さはどれか。
  31. ダイクストラ法で正しい最短経路が求められるための、グラフについての条件として正しいものはどれか。
  32. 作業 A〜E に「A は C より前」「B は C より前」「C は D より前」「B は E より前」「E は D より前」という順序の制約がある。すべての制約を満たす作業の順(トポロジカルソートの結果)はどれか。
  33. 関数 f(x, y) を「y が0なら x を返し、そうでなければ f(y, x mod y) を返す」と定義する。f(84, 36) を呼んだときの戻り値と、f が呼ばれる回数(最初の呼び出しを含む)の組はどれか。
  34. フィボナッチ数を求める関数 fib(n) を「n が1以下なら n を返し、そうでなければ fib(n−1) + fib(n−2) を返す」と再帰で定義した。fib(5) を呼んだとき、fib が呼ばれる回数は最初の呼び出しを含めて何回か。
  35. 1円、4円、6円の3種類の硬貨で8円を支払う。大きい硬貨から使えるだけ使う貪欲法で決めたときの枚数と、最少の枚数の関係として正しいものはどれか。
  36. 容量8のナップサックに、(重さ, 価値) が (2, 3)、(3, 4)、(4, 5)、(5, 6) の4つの品物から選んで入れる。各品物は1つずつしかなく、分割できない。重さの合計が8以下で、価値の合計の最大値はいくらか。
  37. 文字列の中からパターンを探すBM法(ボイヤー・ムーア法)の特徴として正しいものはどれか。
  38. 可変長配列で、容量が満杯のときに要素を追加すると、2倍の容量の領域を新たに確保して全要素をコピーする。容量1の空の配列に要素を1つずつ1,000個追加したとき、コピーされる要素の総数はいくつか。
  39. 要素数が多く、負荷率を0.5程度に保ったハッシュテーブルで、線形探査のオープンアドレス法が、チェイン法(連結リストでつなぐ方法)より速くなりやすい理由として最も適切なものはどれか。
  40. GPUのような並列処理の装置で並べ替えを行うときに、バイトニックソートのような、比較・交換の手順が決まったソート(ソーティングネットワーク)が使われることがある。その理由として正しいものはどれか。

データ構造とアルゴリズムの参考書を探す PR

Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。

コンピュータシステムのほかの分野