令和 3 年度

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

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

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

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

ペ ー ジ

問題数

基

礎

数

学

1

2問

情

報

数

学

2

1問

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

3〜 4

1問

デ ー タ ベ ー ス 工 学

5

1問

注

意

左の 4 科目のうちから 3 科
目を選択し，解答してくだ
さい．

3．解答冊子の表紙の所定欄に氏名と受験番号をはっきりと記入してください．さらに，選択した科目名の選択欄に○印を記入してください．○印のついた 3 科目のみ採点します．

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

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

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

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

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

基 礎 数 学

I a を 0 以上の実数とする．3 次正方行列

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

0 0 1



について, 以下の問いに答えよ.（配点 25 点）
問 1 行列 A の固有値を全て求めよ．さらに，各固有値に対し固有空間の基底を求めよ．
問 2 行列 A が対角化可能かどうか調べよ．さらに，対角化可能ならば P −1 AP が対角行列となるような行列 P を求めよ．

II 以下の問いに答えよ．（配点 25 点）
問 1 極限lim

x→0

sin(2x) log(cos(4x))
sin(3x) log(cos(5x))

を求めよ．
問 2 a を正の実数とする．
∫ a0

2x − 1dx(x + 2)(x2 + 1)

を求めよ．さらに, 広義積分∫ ∞02x − 1dx(x + 2)(x2 + 1)を求めよ．

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

I n を自然数とし，集合 An を An = {a|a は 1 以上 n 以下の整数 } で定める．また R
を An の中の関係 R ⊂ An × An とする．ただし, R = {} も関係とみなす．以下の問
いに答えよ．（配点 50 点）
問 1 直積集合 An × An の要素数を求めよ．また, 集合 An に対して, 相異なる関係

R の総数を求めよ．
問 2 集合 A3 に対して，関係 R を

aRb : “a ≡ b + 2 (mod 3)”で定義する． R の関係行列を求めよ．さらに, R の関係グラフを示せ．
問 3 集合 A2 に対して，対称律 “∀a, b ∈ A2 , aRb ⇒ bRa” をみたす関係 R の関係
行列を全て求めよ．
問 4 集合 An に対して，対称律を満たす関係 R の総数を求めよ．

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

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

問 1 線形探索を用いて，整数配列 a から整数 6 を探索するときの比較回数を答えよ．さらに，この探索における比較過程も答えよ．解答にあたっては注 1) と
注 2) に従うこと．
注 1) 探索の比較回数は，配列の 1 要素と比較するごとに 1 回と数え，目的の整数を見つけて探索を完了するまでの回数とする．
注 2) 比較過程の表記では，n 回目の比較の場合，「比較 n 回目： 1 回目に比較した整数配列 a の要素の値, 2 回目に比較した整数配列 a の要素の値, · · ·, n
回目に比較した整数配列 a の要素の値」を１行に記し，1 回目の比較から探索を完了するまでの全比較過程を答えよ．
問 2 単純選択ソートを用いて，整数配列 a を最小要素に着目して昇順にソートするときの要素の交換回数を答えよ．さらに，このソートにおける交換過程も答えよ．解答にあたっては注 3) と注 4) に従うこと．
注 3) 要素の交換回数は，配列の 1 組の要素を交換するごとに 1 回と数え，ソー
トが完了するまでの回数とする．
注 4) 交換過程の表記では，n 回目の交換の場合，「交換 n 回目： n 回目の交換後の整数配列 a のすべての要素の値の並び」を１行に記し，1 回目の交換からソートが完了するまでの全交換過程を答えよ．

— 3 —問 3 二分探索を用いて，整数配列 b[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9} から，整数 6 を探索するときの比較回数を答えよ．さらに，この探索における着目要素と探索過程も答えよ．解答にあたっては注 5) と注 6) に従うこと．
注 5) 探索の比較回数は，着目する要素を決めて，その要素を用いて探索対象範囲を絞り込むまでを 1 回と数え，目的の整数を見つけて探索を完了するまでの回数とする．
注 6) 比較過程の表記では，n 回目の比較の場合，「比較 n 回目：n 回目の着目要素の値，絞り込んだ探索対象範囲の要素の値の並び」を１行に記し，1回目の比較から探索を完了するまでの全比較過程を答えよ．
問 4 整数配列 a の要素の値を先頭から順に与えた場合に生成される完全二分木を図示せよ．さらに，部分木のヒープ化アルゴリズムを，この木に再帰的に適用した場合に生成されるヒープも図示せよ．ただし，そのヒープでは，子ノードの値より親ノードの値の方が大きいものとする．

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

