東京大学 工学系研究科 電気系工学専攻 2021年8月実施 問題4 情報工学II
Author
Description
I.
論理回路に関する以下の問に答えよ.回路図に使⽤する論理ゲートを図
(1) 図
- (1-i) 図
の X は,A, B の和 D とキャリー出⼒ E を⽣成する半加算器である.D, E の真理値表を⽰せ.また,図 の AND, OR, NOT ゲートのみを⽤いて X の回路を⽰し,クリティカルパスとその遅延を⽰せ. - (1-ii) 図
のすべてのゲートが使⽤できるとき,クリティカルパスの伝搬遅延時間がより⼩さい X の回路を⽰せ.また,クリティカルパスとその伝搬遅延時間を⽰せ. - (1-iii) Y,Z について,CI, D, E を⼊⼒,S, CO を出⼒とする真理値表を⽰し,クリティカルパスの伝搬遅延時間が最⼩となる回路を⽰せ.図
のすべてのゲートを使⽤してよい.また,X に問(1-ii)の回路を使⽤した場合のこの全加算器のクリティカルパスとその伝搬遅延時間を⽰せ.
以下では,半加算器は問(1-ii)で作成したもの,全加算器は問(1-iii)で作成したものを使⽤する.
(2) 全加算器を⽤いてキャリー⼊⼒を持つ符号なし
(3) 図
- (3-i) 積 p のビット幅 N を答えよ.
- (3-ii) 半加算器,全加算器を少なくともひとつずつ使⽤してこの乗算器を作成し,回路図を⽰せ.ただし,クリティカルパスの伝搬遅延時間をなるべく⼩さくすること.図
,図 のすべての記号を⽤いてよい.また,クリティカルパスとその伝搬遅延時間を⽰せ.

II.
学生の学籍番号(sid)を,
(1) プログラム add()
を⽰す.空欄 A, B, C を埋めて完成させよ.
(2) 空の⽊に add()
を使い以下の順で新しいノードを追加したときの
- (2-i) sid = 1040, 1042, 2001, 2004, 2010, 2012
- (2-ii) sid = 2001, 1042, 2010, 1040, 2004, 2012
(3) プログラム enumerate()
を⽰す.空欄 D, E, F, G を埋めて完成させよ.
(4) ノードを
(5) 既に add()
の振る舞いと問題点を簡潔に説明せよ.
(6) 追加する sid をあらかじめ⽤意された⼗分に⼤きな配列に先頭から追加順に格納する⽅法と⽐べ,

/* プログラム1 */
typedef struct node {
int sid;struct node *left;struct node *right;
} node_t;
/* プログラム2 */
node_t *add(node_t *root, node_t *new){
if(root == NULL){
return A ;
}
if(root->sid > new->sid){
B ;
}
else if(root->sid < new->sid){
C ;
}
return root;
}
/* プログラム3 */
void enumerate(node_t *root){
if( D ){
E ;
}
printf("%d¥n", root->sid);
if( F ){
G ;
}
return;
}
Kai
I.
(1)
(1-i)

クリティカルパスは太線で示した
遅延は共に
(1-ii)

クリティカルパスは太線で示した
遅延は共に
(1-iii)

クリティカルパスは太線で示した
遅延は共に
(2)

クリティカルパスは太線で示した
(1-iii) の全加算器で CI から CO の伝搬遅延時間は
これらのクリティカルパスの伝搬遅延時間は共に
(3)
(3-i)
よって積
よって
(3-ii)

クリティカルパスは太線で示した
(1-ii) の全加算器で A から CO の伝搬遅延時間は
これらのクリティカルパスの伝搬遅延時間は共に
II.
(1)
解答は分かりやすいよう空欄だけでなくその行ごと書いてある。
// A
return new;
// B
root->left = add(root->left);
// C
root->right = add(root->right);
(2)
(2-i)

(2-ii)

(3)
解答は分かりやすいよう空欄だけでなく周りごと書いてある。
// D, E
if (root->left != NULL) {
enumerate(root->left);
}
// F, G
if (root->right != NULL) {
enumerate(root->right);
}
(4)
(5)
同じ sid を持つノードは追加されない。 問題点は一つの sid を複数個保持することはできない。
(6)
要素数を