그림과 같은 상태의 크기 13인 해시 테이블에 이중(double) 해싱 방법으로 원소 14를 삽입하고 이어서 원소 20을 삽입할 때, 원소 20의 저장 주소는? (단, 해시 함수 h(k,i) = (h 1 (k) + i·h 2 (k)) mod 13, 충돌 횟수 i = 0, 1, 2, ... 이고, h 1 (k) = k mod 13, h 2 (k) = 1 + (k mod 11)이다) 주소 0 1 66 2 3 4 69 5 18 6 7 72 8 9 10 11 50 12

오픈채팅

이용권 구매

활용 가이드

앱 설치

버그 신고

개선 요청

다크모드

그림과 같은 상태의 크기 13인 해시 테이블에 이중(double) 해싱… | [7급 국가직 알고리즘] 24년 1회차 기출문제 상세 페이지

1[7급 국가직 알고리즘] 24년 1회차

그림과 같은 상태의 크기 13인 해시 테이블에 이중(double) 해싱 방법으로 원소 14를 삽입하고 이어서 원소 20을 삽입할 때, 원소 20의 저장 주소는? (단, 해시 함수 h(k,i) = (h₁(k) + i·h₂(k)) mod 13, 충돌 횟수 i = 0, 1, 2, ... 이고, h₁(k) = k mod 13, h₂(k) = 1 + (k mod 11)이다)주소 
0 
1 66
2 
3 
4 69
5 18
6 
7 72
8 
9 
10 
11 50
12

주소
0
1	66
2
3
4	69
5	18
6
7	72
8
9
10
11	50
12

해설

원소 20은 주소 8에 저장된다.
이중 해싱은 충돌할 때마다  $h_2(k)$ 만큼 건너뛰며 빈 칸을 찾는다.
14 삽입:  $h_1(14)=1$ ,  $h_2(14)=1+3=4$ 
i=0 → 1(66 있음), i=1 → 5(18 있음), i=2 →  $(1+2 \cdot 4) \bmod 13 = 9$ (빈칸) → 14는 주소 9에 저장
20 삽입:  $h_1(20)=7$ ,  $h_2(20)=1+9=10$ 
i=0 → 7(72 있음)
i=1 →  $17 \bmod 13 = 4$ (69 있음)
i=2 →  $27 \bmod 13 = 1$ (66 있음)
i=3 →  $37 \bmod 13 = 11$ (50 있음)
i=4 →  $47 \bmod 13 = 8$ (빈칸) → 저장
주소 6은 20의 탐사 순서 7, 4, 1, 11, 8에 나타나지 않는다.
주소 9는 앞서 삽입한 14가 차지한 자리이며 20의 탐사 순서에도 없다.
주소 10은  $h_2(20)$  값과 혼동한 것으로, 20의 탐사 순서에 나타나지 않는다.

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

이어서 풀어보기

[7급 국가직 알고리즘] 24년 1회차 25문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요

비슷한 기출

7급 국가직 알고리즘 기출문제 암기장 전체 보기

💬 자격증 스터디 커뮤니티헷갈리는 문제, 같이 준비하는 사람들에게 물어보세요

→