I 以下の問いに答えよ．（配点 50 点）
問 1 次の条件を満たす SNS のデータベースを設計するために，どのようなテーブルを用意する必要があるか，すべてを答えよ．ただし，テーブルはテーブル
名 (属性 1, 属性 2, 属性 3, ...) の形式で表し，主キーとなる属性には下線を引くこと．

• SNS のユーザは，最大 8 文字のユーザ ID，最大 8 文字のパスワード，最大
16 文字の表示名をもつ．ただし，ユーザ ID は一意のものとする．
• ユーザは複数の投稿を行うことができる．投稿は最大 140 文字のテキストとする．
問 2 問 1 で設計したデータベースに対して，以下を得るための SQL 文を答えよ．
（1） “user1” というユーザ ID をもつユーザの投稿件数（2） “User Name” という表示名をもつユーザの投稿件数（3） “user1” というユーザ ID をもつユーザの投稿テキストすべて
問 3 問 1 で設計したデータベースに，もう一つテーブルを追加することで，各投稿に対して「いいね！」をしたユーザを記録したい．どのようなテーブルを追加する必要があるか，問 1 と同じ形式で答えよ．
問 4 問 1 および問 3 で設計したデータベースに対して，以下を得るための SQL 文
を答えよ．
（1） “user2” というユーザ ID をもつユーザの投稿に対して，「いいね！」をした
ユーザ全員のユーザ ID 一覧 (重複しない)（2） “user3” というユーザ ID をもつユーザが「いいね！」をしたすべての投稿の，投稿者のユーザ ID 一覧 (重複しない)

データベース工学の問題は，このページで終りである．
— 5 —令和 3 年度

大学院博士 (前期) 課程入学者選抜学力試験
メディアデザイン領域

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

報

認

知

デ

ザ

ペ ー ジ

問題数

イ

ン

1〜 2

1問

理

学

3

1問

ヒューマンインタフェース

4

1問

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

5〜 6

1問

心

注

意

左の 4 科目のうちから 3 科
目を選択し，解答してくだ
さい．

3． 解答冊子の表紙の所定欄に氏名と受験番号をはっきりと記入してください．さらに，選択した科目名の選択欄に○印を記入してください．○印のついた 3 科目のみ採点します．

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

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

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

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

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

情報デザインI 文章による表現は，最初から最後まで順に読み込んでもらうことで，情報の受け手に内容を伝える方法である．これに対して図解による表現は，文章よりも先に伝達
内容の全体像や説明要素の関係性を視覚的に示すことで，情報の受け手に概要を直感的に把握してもらった上で，伝達内容を読み解いてもらうという意図を持った表現と言える．この考え方を前提に，以下の問いに答えよ．（配点 50 点）

問 1 図 1 の内容を図解を用いて再構成し，リーフレットのデザイン案として解答
用紙に手書きで表現せよ．ただし，図 1 の内容は箇条書きになっているが，すべての項目をそのまま表示せず，組み合わせたり，言い換えたりすることにより，再構成して簡潔に表現すること．

• リーフレットの要件–

リーフレットの用途として，地域の高齢者が多く利用する公共施設の受付カウンター付近に掲示することを想定する．
いちべつ–

通りすがりに一瞥しただけでも概要が把握できるよう，紙面全体をひとつの図として構成する．

–

できるだけ短時間で内容を把握してもらえるように，説明項目の表現に図解を用いる．

–

タイトルや見出し，説明文など，内容の伝達に必要と考えられる文字
情報を効果的に配置する．

–

リーフレットは A4 サイズの用紙に縦位置でプリントアウトして掲示する．

–

