다음은 키(key)의 오름차순으로 정렬된 배열을 보여준다. 키 24에 … | [7급 국가직 자료구조론] 18년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 18년 1회차
다음은 키(key)의 오름차순으로 정렬된 배열을 보여준다. 키 24에 대한 보간 탐색(interpolation search)을 수행할 때, 첫 번째 탐색 위치는? (단, 배열에서 크기가 가장 작은 키와 가장 큰 키의 값은 미리 주어지고, 위치의 차이는 키 값의 차이에 비례한다는 가정 하에 탐색 위치를 계산하며, 소수점 이하는 반올림한다)
| 위치 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 키 | 3 | 10 | 15 | 19 | 24 | 30 | 40 | 65 | 70 | 74 | 80 | 82 | 87 | 93 |
1
2
2
3
3
4
4
5
해설
보간 탐색의 첫 번째 탐색 위치는 3이다.
보간 탐색은 키 값의 비율로 위치를 추정한다.
소수점 이하를 반올림하면 3이다.
- 2: 계산값 3.03을 반올림한 결과보다 작다.
- 4: 키 24가 실제로 저장된 위치일 뿐, 첫 탐색 위치는 비례 계산으로 정해진다.
- 5: 계산값 3.03을 반올림한 결과보다 크다.
오류나 개정된 내용이 보이면 알려주세요