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

コンピュータ理工学科

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

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

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

令和 6 年度

３年次編

山梨大学工学部入 学

筆 記 試 験問

題
No 1/4

学

科

コンピュータ理工学科試験 科 目

プログラミング

問 1 プログラムをコンパイル・実行した際の結果に関する以下の設問に答えなさい．
(a) 以下の cout 文を含むソースファイルをコンパイル・実行した際の結果として正しいのは次の内どれか．
cout << "/(^o^)\";

A. コンパイルが正常に行われ，/(^o^)\ がコンソール端末に出力される．
B. コンパイルが正常に行われ，/(^o^)" がコンソール端末に出力される．
C. コンパイルが正常に行われ，(^o^) がコンソール端末に出力される．
D. コンパイルエラーとなり，実行形式ファイルを生成できない．
(b) 以下のプログラムを実行した際の出力結果を答えなさい．
#include <iostream>using namespace std;
int func1( int x );int func2( int x, int y );int func3( int x, int y );int main(){
int a = 4;
int b = -3;
cout << func1( a ) << " " << func1( b ) << "\n";return 0;}
int func1( int x ){int result = 0;if( x < 2 ){result = func2( x, 2 );}else{
result = func3( x, 5 );}return result + 1;}
int func2( int x, int y ){return x * y;}
int func3( int x, int y ){return x + y;}令和 6 年度

３年次編

山梨大学工学部入 学

筆 記 試 験問

題
No 2/4

学

科

コンピュータ理工学科

試

験 科 目

プログラミング(c) 以下のプログラムを実行すると，無限ループとなるか．その理由を含めて答えなさい．
#include <iostream>using namespace std;
int main(){
int a = 0;
while( true ){if( ( 2 * a + 1 ) % 2 == 0 ){break;}
a++;}return 0;}(d) 以下のプログラムは，テキストファイルを読み込んで，そのファイルの行数を出力するものである．しかし，実行時にエラーが発生する．例えば，コマンドラインで「NumOfLines a.txt」と実行すると，「ファイルを開くことができません」と出力される．「NumOfLines」は実行ファイル，「a.txt」 は読み込むテキストファイルの名前である．読み込むテキストファイルはコマンドラインで必ず与えられるものとする．このエラーを修正するために，プログラムの 1 行を修正しなさい．修正する行番号と修正後のソースコードを答えなさい．
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>#include <fstream>using namespace std;
int main(int argc, char *argv[]) {char *filename;ifstream file(filename);if (!file) {cout << "ファイルを開くことができません" << endl;
return 1;}
int lines = 0;char ch;while (file.get(ch)) {if (ch == '\n') {lines++;}}cout << "ファイル内の行数: " << lines << endl;
file.close();return 0;}

令和 6 年度

３年次編

山梨大学工学部入 学

筆 記 試 験問

題
No 3/4

学

科

コンピュータ理工学科試

験 科 目プログラミング

問 2 ソートに関する以下の設問に答えなさい．
(a) 「選択ソート」，「バブルソート」，「ヒープソート」の 3 つのアルゴリズムについて，安定かどうかを解答用紙の表に記入しなさい．
(b) データ数を n とするとき，「選択ソート」，「バブルソート」，「ヒープソート」の 3 つのアルゴリズムについて，平均時間計算量をオーダー記法（O 記法）で解答用紙の表に記入しなさい．
(c) 以下は，昇順に整列する挿入ソートのプログラムである．空欄（ア）と（イ）に当てはまるコードを記述しなさい．
#include <iostream>using namespace std;
void insertionSort(int arr[], int n) {int i, key, j;for (i = 1; i < n; i++) {key = arr[i];j = i - 1;
while ( （ア） ) {（イ） ;j = j - 1;}
arr[j + 1] = key;}}
int main() {int arr[] = {5, 2, 9, 4, 7, 6, 8, 1, 3, 0};
int n = sizeof(arr) / sizeof(arr[0]);insertionSort(arr, n);cout << "Sorted array: \n";for (int i = 0; i < n; i++) {cout << arr[i] << " ";}return 0;}

問 3 二分木を前順（行きかけ順，preorder）ならびに中順（通りがけ順，inorder）でなぞったときの頂点の訪問順序を以下に示す．この訪問順序を満たす二分木を図示しなさい．この二分木を後順（帰りがけ順，postorder）でなぞったときのノードの訪問順序を答えなさい．
前順：7，2，6，5，1，8，3，9，4

中順：6，2，1，5，8，7，3，4，9

令和 6 年度

３年次編

山梨大学工学部入 学

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

コンピュータ理工学科

試

験 科 目

プログラミング

問 4 以下のプログラムは，図１の重み付き有向グラフの任意の 2 頂点間の最短経路問題を解くプログラムの一部である．また，表１はこのプログラムの実行結果として得た最短距離 dist を表している．表中の INF は経路がないことを表している．空欄（ウ）と（エ）に当てはまるコードを記述しなさい．
#include <iostream>using namespace std;
const int INF = 1e9;
const int N = 6;////

