当前位置：首页 > news >正文

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

news 2026/5/12 11:04:25

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

1-前言
2-线性代数-题目
3-线性代数-参考答案
4-数据结构-题目
【問題1】ハッシュ法と衝突処理
【問題2】連結リストの実装と操作
【問題3】再帰処理と連結リスト
【問題4】ソートアルゴリズムと安定性
5-数据结构-参考答案
問題1：ハッシュ法
- （1）O(1)
- - 判定
  - 模范答案（保持即可）
- （2）O(n)
- - 判定
  - 模范答案
- （3）理由说明
- - 你的原答案（问题点）
  - ⭐ 满分标准答案（直接背）
問題2：連結リストとキュー
- （1）O(n)
- - 判定
  - 模范答案
- （2）O(1)
- - 判定
- （3）理由说明
- - 你的原答案（问题点）
  - ⭐ 满分标准答案
問題3：再帰と連結リスト
- （1）処理内容说明
- - 你的原答案（严重扣分点）
  - ⭐ 满分标准答案（非常重要）
- （2）O(n + m)
- - 判定
  - 模范答案
問題4：ソート
- （1）安定性的定义
- - 你的原答案（❌ 错）
  - ⭐ 正确答案（必背）
- （2）O(n²) & 安定
- - 判定
  - 表达升级版
- （3）O(n log n) & 安定
- - 判定
  - 模范答案
🎯 总评（立命馆视角）
6-总结

1-前言

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

2-线性代数-题目

3-线性代数-参考答案

4-数据结构-题目

【問題1】ハッシュ法と衝突処理

要素数 (n) 個のデータ (x_1, x_2, \ldots, x_n) を管理するために，
配列サイズ (m) のハッシュ表を用い，
ハッシュ関数
[
h(x) = x \bmod m
]
によってデータを格納するものとする。

衝突処理としてチェイン法を用いる場合について，次の問いに答えよ。

（1）ハッシュ関数に衝突が発生していない場合の探索に要する最悪時間計算量を，
要素数 (n) を用いてオーダー記法で答えよ。

（2）すべての要素が同一のハッシュ値を取る場合の探索に要する最悪時間計算量を，
要素数 (n) を用いてオーダー記法で答えよ。

（3）上記（2）の場合において，ハッシュ法が探索アルゴリズムとして有効であると言えない理由を簡潔に説明せよ。

※ 陷阱：**「平均」ではなく「最悪」**を正しく答えられるか

【問題2】連結リストの実装と操作

単方向連結リストを用いて，
要素 (x_1, x_2, \ldots, x_n) を格納する線形リストを実装する。

以下の 2 つの実装方法を考える。

実装方法A：先頭要素へのポインタのみを保持する。
実装方法B：先頭要素および末尾要素へのポインタを保持する。

次の問いに答えよ。

（1）実装方法Aにおいて，末尾に新しい要素を追加する操作の最悪時間計算量を，
要素数 (n) を用いてオーダー記法で答えよ。

（2）実装方法Bにおいて，末尾に新しい要素を追加する操作の最悪時間計算量を，
要素数 (n) を用いてオーダー記法で答えよ。

（3）実装方法Bが，キューの実装に適している理由を簡潔に説明せよ。

※ 陷阱：「連結リストの種類」ではなく「操作コスト」を問う

【問題3】再帰処理と連結リスト

先頭要素へのポインタをそれぞれlist1，list2として保持する
2 つの単方向連結リストがある。

両リストは，要素の値が降順に整列されているものとする。

次の擬似コードが与えられた。

function merge(list1, list2) { if (list1 == NULL) return list2 if (list2 == NULL) return list1 if (list1.val >= list2.val) { list1.next = merge(list1.next, list2) return list1 } else { list2.next = merge(list1, list2.next) return list2 } }

（1）この関数の処理内容を簡潔に説明せよ。

（2）list1の要素数を (n)，list2の要素数を (m) としたとき，
この関数の最悪時間計算量をオーダー記法で答えよ。