配色については，コピーして配布することもできるように白／黒のみで表現する．

• 解答方法
–解答用紙の「リーフレット案」の枠の中に，リーフレットのデザイン
案を表現すること．

–

枠の中に配置しにくい内容や補足説明などは欄外に記述し，引出し線などで紙面内の要素や位置との対応を示すこと．

問 2 表現したデザイン案について，独自に工夫した点を 300 字以内で説明せよ．

— 1 —厚生労働省

運営者・リーダー向け

新型コロナウイルス感染症に気をつけて通いの場を開催するための留意点
開催の可否や実施方法については、地域における新型コロナウイルス感染症の流行状況を確認し、市町村の保健師や感染症に詳しい専門職と相談しながら判断しましょう。

通いの場を開催するために、 「３つの密（密閉、密集、密接）」を避ける、「人と人との距離の確保」、「マスクの着用」、「手洗い」が大切です～感染拡大を防ぐためのポイント～♣ 自分自身の健康管理にも十分配慮するようにしましょう♣ 参加者の体温や体調の確認を行い、参加者名簿を作成し、記録するようにしましょう
注:発熱などが認められる場合には、参加を断りましょう♣ 参加者には、「毎日体温を計測をする」「症状がなくてもマスクを着用する」「 水と石けんで丁寧な手洗いをする」ように呼びかけましょう♣ 市町村の担当者などと連携し、参加しなくなった方の把握や参加の呼びかけを行うことも大切です
開催中は、♣ 複数の人が触れる手すり、ドアノブ、テーブル、椅子などは、適宜、塩素系漂白剤（次亜塩素酸ナトリウム0.05％）やアルコールなどで消毒を行いましょう♣ 公民館など室内で開催する場合は、１時間に２回以上の換気を行いましょう♣ 参加者同士の間隔は、互いに手を伸ばしたら手が届く範囲以上空けるようにしましょう♣ 会話をする際は、正面に立たないように、注意を促しましょう♣ 文字（紙）や録音、マイクなどを活用するなど、大きな声を出す機会を少なくするように工夫しましょう

体操は
お互いの
距離をあけてできるだけ２ｍ（最低１ｍ）～体操など身体を動かす活動をする場合～

テキスト
テキスト
テキスト
テキスト
注:公園など屋外で人と十分な距離（２ｍ以上）を確保できる場合は、マスクをはずしましょう
テキスト♣ マスクを着けて運動をする場合は、身体への負荷が著しく大きくなりやすいため、無理のないよう負荷を下げたり、休憩を取るなどの配慮をしましょう♣ 熱中症予防のため、こまめな水分補給や室温調整などを行うよう気をつけましょう～飲食を伴う活動をする場合～♣ 座席の配置は、横並びで座るなどの工夫を行い、距離をとるように調整しましょう♣ 会食等では、料理は個別に配膳し、茶菓は個別包装されたものを用意しましょう♣ 食器やコップ、箸などは、使い捨てにしたり、洗剤でしっかりと洗いましょう
自宅でもできる全国のご当地体操の動画やリーフレットの情報を掲載しています

厚労省 高齢者

体操検索
令和２年６月図1

