다음 배열에 대하여, 위치 값이 증가함에 따라 키(key) 값도 이에 … | [7급 국가직 자료구조론] 22년 1회차 기출문제 상세 페이지

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

다음 배열에 대하여, 위치 값이 증가함에 따라 키(key) 값도 이에 정비례하여 증가한다는 가정으로 탐색 위치를 계산하는 보간 탐색을 수행할 때, 키 45를 찾을 때까지 탐색 위치를 계산한 횟수는? (단, 탐색 위치 계산 시 소수점 이하는 버린다)위치 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]
키 2 3 4 7 13 18 22 27 32 42 45 70 72

위치	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	[11]	[12]
키	2	3	4	7	13	18	22	27	32	42	45	70	72

해설

키 45를 찾을 때까지 탐색 위치는 3회 계산된다.
보간 탐색의 위치 공식은  $low+\dfrac{(key-a[low])(high-low)}{a[high]-a[low]}$  이다.
첫 계산:  $0+\dfrac{43\times 12}{70}\approx 7.37$  → 위치 7, 키 27이 작으므로 low = 8
두 번째:  $8+\dfrac{13\times 4}{40}=9.3$  → 위치 9, 키 42가 작으므로 low = 10
세 번째:  $10+\dfrac{0\times 2}{27}=10$  → 위치 10에서 45를 찾는다.
2회: 두 번째로 계산한 위치의 키는 42로 아직 찾지 못했다.
4회: 세 번째 계산에서 이미 45를 찾는다.
5회: 세 번째 계산에서 탐색이 끝나므로 더 늘어날 수 없다.

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

이어서 풀어보기

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

비슷한 기출

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

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

→