다음의 해시 함수들을 사용하는 이중 해싱(double hashing)에… | [7급 국가직 자료구조론] 18년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 18년 1회차
다음의 해시 함수들을 사용하는 이중 해싱(double hashing)에서 해시 테이블의 크기는 7이며 0부터 6까지의 인덱스를 가진다. h(x)h(x)는 첫 번째 조사 위치를 결정하는 기본적인 해시 함수이고 f(x)f(x)는 충돌 발생 시 조사 위치 간격을 결정하는 추가 해시 함수로서, ii번째 충돌 발생 시 다음 조사 위치를 결정하는 해시 함수는 hi(x)h_i(x)가 된다. 공백 해시 테이블에 일련의 키(key) 값 9, 10, 2, 3, 16, 13, 11을 가지는 레코드들을 순서대로 삽입한 후, 해시 테이블의 위치별 키 값을 보여주는 것은? (단, 해시 테이블 버킷(bucket)당 슬롯(slot) 수는 1개이다)
h(x)=x mod 7h(x) = x \bmod 7
f(x)=5−(x mod 5)f(x) = 5 - (x \bmod 5)
hi(x)=(h(x)+i×f(x)) mod 7h_i(x) = (h(x) + i \times f(x)) \bmod 7
[0][1][2][3][4][5][6]
1
13169101123
2
16139101123
3
31391011216
4
13119102316
해설

삽입 후 해시 테이블은 [0]부터 3, 13, 9, 10, 11, 2, 16이다.

충돌이 없으면 h(x)h(x) 위치에 넣고, 충돌하면 f(x)f(x) 간격으로 다음 위치를 조사한다.

9: h=2 → [2]
10: h=3 → [3]
2: h=2 충돌, f=3 → (2+3) mod 7 = 5 → [5]
3: h=3 충돌, f=2 → [5] 충돌 → (3+4) mod 7 = 0 → [0]
16: h=2 충돌, f=4 → (2+4) mod 7 = 6 → [6]
13: h=6 충돌, f=2 → (6+2) mod 7 = 1 → [1]
11: h=4 → [4]

  • [0]에 13, [6]에 3을 둔 배치: 13은 [1], 3은 [0]에 들어가므로 틀리다.
  • [0]에 16, [1]에 13을 둔 배치: 16은 첫 충돌 후 [6]에 들어가므로 틀리다.
  • [1]에 11, [4]에 2, [5]에 3을 둔 배치: 11은 충돌 없이 [4], 2는 [5]에 들어가므로 틀리다.

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

이어서 풀어보기

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