距離が無限大グラフの頂点数

void Floyd_Warshall(int graph[][N]) {int dist[N][N];for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {dist[i][j] = graph[i][j];}}for (int k = 0; k < N; k++) {for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if ( （ウ） ) {（エ） ;}}}}// 最短経路を表示するソースコードは省略されている// ……
}
int main() {int graph[N][N] = {{0, 4, 2, INF, INF, INF},{INF, 0, 5, 10, INF, INF},{INF, INF, 0, INF, 6, INF},{INF, INF, INF, 0, 3, 8},{INF, INF, INF, INF, 0, 2},{INF, INF, INF, INF, INF, 0}};
Floyd_Warshall(graph);
return 0;}

令和 6 年度

３年

次編

入

山梨大学工学部

学

筆記

試

験問

題
No学

科

コンピュータ理工学科

試

験 科 目

1/2

計算機アーキテクチャ

問 1 論理ゲートに関する以下の設問に答えなさい．
(a) 「3 入力多数決回路」として，入力 A，B，C への入力（0 または 1）のうち，2 つ以上に 1 が入力された場合に出力 Y の出力（0 または 1）が 1 となり，それ以外の場合に出力 Y が 0 となる真理値表を示しなさい．
(b) 設問(a)で作成した真理値表に基づき，この 3 入力多数決回路を以下の MIL 記号で示した 2 種類の論理ゲートを使用して（個数制限なし）作成しなさい．
2 入力 AND ゲート

2 入力 OR ゲート

問 2 以下の＜加算とシフトによる乗数回路＞を使った＜符号なし 2 進数の乗算アルゴリズム＞に関する設問に答えなさい．
＜加算とシフトによる乗数回路＞

レジスタ 3キャリ

レジスタ 1

加算・シフトループカウンタ

レジスタ 2

シフトアウト
ビット

制御回路

…
制御信号

(a) ＜符号なし 2 進数の乗算アルゴリズム＞の中の空欄（ア）～（ウ）に当てはまる適切な数値を示しなさい．

＜符号なし 2 進数の乗算アルゴリズム＞
・ 前提：n ビットの被乗数と n ビットの乗数の乗算により 2n ビット（上位をレジスタ 1，下位をレジスタ2）の積を得る．加算の際の最上位ビットからの出力はキャリ（1 ビット）に保持される．右シフトの際の最下位ビットからの出力はシフトアウトビット（1 ビット）に保持される．
・ 初期設定：レジスタ 1 に 0，レジスタ 2 に乗数，レジスタ 3 に被乗数，ループカウンタに n が設定される．
① レジスタ 1 とレジスタ 2 を連結し，右に 1 ビット論理シフトする．
② シフトアウトビットが，(i) （ア）ならば，③へ移行する．
(ii) （イ）ならば，レジスタ 1 を，レジスタ 1 にレジスタ 3 を加算した結果に置き換える．
③ キャリ，レジスタ 1，レジスタ 2 をこの順で連結し，右に 1 ビット論理シフトする．
④ ループカウンタを 1 減らす．
⑤ ループカウンタが，(i) （ウ）でなければ，②へ戻る．
(ii) （ウ）であれば，処理を終了する．

(b) 被乗数を(0010)2，乗数を(0101)2 としたときの，このアルゴリズムに従ったループカウンタ，レジスタ 1，レジスタ2，およびシフトアウトビットの変化の様子を示しなさい．必要であれば，図や表を用いてかまわない．
(c) このアルゴリズムを応用して，2 の補数表示数による符号付き数の乗算アルゴリズムを考える．乗数は正のみに限定する場合，＜符号なし 2 進数の乗算アルゴリズム＞の中のどこをどのように改変すればよいか．該当するアルゴリズム内の番号・記号（①～⑤，(i)(ii)）と改変後の処理内容を示しなさい．

令和 6 年度

３年

次編

入

山梨大学工学部

学

筆記

試

験

問

題
No学

科

コンピュータ理工学科試

験 科 目

2/2計算機アーキテクチャ

