名古屋工業大学工学研究科工学専攻情報工学系 2022年8月実施計算機ソフトウェア（データ構造とアルゴリズム）

标签：

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

I　次の (1)〜(2) の問いについて答えよ。

(1) ハッシュ法による配列へのデータ格納と探索に関する以下の (ア)〜(オ) の記述の正誤を，それぞれ正か誤で答えよ。ただしハッシュ関数の評価は $O(1)$ とする。また，ここでのハッシュ法はオープンアドレス法と線形探査に基づくものとする。

(ア) ハッシュ法では常に配列中の連続した領域にデータが格納される。

(イ) ハッシュ法ではデータの格納と探索にかかる計算量が配列内において空である要素数に依存する。

(ウ) 格納され得るすべてのデータに対してハッシュ関数の値が重複せず，また，同一のデータが複数回格納されることもないとする。このとき，十分な配列サイズが確保されているなら，ハッシュ法はデータの格納と探索をともに $O(1)$ で実行できる。

(エ) 異なるデータに対してハッシュ関数の値が重複するとハッシュ法を利用することはできない。

(オ) データの探索は最悪の場合でも $O(\log_2 n)$ となる。ただし， $n$ は格納する配列のサイズとする。

(2) 図1は，線形探査を用いたオープンアドレス法に基づくハッシュ表の構築及び探索のための擬似コードである。 $H$ は要素数6の配列とする。格納するデータは正の整数とし， $\varnothing$ は空を意味する。以下の (ア)〜(エ) について答えよ。

Insert(x)
    i <- 0
    while (true) {
        j <- Hash(x,i)
        if ([a]) {
            [b]
            return [c]
        }
        i <- i + 1
        if ([d]) return -1
    }

Search(x)
    i <- 0
    while (true) {
        j <- Hash(x,i)
        if (i = 6 or H[j] = ∅) return -1
        if (H[j] = x) return j
        i <- i + 1
    }

Hash(x,i)
    return (x + i) mod 6

図1：ハッシュ表の構築及び探索アルゴリズム

(ア) 配列 $H$ の各要素が $H[0]=8,H[1]=\varnothing,H[2]=2,H[3]=3,H[4]=10,H[5]=9$ であるとする。図1の $\operatorname{Search}(x)$ を $x=3,9,4,8$ に対して実行した際に， $\operatorname{Search}(x)$ が返す値と $\operatorname{Search}(x)$ 内で return が実行される瞬間の変数 $i$ の値をそれぞれ答えよ。

(イ) 図1の $\operatorname{Insert}(x)$ はハッシュ法によりデータの格納を行う関数であり，格納できた際は格納した配列の添字を，格納できなかった際は $-1$ を返すとする。空欄 (a)〜(d) に入るべき適切な処理を以下の (A)〜(J) からそれぞれ選べ。

選択肢	処理	選択肢	処理
(A)	`i`	(B)	`j`
(C)	`i = 6`	(D)	`j = 6`
(E)	`H[i] = ∅`	(F)	`H[j] = ∅`
(G)	`H[i] <- x`	(H)	`H[j] <- x`
(I)	`j <- j + 1`	(J)	`-1`

(ウ) いま配列 $H$ 中のいずれかの3要素に値が入っており，残りの3要素は $\varnothing$ が入っているとする。どの要素に値が入っているかは等確率であるとしたとき（つまり，任意の要素に値が $1/2$ の確率で格納されているとしたとき）， $H$ に格納されていないある任意の正の整数 $x$ に対して， $\operatorname{Search}(x)$ 内で return が実行される瞬間に $i=2$ となっている確率を求めよ。

(エ) 図1の $\operatorname{Hash}(x,i)$ の2行目を「 $\operatorname{return}\ (x+i(1+a(x\bmod2)))\bmod6$ 」と変更したとする。ただし， $a$ は1以上の整数とする。以下の (a)，(b) に答えよ。

(a) $a=1$ の場合に $\operatorname{Hash}(3,0),\operatorname{Hash}(3,1),\ldots,\operatorname{Hash}(3,5)$ の返す値を答えよ。