出展：厚生労働省ホームページ「新型コロナウィルス感染症への対応について（高齢者の皆様へ）」より．(https://www.mhlw.go.jp/content/000636965.pdf)

情報デザインの問題は，このページで終りである．
— 2 —認知心理学I 外界の事物など，ある対象を特定の長期記憶内の知識表象に対応づける認知過程のことを，カテゴリー化と呼ぶ．典型性に基づいたカテゴリー化は，対象によっては言語に依存しないとする認知心理学の研究報告がある．
色についての言葉を持たないなど，外界の事物のある特性についてカテゴリー化する言葉を持たなくても，典型的な事物は非典型的な事物よりも別の項目との対連
合学習をしやすいとの仮説を適切に検討するための実験計画を考える．以下に示す
四つの項目に分けて 400 字程度の文章で記述せよ．なお，自ら考案する実験計画ではなく，この仮説を検証した先行研究の実験計画について記述しても良い．
（配点 50 点）（1） 実験参加者（参加者の属性など）（2） 実験刺激（実験で提示するものなど）（3） 実験手続き（実験参加者が行うことなど）（4） 分析方法（何の測定結果と何の測定結果を比較し，どのように判断するのかなど）

認知心理学の問題は，このページで終りである．
— 3 —ヒューマンインタフェース

I 次の文章を読み，以下の問いに答えよ．（配点 50 点）
ヤコブ・ニールセンは，著書『ユーザビリティエンジニアリング原論-ユーザーのためのインタフェースデザイン』において，ヒューマンインタフェースにおける五つのユーザビリティ特性をあげている．

•（ア） しやすさ–•

作業をすぐに始められるよう，簡単に （ア） できる．

（イ） 性

–

一度 （ウ） が学習すれば，後は高い （エ） 性を上げられるよう，（イ）的な使用を可能にする．

•（オ） しやすさ–

しばらく使わなくても，再び使うときに覚え直さないで使える．

• エラー発生率–

エラーを起しにくい．もしエラーが発生しても （カ） に回復できる．（キ）的なエラーが起きない．

•（ク） 的満足度–（ウ） が （ケ） 的に満足できる．また，好きになれる． （コ） 利用できる．

問 1 この著書で紹介されている用語を用いて （ア） から （コ） の空欄に入る最も適切な語句を次の選択肢 (1) から (18) の中から一つ選び，番号で答えよ．ただし，同じものは複数回用いてはいけない．

(1)

主観

(2)

客観

(3)

性能

(4)

学習

(5)

生産

(6)

直感

(7)

個人

(8)

クライアント(9)

ユーザー(10) 効率(11) 記憶(12) 忘却(13) 致命(14) 簡単(15) 認知(16) 楽しく(17) 気持ちよく(18) 知覚参考文献：ヤコブ・ニールセン (2002) 『ユーザビリティエンジニアリング原論ユーザーのためのインタフェースデザイン』（ヤコブ・ニールセン 著；篠原稔和 監
訳；三好かおる 訳） 東京電機大学出版局．

ヒューマンインタフェースの問題は，このページで終りである．
— 4 —アルゴリズムとデータ構造

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

問 1 線形探索を用いて，整数配列 a から整数 6 を探索するときの比較回数を答えよ．さらに，この探索における比較過程も答えよ．解答にあたっては注 1) と
注 2) に従うこと．
注 1) 探索の比較回数は，配列の 1 要素と比較するごとに 1 回と数え，目的の整数を見つけて探索を完了するまでの回数とする．
注 2) 比較過程の表記では，n 回目の比較の場合，「比較 n 回目： 1 回目に比較した整数配列 a の要素の値, 2 回目に比較した整数配列 a の要素の値, · · ·, n
回目に比較した整数配列 a の要素の値」を１行に記し，1 回目の比較から探索を完了するまでの全比較過程を答えよ．
問 2 単純選択ソートを用いて，整数配列 a を最小要素に着目して昇順にソートするときの要素の交換回数を答えよ．さらに，このソートにおける交換過程も答えよ．解答にあたっては注 3) と注 4) に従うこと．
注 3) 要素の交換回数は，配列の 1 組の要素を交換するごとに 1 回と数え，ソー
トが完了するまでの回数とする．
注 4) 交換過程の表記では，n 回目の交換の場合，「交換 n 回目： n 回目の交換後の整数配列 a のすべての要素の値の並び」を１行に記し，1 回目の交換からソートが完了するまでの全交換過程を答えよ．

— 5 —問 3 二分探索を用いて，整数配列 b[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9} から，整数 6 を探索するときの比較回数を答えよ．さらに，この探索における着目要素と探索過程も答えよ．解答にあたっては注 5) と注 6) に従うこと．
注 5) 探索の比較回数は，着目する要素を決めて，その要素を用いて探索対象範囲を絞り込むまでを 1 回と数え，目的の整数を見つけて探索を完了するまでの回数とする．
注 6) 比較過程の表記では，n 回目の比較の場合，「比較 n 回目：n 回目の着目要素の値，絞り込んだ探索対象範囲の要素の値の並び」を１行に記し，1回目の比較から探索を完了するまでの全比較過程を答えよ．
問 4 整数配列 a の要素の値を先頭から順に与えた場合に生成される完全二分木を図示せよ．さらに，部分木のヒープ化アルゴリズムを，この木に再帰的に適用した場合に生成されるヒープも図示せよ．ただし，そのヒープでは，子ノードの値より親ノードの値の方が大きいものとする．

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

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

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

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

