山梨大学工学部コンピュータ理工学科令和5年度3年次編入学試験説明資料

コンピュータ理工学科

3年次編入学生の選抜試験では、提出された成績証明書の内容ならびに本学で実施しました試験の結果を総合して判定し、合格者を決定しました。

1. 筆記試験
プログラミング、計算機アーキテクチャ、情報数学の3科目を出題し、2科目の選択解答としました。試験時間は80分です。試験問題は別紙の通りです。

2. 口述試験
コンピュータ理工学に関する専門分野の基礎的事項、意欲、コミュニケーション力、思考力に関する口述試験を行いました。試験時間は10分です。

令和５年度 山梨大学工学部

３年

次編

入 学

筆記 試 験

問

題
No 1/3学科

コンピュータ理工学科試

験 科 目プログラミング

問 1 ソートに関する以下の問いに答えなさい．
(a) ソートアルゴリズムの安定性とは何かを説明しなさい．
(b) 「挿入ソート」，「マージソート」，「クイックソート」の 3 つのアルゴリズムについて，安定かどうかを答えなさい．解答用紙の表に記入しなさい．
(c) データ数を n とする時，「挿入ソート」，「マージソート」，「クイックソート」の 3 つのアルゴリズムについて，平均計算量のオーダー，最悪計算量のオーダー，最良計算量のオーダーを答えなさい．解答用紙の表に記入しなさい．

問 2 ハッシュ表に関する以下の問いに答えなさい．
キー値が 0 から 15 までの整数値を取るとき，キー値の集合からハッシュ表を作成することを考えます．レコードはキー値のみで他にデータはないものとします．ハッシュ表のサイズ L を 5 とし，ハッシュ表の各要素は 0~4 の番地を持つものとします．ハッシュ関数 h(x)を h(x) = 3x mod L とします．
(a) ハッシュ値が 2 で衝突するような 3 つの異なるキー値を挙げなさい．
(b) 空のハッシュ表に，(a)の 3 つのキー値を分離チェイン法（チェイン法，分離連鎖法）によって格納する様子を図示しなさい．ただし，キー値が格納されているところだけの様子が分かればよく，その他の部分は書き入れる必要はありません．
(c) 空のハッシュ表に，(a)の 3 つのキー値を開番地法（空き番地法，オープンアドレス法）によって格納する様子を図示しなさい．ただし，代替ハッシュは線形走査法（線形探査法）で求めなさい．また，キー値が格納されているところだけの様子が分かればよく，その他の部分は書き入れる必要はありません．

問 3 ２分探索木に関する以下の問いに答えなさい．
(a) データ数を n とする時，平衡２分探索木に格納されたデータの中から，特定のデータを探索する作業の平均計算量のオーダーを答えなさい．平衡２分探索木は「どのノードの左右部分木の高さの差も 1 以下」という条件を満たす２分探索木です．
(b) 次のプログラムは，２分探索木の実装の一部です．空欄（ア）～（ウ）に当てはまる，再帰を用いたコードを記述しなさい．
(c) main 関数の「エ」の時点での２分探索木を図示しなさい．この２分探索木を前順（行きかけ順，preorder）ならびに中順（通りがけ順，inorder）でなぞったときのノードの訪問順序を答えなさい．

令和５年度 山梨大学工学部

３年

次編

入 学筆記 試 験問

題
No 2/3

学

科

コンピュータ理工学科

試

験 科 目

#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#include <math.h>typedef struct BinaryNode BinaryNode;typedef struct BinarySearchTree BinarySearchTree;void insert(BinarySearchTree* tree, int value);
struct BinaryNode {int key;
struct BinaryNode* left;
struct BinaryNode* right;};
struct BinarySearchTree {struct BinaryNode* root;};
void insert(BinarySearchTree* tree, int value){
BinaryNode* node=(BinaryNode*)malloc(sizeof(BinaryNode));node->key = value;node->left = NULL;
node->right = NULL;
if (tree->root == NULL) {tree->root = node;}
else{
BinaryNode* temp = tree->root;
while (true){if (value < temp->key) {if (temp->left == NULL) {temp->left = node;
return ;}else{temp = temp->left;}}
else {
if (temp->right == NULL) {temp->right = node;
return ;}else {プログラミング令和５年度 山梨大学工学部

３年

次編

入 学

筆記 試 験問題
No 3/3学科

コンピュータ理工学科試

験 科 目プログラミング

temp = temp->right;}}}}
return ;}int height(BinaryNode* p){// p が指しているノードを根とする木の高さを返す．
if ( p == NULL ) return 0;
return （ア）;}bool is_balanced(BinaryNode* p){// p が指しているノードを根とする木が平衡２分探索木のバランス条件を満たしているかどうかを返す．
if (p == NULL) return true;
if (（イ）)return （ウ）;elsereturn false;}
int main(){
BinarySearchTree bst = {NULL};
insert(&bst,5);
insert(&bst,2);
insert(&bst,3);
insert(&bst,7);
insert(&bst,6);
insert(&bst,4);
insert(&bst,1);// 「エ」
printf("%d\n", height(bst.root));
printf("%s\n", is_balanced(bst.root)?"true":"false");return 0;}令和５年度３ 年