(b) 一般に，1以上の整数 $x,y,z$ に対して $(x+iy)\bmod z$ は $y$ と $z$ が互いに素なら，その時に限り $i=0,1,\ldots,z-1$ に対して， $0,1,\ldots,z-1$ を並び替えた値をとる。任意の正の整数 $x$ に対して $H[\operatorname{Hash}(x,i)]$ を $i=0,1,\ldots,5$ で探査したとき，配列 $H$ のすべての要素を探査できる最小の $a$ を答えよ。

题目描述

I　回答以下 (1)、(2) 问。

(1) 关于利用哈希法向数组存储数据与查找数据，分别判断下列 (ア) 至 (オ) 陈述正确或错误。假设哈希函数求值为 $O(1)$ ，这里的哈希法采用开放寻址和线性探测。

(ア) 哈希法总是将数据存入数组中的连续区域。

(イ) 哈希法存储与查找数据所需的计算量依赖于数组中空元素的数量。

(ウ) 假设所有可能存储的数据的哈希值互不重复，且不会多次存入同一个数据。如果有足够大的数组，哈希法的数据存储与查找均可在 $O(1)$ 时间完成。

(エ) 不同数据的哈希值重复时，就不能使用哈希法。

(オ) 即使最坏情况下，数据查找也是 $O(\log_2 n)$ 。其中 $n$ 是存储数组的大小。

(2) 图1为采用线性探测的开放寻址哈希表构建与查找伪代码。 $H$ 是含6个元素的数组，存储的数据为正整数， $\varnothing$ 表示空。回答下列 (ア) 至 (エ) 问。

Insert(x)
    i <- 0
    while (true) {
        j <- Hash(x,i)
        if ([a]) {
            [b]
            return [c]
        }
        i <- i + 1
        if ([d]) return -1
    }

Search(x)
    i <- 0
    while (true) {
        j <- Hash(x,i)
        if (i = 6 or H[j] = ∅) return -1
        if (H[j] = x) return j
        i <- i + 1
    }

Hash(x,i)
    return (x + i) mod 6

图1：哈希表构建与查找算法

(ア) 设 $H[0]=8,H[1]=\varnothing,H[2]=2,H[3]=3,H[4]=10,H[5]=9$ 。分别对 $x=3,9,4,8$ 执行图1的 $\operatorname{Search}(x)$ ，求返回值及执行 return 瞬间变量 $i$ 的值。

(イ) 图1的 $\operatorname{Insert}(x)$ 利用哈希法存储数据，成功时返回所存入数组位置的下标，失败时返回 $-1$ 。请分别从 (A) 至 (J) 中选择适合填入 (a) 至 (d) 的处理。

选项	处理	选项	处理
(A)	`i`	(B)	`j`
(C)	`i = 6`	(D)	`j = 6`
(E)	`H[i] = ∅`	(F)	`H[j] = ∅`
(G)	`H[i] <- x`	(H)	`H[j] <- x`
(I)	`j <- j + 1`	(J)	`-1`

(ウ) 假设数组 $H$ 的某3个元素存有值，其余3个元素为 $\varnothing$ 。各组被占用位置等可能（也就是说，任意元素被存入值的概率为 $1/2$ ）。对于某个没有存储在 $H$ 中的正整数 $x$ ，求 $\operatorname{Search}(x)$ 执行 return 瞬间 $i=2$ 的概率。

(エ) 将图1的 $\operatorname{Hash}(x,i)$ 第2行改为「 $\operatorname{return}\ (x+i(1+a(x\bmod2)))\bmod6$ 」，其中 $a$ 是不小于1的整数。回答 (a)、(b)。

(a) 当 $a=1$ 时，求 $\operatorname{Hash}(3,0),\operatorname{Hash}(3,1),\ldots,\operatorname{Hash}(3,5)$ 的返回值。