ペ ー ジ

問題数

基

礎

数

学

1

2問

情

報

数

学

2

1問

応

用

数

学

3

1問

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

5〜 6

1問

注

意

左の 4 科目のうちから 3 科
目を選択し，解答してくだ
さい．

3．解答冊子の表紙の所定欄に氏名と受験番号をはっきりと記入してください．さらに，選択した科目名の選択欄に○印を記入してください．○印のついた 3 科目のみ採点します．

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

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

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

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

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

基 礎 数 学

I a を 0 以上の実数とする．3 次正方行列

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

0 0 1



について, 以下の問いに答えよ.（配点 25 点）
問 1 行列 A の固有値を全て求めよ．さらに，各固有値に対し固有空間の基底を求めよ．
問 2 行列 A が対角化可能かどうか調べよ．さらに，対角化可能ならば P −1 AP が対角行列となるような行列 P を求めよ．

II 以下の問いに答えよ．（配点 25 点）
問 1 極限lim

x→0

sin(2x) log(cos(4x))
sin(3x) log(cos(5x))

を求めよ．
問 2 a を正の実数とする．
∫ a0

2x − 1dx(x + 2)(x2 + 1)

を求めよ．さらに, 広義積分∫ ∞02x − 1dx(x + 2)(x2 + 1)を求めよ．

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

I n を自然数とし，集合 An を An = {a|a は 1 以上 n 以下の整数 } で定める．また R
を An の中の関係 R ⊂ An × An とする．ただし, R = {} も関係とみなす．以下の問
いに答えよ．（配点 50 点）
問 1 直積集合 An × An の要素数を求めよ．また, 集合 An に対して, 相異なる関係

R の総数を求めよ．
問 2 集合 A3 に対して，関係 R を

aRb : “a ≡ b + 2 (mod 3)”で定義する． R の関係行列を求めよ．さらに, R の関係グラフを示せ．
問 3 集合 A2 に対して，対称律 “∀a, b ∈ A2 , aRb ⇒ bRa” をみたす関係 R の関係
行列を全て求めよ．
問 4 集合 An に対して，対称律を満たす関係 R の総数を求めよ．

情報数学の問題は，このページで終りである．
— 2 —応 用 数 学

I 互いに独立な確率変数 X1 , X2 が, それぞれ以下の確率密度関数をもつ分布に従う
ものとする．

p(x) = λ exp(−λx)

x>0

 0

x≤0

ただし，λ は正の実数とする．このとき，以下の問いに答えよ．（配点 50 点）
問 1 X1 の累積分布関数 F (x) = P (X1 ≤ x) を求めよ．ただし, P (A) は事象 A の確率とする．
問 2 X1 の期待値と分散を求めよ．
問 3 問 2 で求めた期待値を µ とし, p(x1 , x2 ) を確率ベクトル (X1 , X2 ) の同時確率密度関数とする．
∫ ∞ ∫ ∞−∞−∞{(x1 − µ) + (x2 − µ)}2 p(x1 , x2 )dx1 dx2を求めよ．

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

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

