令和 6 年度

大学院博士 (前期) 課程入学者選抜学力試験

B 日程
情報アーキテクチャ・高度 ICT 領域

専 門 科 目［90 分］
注 意 事 項

1．試験開始の合図があるまで，この問題冊子を開かないでください．
2．出題科目およびページは，下表のとおりです．問題ごとに配点が記されています．
出 題 科 目

ペ ー ジ

問題数

基礎数

学

12問

情報

数

学

21問

アルゴリズムとデータ構造

3〜 41問注意

左の 3 科目すべてを解答してください．

3．解答冊子の表紙の所定欄に氏名と受験番号をはっきりと記入してください．
4．解答用紙は 3 科目分がそれぞれ綴じてあります．解答に用いなかった解答用紙も含め，すべての解答用紙 1 枚目の所定欄に受験番号をはっきりと記入してください．

5．解答用紙には，科目名，問題番号（I，II など），問いの番号（問 1 など）が記入されているので，該当する科目の解答用紙を用いてください．

6．計算／下書き用紙 3 枚が解答用紙と一緒にあります．
7．試験中に問題冊子の印刷不明瞭，ページの落丁・乱丁および解答用紙の汚れ等に気がついた場合は，静かに手を挙げて監督員に知らせてください．

8．試験終了後，監督員の指示に従って，解答冊子の表紙と 3 科目分の解答用紙を袋に入れてください．3 科目分の解答用紙が入っていない場合，入っていない科目の点数は 0 点となります．

9．問題冊子と計算／下書き用紙は持ち帰ってください．

基 礎 数 学I 行列



 1

 2


−1

1−311 −1 
2−50aA= −1 −1 −2 −2 に対し，線形写像 f : R4 → R4 を f (x) = Ax (x ∈ R4 ) により定める．以下の問いに答えよ．ただし，a は実数とする．（配点 25 点）
問 1 行列 A の階数 rank A を求めよ．
問 2 線形写像 f の核 Ker(f ) の基底を求めよ．
問 3 線形写像 f の像 Im(f ) の基底を求めよ．

II 以下の問いに答えよ．（配点 25 点）
問 1 t は t=
\ −1 かつ t =\とするとき，(12) 13を満たす実数とする．x =dyを t を用いて表せ．
dx3t3t2,y=
1 + t3
1 + t3

問 2 次の極限を求めよ．

1limn→∞ n(1222n2++···+n 2 + 12n2 + 22n2 + n2

基礎数学の問題は，このページで終りである．
— 1 —)

情 報 数 学

I n 個 (n ≥ 1) の要素からなる節点集合 Vn ={vi |i は n 以下の自然数 } からなる完全無向グラフを Kn とする．以下の問いに答えよ．（配点 50 点）
問 1 K5 を示せ．
問 2 Kn の全ての節点を通る順路が何通りあるか，n を用いて表せ．ただし，逆向きの順路は異なる順路とみなす．
問 3 Kn の全ての節点を v1 , v2 , · · · , vn の順に白または黒で彩色する．ただし，同じ色を 3 回以上連続して用いることはできないとする．例えば，v1 , v2 を白で彩色した場合，v3 を白で彩色することはできない．v1 を白で彩色したとき，n個の節点の異なる彩色方法の数を f (n) とする．n = 4 および 5 のとき，f (n) の値をそれぞれ求めよ．
問 4 問 3 で定めた f (n) の帰納的定義を 1 つ示せ．

情報数学の問題は，このページで終りである．
— 2 —アルゴリズムとデータ構造

I 要素数が 7 である整数配列 a[7] = { 4, 1, 5, 9, 7, 12, 8 } について，次の文章を読み，以下の問いに答えよ．（配点 50 点）

線形探索を用いて，整数配列 a から整数 7 を探索すると，配列の要素を一つ参照するごとの探索過程は表 1 のようになる．なお，表の使用しない欄には × を記入している．
表1参照
1 回目
2 回目
3 回目
4 回目
5 回目
6 回目
7 回目

参照要素の値
41
597××