(b) 一般地，对不小于1的整数 $x,y,z$ ，当且仅当 $y,z$ 互素时， $(x+iy)\bmod z$ 在 $i=0,1,\ldots,z-1$ 时依次取 $0,1,\ldots,z-1$ 的某种排列。求最小的 $a$ ，使对任意正整数 $x$ ，依次以 $i=0,1,\ldots,5$ 探测 $H[\operatorname{Hash}(x,i)]$ 时，都能探测数组 $H$ 的全部元素。

Kai

(1)

(ア) 誤。ハッシュ値に応じて格納位置が決まるため、全データが一つの連続領域に入るとは限らない。
(イ) 正。空要素が少なく、すなわち負荷率が高くなるほど、衝突後に必要な探査回数が増えやすい。厳密な回数はデータの配置にも依存する。
(ウ) 正。衝突がなければ、ハッシュ値の計算と 1 回の配列アクセスで格納・探索できる。
(エ) 誤。線形探査などの衝突解決法を用いれば格納できる。
(オ) 誤。最悪の場合は配列の全要素を調べるため、時間計算量は $\Theta(n)$ となる。

したがって、

\boxed{\text{(ア) 誤、(イ) 正、(ウ) 正、(エ) 誤、(オ) 誤}}

である。

(2)

(ア)

線形探査で調べる添字を順に追う。

$x$	調べる添字	返り値	`return` 時の $i$
3	$3$	$3$	$0$
9	$3,4,5$	$5$	$2$
4	$4,5,0,1$	$-1$	$3$
8	$2,3,4,5,0$	$0$	$4$

よって、

\boxed{(3,0),\ (5,2),\ (-1,3),\ (0,4)}

である。各組は「返り値、 $i$ 」の順である。

(イ)

空要素を発見したとき、その添字 $j$ に $x$ を格納して $j$ を返す。6 箇所を探査しても空きがなければ失敗とする。したがって、

(a) H[j] = ∅        : (F)
(b) H[j] <- x       : (H)
(c) j               : (B)
(d) i = 6           : (C)

となる。

(ウ)

3 個の格納位置を $\binom63$ 通りから一様に選ぶ場合を考える。最初の二つの探査位置が使用中で、三つ目が空のときに限り、 $i=2$ で return が実行される。使用中の 3 要素の選び方は全部で

\binom{6}{3}=20

通りである。最初の二位置を使用中、三位置目を空と固定すると、残りの使用中 1 要素は他の 3 位置から選べるので 3 通りである。よって、求める確率は

\boxed{\frac{3}{\binom{6}{3}}=\frac{3}{20}}

となる。

各位置が使用中となる周辺確率 $1/2$ だけを条件とする場合、この答えは一意には定まらない。例えば、格納位置を $\{0,2,4\}$ と $\{1,3,5\}$ から等確率で選べば、各位置の周辺確率は $1/2$ であるが、二つ連続した探査位置が使用中になることはなく、求める確率は $0$ となる。 $3/20$ は格納位置の組を一様に選ぶモデルでの値である。

(エ)

1.

$a=1$ 、 $x=3$ では $x\bmod2=1$ なので、探査幅は $1+a=2$ である。したがって、

\operatorname{Hash}(3,i)=(3+2i)\bmod6

より、

\boxed{3,5,1,3,5,1}

となる。

2.

$x$ が偶数なら探査幅は常に 1 であり、6 要素すべてを探査できる。 $x$ が奇数なら探査幅は $1+a$ であるため、全要素を探査する必要十分条件は

\gcd(1+a,6)=1

である。 $a=1,2,3$ では探査幅がそれぞれ $2,3,4$ となり 6 と互いに素ではない。 $a=4$ では探査幅が 5 となり、 $\gcd(5,6)=1$ である。したがって、

\boxed{a=4}

が最小である。

Author​

Description​

题目描述​

Kai​

(1)​

(2)​

(ア)​

(イ)​

(ウ)​

(エ)​

1.​

2.​

Reference​

Author

Description

题目描述

Kai

(1)

(2)

(ア)

(イ)

(ウ)

(エ)

1.

2.

Reference