問 3 メモリアーキテクチャにおける「キャッシュ（キャッシュメモリ）」に関する以下の設問に答えなさい．
(a) 実行中のプログラムが主記憶装置にアクセスする場合における「空間的参照局所性」および「時間的参照局所性」について，それぞれ 50 字程度で説明しなさい．
(b) 以下の＜説明＞の(1)～(3)は，主記憶装置とキャッシュとの対応（マッピング）の方式に関する説明である．それぞれの説明について，最も適する名称を以下の＜解答群＞の（ア）～（カ）からひとつずつ選んでその記号を示しなさい．
＜説明＞(1) 主記憶アドレスをタグ，インデックス，およびオフセットに分割する．キャッシュディレクトリには，キャッシュブロックに保持されている主記憶ブロックのタグの値を格納する．つぎに，キャッシュブロックのタグとキャッシュディレクトリ内のタグとが一致しているかを調べ，一致する場合，オフセットを用いてデータにアクセスする．
(2) 主記憶アドレスをタグとオフセットに分割する．主記憶アドレスがどのキャッシュブロックに保持されているのかを調べるため，主記憶アドレスのタグとすべてのキャッシュディレクトリのエントリとを比較する．主記憶アドレスのタグがいずれかのキャッシュディレクトリのエントリと一致する場合，オフセットを用いてデータにアクセスする．
(3) 連想度にあわせてキャッシュブロックをグループ化する．主記憶アドレスをタグ，インデックス，オフセットに分解する．それぞれのキャッシュブロックに該当する主記憶アドレスが格納されているかを調べるため，タグとエントリとを比較する．いずれかのエントリと一致する場合，オフセットを用いてデータにアクセスする．
＜解答群＞（ア）セットアソシアティブ方式，（イ）スーパースカラ方式，（ウ）ダイレクトマッピング方式，（エ）メモリインタリーブ方式，（オ）フルアソシアティブ方式，（カ）シングルスカラ方式(c) 要求された主記憶ブロックをキャッシュにロードするとき，キャッシュブロックに空きブロックがない場合，キャッシュのいずれかのブロックとこの主記憶ブロックとを置換する必要がある．この置換のためのブロックを選び出すアルゴリズムの中の「FIFO（first in first out）法」および「LRU（least recently used）法」について，それぞれ 50 字程度で説明しなさい．
(d) キャッシュのアクセス時間が 5 ns，主記憶装置のアクセス時間が 20 ns，キャッシュのヒット率が 95%であるとき，期待できる実効アクセス時間を計算しなさい．ただし，計算過程がわかるように式も示すこと．また，最終的な解答として，必要であれば，小数第 3 位を四捨五入して小数第 2 位までを示すこと．
(e) 2 階層キャッシュにおいて，2 次キャッシュのミス率が 1 次キャッシュのミス率の1⁄6，1 次キャッシュをミスして 2次キャッシュへアクセスする時間が主記憶へアクセスする時間の1⁄5とする．この場合において，キャッシュが 1つのみ（1 階層）と比べ，2 階層キャッシュによって，主記憶へのアクセス（ミスペナルティ）をどの程度に減少できるのかを，導出過程も含めて示しなさい．必要であれば，小数第 3 位を四捨五入した小数第 2 位までの数値を使用すること．

令和 6 年度

３年

次編

入

山梨大学工学部

学

筆 記 試

験

問

題
No学

科

コンピュータ理工学科

試

験 科 目

1/1

情報数学

問 1 1 万人に 1 人の割合で感染する新型のウイルスがある．このウイルスに対する感染検査では，ウイルスに感染していることも感染していないこともどちらも確率 0.99 で正しく判定でき，誤った判定が出る確率は 0.01 である．このとき，以下の設問に答えなさい．解答には計算過程がわかるように式も示すこと．
(a) ある人物が，このウイルスに感染していて，かつこの感染検査を受けたときに陽性（ウイルスに感染している）と判定される確率を求めなさい．答えは四捨五入せずに表しなさい．
(b) このウイルスに感染しているかどうか不明である人物がこの感染検査を受けたとき，陽性と判定される確率を求めなさい．答えは四捨五入せずに表しなさい．
(c) このウイルスに感染しているかどうか不明である人物がこの感染検査で陽性と判定されたとき，実際にウイルスに感染している確率を求めなさい．ただし，答えは小数点以下第 5 位を四捨五入して表しなさい．

問 2 6 種類の記号 A～F の情報源がある．記号の発生確率がそれぞれ
5432
1
1
A: ，B: ，C: ，D: ，E: ，F:
16
16
1616
1616のとき，下の設問に答えなさい．ただし，計算にはlog2 3 = 1.58， log 2 5 = 2.32 を用いてよい．また，計算の答えは小数点以下第 3 位を四捨五入して表しなさい．設問(a)，(c)の解答には計算過程がわかるように式も示すこと．
(a) 情報源のエントロピーを求めなさい．
(b) この情報源のハフマン符号を求めなさい．ただし，解答は符号化の過程がわかるように示すこと．
(c) (b)のハフマン符号の平均符号長及び符号化の効率を求めなさい．

問 3 𝑥0 = 1，𝑦0 = 1 として，数列{𝑥𝑛 }，{𝑦𝑛 } を次の連立漸化式で定義する．このとき，下の設問に答えなさい．
𝑥 = 5𝑥𝑛−1 + 2𝑦𝑛−1{ 𝑛𝑦𝑛 = −𝑥𝑛−1 + 2𝑦𝑛−1(a) 上の漸化式を次式のように表すとき，行列 𝐴 を求めなさい．
𝑥𝑛𝑥𝑛−1(𝑦 ) = 𝐴 (𝑦 )𝑛𝑛−1(b) 𝐴 を対角化する行列 𝑃 と 𝑃 によって得られる対角行列 𝐵 を求めなさい．
(c) 𝐴𝑛 を求めなさい．
(d) 一般項𝑥𝑛 ，𝑦𝑛 を求めなさい．