다음은 키(key)의 오름차순으로 정렬된 배열을 보여준다. 키 24에 … | [7급 국가직 자료구조론] 18년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 18년 1회차
다음은 키(key)의 오름차순으로 정렬된 배열을 보여준다. 키 24에 대한 보간 탐색(interpolation search)을 수행할 때, 첫 번째 탐색 위치는? (단, 배열에서 크기가 가장 작은 키와 가장 큰 키의 값은 미리 주어지고, 위치의 차이는 키 값의 차이에 비례한다는 가정 하에 탐색 위치를 계산하며, 소수점 이하는 반올림한다)
위치012345678910111213
키310151924304065707480828793
1
2
2
3
3
4
4
5
해설

보간 탐색의 첫 번째 탐색 위치는 3이다.

보간 탐색은 키 값의 비율로 위치를 추정한다.
pos=low+(key−a[low])×(high−low)a[high]−a[low]pos = low + \dfrac{(key - a[low]) \times (high - low)}{a[high] - a[low]}

pos=0+(24−3)×1393−3=27390≈3.03pos = 0 + \dfrac{(24 - 3) \times 13}{93 - 3} = \dfrac{273}{90} \approx 3.03
소수점 이하를 반올림하면 3이다.

  • 2: 계산값 3.03을 반올림한 결과보다 작다.
  • 4: 키 24가 실제로 저장된 위치일 뿐, 첫 탐색 위치는 비례 계산으로 정해진다.
  • 5: 계산값 3.03을 반올림한 결과보다 크다.

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

이어서 풀어보기

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