問 1 整数配列 a を昇順にソートした整数配列を b[7] = {1, 4, 5, 7, 8, 9, 12} とする．二分探索を用いて，整数配列 b から整数 12 を探索するときの探索過程を解答用紙の表に示せ．なお，使用しない欄には × を記入すること．
問 2 バブルソート (単純交換ソート) を用いて，整数配列 a を昇順にソートするとき，ソートが完了するまでの過程を解答用紙の表に示せ．ただし，末尾に位置する二つの要素に着目してソートを始めるものとし，配列の 2 個 1 組の要素を交換するごとに交換後のすべての要素の並びを記せ．なお，使用しない欄には× を記入すること．
問 3 クイックソートを用いて，整数配列 a を昇順にソートする過程を説明せよ．
ただし，ピボットをどのように選んだかと，ピボットを選んで操作をした後の要素の並びを説明に含めること．

— 3 —問 4 要素数を n としたとき，次の (1)∼(5) のそれぞれを表す最も適切な式を，以下の (ア)∼(コ) から一つずつ選び記号で答えよ．ただし，同じ式を何度選んでもよい．
（1） 線形探索の平均の時間計算量（2） 二分探索の平均の時間計算量（3） バブルソート (単純交換ソート) の平均の時間計算量（4） クイックソートの平均の時間計算量（5） クイックソートの最悪時の時間計算量(ア) O(1)√(イ) O(log n) (ウ) O( n) (エ) O(n)(カ) O(n2 )(キ) O(n3 )(ク) O(2n )(オ) O(n log n)√(ケ) O(3n ) (コ) O(n n)

アルゴリズムとデータ構造の問題は，このページで終りである．
— 4 —令和 6 年度

大学院博士 (前期) 課程入学者選抜学力試験

B 日程
知能情報科学領域

専 門 科 目［90 分］
注 意 事 項

1．試験開始の合図があるまで，この問題冊子を開かないでください．
2．出題科目およびページは，下表のとおりです．問題ごとに配点が記されています．
出 題 科 目

ペ ー ジ

問題数

基礎数

学

1

2問

人工知

能

3〜 4

1問

アルゴリズムとデータ構造

5〜 61問注意

左の 3 科目すべてを解答してください．

3．解答冊子の表紙の所定欄に氏名と受験番号をはっきりと記入してください．
4．解答用紙は 3 科目分がそれぞれ綴じてあります．解答に用いなかった解答用紙も含め，すべての解答用紙 1 枚目の所定欄に受験番号をはっきりと記入してください．

5．解答用紙には，科目名，問題番号（I，II など），問いの番号（問 1 など）が記入されているので，該当する科目の解答用紙を用いてください．

6．計算／下書き用紙 3 枚が解答用紙と一緒にあります．
7．試験中に問題冊子の印刷不明瞭，ページの落丁・乱丁および解答用紙の汚れ等に気がついた場合は，静かに手を挙げて監督員に知らせてください．

8．試験終了後，監督員の指示に従って，解答冊子の表紙と 3 科目分の解答用紙を袋に入れてください．3 科目分の解答用紙が入っていない場合，入っていない科目の点数は 0 点となります．

9．問題冊子と計算／下書き用紙は持ち帰ってください．

基 礎 数 学

I 行列 1 2


−1

1−311 
−1 

2−50a

A= −1 −1 −2 −2 

に対し，線形写像 f : R4 → R4 を f (x) = Ax (x ∈ R4 ) により定める．以下の問いに答えよ．ただし，a は実数とする．（配点 25 点）
問 1 行列 A の階数 rank A を求めよ．
問 2 線形写像 f の核 Ker(f ) の基底を求めよ．
問 3 線形写像 f の像 Im(f ) の基底を求めよ．

II 以下の問いに答えよ．（配点 25 点）
問 1 t は t=\ −1 かつ t =\とするとき，(12) 13を満たす実数とする．x =dyを t を用いて表せ．
dx3t3t2,
y=1 + t3
1 + t3

問 2 次の極限を求めよ．

1limn→∞ n(1222n2++···+n 2 + 12
n2 + 22n2 + n2

基礎数学の問題は，このページで終りである．
— 1 —)(このページは白紙である)— 2 —人 工 知 能

