n개의 버킷(bucket)으로 구성된 비어있는 해시 테이블에 다음 에 따라 해시 함수 h(x)=x \bmod n을 사용하여 키값 을 차례대로 삽입할 때, 발생하는 전체 충돌 횟수가 가장 많은 n값은? ○ n은 자연수이다. ○ 버킷 내 슬롯(slot) 수는 1이다. ○ 버킷의 인덱스는 0부터 시작한다. ○ 충돌 해결 방법으로 선형 조사법(linear probing)을 사용한다. ○ 각 키값의 삽입과정에서 발생하는 충돌 횟수가 k(k는 0 이상의 정수)일 때 전체 충돌 횟수가 k만큼 …

오픈채팅

이용권 구매

활용 가이드

앱 설치

버그 신고

개선 요청

다크모드

n개의 버킷(bucket)으로 구성된 비어있는 해시 테이블에 다음 &l… | [7급 국가직 자료구조론] 26년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 26년 1회차

 $n$ 개의 버킷(bucket)으로 구성된 비어있는 해시 테이블에 다음 <조건>에 따라 해시 함수  $h(x)=x \bmod n$ 을 사용하여 키값 <1, 20, 2, 35, 18>을 차례대로 삽입할 때, 발생하는 전체 충돌 횟수가 가장 많은  $n$ 값은?<조  건>
○  $n$ 은 자연수이다.
○ 버킷 내 슬롯(slot) 수는 1이다.
○ 버킷의 인덱스는 0부터 시작한다.
○ 충돌 해결 방법으로 선형 조사법(linear probing)을 사용한다.
○ 각 키값의 삽입과정에서 발생하는 충돌 횟수가 k(k는 0 이상의 정수)일 때 전체 충돌 횟수가 k만큼 증가한다.

해설

전체 충돌 횟수가 가장 많은 것은  $n=17$ 일 때(7회)이다.
각  $n$ 에 대해 1, 20, 2, 35, 18 순으로 넣으며 이미 찬 버킷을 만난 횟수를 센다.
 $n=5$ : 1→1, 20→0, 2→2, 35는 0·1·2에서 충돌해 3에 저장(3회), 18은 3에서 충돌해 4에 저장(1회) → 총 4회
 $n=7$ : 1, 6, 2, 0, 4로 모두 다른 버킷 → 0회
 $n=13$ : 1, 7, 2, 9, 5로 모두 다른 버킷 → 0회
 $n=17$ : 1→1, 20→3, 2→2, 35는 1·2·3에서 충돌해 4에 저장(3회), 18은 1·2·3·4에서 충돌해 5에 저장(4회) → 총 7회

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

이어서 풀어보기

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

비슷한 기출

7급 국가직 자료구조론 기출문제 암기장 전체 보기

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

→