東京大学 工学系研究科 電気系工学専攻 2020年8月実施 問題4 情報工学II

Author

donguri0912

Description

I.

論理回路に関する以下の問に答えよ．bit の正の値 と を⼊⼒とする bit⽐較器 を設計したい．⽐較器 は，⼊⼒が の時 を,それ以外の時 を出⼒ として出⼒する回路とする．bit⽐較器 は，図 に⽰す記号で表される．

(1) , を⼊⼒として，以下に⽰す を出⼒する bit⽐較器 の真理値表を書け．

(2) 問 (1) に⽰した と , , を⼊⼒として，以下に⽰す を出⼒する bit⽐較器 の真理値表を書け．

(3) 問 (1) および (2) で⽰した⽐較器 の回路を組合せることで bit ⽐較器 を作成することができる. この回路を図 に⽰す記号を⽤いて図⽰せよ．

次に，bit⽐較器 を⽤いて順序回路 を設計したい． は，bit の正の値 , , を順に⼊⼒すると，⼊⼒値の最⼤値を出⼒する．以下の⼿順で の回路を設計せよ．

(4) bit⽐較器 2D(D-FF)D-FF\max(A,B)123$ の記号を⽤いて図⽰せよ．

(5) 問 (4) で設計した回路の⼊⼒ に を, に を配線することで，順序回路 を作成できる．順序回路 を図 ，図 および図 の記号を⽤いて図⽰せよ．ここで，⼊⼒ の初期値は であると仮定してよい．

II.

ハッシュテーブルを⽤いたデータの格納と管理に関する以下の問に答えよ． 個の要素を持つハッシュテーブル table[N]により正の整数を管理する⽅法について考える．ここで，正の整数 をハッシュテーブルに格納する位置を定める際に⽤いるハッシュ関数を とする．正の整数が同じハッシュ値を持つ場合は，プログラム 1に⽰すデータ構造 nodeの連結リストにより管理する．

(1) 整数 をハッシュ関数を⽤いて順に の table[N]に格納した時，ハッシュテーブルの内容を⽰せ．

(2) プログラム 2 は，正の整数 をtable[N] に格納する関数 insert(x) を⽰している．プログラム 2 の空欄を埋めて ⾔語のプログラムを完成させよ．

(3) search(x) は，与えられた正の整数 の値が table[N] に格納されている場合に を, そうでない場合は を返す関数とする．関数 search(x) を ⾔語で記述せよ．

(4) table[N] に格納されている正の整数 を削除する関数を記述する際に留意すべき点を数⾏で述べよ．

/* プログラム 1 */ 
struct node {
    int  value; 
    struct node *next;
}; 
struct node *table[N];

/* プログラム 2 */ 
int H(int x) { return(x % N); } void insert(int x) {
    struct node *new, *check; new = (struct node *)malloc(sizeof (struct node)); new -> value = x; new -> next = NULL; check = table[H(x)]; 
    /* ------------------------------------------- */
    /* |                                         | */
    /* |                 BLANK                   | */
    /* |                                         | */
    /* ------------------------------------------- */
} 

Kai

I.

(1)

0	0	1
0	1	0
1	0	1
1	1	1

(2)

0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

(3)

PCで書くのが面倒だったので載せませんがカルノー図を書きます。

(4)

(5)

II.

(1)

ハッシュテーブルに一般的な書き方があるわけではないと思うので、書き方はなんでもいいと思う。

(2)

if(check == NULL) {
  table[H(x)] = new;
} else {
  while(check->next != NULL) check = check->next;
  check->next = new;
}

(3)

int search(int x) {
  struct node *check = table[H(x)];
  while(check != NULL) {
    if(check->value == x) return 1;
    check = check->next;
  }
  return 0;
}

(4)

を格納するノードを消す際にその子ノードを消さずに親につなげること。 また、 を格納するノードのメモリを開放すること。