平成 31 年度

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

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

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

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

ペ ー ジ

問題数

基礎

数学

13問

情報

数学

2

1問

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

3

1問

注

意

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

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

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

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

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

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

基 礎 数 学
tanh x − x
ex − e−xex − e−xを求めよ．ただし，sinh x =, tanh x = xx − sinh x
2e + e−xである．（配点 15 点）

I 極限 x→0lim∫ √3II 定積分

x Tan−1 x dx を求めよ．ただし，Tan−1 x は逆正接関数で arctan x と書く

0こともある．（配点 10 点）

III a は実数とする．3 次正方行列 0 2 a 
A= 2 0 2 

a 2 0

が逆行列をもつかどうかを調べよ．さらに，行列 A が逆行列をもつ場合は逆行列を求めよ．（配点 25 点）

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

I 以下の無向グラフ G について，以下の問いに答えよ．（配点 50 点）

問 1 グラフ G の直径を求めよ．
問 2 節点 a から節点 h に至る順路の数を求めよ．
問 3 節点 a から節点 d に至る長さ 4 の経路の数を求めよ．
問 4 グラフ G の可能な全域木の数を求めよ．

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

I 単純交換ソートを用いて，整数を要素とする配列をソートすることを考える．このとき，以下の問いに答えよ．ただし，要素数を n (> 1) とする．（配点 50 点）
問 1 単純交換ソートでの二つの要素の比較回数について，最少比較回数のオーダを示すのに最も適切な式を，次の選択肢（ア） ∼（ケ）のなかから一つ選び，それを選択した理由とともに答えよ．

√（ウ） O ( n)（ア） O (1)（イ） O (log n)（エ） O (n)（オ） O (n log n) （カ） O (n2 )（キ） O (n2 log n) （ク） O (n3 )（ケ） O (2n )問 2 単純交換ソートでの二つの要素の交換回数について，平均交換回数のオーダを示すのに最も適切な式を，問 1 の選択肢（ア）∼（ケ）のなかから一つ選び，それを選択した理由とともに答えよ．
問 3 単純交換ソートでの要素の 1 回の比較にかかる時間計算量を 1 とし，1 回の交換にかかる時間計算量を log n とする．このとき，ソートでの要素の比較と交換をあわせた平均時間計算量のオーダを示すのに最も適切な式を，問 1 の選択肢（ア）∼（ケ）のなかから一つ選び，それを選択した理由とともに答えよ．

問 4 昇順の単純交換ソートにおいて，問 3 と同じ時間計算量の考え方で，最悪時間計算量になる配列の並びの例を一つ答えよ．また，なぜそのような配列の並びで最悪時間計算量になるのかを説明せよ．

アルゴリズムとデータ構造の問題は，このページで終りである．
— 3 —平成 31 年度

大学院博士 (前期) 課程入学者選抜学力試験
二次募集
複雑系情報科学領域

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

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

ペ ー ジ

問題数

基礎数学

13問

応用数学

21問

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

31問

注意

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

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

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

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

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

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

基 礎 数 学
tanh x − x
ex − e−xex − e−xを求めよ．ただし，sinh x =, tanh x = xx − sinh x2e + e−xである．（配点 15 点）

I 極限 x→0lim∫ √3II 定積分

x Tan−1 x dx を求めよ．ただし，Tan−1 x は逆正接関数で arctan x と書く

0こともある．（配点 10 点）

III a は実数とする．3 次正方行列


 0 2 a A= 2 0 2 

a 2 0が逆行列をもつかどうかを調べよ．さらに，行列 A が逆行列をもつ場合は逆行列を求めよ．（配点 25 点）

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

I 実数値関数 x = x(t), y = y(t) に対する連立微分方程式
dx= −x − ydtdy=x−ydtの解で，初期条件 (x(0), y(0)) = (1, 1) をみたすものを求めよ．（配点 50 点）

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

I 単純交換ソートを用いて，整数を要素とする配列をソートすることを考える．このとき，以下の問いに答えよ．ただし，要素数を n (> 1) とする．（配点 50 点）
問 1 単純交換ソートでの二つの要素の比較回数について，最少比較回数のオーダを示すのに最も適切な式を，次の選択肢（ア） ∼（ケ）のなかから一つ選び，それを選択した理由とともに答えよ．