次 編 入

山梨大学工学部

学

筆記

試

験問

題
No 1 / 2学

科

コンピュータ理工学科

試

験 科 目

計算機アーキテクチャ

問 1 論理変数 x  ( p0 , p1 , p2 ) があり，その最上位 bit （MSB）が p0 ，最下位 bit （LSB）が p2 として 3bit 符号なし
2 進整数を表すとすると，その数の 10 進表記は x  p0  22  p1  21  p2  20 で与えられます．
(a) 以下のような値を取る論理関数 y  f  x  があります． y , p0 , p1 , p2 の値の真理値表を作成しなさい．ただし，真を“1”, 偽を “0”で記すこととします．解答の際は，右の真理値表を解答用紙に転記したうえで y の列に適切な値を記入すること．
0y1yx  2 または x が奇数の場合
その他

p0p1p2000011110011001101010101(b) 上記の真理値表を元にして，主加法標準形（積和標準形，選言標準形，論理和標準形，などとも呼ばれる）の論理式を求めなさい．ただし，論理積を “・” で，また論理和を “+” で，否定を論理変数の上の “－” で表すものとします．例えば，変数 a の否定は a で， a と b の論理積は a b で， a b と c の論理和は a b  cで，それぞれ表記します．

問 2 2 の補数を用いた 8 bit の符号付き 2 進数を考えます．
(a) a = 11011000 を 10 進で表記しなさい．
(b) 上記(a)の a と b = 11101100 を加算した結果 c を 2 進数と 10 進数の両方で答えなさい．
(c) 上記(b)の c を右に 2bit 算術シフトした結果 d を 2 進数と 10 進数の両方で答えなさい．
(d) 2 進数 e = 00011001 と 2 進数 f = 00000101 の乗算 e × f を以下のように 2 進数の筆算で行う過程 (下の筆算の ? の部分) とその乗算結果の値を記しなさい．筆算の過程とその乗算結果の値は 2 進数で表記すること．
00011001
 00000101?

令和５年度３ 年

次 編 入

山梨大学工学部

学

筆記

試験

問題
No 2 / 2学科コンピュータ理工学科

試

験 科 目

計算機アーキテクチャ

問 3 プロセッサ A の命令セットアーキテクチャでは，アドレス空間が 24bit で，番地指定単位は 1Byte です（アドレスが 1 増えると次の 1Byte を指します）．このプロセッサ A の記憶システムをページ仮想記憶方式で実装します．実装するページ仮想記憶では，物理ページ番号に 12bit を，ページ内オフセットに 12bit を，それぞれ割り振り，以下のような内容のページテーブルを用いて仮想アドレス（論理アドレス）から物理アドレス（実アドレス）に変換します．また，この計算機システムの主記憶（物理メモリ）は 4MByte が実装されているとします．
（1kByte = 1,024byte，1MByte = 1,024kByte とします．）
右に示すページテーブルの各エントリは，存在
ビット E，参照ビット R，変更ビット M，および物理
ページ番号 P で構成され，E, R, M ビットの意味はそれぞれ以下のように定義されます．また，表の物理ページ番号は 2 進数で表記されており，読みやすさのために 4bit 区切りで空白を入れてあります．

＜仮想記憶のページテーブル（その一部）＞
エントリ番号
ERM
P0000010 0000 0010
01110011 0010 0011
11000000 1100 1001
21100011 0111 0111
30000001 1000 1011
40000001 0100 1111
50000000 1101 1001
6…

…

存在ビット E

当該ページが主記憶上に存在する場合には“1”, 存在しない場合に“0”に設定．

参照ビット R

