【大学院-筆記試験練習：线性代数和数据结构（24）】

1-前言

为了升到自己目标的大学院，所作的努力和学习，这里是线性代数和数据结构部分。

2-线性代数-题目

3-线性代数-参考答案

4-数据结构-题目

【模擬問題1】

問題1：スタックとキューの操作系列

次の操作列を、空のデータ構造から開始して実行する。

• スタック S
• キュー Q

操作列は以下の通りである。

1. S に 3 を push
2. S に 7 を push
3. Q に 5 を enqueue
4. S から pop し、その値を Q に enqueue
5. Q に 9 を enqueue
6. Q から dequeue し、その値を S に push
7. S に 4 を push

問1

すべての操作終了後の

• スタック S の内容
• キュー Q の内容

を要素の順序が分かる形で示せ。

問2

操作 4 と操作 6 において、
「スタック」と「キュー」の構造的性質（FIFO / LIFO）が
結果にどのように影響しているかを、簡潔に説明せよ。

【模擬問題2】

問題2：グラフの表現と探索の性質（BFS / DFS）

頂点集合 {A, B, C, D, E, F} からなる無向グラフ Gがあり、
辺集合は以下の通りである。

• (A, B), (A, C), (B, D), (C, D), (C, E), (D, F)

問1

このグラフを

1. 隣接リスト
2. 隣接行列

の両方で表現せよ。

問2

頂点 A を開始点として幅優先探索（BFS）を行ったときの
探索順序を示せ。ただし、

• 隣接頂点はアルファベット順に探索するものとする。

問3

同じ条件で深さ優先探索（DFS）を行ったときの
探索順序を示し、
BFS との違いを探索木の性質の観点から説明せよ。

↓ ここから予想問題（過去問と被らない方向）↓

【予想問題1】

問題3：ヒープ構造と部分順序

次の整数列を、空の最大ヒープに
与えられた順に挿入する。

8, 3, 10, 1, 6, 14, 4

問1

すべての挿入が完了した後の
ヒープを完全二分木として図示せよ。

問2

そのヒープから最大要素を 1 回削除したときの
ヒープの状態を図示せよ。

問3

ヒープが二分探索木ではない理由を、
「順序の制約」という観点から説明せよ。

【予想問題2】

問題4：連結リストの構造と操作

次の単方向連結リストが与えられている。

10 → 20 → 30 → 40

問1

値 25 を20 と 30 の間に挿入するために必要な
ポインタ操作を、図を用いて説明せよ。

問2

値 30 を削除した後の連結リストの状態を示せ。

問3

この連結リストにおいて、

• 配列と比較した場合の利点
• 配列と比較した場合の欠点

をそれぞれ1つずつ述べよ。

5-数据结构-参考答案

【模擬問題1】満点答案

問1：操作終了後のスタックとキュー

操作の追跡

• 操作1：S = [3]

• 操作2：S = [3, 7]

• 操作3：Q = [5]

• 操作4：S から 7 を pop → Q に enqueue

  • S = [3]
  • Q = [5, 7]

• 操作5：Q = [5, 7, 9]

• 操作6：Q から 5 を dequeue → S に push

  • Q = [7, 9]
  • S = [3, 5]

• 操作7：S = [3, 5, 4]

最終結果

• スタック S（下 → 上）：

  3, 5, 4

• キュー Q（先頭 → 末尾）：

  7, 9

問2：構造的性質の影響

スタックはLIFO（後入れ先出し）構造であるため、
最後に push された要素が最初に取り出される。

一方、キューはFIFO（先入れ先出し）構造であるため、
最初に enqueue された要素が最初に取り出される。

操作4と操作6では、
これらの性質により要素の移動順序が決定され、
最終的なデータ配置に影響を与えている。

【模擬問題2】満点答案

問1：グラフの表現

隣接リスト

• A：B, C
• B：A, D
• C：A, D, E
• D：B, C, F
• E：C
• F：D

隣接行列

問2：BFS の探索順序

開始点：A
隣接頂点はアルファベット順

A → B → C → D → E → F

問3：DFS の探索順序と違い

DFS の探索順序

A → B → D → C → E → F

BFS との違い

BFS は距離の近い頂点から順に探索するため、
開始点からの最短距離を保つ探索木が得られる。

一方、DFS は可能な限り深く探索してから戻るため、
探索木の形状が深く偏る特徴を持つ。

【予想問題1】満点答案

問1：最大ヒープの構築結果

挿入後の完全二分木：

14 / \ 6 10 / \ / 1 3 8 / 4

（※ 親ノードは常に子ノード以上）

問2：最大値削除後

最大要素 14 を削除し、再構成すると：

10 / \ 6 8 / \ / 1 3 4

問3：二分探索木でない理由

ヒープは

• 親ノードが子ノード以上（または以下）
  という部分順序のみを満たす。

左部分木 < 親 < 右部分木
という全順序条件を持たないため、
二分探索木ではない。

【予想問題2】満点答案

問1：25 の挿入

ノード 20 の next を 25 に変更し、
25 の next を 30 に設定する。

10 → 20 → 25 → 30 → 40

問2：30 の削除後

10 → 20 → 25 → 40

問3：配列との比較

利点

連結リストは、
要素の挿入・削除時に
他の要素を移動させる必要がない。

欠点

任意位置の要素に
直接アクセスできず、
先頭から順に探索する必要がある。

6-总结

训练成长。！！