√（ウ） O ( n)（ア） O (1)（イ） O (log n)（エ） O (n)（オ） O (n log n) （カ） O (n2 )（キ） O (n2 log n) （ク） O (n3 )（ケ） O (2n )問 2 単純交換ソートでの二つの要素の交換回数について，平均交換回数のオーダを示すのに最も適切な式を，問 1 の選択肢（ア）∼（ケ）のなかから一つ選び，それを選択した理由とともに答えよ．
問 3 単純交換ソートでの要素の 1 回の比較にかかる時間計算量を 1 とし，1 回の交換にかかる時間計算量を log n とする．このとき，ソートでの要素の比較と交換をあわせた平均時間計算量のオーダを示すのに最も適切な式を，問 1 の選択肢（ア）∼（ケ）のなかから一つ選び，それを選択した理由とともに答えよ．

問 4 昇順の単純交換ソートにおいて，問 3 と同じ時間計算量の考え方で，最悪時間計算量になる配列の並びの例を一つ答えよ．また，なぜそのような配列の並びで最悪時間計算量になるのかを説明せよ．

アルゴリズムとデータ構造の問題は，このページで終りである．
— 3 —平成 31 年度

大学院博士 (前期) 課程入学者選抜学力試験
二次募集
知能情報科学領域

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

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

ペ ー ジ

問題数学

13問

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

21問

人

31問

基礎

工数知

能注

意

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

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

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

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

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

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

基 礎 数 学
tanh x − x
ex − e−xex − e−xを求めよ．ただし，sinh x =, tanh x = x
x − sinh x
2e + e−xである．（配点 15 点）

I 極限 x→0lim∫ √3II 定積分x Tan−1 x dx を求めよ．ただし，Tan−1 x は逆正接関数で arctan x と書く

0こともある．（配点 10 点）

III a は実数とする．3 次正方行列


 0 2 a A= 2 0 2 

a 2 0が逆行列をもつかどうかを調べよ．さらに，行列 A が逆行列をもつ場合は逆行列を求めよ．（配点 25 点）

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

I 単純交換ソートを用いて，整数を要素とする配列をソートすることを考える．このとき，以下の問いに答えよ．ただし，要素数を n (> 1) とする．（配点 50 点）
問 1 単純交換ソートでの二つの要素の比較回数について，最少比較回数のオーダを示すのに最も適切な式を，次の選択肢（ア） ∼（ケ）のなかから一つ選び，それを選択した理由とともに答えよ．

√（ウ） O ( n)（ア） O (1)（イ） O (log n)（エ） O (n)（オ） O (n log n) （カ） O (n2 )（キ） O (n2 log n) （ク） O (n3 )（ケ） O (2n )問 2 単純交換ソートでの二つの要素の交換回数について，平均交換回数のオーダを示すのに最も適切な式を，問 1 の選択肢（ア）∼（ケ）のなかから一つ選び，それを選択した理由とともに答えよ．
問 3 単純交換ソートでの要素の 1 回の比較にかかる時間計算量を 1 とし，1 回の交換にかかる時間計算量を log n とする．このとき，ソートでの要素の比較と交換をあわせた平均時間計算量のオーダを示すのに最も適切な式を，問 1 の選択肢（ア）∼（ケ）のなかから一つ選び，それを選択した理由とともに答えよ．

問 4 昇順の単純交換ソートにおいて，問 3 と同じ時間計算量の考え方で，最悪時間計算量になる配列の並びの例を一つ答えよ．また，なぜそのような配列の並びで最悪時間計算量になるのかを説明せよ．

アルゴリズムとデータ構造の問題は，このページで終りである．
— 2 —人 工 知 能I 図 1 のグラフにおいて S を始点，G を終点とする．このグラフを，(1) 山登り法，(2)最良優先探索，(3) A*アルゴリズムで探索し，各々の探索法により得られた経路を求め，さらに，終点 G に達した場合は総コストを示せ．各エッジに書かれた数字はそのエッジをたどるときのコストを表す．なお，ヒューリスティック関数として Gからのマンハッタン距離を採用する．座標 (x1 , y1 ) と座標 (x2 , y2 ) の間のマンハッタ
ン距離は |x1 − x2 | + |y1 − y2 | である．（配点 50 点）

図1

人工知能の問題は，このページで終りである．
— 3 —