버킷 용량 C=2인 버킷들의 주소 공간이 0 \sim (N-1)인 해시… | [7급 국가직 데이터베이스론] 20년 1회차 기출문제 상세 페이지

1[7급 국가직 데이터베이스론] 20년 1회차
버킷 용량 C=2C=2인 버킷들의 주소 공간이 0∼(N−1)0 \sim (N-1)인 해시에서 키를 KK로 하는 해시 함수 h(K)=K mod Nh(K) = K \bmod N이고, NN 값은 5이다. 이때 일련의 KK 값들이 3, 5, 7, 9, 11, 13, 18, 14 순서로 삽입된 후 4번 버킷의 값은? (단, 버킷에서의 충돌은 충돌 발생 버킷 주소 ii에 대하여 (i+1) mod N(i+1) \bmod N을 통해 지정하는 선형탐색 개방 주소법을 이용하여 해결한다)
1
5, 14
2
3, 13
3
9, 14
4
9, 18
해설

삽입이 끝난 뒤 주소 4 버킷에는 9, 18이 저장된다.

홈 주소 K mod 5K \bmod 5에 따라 3→3, 5→0, 7→2, 9→4, 11→1, 13→3으로 저장되며, 버킷 3은 3과 13으로 용량 2가 가득 찬다.

18은 홈 주소 3이 가득 차 선형 탐색으로 다음 주소 4에 들어가 9와 함께 저장되고, 14는 홈 주소 4가 가득 차 (4+1) mod 5=0(4+1) \bmod 5 = 0인 버킷 0에 5와 함께 저장된다.

  • 5, 14는 버킷 0의 최종 값이다.
  • 3, 13은 버킷 3의 최종 값이다.
  • 9, 14는 18이 먼저 버킷 4를 채워 14가 버킷 0으로 넘어간다는 점을 놓친 조합이다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 데이터베이스론] 20년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 데이터베이스론 기출문제 암기장 전체 보기