名古屋工業大学
平成30年度編入学者・転入学者選抜学力検査［問題］
一専門試験一
（情報工学科）
ぎ
試験日時 平成29年6月23日（金）
10：00∼12 00
●
解答上の注意
川解答の際，解答用紙のホチキス止めを外してください。
（2）配布物は，問題冊子1冊，解答用紙3枚，計算用紙1枚です。
（3）解答は各問題番号に対応する解答用紙に解答してください。
（4）解答が解答用紙表面に書ききれない場合は，裏面に続いてもよいが，
その場合は表面の下側が裏面の上側になるようにし，上側2／3のス
ペースに解答を収めてください。
㈲電卓は使用できません。
問題丁 設問すべてについて解答すること。ただし，回路を示す場合には，記号として 図1づに示す論理記号を用いること。
AND OR NOT NAND
図1−1論理記号
1 次の（1）∼（3）の問いについて答えよ。
（1）ある符号付き整数Nを2進数12ビット整数表記の2の補数で表すと110000010011
になる。Nを符号付き10進数，符号付き8進数，符号付き16進数でそれぞれ表せ。
（2）2進数8ビット整数表記の2の補数表現〃二10011100に対して算術シフト演算を行う。
次の（a），（b）について答えよ。
（a）Mを左に2ビットシフトさせるとどのようなビット列になるか。また，それはど のような四則演算に相等するか，以下の例のようにMと四則演算記号と10進数 で表せ。
（b）〃を右に2ビットシフトさせるとどのようなビット列になるか。また，それはど のような四則演算に相等するか，以下の例のように〃と四則演算記号と10進数 で表せ。
（｛ 1』）〃＋9
（3）図仁2に示すANDとORで構成された2段の回路がある。次の（a），（b）について答えよ。
（a）図1−2に示す回路は，NANDのみを用いて2段の等価回路を構成できる。その理
由を，A， B， C， D， Zを用いた論理式を式変形して示せ。その際，どのような法
則を用いて式を変形したのかを明記すること。
（b）図1−2に示すANDとORで構成された2段の回路を， NANDのみを用いた2段の等 価回路で示せ。
A B
Z C
D
H 次の文章を読み，（1）∼（3）の問いについて答えよ。
ある自動車では，方向指示器が点滅しているときの「カチカチ… 」という通知音や，シフ トレバーが後退レンジのときの「ピーピー… 」という後退警告音を，スピーカから電子音で 出している。ただし，後退レンジの警告音は，エンジンがONの状態でのみ鳴る。また，エン ジンがONの状態で，方向指示器が点滅し，かつシフトレバーが後退レンジのときは，方向指 示器の通知音はキャンセルされて鳴らず，後退レンジの警告音のみが鳴る。
以降，エンジンの状態を8，方向指示器の状態をF，シフトレバーの状態をR，方向指示器 の通知音の状態をSで表す。ここで，E（エンジンの状態）， F（方向指示器の状態），川シフト
レバーの状態），5（方向指示器の通知音の状態）と論理値の対応を表1−1に示す。
表1−1E，呪R， Sと論理値の対応
論理値 E（エンジン） F（方向指示器） R（シフトレバー） 5（方向指示器の通知音）
0 OFF 滅（消灯） 後退レンジ以外 止
1 ON
点滅 後退レンジ 鳴
（1）方向指示器の通知音を鳴らす仕組みを論理回路で実現する。E， F， Rを入力，5を出力
とする真理値表を示せ。
（2）5のカルノー図を表1−2の形式で解答用紙に示せ。
表1−2カルノー図
（3）（2）で作成したカルノー図を用いて5の論理回路を簡単化する。次の（a）∼（c ）について
答えよ。
（a）どのように簡単化したら良いか，（2）で作成したカルノー図の一部を丸で囲んで
示せ。
（b）（a）で作成したカルノー図を用いて簡単化した回路を示せ。
（c ）（b）で作成した回路は，より少ない論理素子数で等価な回路を構成できる。その
問題2 設問すべてについて解答すること。プログラム中の［：：：：］で隠された部分の大き
さと，本来の記述の長さとは無関係である。また，必要な＃i nc l ude行は記述されているとみ
なせ。
1 次の文章を読み，（1）∼（3）の問いについて答えよ。
図2−1は整数型の要素を管理するスタックを実装したC言語のプログラムである。pus h 関数はその引数をスタックにその要素として格納する。poρ 関数はスタックから要素を一っ 取り出し，その値を返す。
（1）図2−1の（ア）と（イ）に入る適切な記述を答えよ。ただし，セミコロンを含んでい てはいけない。
（2）プログラム1の実行完了後におけるSTDOUTへの出力結果を答えよ。
（3）スタックのようなデータの出し入れ方式を何と呼ぶか。下記の（あ）∼（え）から選 択せよ。
（あ）LI FO （い）FI FO （う）LI LO （え）LI SP
H 次の文章を読み，（D∼（2）の問いについて答えよ。
図2づは逆ポーランド記法で指定された一桁の数値の四則演算をするC言語のプログラム である。pus h関数およびpop関数の定義は図2−1に記載されているものである。
（1）下記の計算式を逆ポーランド記法で記せ。
（a） 1 ÷ 2 ＊ 3
（b） 1÷ （2＋3）＊4＋5
＃def i ne MAXVAL 50
i nt s P ②3
i nt s t ac k［MAXVA【＿］
voi d pus h（i nt val ue）｛ s t ac k［s p］ val ue三
s p÷÷；
i nt POP（voi d）｛
i nt mai n（voi d）｛
pus h（1）
pus h（2）
pus h（3）
pr i nt f （‘ 1％d￥nま㌧ pr i nt 千（” ％d￥n“ ，
pr i nt f （“ ％d￥n” 3
r et し1pn θ；
popO）
POPO）
popO）
図2−1プログラム1
皿 次の文章を読み，（1）∼（3）の問いについて答えよ。
図2−3はハッシュ表をチェイン法により実装したC言語のプログラムである。
（1）工ns er t 関数はハッシュ表に新たな要素を追加し， Del et e関数はハッシュ表から要素
を削除する。図2づの（ク）∼（シ）に入る適切な記述を答えよ。ただし，セミコロ ンを含んでいてはいけない。
（2）プログラム3の実行完了後におけるSTDOUTへの出力結果を答えよ。
（3）次の文章の（ス）∼（タ）に入る適切な記述を答えよ。ただし，（セ）には，線形探索，
ハッシュ探索，二分探索，二分木探索のいずれかが入る。
ハッシュ表の要素をバケットと呼ぶ。バケットの数をA，登録するデータの数をBと する。Sear c h関数による探索では，まず， Get Has h関数によりハッシュ値を求めてい
る。この計算量は0（画）である。そして，連結リストを［亙コしている。ま
た，Sear c h関数による探索の計算量は，Bに対してAが十分に大きいとき0（［てZΣ ］）
］≠ def i ne HASH LEN 10
］‡ def i ne CODE LEN 10
＃def i ne T工TLE L≡… N 50
t ypede千 s t r ’ uc t Node
c har c ode［CODE＿LEN＋1］
c har t i † ：1e［丁工TLC… ＿Ll … N＋1］
s t r uc て Node ＊next ； Node；
＊t abl e［HASH＿Li … N］
i nt Get Has h（c hap ＊c ode）｛ r et um c ode［CODE＿LEN−1］
voi d 工ni t （）｛ i nt エ；
千or （i ＝0；i ＜HASH LEN；i ＋→・）｛
t abl e［i ］ NULL三
c har ＊Seapc h（c har ＊c ode）｛
Node＊n；
i nt h三
Get Has h（c ode）
f or （n＝てabl e［h］j nl ＝NULL；n＝n−＞next ）｛
i f （s t r c mp（n−＞c ode， c ode）＝＝②）｛ r et ur n n−＞t i てl e；
voi d 工ns er t （c hap ＊c ode，
Node＊n3 i nt
i f （Seapc h（c ode）
c har ＊t i t l e）｛
NULL）｛
i nt mai n（voi d）｛
Node＊n；
エni t O
工ns er ’ t C81234567890‘ ㌧
工ns er t （’ ‘ 0123456789“ 戊
工ns er t C10123454321’ ㌧
工ns er t （」’ 1234543210’ ‘ ，
us a
〕pn
“ c hn” ） “ t wn“ j
ヂop（n ＝t abl e［0］；n！＝NULL三n＝n−＞next ）｛
ppi nt 千（” ％s 告％5￥n” 。
n−＞c ode， n−＞t i t l e）
問題3 設問すべてについて解答すること。答えだけでなく解に至る過程を明記すること。
1 ある情報源から5種類の通報｛んB，o， D， E｝が独立に生起しているとする。この情報源から
の出力をアルファベット｛0，1｝からなる語頭符号により符号化することを考える。このと
き，次の（1）∼（3）の問いについて答えよ。
（1）各通報に対して，表3づのように生起確率と符号語が定まっているとする。符号語は 最短符号を構成するものである。ハフマン符号化を行い，残りの（ア），（イ），（ウ）
に入るべき符号語を求めよ。
表3−1情報源と符号語
通報 生起確率 符号語
A
0．4 （ア）
8 0．05
（イ）
o 0．2 （ウ）
D 0．1 1101
E 0．25 10
（2）（1）で求めた符号の平均符号語長Lを求めよ。
（3）（1）で求めた符号がクラフトの不等式を満足することを示せ。
1 ある病気に3種類のサブタイプが存在するとする。それぞれのサブタイプをa型，b型， c 型とし，この病気の患者全体に対する，男女とサブタイプの組み合わせの割合が表3づ の通りであるとする。男女の別を表す確率変数をXとし，男性の場合X＝m，女性の場合 X＝ψ と表現するとする。また，サブタイプを表す確率変数をγ とし，それぞれの生起を γ ＝a，γ ＝b，γ ＝oと表現する。このとき，次の（1）∼（4）の問いについて答えよ。ただ
し，010920＝0とする。l og23はそのまま残し，分数を最も簡単な形にして答えよ。
表3−2性別とサブタイプ
a型 b型 c 型
男性 1／8 1／2 1／8
（1）エントロピー駅y）を求めよ。
（2）条件付き確率P（γ i X）をすべての万とγ の組み合わせPOと∂1炸m）， P（ピ例炸m），
P（｝乞c l 右加）， POと∋右め， P（ピ川胸の， P（1なol 炸めについて示せ。
（3）条件付きエントロピー〃（γ i x）を求めよ。 （4）相互情報量∫ （γ ；Dを求めよ。
田 図3−1に示す通信路において送信記号Xの発生確率がP（ノ←0）＝a，P（た1）＝1−∂であ
るとする。この通信路について，次の（1）∼（3）の問いについて答えよ。ただし010920＝0
とする。10923はそのまま残し，分数を最も簡単な形にして答えよ。
0
1
0
1）（11… ＝el X… ＝0） ＝ 1／4
θ γ
／）（｝とθ1炸1） ＝ 1／4
1 P（H1炸1） ＝ 3／4
図3−1通信路
（1）受信記号γ が各値をとる確率PO伝0），／）0と1），ρ 0乞e）をaを使って示せ。
（2）エントロピー〃（りを∂の式として示せ。ただし，aを含む項については以下の2元エ
ントロピー関数パa）を用いて最も簡略化した形で答えを示すこと。
ゐ（a） ＝ − a l og2∂ 一 （1−a） 1092（1−∂）
