大学院-筆記試験練習：线性代数和数据结构（24）
- 1-前言
- 2-线性代数-题目
- 3-线性代数-参考答案
- 4-数据结构-题目
- 【模擬問題1】
- 問題1：スタックとキューの操作系列
- 問1
- 問2
- 【模擬問題2】
- 問題2：グラフの表現と探索の性質（BFS / DFS）
- 問1
- 問2
- 問3
- ↓ ここから予想問題（過去問と被らない方向）↓
- 【予想問題1】
- 問題3：ヒープ構造と部分順序
- 問1
- 問2
- 問3
- 【予想問題2】
- 問題4：連結リストの構造と操作
- 問1
- 問2
- 問3
- 5-数据结构-参考答案
- 【模擬問題1】満点答案
- 問1：操作終了後のスタックとキュー
- 操作の追跡
- 最終結果
- 問2：構造的性質の影響
- 【模擬問題2】満点答案
- 問1：グラフの表現
- 隣接リスト
- 隣接行列
- 問2：BFS の探索順序
- 問3：DFS の探索順序と違い
- DFS の探索順序
- BFS との違い
- 【予想問題1】満点答案
- 問1：最大ヒープの構築結果
- 問2：最大値削除後
- 問3：二分探索木でない理由
- 【予想問題2】満点答案
- 問1：25 の挿入
- 問2：30 の削除後
- 問3：配列との比較
- 利点
- 欠点
- 6-总结
1-前言
为了升到自己目标的大学院，所作的努力和学习，这里是线性代数和数据结构部分。
2-线性代数-题目
3-线性代数-参考答案
4-数据结构-题目
【模擬問題1】
問題1：スタックとキューの操作系列
次の操作列を、空のデータ構造から開始して実行する。
- スタック S
- キュー Q
操作列は以下の通りである。
- S に 3 を push
- S に 7 を push
- Q に 5 を enqueue
- S から pop し、その値を Q に enqueue
- Q に 9 を enqueue
- Q から dequeue し、その値を S に push
- 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
このグラフを
- 隣接リスト
- 隣接行列
の両方で表現せよ。
問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
隣接行列
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 | 0 | 0 |
| B | 1 | 0 | 0 | 1 | 0 | 0 |
| C | 1 | 0 | 0 | 1 | 1 | 0 |
| D | 0 | 1 | 1 | 0 | 0 | 1 |
| E | 0 | 0 | 1 | 0 | 0 | 0 |
| F | 0 | 0 | 0 | 1 | 0 | 0 |
問2：BFS の探索順序
開始点：A
隣接頂点はアルファベット順
A → B → C → D → E → F問3：DFS の探索順序と違い
DFS の探索順序
A → B → D → C → E → FBFS との違い
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-总结
训练成长。！！
