アルゴリズムとプログラミング

双方向のポインタをもつリスト構造のデータを表に示す。この表において新たな社員Gを社員Aと社員Kの間に追加する。追加後の表のポインタa～fの中で追加前と比べて値が変わるポインタだけを全て列記したものはどれか。

キーが小文字のアルファベット 1 文字（a、b、…、z のいずれか）であるデータを、 大きさが 10 のハッシュ表に格納する。ハッシュ関数として、アルファベットの ASCII コードを 10 進表記法で表したときの 1 の位の数を用いることにする。衝突が 起こるキーの組合せはどれか。ASCII コードでは、昇順に連続した 2 進数が、アルフ ァベット順にコードとして割り当てられている。

二分探索木（Binary Search Tree）に対して中順走査（in-order traversal）を行ったとき、ノードの値が取り出される順序はどれか。

図の木構造は2分探索木である。a〜gの値の大小関係として、適切なものはどれか。ここで、a〜gの値は重複しないものとする。

次の流れ図において、①→②→③→⑤→②→③→④→②→⑥ の順に実行させるために、①においてmとnに与えるべき初期値aとbの関係はどれか。ここで、a、bはともに正の整数とする。

オブジェクト指向プログラミングの特徴のうち、異なるクラスのオブジェクトを同 一のインタフェースで操作したときに、操作対象クラスに応じた異なる動作を可能に することを何と呼ぶか。

n個の要素を整列するとき、要素の初期配置に関わらず最悪の場合でも時間計算量がO(n log n)となることが保証されている整列アルゴリズムはどれか。

グラフの探索アルゴリズムである幅優先探索（BFS）と深さ優先探索（DFS）の説明として、最も適切なものはどれか。

n 個のデータをソートするとき、最悪計算量が O(n²) となるソートアルゴリズムはどれか。

ソート済みの n 個のデータに対して二分探索を行うときの、最悪計算量はどれか。

空のスタックに対して、push(1)、push(2)、push(3)、pop、push(4)、pop、pop の操作を順に行ったとき、最後に pop で取り出される値はどれか。

単方向連結リストの先頭にノードを1個挿入する操作の計算量として、適切なものはどれか。

ハッシュ法によるデータ管理において、異なるキーが同じハッシュ値を返す現象を何と呼ぶか。

完全二分木に要素を格納したヒープ（最大ヒープ）の性質として、正しいものはどれか。

次の再帰関数 f(n) を f(5) で呼び出したときの戻り値はどれか。 f(n): if n <= 1 then return 1 else return n * f(n - 1)

O 記法（ビッグオー）に関する記述として、最も適切なものはどれか。

重み付きグラフにおいて、ある始点から各頂点への最短経路を求めるアルゴリズムとして適切なものはどれか。ただし、辺の重みはすべて非負とする。

動的計画法（DP）に関する記述として、最も適切なものはどれか。

Boyer-Moore法（BM法）による文字列検索の特徴として正しいものはどれか。

ハッシュテーブルのオープンアドレス法における衝突解決の説明として正しいものはどれか。

B木（B-tree）の特徴として最も適切なものはどれか。

AVL木でノードを挿入した後に「左左型（LL型）」の不均衡が発生した場合の修正操作はどれか。

トポロジカルソートが適用できるグラフの条件として正しいものはどれか。

クラスカル法（Kruskal's Algorithm）による最小全域木の構築手順として正しいものはどれか。

ダイクストラ法（Dijkstra's Algorithm）の制約として正しいものはどれか。

配列の線形探索における「番兵法（Sentinel Method）」の主な目的はどれか。

次の疑似コードを実行したとき、最後に出力される値はどれか。 ``` var x = 10 function foo(): var x = 20 bar() print(x) function bar(): x = 30 foo() ``` ここで、`bar()` 内の `x = 30` はグローバル変数 `x` を変更し、`foo()` 内の `var x` はローカルスコープを生成するものとする。

次の疑似コードを実行した後、変数 a と b の値として正しいものはどれか。 ``` function swap_by_value(x, y): // 値渡し temp = x x = y y = temp function swap_by_ref(ref x, ref y): // 参照渡し temp = x x = y y = temp a = 1 b = 2 swap_by_ref(a, b) // 参照渡しで呼び出す // この時点での a, b は？ ```

