다음 조건에 따라 공백 해시 테이블에 키(key) 값 12, 15, 2… | [7급 국가직 자료구조론] 22년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 22년 1회차
다음 조건에 따라 공백 해시 테이블에 키(key) 값 12, 15, 25, 34, 37, 75, 62, 33, 47, 55, 21, 42, 53을 순서대로 삽입할 때, 충돌 횟수가 가장 많은 키 값은? (단, 해시 함수 또는 선형 조사법을 적용하여 찾아간 버킷에 빈 슬롯이 없을 때마다 충돌이 발생한 것으로 본다)○ 해시 함수: h(x) ＝ x mod 13
○ 충돌 해결책: 선형 조사법(linear probing)
○ 해시 테이블의 크기: 13개 버킷(0부터 12까지 인덱스를 가짐)
○ 해시 테이블 버킷당 슬롯 수: 1개
1
21
2
42
3
53
4
62
해설
충돌 횟수가 가장 많은 키는 21이다.
h(x) = x mod 13과 선형 조사로 넣으면 12→12, 15→2, 25→12 충돌 후 0, 34→8, 37→11, 75→10, 62→10부터 4회 충돌 후 1, 33→7, 47→8에서 1회 충돌 후 9, 55→3이다.
21은 8부터 9, 10, 11, 12, 0, 1, 2, 3이 모두 차 있어 9회 충돌 후 4에 들어간다. 이어 42는 3·4에서 2회 충돌 후 5, 53은 1부터 5까지 5회 충돌 후 6에 들어간다.
- 42: 2회 충돌에 그친다.
- 53: 5회 충돌이다.
- 62: 4회 충돌이다.
오류나 개정된 내용이 보이면 알려주세요