問 1 線形探索を用いて，整数配列 a から整数 6 を探索するときの比較回数を答えよ．さらに，この探索における比較過程も答えよ．解答にあたっては注 1) と
注 2) に従うこと．
注 1) 探索の比較回数は，配列の 1 要素と比較するごとに 1 回と数え，目的の整数を見つけて探索を完了するまでの回数とする．
注 2) 比較過程の表記では，n 回目の比較の場合，「比較 n 回目： 1 回目に比較した整数配列 a の要素の値, 2 回目に比較した整数配列 a の要素の値, · · ·, n
回目に比較した整数配列 a の要素の値」を１行に記し，1 回目の比較から探索を完了するまでの全比較過程を答えよ．
問 2 単純選択ソートを用いて，整数配列 a を最小要素に着目して昇順にソートするときの要素の交換回数を答えよ．さらに，このソートにおける交換過程も答えよ．解答にあたっては注 3) と注 4) に従うこと．
注 3) 要素の交換回数は，配列の 1 組の要素を交換するごとに 1 回と数え，ソー
トが完了するまでの回数とする．
注 4) 交換過程の表記では，n 回目の交換の場合，「交換 n 回目： n 回目の交換後の整数配列 a のすべての要素の値の並び」を１行に記し，1 回目の交換からソートが完了するまでの全交換過程を答えよ．

— 5 —問 3 二分探索を用いて，整数配列 b[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9} から，整数 6 を探索するときの比較回数を答えよ．さらに，この探索における着目要素と探索過程も答えよ．解答にあたっては注 5) と注 6) に従うこと．
注 5) 探索の比較回数は，着目する要素を決めて，その要素を用いて探索対象範囲を絞り込むまでを 1 回と数え，目的の整数を見つけて探索を完了するまでの回数とする．
注 6) 比較過程の表記では，n 回目の比較の場合，「比較 n 回目：n 回目の着目要素の値，絞り込んだ探索対象範囲の要素の値の並び」を１行に記し，1回目の比較から探索を完了するまでの全比較過程を答えよ．
問 4 整数配列 a の要素の値を先頭から順に与えた場合に生成される完全二分木を図示せよ．さらに，部分木のヒープ化アルゴリズムを，この木に再帰的に適用した場合に生成されるヒープも図示せよ．ただし，そのヒープでは，子ノードの値より親ノードの値の方が大きいものとする．

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

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

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

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

ペ ー ジ

問題数

基

礎

数

学

1

2問

情

報

数

学

2

1問

人

工

知

能

3〜 4

1問

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

5〜 6

1問

注

意

左の 4 科目のうちから 3 科
目を選択し，解答してくだ
さい．

3．解答冊子の表紙の所定欄に氏名と受験番号をはっきりと記入してください．さらに，選択した科目名の選択欄に○印を記入してください．○印のついた 3 科目のみ採点します．

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

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

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

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

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

基 礎 数 学

I a を 0 以上の実数とする．3 次正方行列

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

0 0 1



について, 以下の問いに答えよ.（配点 25 点）
問 1 行列 A の固有値を全て求めよ．さらに，各固有値に対し固有空間の基底を求めよ．
問 2 行列 A が対角化可能かどうか調べよ．さらに，対角化可能ならば P −1 AP が対角行列となるような行列 P を求めよ．

II 以下の問いに答えよ．（配点 25 点）
問 1 極限lim

x→0

sin(2x) log(cos(4x))
sin(3x) log(cos(5x))

を求めよ．
問 2 a を正の実数とする．
∫ a0

2x − 1dx(x + 2)(x2 + 1)

を求めよ．さらに, 広義積分∫ ∞02x − 1dx(x + 2)(x2 + 1)を求めよ．

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

I n を自然数とし，集合 An を An = {a|a は 1 以上 n 以下の整数 } で定める．また R
を An の中の関係 R ⊂ An × An とする．ただし, R = {} も関係とみなす．以下の問
いに答えよ．（配点 50 点）
問 1 直積集合 An × An の要素数を求めよ．また, 集合 An に対して, 相異なる関係

R の総数を求めよ．
問 2 集合 A3 に対して，関係 R を

aRb : “a ≡ b + 2 (mod 3)”で定義する． R の関係行列を求めよ．さらに, R の関係グラフを示せ．
問 3 集合 A2 に対して，対称律 “∀a, b ∈ A2 , aRb ⇒ bRa” をみたす関係 R の関係
行列を全て求めよ．
問 4 集合 An に対して，対称律を満たす関係 R の総数を求めよ．

情報数学の問題は，このページで終りである．
— 2 —人 工 知 能