I 次の文章を読み，以下の問いに答えよ．（配点 50 点）

三目並べというゲームに対して，MiniMax アルゴリズムを用いて次の一手を探索することを考える．三目並べとは，3 × 3 マスの盤面が与えられ，白の石を持つプレイヤーと黒の石を持つプレイヤーが交互にマスに石を置き，先に縦，横，対角線のいずれか一つ以上の列に三つ連続して石を並べたプレイヤーが勝つゲームである．白の石を持つプレイヤーが先攻，黒の石を持つプレイヤーが後攻である．
問 1 図 1 は現在の局面 X から二手先までを表したゲーム木である．図中の終端ノードにおいて，白の石のプレイヤーからみて勝ちの評価値を 10，負けの評価値を −10，引き分け（またはまだ勝敗がついていない場合）の評価値を 0 とした場合の，各ノードにおける評価値を A から G に対して求めよ．
問 2 問 1 では勝敗に関してのみ評価値を定めたが，さらなるヒューリスティクスを導入したい．そこで以下のように図中の終端ノードにおける評価値を求める．
（1） 白の石のプレイヤーからみて勝ちの評価値を 10，負けの評価値を −10，引き分け（またはまだ勝敗がついていない）の評価値を 0 とする（2） (白の石二つのみを含む列の数)×1，(黒の石二つのみを含む列の数)×(−1)
を加える
この場合の各ノードにおける評価値を A から G に対して求めよ．
問 3 図 1 のゲーム木について，MiniMax アルゴリズムを用いて深さ優先探索を行う場合の各ノードの評価値が定まる順序を示せ．例えば，ノード A，B，Cの順に評価値が定まる場合は A，B，C と記述すること．また，探索する対象のノードが複数ある場合は，アルファベット順で探索するものとする．

— 3 —

図1

人工知能の問題は，このページで終りである．
— 4 —アルゴリズムとデータ構造

I 要素数が 7 である整数配列 a[7] = { 4, 1, 5, 9, 7, 12, 8 } について，次の文章を読み，以下の問いに答えよ．（配点 50 点）

線形探索を用いて，整数配列 a から整数 7 を探索すると，配列の要素を一つ参照するごとの探索過程は表 1 のようになる．なお，表の使用しない欄には × を記入している．
表1参照
1 回目
2 回目
3 回目
4 回目
5 回目
6 回目
7 回目

参照要素の値
41
597××

問 1 整数配列 a を昇順にソートした整数配列を b[7] = {1, 4, 5, 7, 8, 9, 12} とする．二分探索を用いて，整数配列 b から整数 12 を探索するときの探索過程を解答用紙の表に示せ．なお，使用しない欄には × を記入すること．
問 2 バブルソート (単純交換ソート) を用いて，整数配列 a を昇順にソートするとき，ソートが完了するまでの過程を解答用紙の表に示せ．ただし，末尾に位置する二つの要素に着目してソートを始めるものとし，配列の 2 個 1 組の要素を交換するごとに交換後のすべての要素の並びを記せ．なお，使用しない欄には× を記入すること．
問 3 クイックソートを用いて，整数配列 a を昇順にソートする過程を説明せよ．
ただし，ピボットをどのように選んだかと，ピボットを選んで操作をした後の要素の並びを説明に含めること．

— 5 —問 4 要素数を n としたとき，次の (1)∼(5) のそれぞれを表す最も適切な式を，以下の (ア)∼(コ) から一つずつ選び記号で答えよ．ただし，同じ式を何度選んでもよい．
（1） 線形探索の平均の時間計算量（2） 二分探索の平均の時間計算量（3） バブルソート (単純交換ソート) の平均の時間計算量（4） クイックソートの平均の時間計算量（5） クイックソートの最悪時の時間計算量(ア) O(1)√(イ) O(log n) (ウ) O( n) (エ) O(n)(カ) O(n2 )(キ) O(n3 )(ク) O(2n )(オ) O(n log n)√(ケ) O(3n ) (コ) O(n n)

アルゴリズムとデータ構造の問題は，このページで終りである．
— 6 —