当該ページが主記憶に読み込まれる（ページイン）したときに“0”に初期化．そのページ内のデータがアクセスされた時点で“1”に設定され，一定動作クロック経過後に“0”に設定．

変更ビット M

ページイン時に“0”に初期化．そのページが主記憶上に存在する間にそのページ内のデータに書き込みがあると，その時点で“1”に設定．

(a) この仮想記憶システムの 1 ページの容量は何 kByte ですか． また，4 MByte の主記憶は何ページ分に相当しますか．
(b) このプロセッサはユーザモードおよびスーパバイザモードの 2 つの実行モードを持ちます．スーパバイザモード
はまた，カーネルモード，特権モードなどとも呼ばれます．ページテーブルの先頭番地の設定，ページテーブルのエントリ内容の書き換え，などの処理は，この 2 つのどちらの実行モードで行われますか．簡単な理由とともに答えなさい．
(c) 上記のページテーブルにおいて，新たなページを主記憶にページインするため，主記憶から 1 ページを追い出す（ページアウトする）必要があるとします．ページテーブルのエントリ 0～6 から選ぶとするなら，どのエントリ番号のページが追い出されるでしょうか．そのように判断した理由とともに答えなさい．
(d) このプロセッサの記憶システムでは，プロセッサと主記憶の間に容量 16 kByte のキャッシュメモリが採用されています．まず，キャッシュメモリの目的と仕組みを簡単に述べなさい．次いで，キャッシュメモリと仮想記憶を比較し，これら 2 つの類似点と相違点を簡単に述べなさい．

令和５年度３学

科年

次編

コンピュータ理工学科

山梨大学工学部

入 学

筆 記

試

試 験

問 題

験 科 目

No 1 / 1
情報数学

問 1 𝑛𝑛 個の元からなる集合 𝐴𝐴 には 2𝑛𝑛 個の部分集合があることを数学的帰納法を用いて証明しなさい．
問 2 2 個の赤球と 18 個の白球が入った袋から，太郎，花子がこの順で 1 回ずつ球を取り出すとき，太郎が赤球を取り出す事象を 𝑇𝑇，花子が赤球を取り出す事象を 𝐻𝐻 とします．なお，取り出した球は袋に戻さないものとします．次の問いに答えなさい．
(a) 太郎が赤球を取り出した後，花子も赤球を取り出す確率 𝑃𝑃(𝑇𝑇 ∩ 𝐻𝐻) を求めなさい．

(b) 太郎が赤球を取り出す確率 𝑃𝑃(𝑇𝑇) と花子が赤球を取り出す確率 𝑃𝑃(𝐻𝐻) は等しいことを証明しなさい．

問 3 2 部グラフと n 彩色可能グラフは次のように定義されます．
 グラフ 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸) が 2 部であるとは，その頂点集合 𝑉𝑉 が 2 つの部分集合 𝐿𝐿, 𝑅𝑅 に分割され，かつ 𝐺𝐺 の各辺が𝐿𝐿 の頂点と 𝑅𝑅 の頂点を結んでいるときをいいます． これは数式を用いて以下のように表すことができます．
𝐿𝐿 ⊆ 𝑉𝑉, 𝑅𝑅 = 𝑉𝑉 − 𝐿𝐿 のとき，各辺 (𝑣𝑣, 𝑤𝑤) ∈ 𝐸𝐸 について 𝑣𝑣 ∈ 𝐿𝐿, 𝑤𝑤 ∈ 𝑅𝑅 または 𝑤𝑤 ∈ 𝐿𝐿, 𝑣𝑣 ∈ 𝑅𝑅

 グラフ 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸) が 𝑛𝑛 彩色可能であるとは， 隣接した頂点が異なる色を持つように 𝐺𝐺 の各頂点に 𝑛𝑛 種類の色から 1 色を割り当てられるときをいいます． これは数式を用いて以下のように表すことができます．
𝑓𝑓: 𝑉𝑉 → 𝐶𝐶 を頂点から色への写像としたとき（ここで |𝐶𝐶| = 𝑛𝑛），各辺 (𝑣𝑣, 𝑤𝑤) ∈ 𝐸𝐸 について 𝑓𝑓(𝑣𝑣) ≠ 𝑓𝑓(𝑤𝑤)

グラフ 𝐺𝐺 について次の 3 つの命題が同値であることを証明しなさい．
(i)

𝐺𝐺 が 2 彩色可能である．

(ii) 𝐺𝐺 が 2 部グラフである．

(iii) 𝐺𝐺 の各閉路の長さは偶数である．