I 次の文章を読み，以下の問いに答えよ．（配点 50 点）
N クイーン問題は，チェスのルールを利用したパズルである．チェスには縦・横・斜めのうちのいずれか一つの方向に何マスでも動くことのできるクイーンの駒（以後 Q と表す）がある．N 個の Q を N×N サイズのマス目上で互いの移動を妨げないように配置する問題が N クイーン問題である．例えば，4 クイーン問題には図 1 の解が存在する．

Q
Q
Q
Q
図1

Q

Q

[A]
× Q

〇

Q

Q

Q

×

Q

Q
Q

Q

Q

×

Q

Q

Q

Q

Q
Q

Q

Q

Q

×

Q

×

Q

Q

Q
Q

×

×

Q

Q
Q

×

Q

Q

Q

× Q

Q

×

〇

〇

Q
Q

図2

— 3 —

Q

Q
Q

×
Q
Q

Q

×
Q

Q

×

Q

Q
Q

Q

問 1 図 2 は，一行目に Q を一つ置いた盤面から始めて，次の行から順に一行に一つずつ Q を置いていく場合の探索木の一例を示している．探索木の各盤面の上側に記された〇は N クイーン問題の配置として適切であることを示している．
逆に × は N クイーン問題の配置として不適切であることを示しており，この配置にさらに Q を追加して探索を行う必要がないことを意味する．このとき [A]にあてはまる盤面を図 1 と同様の形式で記せ．
問 2 4 クイーン問題の探索を，図 3 のように一行目に Q を一つ置いた盤面から始めたとする．この場合，二行目以降に Q を順に置いていく探索木を，探索が終了するところまで図 2 と同様の形式で記せ．

Q

図3

問 3 5 クイーン問題のすべての解を図 1 と同様の形式で記せ．ただし，盤面を回転・反転した場合に同じとなる解はそのうちの一つを記せ．

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

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

問 1 線形探索を用いて，整数配列 a から整数 6 を探索するときの比較回数を答えよ．さらに，この探索における比較過程も答えよ．解答にあたっては注 1) と
注 2) に従うこと．
注 1) 探索の比較回数は，配列の 1 要素と比較するごとに 1 回と数え，目的の整数を見つけて探索を完了するまでの回数とする．
注 2) 比較過程の表記では，n 回目の比較の場合，「比較 n 回目： 1 回目に比較した整数配列 a の要素の値, 2 回目に比較した整数配列 a の要素の値, · · ·, n
回目に比較した整数配列 a の要素の値」を１行に記し，1 回目の比較から探索を完了するまでの全比較過程を答えよ．
問 2 単純選択ソートを用いて，整数配列 a を最小要素に着目して昇順にソートするときの要素の交換回数を答えよ．さらに，このソートにおける交換過程も答えよ．解答にあたっては注 3) と注 4) に従うこと．
注 3) 要素の交換回数は，配列の 1 組の要素を交換するごとに 1 回と数え，ソー
トが完了するまでの回数とする．
注 4) 交換過程の表記では，n 回目の交換の場合，「交換 n 回目： n 回目の交換後の整数配列 a のすべての要素の値の並び」を１行に記し，1 回目の交換からソートが完了するまでの全交換過程を答えよ．

— 5 —問 3 二分探索を用いて，整数配列 b[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9} から，整数 6 を探索するときの比較回数を答えよ．さらに，この探索における着目要素と探索過程も答えよ．解答にあたっては注 5) と注 6) に従うこと．
注 5) 探索の比較回数は，着目する要素を決めて，その要素を用いて探索対象範囲を絞り込むまでを 1 回と数え，目的の整数を見つけて探索を完了するまでの回数とする．
注 6) 比較過程の表記では，n 回目の比較の場合，「比較 n 回目：n 回目の着目要素の値，絞り込んだ探索対象範囲の要素の値の並び」を１行に記し，1回目の比較から探索を完了するまでの全比較過程を答えよ．
問 4 整数配列 a の要素の値を先頭から順に与えた場合に生成される完全二分木を図示せよ．さらに，部分木のヒープ化アルゴリズムを，この木に再帰的に適用した場合に生成されるヒープも図示せよ．ただし，そのヒープでは，子ノードの値より親ノードの値の方が大きいものとする．

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