해시함수(hash function)로 h(k)=k mod 7을 사용하고… | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 12년 1회차
해시함수(hash function)로 h(k)=k mod 7을 사용하고, 선형탐색(linear probing) 기법을 이용하여 충돌을 해결하고자 한다. 키가 3, 10, 5, 9, 12 순서대로 입력되었을 때, 생성된 해시테이블은?
1
[0][1][2][3][4][5][6]
1293105
2
[0][1][2][3][4][5][6]
1231059
3
[0][1][2][3][4][5][6]
9103125
4
[0][1][2][3][4][5][6]
9310512
해설

선형탐색으로 충돌을 해결하면 해시테이블은 [2]=9, [3]=3, [4]=10, [5]=5, [6]=12가 된다.

3 → 3 mod 7 = 3, [3]에 저장
10 → 10 mod 7 = 3, 충돌 → 다음 빈 칸 [4]에 저장
5 → 5 mod 7 = 5, [5]에 저장
9 → 9 mod 7 = 2, [2]에 저장
12 → 12 mod 7 = 5, 충돌 → [6]에 저장

  • 12를 [0], 9를 [1]에 둔 테이블은 9의 해시값 2와 12의 다음 빈 칸 [6]을 무시했다.
  • 12를 [0], 9를 [6]에 둔 테이블은 9가 비어 있는 [2]에 바로 들어가야 함을 무시했다.
  • 10을 [2], 12를 [4]에 둔 테이블은 충돌 시 다음 칸으로 이동하는 선형탐색 규칙에 어긋난다.

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

이어서 풀어보기

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