다음 그림은 키 값에 대한 해시함수 h의 결과와, 확장 가능 해싱(extendible hashing) 기법에 의해 최초에 키 값 4, 8, 9를 순서대로 입력하여 수행한 결과이다. 이후 키 값 11, 7, 2, 5, 13을 순서대로 입력하는 경우에 대한 설명으로 옳은 것은? (단, 버킷(bucket)의 크기는 2이고 입력된 키 값은 삽입한 순서대로 버킷 내의 왼쪽부터 저장된다)
키 값 | 해시함수 h(키 값) |
4 | 1010 |
8 | 0001 |
9 | 1101 |
11 | 1110 |
7 | 0110 |
2 | 1111 |
5 | 0111 |
13 | 0101 |
- ①키 값 7이 삽입될 때 새 버킷이 생성된다.
- ②모든 키 값이 삽입된 후 버킷의 개수는 5이다.
- ③모든 키 값이 삽입된 후 디렉토리 인덱스 010이 가리키는 버킷에는 2개의 키 값이 존재한다.
- ④모든 키 값이 삽입된 후 디렉토리 인덱스 111이 가리키는 버킷의 첫 번째 키 값은 11이다.
선지를 골라 바로 채점해 보세요.
정답 ④
출처: 인사혁신처 공개 기출(공공데이터포털, 이용허락 제한 없음)