크기가 11인 해시 테이블이 있고, 해시함수로 h(k) = k mod … | [7급 국가직 자료구조론] 10년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 10년 1회차
크기가 11인 해시 테이블이 있고, 해시함수로 h(k) = k mod 11을 사용한다. 여기서 mod는 모듈로(modulo) 함수를 의미한다. 하나의 해시 값에 대해 두 개씩의 슬롯이 할당되어 있고, 오버플로가 발생하면 다음의 빈 슬롯에 저장하는 선형 조사법(linear probe)을 사용한다고 하자. 데이터가 다음과 같은 순서로 입력된다고 할 때, 원래 계산된 슬롯에 저장되지 않는 데이터의 개수는?54, 27, 70, 55, 13, 2, 37, 23, 33, 44, 45, 77, 56, 6, 9
1
3
2
4
3
5
4
6
해설
원래 계산된 슬롯을 벗어나 저장되는 데이터는 44, 45, 77, 56의 4개이다.
해시값: 54→10, 27→5, 70→4, 55→0, 13→2, 2→2, 37→4, 23→1, 33→0, 44→0, 45→1, 77→0, 56→1, 6→6, 9→9
버킷 0은 55·33, 버킷 2는 13·2, 버킷 4는 70·37로 찬다. 44는 버킷 0이 차서 버킷 1의 남은 칸으로, 45는 버킷 1·2가 차서 버킷 3으로, 77은 버킷 0~2가 차서 버킷 3의 남은 칸으로 간다.
56은 버킷 1~4가 모두 차 있어 버킷 5로 밀려나고, 6과 9는 제자리에 들어간다. 따라서 선형 조사로 밀려난 데이터는 4개다.
오류나 개정된 내용이 보이면 알려주세요