循環配列キューは、取り出し後の要素移動をどう避けるか？

先頭・末尾の添字を容量で剰余を取りながら循環させる。取り出しは先頭添字を進めるため、他の要素を動かさず空き領域を再利用できる。

二分木の先行順・中間順・後行順の走査順序は？

先行順：ノード → 左 → 右。中間順：左 → ノード → 右。後行順：左 → 右 → ノード。

n 個の要素からボトムアップでヒープを構築するコストは？

O(n)。大半のノードは葉に近く、下方への調整が少ない。ノードの高さ別に仕事量を足すと全体は線形になる。

長さ n、添字が0始まりのヒープ配列で、ノード i の親と子はどこか？

親：i>0 のとき ⌊(i−1)/2⌋。子：2i+1 と 2i+2。ただし添字が n 未満の場合のみ。添字0には親がない。

経路圧縮とランクによる併合を使う union/find の償却コストは？

1操作あたり O(α(n))。α は逆アッカーマン関数、n は要素数。初期化は O(n)。これは操作列に対する評価であり、各呼び出しの最悪コストが定数という意味ではない。

表の検索用ハッシュ関数に必要な性質は？

決定的で、想定するキーをよく分散させること。固定長キーの計算は O(1) にできるが、新しい L 文字の文字列のハッシュ計算は通常 O(L)。

分離連鎖法はハッシュ衝突をどう解決するか？

各バケットが、その添字に対応する項目の集合を保持する。連結リストを使うことが多い。同じバケットの異なるキーも別々の項目として残る。

異なるキーを持つ BST を中間順に走査すると何が得られるか？

すべてのキーが厳密な昇順で得られる。n ノードを O(n) 時間で訪問する。

ハッシュ表の負荷率とは何か。また、なぜサイズを変更することがあるか？

α = n/m。n は項目数、m はバケット数またはスロット数。実装の閾値を超えると拡大・再ハッシュする場合がある。0.75 は共通の規則ではない。

双方向連結リストで、与えられたノードを O(1) で削除できるのはなぜか？

前後へのリンクで隣接ノードを直接つなぎ直せる。必要なら先頭・末尾を更新する。直前のノードを探す必要はない。

互いに素な集合のデータ構造で find と union は何をするか？

find(x) は x の属する集合の代表を返す。union(x,y) は異なる集合なら併合する。すでに同じ集合なら分割は変わらない。

キューの取り出し規則と典型的な操作コストは？

FIFO：末尾に追加し先頭から取り出す。先頭・末尾リンクや固定容量のリングバッファなら両方 O(1)。配列要素をずらす実装では取り出しが O(n)。

経路圧縮・ランクによる併合・サイズによる併合はどう違うか？

経路圧縮は訪問したノードを根に付け替える。ランク併合は低ランクの根を高ランクの根の下へ、サイズ併合は小集合を大集合の下へつなぐ。ランクは現在の高さとは限らない。

二分最小ヒープを定義する2つの性質は？

完全二分木であり、親のキーは子のキー以下である。したがって根には最小値がある。

AVL 挿入後の左・右型の不均衡はどう直すか？

まず左の子を左回転し、次に不均衡なノードを右回転する。

固定長配列の添字アクセスが O(1) なのはなぜか？

同じ大きさの領域が連続しており、アドレス(i) = 先頭アドレス + i·要素領域の大きさで求まる。アドレス計算が定数時間であると仮定する。

容量を倍増させる動的配列で、末尾追加の償却コストはいくらか？

1回あたり O(1)。サイズ変更1回は O(n) になり得るが、空の配列から n 回追加する合計は O(n)。

二分ヒープの挿入・根の削除・根の参照にかかるコストは？

配列のサイズ変更が不要なら、それぞれ O(log n)、O(log n)、O(1)。サイズ変更は O(n) になり得る。

BST の検索・挿入・削除は高さ h にどう依存するか？

O(h) かかる。平衡木なら h = O(log n)、鎖状なら h = O(n)。期待 O(log n) にはランダムな挿入順などの仮定が必要。

n → ∞ のとき、増加の遅い順に並べよ：n!、n、1、n²、log n、2ⁿ、n log n。

漸近的には 1 < log n < n < n log n < n² < 2ⁿ < n!。

トライとは何か。L 文字のキーの検索が O(L) になる条件は？

文字の経路にキーを格納する接頭辞木で、完全なキーの終端を印で示す。次の文字への各遷移が O(1) なら、検索は O(L)。

AVL 木の平衡条件は？

各ノードで高さ(左) − 高さ(右) ∈ {−1, 0, 1}。BST の順序不変条件も満たす。

単方向連結リストと動的配列の先頭挿入・添字アクセスを比較せよ。

リスト：先頭挿入 O(1)、添字アクセス O(n)。配列：先頭挿入 O(n)、添字アクセス O(1)。配列の先頭挿入では要素をずらす。

二分木のレベル順走査はどう行うか？

