다음과 같은 7개의 모조키(pseudo key) 값을 갖는 키가 순서대… | [7급 국가직 데이터베이스론] 12년 1회차 기출문제 상세 페이지

1[7급 국가직 데이터베이스론] 12년 1회차
다음과 같은 7개의 모조키(pseudo key) 값을 갖는 키가 순서대로 삽입되어 확장성 해싱(extendible hashing)이 구축되었을 때, 전역 깊이(global depth) 값과 R7이 저장되는 버킷(bucket)에 저장된 키의 개수를 합한 값은? (단, 버킷의 크기는 2이고, 삽입을 위한 모조키의 비교는 상위 비트에서 하위 비트 순서로 한다)
<삽입순서>
h(R1)=01101, h(R2)=10011, h(R3)=01000, h(R4)=10010,
h(R5)=00110, h(R6)=00011, h(R7)=11101
1
2
2
3
3
4
4
5
해설

최종 전역 깊이는 2이고 R7이 저장된 버킷의 키는 1개이므로 합은 3이다.

R1, R2로 첫 버킷이 차고 R3 삽입 시 첫 비트로 분할해 0 버킷에 R1·R3, 1 버킷에 R2가 들어가며, R4는 1 버킷에 들어간다.
R5(00110)가 가득 찬 0 버킷에 들어가면서 디렉터리가 두 배가 되어 전역 깊이가 2가 되고, 00 버킷에 R5, 01 버킷에 R1·R3이 남는다. R6은 00 버킷에 들어간다.

R7(11101)은 지역 깊이 1인 버킷(R2·R4)에 들어가야 하는데 가득 차 있으므로, 디렉터리 확장 없이 그 버킷만 분할한다. 10 버킷에 R2·R4, 11 버킷에 R7만 남아 전역 깊이는 그대로 2이다.

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

이어서 풀어보기

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