한국어
메뉴

자료 구조와 알고리즘

크기 7인 해시 테이블(위치 0~6)에 해시 함수 h(k) = k mod 7로 키 10, 17, 24, 3을 이 순서로 저장한다. 충돌했을 때는 위치를 하나씩 뒤로 옮기며(6 다음은 0) 빈 위치를 찾는 선형 탐사법을 사용한다. 키 3이 저장되는 위치는?

  1. A위치 3
  2. B위치 4
  3. C위치 6
정답과 해설 보기

정답: C. 위치 6

네 키는 모두 7로 나눈 나머지가 3이므로, 전부 위치 3을 처음에 조사합니다. 10은 위치 3에 들어가고, 17은 위치 3이 차 있으므로 위치 4, 24는 위치 3, 4가 차 있으므로 위치 5에 들어갑니다. 3은 위치 3, 4, 5가 차 있으므로 위치 6에 저장됩니다. 이처럼 선형 탐사법에서는 채워진 위치가 뭉쳐서 늘어서고(클러스터), 나중에 오는 키일수록 조사하는 횟수가 늘어납니다.

이 분야 연습하기 분야로 돌아가기

자료 구조와 알고리즘의 다른 문제

  1. 해시 테이블의 충돌을 처리하는 방법으로 체이닝(같은 위치의 원소를 연결 리스트로 잇는다)과 개방 주소법(표 안의 비어 있는 다른 위치를 찾는다)을 비교한 설명으로 올바른 것은? 적재율은 저장한 원소 수를 표의 크기로 나눈 값으로 한다.
  2. 배열 가운데의 원소와 비교하여 찾는 범위를 절반씩 좁혀 가는 이진 탐색을 사용하기 위한 전제 조건으로 올바른 것은?
  3. 오름차순으로 정렬된 서로 다른 1,000개의 값에서 이진 탐색으로 값을 찾는다. 1회의 비교로 '일치·더 작다·더 크다'를 알 수 있다고 하면, 찾는 경우와 찾지 못하는 경우를 모두 포함하여 비교 횟수는 최대 몇 회인가?
  4. 오름차순으로 늘어선 배열 a[0]~a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60에서 이진 탐색으로 38을 찾는다. 찾는 범위를 하한 lo = 0, 상한 hi = 9에서 시작하고, 가운데 위치를 (lo + hi) ÷ 2의 버림으로 한다. 38과 비교되는 원소의 값을 차례로 나열한 것은?
  5. 배열 5, 3, 8, 1, 4를 버블 정렬로 오름차순 정렬한다. 앞에서부터 이웃한 원소끼리 비교하여 왼쪽이 더 크면 교환하는 조작을 끝까지 1회 수행한(1패스) 후의 배열은?