FIFO キューで深さごとに訪問する。左の子を右の子より先にキューへ追加すると、各段で左から右の順になる。

非負の関数 f と g について、f(n) ∈ O(g(n)) は何を意味するか？

ある定数 c > 0 と n₀ ≥ 0 が存在し、すべての n ≥ n₀ で f(n) ≤ c·g(n) が成り立つ。

挿入だけを許すブルームフィルタは、どのような答えを返すか？

陰性なら未挿入、陽性なら挿入済みの可能性がある。ハッシュでビット配列のビットを立てるため、偽陽性はあり得るが、状態が損なわれていなければ偽陰性はない。

キーがすべて異なる二分探索木（BST）の順序不変条件は？

各ノードについて、左部分木のキーはすべて小さく、右部分木のキーはすべて大きい。この規則が再帰的に成り立つ。

赤黒 BST の平衡を保つ色の規則は？

ノードは赤か黒。根と NIL 葉は黒。赤いノードに赤い子はない。各ノードからその子孫の NIL 葉へのすべての経路で黒いノード数が等しい。これにより高さは O(log n) に抑えられる。

オープンアドレス法の線形探査と二次探査はどう違うか？

項目は配列内に置く。表の大きさ m、初期添字 h に対し、それぞれ (h+i) mod m、(h+c₁i+c₂i²) mod m を調べる。二次探査には適切なパラメータが必要。

分離連鎖法のハッシュ表における期待コストと最悪コストは？

負荷が有界で、ハッシュがよく分散し、キー操作が定数時間なら検索・削除の期待値は O(1)。容量を幾何的に増やす挿入は期待償却 O(1)。n 個の衝突キーが連鎖すると O(n) になり得る。

O、Ω、Θ はどう違うか？

それぞれ漸近的な上界、下界、タイトな上下界を表す。対象は指定されたコスト関数であり、O 自体が最悪ケースを意味するわけではない。

スタックはどう動作し、操作が O(1) になるのはいつか？

LIFO：最後に入れた要素を最初に取り出す。連結リストの先頭なら push・pop・先頭の参照は O(1)。配列のサイズ変更を伴う1回の push は O(n) になり得る。

データ構造・計算量解析（Big-O記法）・基本アルゴリズム

基礎的なプログラミング知識を前提とする大学学部レベルの復習。配列、リスト、ハッシュ、木、ヒープ、トライ、Union–Find、ブルームフィルタ、計算量を扱う32枚。

