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

标签：

• Tokyo-University
• Hash-Table

Author

donguri0912

Description

I.

論理回路に関する以下の問に答えよ．$2$bit の正の値 $A = a_2a_1$ と $B = b_2b_1$ を⼊⼒とする $2$bit⽐較器 $CMP$ を設計したい．⽐較器 $CMP$ は，⼊⼒が $A \ge B$ の時 $1$ を,それ以外の時 $0$ を出⼒ $c$ として出⼒する回路とする．$2$bit⽐較器 $CMP$ は，図 $1$ に⽰す記号で表される．

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

$$c_1 = \left \{ \begin{aligned} 1,\quad a_1 \ge b_1 \\ 0,\quad a_1 < b_1 \\ \end{aligned} \right.$$

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

$$c_2 = \left \{ \begin{aligned} &1,\quad a_2 > b_2 \\ &c_1,\quad a_2 = b_2 \\ &0,\quad a_2 < b_2 \\ \end{aligned} \right.$$

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

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

(4) $2$bit⽐較器 $CMP と$2$bitの$D$フリップフロップ$(D-FF)$を用いて，$D-FF$に$\max(A,B)$を記録する回路を設計したい．この回路を図$1$，図$2$および 図$3$ の記号を⽤いて図⽰せよ．

(5) 問 (4) で設計した回路の⼊⼒ $A$ に $X_i$ を, $B$ に $\max(X_1,X_2,\dots,X_{i-1})$ を配線することで，順序回路 $MAX$ を作成できる．順序回路 $MAX$ を図 $1$ ，図 $2$ および図 $3$ の記号を⽤いて図⽰せよ．ここで，⼊⼒ $B$ の初期値は $00$ であると仮定してよい．

II.

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

(1) 整数 $\{15, 53, 22, 59, 15, 41, 20\}$ をハッシュ関数を⽤いて順に $N = 11$ の table[N]に格納した時，ハッシュテーブルの内容を⽰せ．

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

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

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

/* プログラム 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)

$a_1$	$b_1$	$c_1$
0	0	1
0	1	0
1	0	1
1	1	1

(2)

$c_1$	$a_2$	$b_2$	$c_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)

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