次の再帰関数 f(n) を f(4) として呼び出したとき、返り値はどれか。 ``` function f(n): if n <= 1: return 1 return n * f(n - 1) ```

要素数 n の配列の先頭（インデックス0）に新しい要素を挿入するとき、既存要素の移動回数として正しいものはどれか。ただし配列のサイズは十分に確保されているものとする。

n 個の要素を持つ整列されていない配列から、線形探索（逐次探索）で特定の値を探すときの平均比較回数として最も適切なものはどれか。ただし探索する値は必ず配列中に存在するものとする。

C言語において、整数変数 x のアドレスが 0x1000 であり、x の値が 42 であるとする。ポインタ変数 p を `int *p = &x;` と宣言したとき、`*p` の値と `p` の値の組合せとして正しいものはどれか。

オブジェクト指向プログラミングにおける「カプセル化」の説明として最も適切なものはどれか。

次の疑似コードを実行したとき、出力される文字列の順序として正しいものはどれか。 ``` try: print("A") raise Exception("エラー") print("B") catch(e): print("C") return finally: print("D") ```

参照カウント法によるガベージコレクションの説明として正しいものはどれか。

空のスタックに対して次の順序で操作を行った。push(1), push(2), pop, push(3), push(4), pop, push(5), pop, pop。すべての操作後、スタックに残っている要素を底から順に並べたものはどれか。

空の二分探索木（BST）に対して、次の順序でキーを挿入した：50, 30, 70, 20, 40, 60, 80。この木を中間順（in-order）走査したときの出力として、正しいものはどれか。

ハッシュ表のサイズ m=7 とし、ハッシュ関数を h(k) = k mod 7 で定義する。キー集合 {15, 22, 8, 36, 25} を順に挿入したとき、衝突が発生する組み合わせとして正しいものはどれか。

シェルソートの特徴として最も正しいものはどれか。

ヒープソートの計算量として正しいものはどれか。

基数ソートの動作原理として最も正しいものはどれか。

線形探索と二分探索の使い分けとして最も適切なものはどれか。

グラフ探索における深さ優先探索(DFS)と幅優先探索(BFS)の特徴比較として正しいものはどれか。

A*アルゴリズムについての説明として最も正しいものはどれか。

挿入ソートで配列 [5, 3, 8, 1, 6] を昇順に整列する。2回の挿入操作（3を挿入、次に8を確認）を行った後の配列の状態として正しいものはどれか。

クイックソートで配列 [7, 2, 9, 4, 1, 5, 3] を昇順に整列する。先頭要素7をピボットとして1回の分割操作を行った後の状態として正しいものはどれか。

n個の要素をマージソートで整列するとき、マージ操作の回数として正しいものはどれか。8要素の場合は何回か。

二分探索木（BST）からノード30を削除する。ノード30は左の子ノードに20、右の子ノードに40を持つ。中順後継者（in-order successor）を使った削除後の状態として正しいものはどれか。

サイズ7のハッシュテーブル（インデックス0〜6）に線形探査法でキー15, 22, 8, 29を順番に挿入する。ハッシュ関数 h(k) = k mod 7 を使用する。挿入後のテーブルの状態として正しいものはどれか。

サイズ7のハッシュテーブルでダブルハッシュ法を使用する。h1(k)=k mod 7、h2(k)=1+(k mod 5)。スロット1がすでに占有されている状態でキー36を挿入するとき、最終的に格納されるインデックスはどれか。

5頂点のグラフでダイクストラ法を使い頂点Aから頂点Eへの最短路を求める。辺の重みは A-B=4, A-C=2, B-D=3, B-E=6, C-D=1, C-E=5, D-E=2 とする。A→Eの最短距離はどれか。

4頂点グラフにプリム法で最小全域木を求める。辺の重みは A-B=2, A-C=4, A-D=7, B-C=1, B-D=5, C-D=3 とする。最小全域木の総コストはどれか。

手続き型言語・関数型言語・論理型言語の特徴を比較した説明として、最も適切なものはどれか。

スクリプト言語の特徴として最も適切なものはどれか。

マークアップ言語に関する説明として最も適切なものはどれか。