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

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

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

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

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

3年次編入学筆記試験問題（表紙）（一般選抜）
コンピュータ理工学科
プログラミング,計算機アーキテクチャ，情報数学から2科目を選択して解答用紙に解答してください．解答にあたっては,解答用紙の表紙の指示に従ってください．
解答開始の合図の後，各科目の問題用紙が下表中に示すページNo.のとおりに配布されていることを確認してください．用紙に乱丁・落丁がある場合には，手を挙げて試験監督に知らせてください．

科目名

問題用紙の枚数とページNo.

プログラミング

7枚(No.1/7,No.2/7,No.3/7,No.4/7,No.5/7,No.6/7,No.7/7)

計算機アーキテクチャ

2枚(No.1/2,No､2/2)

情報数学

1枚(No.1/1)

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

3年次編入学筆記試験問題
Nol/7学

コンピュータ理工学科科

試験科目

プログラミング

問1(配点:60点）

仮引数として受け取った自然数〃が素数(true)か否(false)かを戻り値として返す関数を作成する課題において,学生Aさんと学生Bさんは,それぞれ以下のコードを記述した(<C言語＞は,<C‑ﾄﾄ言語＞のコードに｢#includeくstdbool.h>｣を加筆したコードである. ).これらのコードについて,以下の設問に答えなさい．
<C++言語＞/*学生Aさん*／boolisPrimeA(constintN)｛
for(inti=2; i*i<=N; ++i) {/*学生Bさん*／boolisPr,imeB(constintN)｛for (inti=2j i<N; ++i)f

if(N%i==6) return「研1;if(N%i==6) return｢扇1;｝｝return[ a];return[てうm;｝

｝

<C言語＞

/*学生Aさん*／/*学生Bさん*／#include<stdbool.h>#include<stdbool.h>boolisPrimeA(constintN)｛

boolisPrimeB(constintN)｛for (inti=2; i<N; ++i)ffor(inti=2j i*iく=Nj ++i) {if(N%i==9) return「研];if(N%i==9) retur､n「研1;｝｝return｢Fm;トeturnFZ71;｝｝(a)空欄(ア)〜(エ)には,題意を満たすために:@true''または"false''が記述されている.この空欄(ア)〜(エ)のそれぞれについて,正しく当てはまるコードを示しなさい．

(b)学生Aさんと学生Bさんの関数のアルゴリズムについて,それぞれの最悪の時間計算量をオーダー記法で示し,どちらの方が効率のよいアルゴリズムなのかを答えなさい．

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

3年次編入学筆記試験問題
No2/7

学科

コンピュータ理工学科

試験科目

プログラミング

問2(配点:70点）

ページNo3/7(同内容のC言語版はページNo4/7)に示したくソースコード＞は,整数の2進数表現とピｯﾄ演算を用いて以下の囲みに示したく部分和問題＞を解くコードである．
＜部分和問題＞

Ⅳ個の正の整数αO"ql'…,αⅣ‑,と正の整数wが与えられたとき'QO'ql' ･･･"αⅣ‑,の中からいくつかを選んで，その和をWとできる(Yes)か否(No)かを出力する．

たとえば,このコードの実行結果として,main( )関数のconstintMが19の場合GGYegと出力され,26の場合G(No''と出力される.このソースコードについて,以下の設問に答えなさい．

(a)関数boolisSubsetSum( )内の//(A)の行の｢bit&(1くくi)｣は,この部分和問題を解くためのどのような処理をおこなっているか.この中の｢&｣および｢くく｣の機能の説明を含めて, 150字程度で説明しなさい．

(b)このソースコードにおける最悪の時間計算量をオーダー記法で示し,その理由を50字程度で示しなさい．

(c)このソースコードのアルゴリズムの時間計算量よりも効率よく部分和問題を解くアルゴリズムとして,時間計算量が0(NW)となるアルゴリズムがある.この時間計算量0(NW)となるアルゴリズムとして,どのようなアルゴリズムが考えられるか.200字程度で説明しなさい.必要であれば,この説明文に加えて図を用いてかまわない．

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

3年次編入学筆記試験問題
No3/7

学

コンピュータ理工学科科

試験科目＜ソースコード(C++言語)>
●Ｑ一

シ０．
︐．ｔ

Ｏ︑０．ユＳ

ａＳｅｒｅｔＣ
Ｓａｕ０ｄｎくｅｍｅａｎ．１Ｃｎ﹃Ｌｇ︒ユＳ
壮 ｕboolisSubsetSum(constinta[],constintN,constintm)｛
for(intbit=6; bit< (1くくN); ++bit)｛
intsum=e;for(inti=e; iくN;++i) {if(bit&(ユくくi)) {sum+=a[i];｝｝if(sum==M) returntrue;

//(A)

｝
returnfalse;｝
intmain()｛constintN= 4JM=19;

constinta[] ＝｛3， 5， 7， 9｝；if(isSubsetSum(a, N,M)) cout<< '0Yes¥nG';
elsecoutくく "No¥n";returne;｝プログラミング令和4年度山梨大学工学部

3年次編入学筆記試験問題
No4/7

学科

コンピュータ理工学科

試験科目＜ソースコード(C言語)>#include<stdio.h>#include<stdbool.h>boolisSubsetSum(constinta[], constintN, constintN)｛
for(intbit=e; bit< (1くくN); ++bit)｛
intsum=6;

for(inti=9; iくN;++i) {if(bit&(1くくi)) {sum+=a[i];｝｝if(sum==N) returntrue;

//(A)

｝
retur､nfalSe;｝
intmain()｛constintN=4JN=19;

constinta[] ={3, 5, 7, 9};if(isSubsetSum(a, N,N)) printf("Yes¥n'');elseprintf(''No¥n");returne;｝プログラミング令和4年度山梨大学工学部

3年次編入学筆記試験問題
No5/7

学科

コンピュータ理工学科

試験科目

プログラミング

問3(配点:70点）
ページNo6/7(同内容のC言語版はページNo7/7)に示したくソースコード＞は,都県名の一覧を処理するソースコードである.このソースコードについて,以下の設問に答えなさい．

(a)このソースコードをコンパイルして実行したときの,標準出力への出力をすべて書き出しなさい．

(b)main( )関数内の｢//(A)｣の行で呼び出されるfuncl( )について,このときに渡される実引数に基づく実行の様子を説明しなさい.必要であれば,図を用いてかまわない．

(c)このソースコードで都県名の一覧に用いられているデータ構造の代わりに配列の使用を考える.設問(b)の処理においては,時間計算量の観点から,配列の方が効率が悪い.その理由を150字程度で説明しなさい．

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

3年次編入学筆記試験問題
No6/7

学科

試験科目

コンピュータ理工学科

プログラミング＜ソースコード(C十卜言語)>

ジｍＤ︲ｑてａシシＳ
ｅ︽届ｒｒｎｏｅ

ｔ・１ｔＣ
ｓｒＣａ
ＯｔｅＤ０
ｏ１ＳＶＳ

●●タ︒工・１．１Ｓ

ｎｎｎｏ工くくくｅｍｅｅｅａ
ｏｄ０ｄ︒．ｎｕｕｕ﹃ＬｍＬ勺Ｌ︽巳Ｃｃｃｎ＃＃＃ｕclassNode{public://左段からのつづきintmain()｛
Nod3np;np=newNode()jnp‑>next=np;

Node*next;

constvectorくstring>pr,efs={ ''Tokyo'',''Kanagawa'',stringpref;
Node(stringp ＝ "） ：next(NULL), pref(p) {}}；,'saitama'､,''Nagano'' };voidfuncl(Node*v, Node*p)｛for (inti=6; i< (int)prefs・size()j ++i) {Node*node=newNode(prefs[i]);funcl(node, np);
func2(np);｝v‑>next=p‑>nextjp‑>next=v;｝●●シ企︑日ログ

１９Ｓｆｔ．１︑ノｍ″

ｈＡ叩ｍａ〃日Ⅱ︑●Ｑ夕Ｙ

ｅ︑ノＤｄｔｎ//右段へ続くＯＸ｝｝

ＮｅdeleteCur;
cur=temp;

︑ＤＵ

Node*cur=n‑>next;

while(cur !=n) {Node*temp=cur,‑>nextj

ｅ一

voidfunc3(Node*n)｛Ｗシretur,ne;｝Ｊ

cOutく<endl;｝

ｎfunc3(np);deletenp;

｝

−−

くく

cur=cur,‑>next;

ｅｅ・Ｊ
０ｄ０ｄ１ノ０ｏＤ０

while(cur !=n) {COutくくcur‑>pref<< "‑>'';＊釦Ｌ︽坐Node*cur=n‑>next;

ｎｎｎ

ｅｃｃ

０．ｎｎ
Ｏｕｕ
Ｎｆ戸十voidfunc2(constNode*n)｛令和4年度山梨大学工学部

3年次編入学筆記試験問題
No7/7

学科

コンピュータ理工学科

プログラミング

試験科目＜ソースコード(C言語)>
ジジ・０︐︽巳ジＤｈｈ０．１ｎＤｈ︒︒○て・て・て●１﹃上・ユｏｑ０ｄｒＳＳＳ
くくくｅｅｅ０ｑ０ｄ０ｄｕｕｕ
ｌ１−１
ＣＣＣ
ｎｎｎｏユ◇１・工＃＃＃#defineCHARNUM19
一

typedefstruct̲Node{//左段からのつづき
intmain()｛
Node*npj
np=malloc(sizeof(Node));strcpy(np‑>pref, ''");

struct̲Node*next;

np‑>next=np;

charpref[CHAR̲NUM];}Node;

constcharprefs[][CHAR̲NUM]={ ､'Tokyo'',,'Kanagawa'',

voidfuncl(Node*v, Node*p)｛''Saitama'',v‑>next=p‑>next;
p‑>next=v;''Nagano'' };｝for (inti=6; iく (int)sizeof(prefs) /sizeof(prefs[6]); ++i) {Node*node=malloc(sizeof(Node));strcpy(node‑>pref, prefs[i]);funcl(node, np);
func2(np);｝voidfunc2(constNode*n)｛
Node*cur=n‑>next;

while(cur !=n) {printf(''%s‑>", cur‑>pref);●●夕︑日〃〃●●夕︑Ｅ″ク

ｊＨｕ叩〃Ｉ︑ｅ︑ノＡ

〃ｌＳ
ＦＴａ

恥匝″

ＳＶ︐︑ノＯｎ
ｅａＺ︑

ｏ工ａ・Ｊ

﹃Ｌ︽十ｎｆｌ叩・ｔＣＸＯｊｅ

句上ｅシａｒ一ｍ︑︲ｐ︲夢ｎｅ〃●Ｑシ｝

一一一︑０︐ノ︑■″〃●●夕returne;ｅ︲︒ｅｏｊＯｑ００．︐ノ０ｎｏＤ０

一コ〃Ｉ︑Ｄｏｆｌｎ//右段へ続くＶ診〃１ｆｔ｝｝

ｎ″ｌｎｎ

Node*cur=n‑>next;

cur=temp;＊︑０﹃ユ︽坐Ｃｅｎｅｕｒｆｆ

voidfunc3(Node*n)
｛

ｅｃｃＣ

ｏ・てｕｕ

ＮＳ一十︽十｝while (cur !=n) {Node*temp=cur‑>next;
fr,ee(cur);０ｄｒｎｎ

cur=cur‑>next;｝
printf(''\n'');令和4年度山梨大学工学部

3年次編入学筆記試験問題
Nol/2

学科

コンピュータ理工学科

試験科目

計算機アーキテクチャ

WHI(配点:120点）

4bitの2進数x=(q,b,c,d)があり,そのIO進数表記は
X==α×23+b×22+c×21+d×20であるとする.論理関数y=/(x)の出力yは,入力xをlO進数表記したとき,Xが4または5の倍数(0は除く)のときにlとなり,それ以外のときに0となる.このとき/ を実現する論理回路を次の手順で設計しなさい．

ｄ−０１０１０１０１０１０１０１０１(b)上記(a)の真理値表をもとに,fに対する主加法標準形(積和標準形)のＣｌハリ０．１．１︿Ｕ︿Ｕ０１．１Ｏ︽Ｕ・１．１ＯＯ１且．１

解答用紙に書き写してから作成しなさい．

６−００００１１１１００００１１１１
α ００００００００１１１１１１１１(a)入力変数α,b,c,dと出力変数yに関する真理値表を,右図の真理値表をV

論理式を求めなさい．

(c)論理関数'を表す論理式の最簡形を,以下の真理値表をもとにカルノー図を作成して求めなさい．
aα〃0001111000011110(d)上記(c)で求めた論理式を計算する論理回路を描きなさい.なお論理素子は4入力1出力のAND素子

心,3入力1出力のAND素子D,4入力l出力のOR素子分, 1入力1出力のNOT素子惨←の4種類だけを使用し,図表記もこの説明文内のものを用いること.使用される素子数は問わない.また入力端子は余らせずに全て接続すること．

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

3年次編入学筆記試験問題
No2/2

学科

試験科目

コンピュータ理工学科

計算機アーキテクチャ

問2(配点:80点）

下図のノイマン型コンピュータに関して以下の設問に答えなさい.なお図中の数値は10進数で表記する.演算には2進法を用いる.プログラムカウンタの値はlずつ増えることにする．レジスタ,メモリアドレス,メモリデータは全て32ビット固定長とする．

(a)以下の説明文の(ア)〜(エ)を埋めなさい．
制御装置の(ア)に格納されているアドレスを主記憶装置の(イ)に送る． （イ)が参照しているアドレスに格納されている命令を(ウ)に取り出し， （エ)に送り解読する． （エ)は命令に応じた制御信号を演算装置に送る.演
算装置は制御信号に従って命令を実行する.命令の実行完了後， （ア)に格納されているアドレスを更新する.以上の作業を繰り返す．

(b)プログラムカウンタと各種レジスタ,メモリの内容が下図の通りである.0100番地から0102番地のﾒﾓﾘに格納したプログラムを実行した際の汎用レジスタ(RO)の値(10進数)の変化を答えなさい．
アドレスバス0100｡prユ｡p

中■■■■■■■■＜命令セット＞：棚巽ﾛﾛﾛﾛﾛﾛ･ﾛロ

命令

命令の意味

LDoprl,opr2

opr2が示すアドレスの内容をoprlが示すレジスタに転送する．

SLoprl,opr2

Oprlがレジスタの値をビット列としてopr2桁だけ左にずらす．

ADDoprl,Opr2

opr2が示すアドレスの内容をoprlが示すレジスタの値に加算する．

注)oP:命令コード,oprl:オペランド1,opr2:オペランド2令和4年度山梨大学工学部

3年次編入学筆記試験問題
Nol/1

学科

コンピュータ理工学科

試験科目

情報数学

問1(配点:100点）
2種の記号AとBの発生確率がそれぞれ0.8と0.2である記憶のない情報源Sを考える.このとき,以下の設問に1「答えなさい.計算には' log210=3.322を用いてよい.また,答えは小数点以下第4位を四捨五入して表しなさ
い．

(a) Sのエントロピーを求めなさい．
(b) Sを2次に拡大してからハフマン符号化をした場合に生成される符号を示しなさいまた, 1情報源記号当たりの平均符号長を求めなさい．

｜(c)AとBの発生確率が偏っているので,ランレングス符号化を行う.ただし,Aは長さ4までのランを考え,Bは長さ1のランのみを考える.すなわち,下記の5種類のランを考える.これをハフマン符号化し,生成される符号を示しなさい.また, 1情報源記号当たりの平均符号長を求めなさい．

｜

AAAA,AAAB,AAB,AB,B(d) (c)の符号化は(b)の符号化に比べて,どれだけ符号化の効率(1情報源記号当たりの平均符号長に対するエントロピーの比)が改善されているか答えなさい．

｜

問2(配点:100点）
行列A=(i")について以下の設問に答えなき 、(a)Aの固有値,固有ベクトルを求めなさい．
｜(b)

(c)

I(三)を の固榊lVl/Ol次結合で表しな誉 、（三）自然数刀に対して,A7'を求めなさい．