大学院-筆記試験練習：线性代数和数据结构（１３）
- 1-前言
- 2-线性代数-题目
- 【模擬①】問1（平面・直線・距離：符号ミス誘導）
- 【予測①】問3（パラメータ付き：階数・解の個数の分岐が罠）
- 3-线性代数-参考答案
- 4-数据结构-题目
- 【問題１：本番シミュレーション問題（データ構造）】
- 【問題２：予測問題（アルゴリズム＋計算量）】
- 5-数据结构-参考答案
- 問題１（連結リスト削除）答案：**「3 2」**
- 問題２(1)（スタック最終状態）答案：**「4 3 2」**
- 問題２(2)（最悪時間計算量）：**O(n log n)**
- 6-总结
1-前言
为了升到自己目标的大学院，所作的努力和学习，这里是线性代数和数据结构部分。
2-线性代数-题目
【模擬①】問1（平面・直線・距離：符号ミス誘導）
3点 (P_1(1,3,5),\ P_2(-3,0,1),\ P_3(6,2,-4)) を通る平面を (\pi) とする。
平面 (\pi) の方程式を
[
ax+by+cz+d=0
]
の形で求めよ（ただし (a,b,c,d) は実数）。点 (A(7,1,-3)) を通り、平面 (\pi) に垂直な直線 (\ell) の方程式を求めよ。
直線 (\ell) と平面 (\pi) の交点を (Q) とするとき、線分 (AQ) の長さを求めよ。
（※距離公式の適用で符号と平方根の整理に注意。）
【予測①】問3（パラメータ付き：階数・解の個数の分岐が罠）
実数 (t) を含む連立一次方程式
[
\begin{cases}
x+y+z=1
2x+ty+2z=2
x+2y+tz=1
\end{cases}
]
について、次の問いに答えよ。
係数行列の階数 (\operatorname{rank}) を (t) により場合分けして求めよ。
上の連立方程式が
(i) 一意解をもつ、(ii) 解を無数にもつ、(iii) 解をもたない
それぞれの場合の (t) の条件を求めよ。(ii) の場合（解が無数にある場合）について、一般解を具体的に表せ。
（※「階数＝未知数の個数」などの判定で、拡大係数行列を見落とすのが典型的な罠。）
3-线性代数-参考答案
4-数据结构-题目
了解。下面严格按立命馆大学「データ構造とアルゴリズム」本番出题风格给2 道题，满足给出的全部条件：
- ✅无选项
- ✅难度 = 本番难度
- ✅描述方式 = 真题口吻（日语）
- ✅包含立命馆常见陷阱
- ✅1 道模拟题 + 1 道预测题
- ❗ 不给答案（符合真题）
【問題１：本番シミュレーション問題（データ構造）】
以下の条件を満たす単方向連結リストがある。
各ノードは整数値keyと，次ノードへのポインタnextを持つものとする。
先頭ノードへの参照はheadにより与えられる。
次の擬似コードremoveGreaterThanXは，
連結リスト中の値が x より大きい要素をすべて削除する処理を表す。
function removeGreaterThanX(Node head, int x): Node p = head Node prev = null while p != null: if p.key > x then if prev == null then head = p.next else prev.next = p.next end if else prev = p end if p = p.next end while return head連結リストに
先頭から順に{ 5, 3, 8, 2, 7 }が格納されており，x = 4として上記関数を実行したとき，
関数終了後の連結リストに格納されている要素を先頭から順にすべて記述せよ。
なお，本処理において
- メモリ解放は正しく行われているものとする
- ポインタの参照ミスによる実行時エラーは起こらないものとする
prevが更新されるタイミング- 削除した直後でも
p = p.nextが必ず実行される点 - 先頭要素が削除される場合の
headの変化
【問題２：予測問題（アルゴリズム＋計算量）】
以下の擬似コードは，
スタックを用いて配列の要素を処理するアルゴリズムを表している。
function processArray(A[0 … n-1]): Stack S for i = 0 to n-1 do while S is not empty and S.top() > A[i] do pop(S) end while push(S, A[i]) end for(1)
配列
A = { 4, 6, 3, 5, 2 }
を入力として上記アルゴリズムを実行したとき，
最終的にスタック S に格納されている要素を，下から上の順にすべて記述せよ。
(2)
本アルゴリズムの最悪時間計算量を，
配列の要素数nを用いてオーダー記法で答えよ。
5-数据结构-参考答案
問題１（連結リスト削除）答案：「3 2」
结论：不对（少了一个元素）。
关键点：这题的代码有个典型陷阱——删除节点后没有把prev往前推进，但p仍然会p = p.next，因此会出现“连续删除时 prev 仍指向被删节点”的效应。
我们按顺序跑（A = {5,3,8,2,7}, x=4）：
- 初始：
head=5,prev=null,p=5
p=5 >4丢掉头：head=3，prev仍null，然后p=p.next→p=3p=3 <=4：prev=3，p=p.next→p=8p=8 >4：prev.next = p.next→3.next=2，prev仍是3，p=p.next→p=2p=2 <=4：prev=2，p=p.next→p=7p=7 >4：prev.next = p.next→2.next=null，结束
最终链表：3 → 2
✅問題１：判定为正确。
問題２(1)（スタック最終状態）答案：「4 3 2」
✅ 这个是正确。
快速验证（A={4,6,3,5,2}）：
- push 4 → [4]
- 6：top 4>6? 否 → push → [4,6]
- 3：top 6>3 pop → [4]；top 4>3 pop → []；push 3 → [3]
- 5：top 3>5? 否 → push → [3,5]
- 2：top 5>2 pop → [3]；top 3>2 pop → []；push 2 → [2]
最终从下到上：2—— 等等，这里发现写的4 3 2似乎不一致。
我再严谨重算一遍（每步写清楚）：
- i=0, A[0]=4: S空 → push 4 → S=[4]
- i=1, A[1]=6: top=4 >6? 否 → push 6 → S=[4,6]
- i=2, A[2]=3: top=6 >3? 是 pop → S=[4]；top=4 >3? 是 pop → S=[]；push 3 → S=[3]
- i=3, A[3]=5: top=3 >5? 否 → push 5 → S=[3,5]
- i=4, A[4]=2: top=5 >2? 是 pop → S=[3]；top=3 >2? 是 pop → S=[]；push 2 → S=[2]
最终：[2]
✅ 正确答案应写：2（下から上も同じ 2）
所以：
- ❌「4 3 2」不对（像是把“单调栈过程”记成“保留递减序列”，但实际是保留“递增栈”的结果）
問題２(2)（最悪時間計算量）：O(n log n)
❌ 这题最常见陷阱：看到 while 就乱猜，或看到栈就联想到 nlogn。
正确结论：最悪でも O(n)
理由
- 各要素は高々1回 pushされる
- 各要素は高々1回 popされる
→ 全操作回数は高々 2n 程度 →O(n)
6-总结
训练成长。！！
