問題プレビューID: 5a14e3e6基本情報技術者試験 午前免除試験 2021年1月24日

問 9
基本情報技術者試験 午前免除試験 2021年1月24日

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

〔規則〕

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

正解は「エ」です。

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

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

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

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

関連問題

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