다음 조건에서 데이터가 순서대로 해시 테이블에 입력된다고 할 때, 원래… | [7급 국가직 자료구조론] 25년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 25년 1회차
다음 조건에서 데이터가 순서대로 해시 테이블에 입력된다고 할 때, 원래 계산된 버킷(bucket)에 저장되지 않는 데이터의 개수는? (단, 충돌(collision)로 인한 오버플로 발생 시, 선형 조사법(linear probing)으로 처리한다)○ 버킷 크기: 13
○ 슬롯(slot) 크기: 2
○ 해시 함수: h(k) = k mod 1321, 33, 8, 19, 76, 58, 27, 83, 30, 44, 7, 73, 2, 66, 85
1
1
2
2
3
3
4
4
해설
버킷 7과 8이 가득 찬 뒤 들어온 73과 85만 다른 버킷으로 밀려나므로 2개이다.
해시값(k mod 13): 21→8, 33→7, 8→8, 19→6, 76→11, 58→6, 27→1, 83→5, 30→4, 44→5, 7→7, 73→8, 2→2, 66→1, 85→7
슬롯이 2개이므로 한 버킷에 2개까지 저장된다.73: 버킷 8(21, 8)이 가득 차 선형 조사로 버킷 9에 저장
85: 버킷 7(33, 7)과 버킷 8이 가득 차 버킷 9에 저장
나머지는 같은 해시값이 2개 이하라 원래 버킷에 저장된다.
오류나 개정된 내용이 보이면 알려주세요