다음 해시구조는 개방 주소법(open addressing) 중 선형 검… | [7급 국가직 자료구조론] 15년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 15년 1회차
다음 해시구조는 개방 주소법(open addressing) 중 선형 검색법(linear probing)을 사용하여 오버플로우를 처리하는 예제이다. 해시함수가 ‘입력되는 색인키의 첫 번째 문자에 대한 알파벳 순위’라고 가정할 때, 버킷 테이블의 ㉠, ㉡에 대한 접근 횟수로 옳게 짝지어진 것은? (예로, 해싱함수 h(alpha)=0, h(beta)=1, h(computer)=2, h(data)=3, h(email)=4, h(father)=5 등을 의미한다)
버킷색인키탐색에 필요한 버킷 접근 횟수
0ascii1
1atoi2
2char1
3define1
4equal1
5ceil㉠
6for㉡
…

㉠ ㉡
1
3 1
2
4 2
3
1 1
4
4 1
해설

㉠은 4, ㉡은 2이다.

h(ceil)=2인데 버킷 2·3·4가 이미 차 있어 선형 검색으로 버킷 2, 3, 4, 5를 차례로 확인하므로 네 번 접근한다.

h(for)=5인데 버킷 5를 ceil이 차지하고 있어 버킷 5, 6을 확인하므로 두 번 접근한다.

  • ㉠ 3, ㉡ 1: ceil은 버킷 5까지 가야 하므로 세 번으로는 찾을 수 없다.
  • ㉠ 1, ㉡ 1: 두 키 모두 홈 버킷이 아닌 곳에 저장되어 한 번에 찾을 수 없다.
  • ㉠ 4, ㉡ 1: for의 홈 버킷 5는 ceil이 차지하고 있어 한 번에 찾을 수 없다.

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

이어서 풀어보기

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