基本情報技術者令和5年[科目B]問4 ハッシュ表の内容

基本情報技術者令和5年 [科目B]問4

問4

次の記述中の　に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は1から始まる。

　関数 add は，引数で指定された正の整数 value を大域の整数型の配列 hashArray に格納する。格納できた場合は true を返し，格納できなかった場合は false を返す。ここで，整数 value を hashArray のどの要素に格納すべきかを，関数 calcHash1 及びcalcHash2 を利用して決める。
　手続 test は，関数 add を呼び出して，hashArray に正の整数を格納する。手続 test の処理が終了した直後の hashArray の内容は，　である。

〔プログラム〕

{－1, 3, －1, 18, 11}
{－1, 11, －1, 3, －1}
{－1, 11, －1, 18, －1}
{－1, 18, －1, 3, 11}
{－1, 18, 11, 3, －1}

分類

アルゴリズムとプログラミング » データ構造及びアルゴリズム

正解

エ

解説

手続 test の最初で、配列 hashArray は{－1, －1, －1, －1, －1}に初期化されています。3回の関数 add では、以下のように値が格納されていきます。

add(3)

i ← calcHash1(3) が実行される
value=3、hashArrayの要素数が5なので、calcHash1(3) は、3÷5の余りに1を加えた数、すなわち4を返す
hashArray[4] = -1 なので、hashArray[4] に3を格納して終了する

add(18)

i ← calcHash1(18)
value=18、hashArrayの要素数が5なので、calcHash1(18) は、18÷5の余りに1を加えた数、すなわち4を返す
hashArray[4] ≠ -1 なので、else文に飛び、i ← calcHash2(18) が実行される
value + 3 = 21、hashArrayの要素数が5なので、calcHash2(18) は、21÷5の余りに1を加えた数、すなわち2を返す
hashArray[2] = -1 なので、hashArray[2] に18を格納して終了する

add(11)

i ← calcHash1(11)
value=11、hashArrayの要素数が5なので、calcHash1(11) は、11÷5の余りに1を加えた数、すなわち2を返す
hashArray[2] ≠ -1 なので、else文に飛び、i ← calcHash2(11) が実行される
value + 3 = 14、hashArrayの要素数が5なので、calcHash2(11) は、14÷5の余りに1を加えた数、すなわち5を返す
hashArray[5] = -1 なので、hashArray[5] に11を格納して終了する

以上より、hashArray[4]には3、hashArray[2]には18、hashArray[5]には11が、それぞれ格納されます。したがって、手続 test 終了後の配列 hashArray の内容は {－1, 18, －1, 3, 11} になっています。よって正解は「エ」です。