Level: basic
Languages: ja → ja
Cards: 32
Markdown: データ構造・計算量解析（Big-O記法）・基本アルゴリズム (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	循環配列キューは、取り出し後の要素移動をどう避けるか？	先頭・末尾の添字を容量で剰余を取りながら循環させる。取り出しは先頭添字を進めるため、他の要素を動かさず空き領域を再利用できる。
2	二分木の先行順・中間順・後行順の走査順序は？	先行順：ノード → 左 → 右。中間順：左 → ノード → 右。後行順：左 → 右 → ノード。
3	n 個の要素からボトムアップでヒープを構築するコストは？	O(n)。大半のノードは葉に近く、下方への調整が少ない。ノードの高さ別に仕事量を足すと全体は線形になる。
4	長さ n、添字が0始まりのヒープ配列で、ノード i の親と子はどこか？	親：i>0 のとき ⌊(i−1)/2⌋。子：2i+1 と 2i+2。ただし添字が n 未満の場合のみ。添字0には親がない。
5	経路圧縮とランクによる併合を使う union/find の償却コストは？	1操作あたり O(α(n))。α は逆アッカーマン関数、n は要素数。初期化は O(n)。これは操作列に対する評価であり、各呼び出しの最悪コストが定数という意味ではない。
6	表の検索用ハッシュ関数に必要な性質は？	決定的で、想定するキーをよく分散させること。固定長キーの計算は O(1) にできるが、新しい L 文字の文字列のハッシュ計算は通常 O(L)。
7	分離連鎖法はハッシュ衝突をどう解決するか？	各バケットが、その添字に対応する項目の集合を保持する。連結リストを使うことが多い。同じバケットの異なるキーも別々の項目として残る。
8	異なるキーを持つ BST を中間順に走査すると何が得られるか？	すべてのキーが厳密な昇順で得られる。n ノードを O(n) 時間で訪問する。
9	ハッシュ表の負荷率とは何か。また、なぜサイズを変更することがあるか？	α = n/m。n は項目数、m はバケット数またはスロット数。実装の閾値を超えると拡大・再ハッシュする場合がある。0.75 は共通の規則ではない。
10	双方向連結リストで、与えられたノードを O(1) で削除できるのはなぜか？	前後へのリンクで隣接ノードを直接つなぎ直せる。必要なら先頭・末尾を更新する。直前のノードを探す必要はない。
11	互いに素な集合のデータ構造で find と union は何をするか？	find(x) は x の属する集合の代表を返す。union(x,y) は異なる集合なら併合する。すでに同じ集合なら分割は変わらない。
12	キューの取り出し規則と典型的な操作コストは？	FIFO：末尾に追加し先頭から取り出す。先頭・末尾リンクや固定容量のリングバッファなら両方 O(1)。配列要素をずらす実装では取り出しが O(n)。
13	経路圧縮・ランクによる併合・サイズによる併合はどう違うか？	経路圧縮は訪問したノードを根に付け替える。ランク併合は低ランクの根を高ランクの根の下へ、サイズ併合は小集合を大集合の下へつなぐ。ランクは現在の高さとは限らない。
14	二分最小ヒープを定義する2つの性質は？	完全二分木であり、親のキーは子のキー以下である。したがって根には最小値がある。
15	AVL 挿入後の左・右型の不均衡はどう直すか？	まず左の子を左回転し、次に不均衡なノードを右回転する。
16	固定長配列の添字アクセスが O(1) なのはなぜか？	同じ大きさの領域が連続しており、アドレス(i) = 先頭アドレス + i·要素領域の大きさで求まる。アドレス計算が定数時間であると仮定する。
17	容量を倍増させる動的配列で、末尾追加の償却コストはいくらか？	1回あたり O(1)。サイズ変更1回は O(n) になり得るが、空の配列から n 回追加する合計は O(n)。
18	二分ヒープの挿入・根の削除・根の参照にかかるコストは？	配列のサイズ変更が不要なら、それぞれ O(log n)、O(log n)、O(1)。サイズ変更は O(n) になり得る。
19	BST の検索・挿入・削除は高さ h にどう依存するか？	O(h) かかる。平衡木なら h = O(log n)、鎖状なら h = O(n)。期待 O(log n) にはランダムな挿入順などの仮定が必要。
20	n → ∞ のとき、増加の遅い順に並べよ：n!、n、1、n²、log n、2ⁿ、n log n。	漸近的には 1 < log n < n < n log n < n² < 2ⁿ < n!。
21	トライとは何か。L 文字のキーの検索が O(L) になる条件は？	文字の経路にキーを格納する接頭辞木で、完全なキーの終端を印で示す。次の文字への各遷移が O(1) なら、検索は O(L)。
22	AVL 木の平衡条件は？	各ノードで高さ(左) − 高さ(右) ∈ {−1, 0, 1}。BST の順序不変条件も満たす。
23	単方向連結リストと動的配列の先頭挿入・添字アクセスを比較せよ。	リスト：先頭挿入 O(1)、添字アクセス O(n)。配列：先頭挿入 O(n)、添字アクセス O(1)。配列の先頭挿入では要素をずらす。
24	二分木のレベル順走査はどう行うか？	FIFO キューで深さごとに訪問する。左の子を右の子より先にキューへ追加すると、各段で左から右の順になる。
25	非負の関数 f と g について、f(n) ∈ O(g(n)) は何を意味するか？	ある定数 c > 0 と n₀ ≥ 0 が存在し、すべての n ≥ n₀ で f(n) ≤ c·g(n) が成り立つ。
26	挿入だけを許すブルームフィルタは、どのような答えを返すか？	陰性なら未挿入、陽性なら挿入済みの可能性がある。ハッシュでビット配列のビットを立てるため、偽陽性はあり得るが、状態が損なわれていなければ偽陰性はない。
27	キーがすべて異なる二分探索木（BST）の順序不変条件は？	各ノードについて、左部分木のキーはすべて小さく、右部分木のキーはすべて大きい。この規則が再帰的に成り立つ。
28	赤黒 BST の平衡を保つ色の規則は？	ノードは赤か黒。根と NIL 葉は黒。赤いノードに赤い子はない。各ノードからその子孫の NIL 葉へのすべての経路で黒いノード数が等しい。これにより高さは O(log n) に抑えられる。
29	オープンアドレス法の線形探査と二次探査はどう違うか？	項目は配列内に置く。表の大きさ m、初期添字 h に対し、それぞれ (h+i) mod m、(h+c₁i+c₂i²) mod m を調べる。二次探査には適切なパラメータが必要。
30	分離連鎖法のハッシュ表における期待コストと最悪コストは？	負荷が有界で、ハッシュがよく分散し、キー操作が定数時間なら検索・削除の期待値は O(1)。容量を幾何的に増やす挿入は期待償却 O(1)。n 個の衝突キーが連鎖すると O(n) になり得る。
31	O、Ω、Θ はどう違うか？	それぞれ漸近的な上界、下界、タイトな上下界を表す。対象は指定されたコスト関数であり、O 自体が最悪ケースを意味するわけではない。
32	スタックはどう動作し、操作が O(1) になるのはいつか？	LIFO：最後に入れた要素を最初に取り出す。連結リストの先頭なら push・pop・先頭の参照は O(1)。配列のサイズ変更を伴う1回の push は O(n) になり得る。