問題プレビューID: 6d7c00d0基本情報技術者試験 午前免除試験 2018年1月28日

問 6
基本情報技術者試験 午前免除試験 2018年1月28日

次の規則に従って配列の要素 A[0], A[1], …, A[9] に正の整数 k を格納する。k として 16, 43, 73, 24, 85 を順に格納したとき,85 が格納される場所はどこか。ここで,x mod y は,x を y で割った剰余を返す。また,配列の要素は全て 0 に初期化されている。

〔規則〕

  1. A[k mod 10] = 0 ならば,k を A[k mod 10] に格納する。
  2. (1)で格納できないとき,A[(k+1) mod 10] = 0 ならば,k を A[(k+1) mod 10] に格納する。
  3. (2)で格納できないとき,A[(k+4) mod 10] = 0 ならば,k を A[(k+4) mod 10] に格納する。
解説

正解は「エ」です。

ハッシュ法(剰余法)で,衝突した場合は +1,さらに衝突した場合は +4 の位置を調べる方式です。順に格納していきます。

  • 16:16 mod 10 = 6 なので A[6] = 16
  • 43:43 mod 10 = 3 なので A[3] = 43
  • 73:73 mod 10 = 3 は A[3] が使用済み。(73+1) mod 10 = 4 なので A[4] = 73
  • 24:24 mod 10 = 4 は A[4] が使用済み。(24+1) mod 10 = 5 なので A[5] = 24
  • 85:85 mod 10 = 5 は A[5] が使用済み。(85+1) mod 10 = 6 は A[6] が使用済み。(85+4) mod 10 = 9 なので A[9] = 85

したがって,85 は A[9] に格納されます。

  • ア: A[3] には 43 が入っています。
  • イ: A[5] には 24 が入っています。
  • ウ: A[6] には 16 が入っており,85 の 2 回目の候補位置ですが空きではありません。
  • エ: 上記のとおり A[9] が正しい格納場所です。

関連問題

本文が同じ・似ている問題を表示しています