자료구조 12장 연습문제 풀이

1. 다음의 키값에 대한 버킷 주소를 결정하여라. 해시 테이블의 버킷 수는 256개이며, 알파벳 'a~z'의 아스키 코드값 97~122를 사용하여라.

[tree, heap, deap, list]

① 중간 제곱 함수를 이용하여 주소를 구하여라.

tree = t + r + e + e = 116 + 114 + 101 + 101 = 432

(432)₁₀ = (110110000)₂

(110110000)² = 101101100100000000

(11001000)₂ = (200)₁₀ 이므로 tree의 주소는 200

 

heap = h + e + a + p = 104 + 101 + 97 + 112 = 414

(414)₁₀ = (110011110)₂

(110011110)² = 101001110110000100

(11100110)₂ = (230)₁₀ 이므로 heap의 주소는 230

 

deap = d + e + a + p = 100 + 101 + 97 + 112 = 410

(410)₁₀ = (110011010)₂

(110011010)² = 101001000010100100

(10000101)₂ = (133)₁₀ 이므로 deap의 주소는 133

 

list = l + i + s + t = 108 + 105 + 115 + 116 = 444

(444)₁₀ = (110111100)₂

(110111100)² = 110000001000010000

(00010000)₂ = (16)₁₀ 이므로 list의 주소는 16

 

② 제산 함수를 이용하여 주소를 구하여라.

[tree]

432 % 256 = 176

 

[heap]

414 % 256 = 158

 

[deap]

410 % 256 = 154

 

[list]

444 % 256 = 188

 

③ 승산 함수를 이용하여 주소를 구하여라. (단, α=0.001일 경우와 α=0.618일 경우에 대해서 주소를 구하여라.)

[tree]

α=0.001일 경우

432 * 0.001 = 0.432

0.432 * 256 = 110.592 이므로 tree의 주소는 110이다.

 

α=0.618일 경우

432 * 0.618 = 266.976

0.976 * 256 = 249.856 이므로 tree의 주소는 249이다.

 

[heap]

α=0.001일 경우

414 * 0.001 = 0.414

0.414 * 256 = 105.984 이므로 heap의 주소는 105이다.

 

α=0.618일 경우

414 * 0.618 = 255.852

0.852 * 256 = 218.112 이므로 heap의 주소는 218이다.

 

[deap]

α=0.001일 경우

410 * 0.001 = 0.41

0.41 * 256 = 104.96 이므로 deap의 주소는 104이다.

 

α=0.618일 경우

410 * 0.618 = 253.38

0.38 * 256 = 97.28 이므로 deap의 주소는 97이다.

 

[list]

α=0.001일 경우

444 * 0.001 = 0.444

0.444 * 256 = 113.664 이므로 list의 주소는 113이다.

 

α=0.618일 경우

444 * 0.618 = 274.392

0.392 * 256 = 100.352 이므로 list의 주소는 100이다.

 

 

 

2. 다음과 같이 레코드가 구성되어 있을 때 이진 검색 방법으로 14을 찾을 경우 비교 횟수는 몇 번인가?

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

가. 2번    나. 3번    다. 4번    라. 5번

 

답 : 나. 3번

? : 8 - 12 - 14

 

 

 

3. What's the explaint next sentence? Choose the collect answer.

A quick method for finding an ordered dense list for particular record by successively looking at that half of the remaining portion of the list in which the record is known to.

가. Tree Search    나. Hashing    다. Block Search    라. Binary Search

 

답 : 라. Binary Search

? : 리스트의 절반을 탐색하여 특정 레코드를 찾는 빠른 방법

 

 

 

4. 탐색 방법 중 키 값으로부터 레코드가 저장되어 있는 주소를 직접 계산하여 산출된 주소로 바로 접근하는 방법은?
가. 이진 탐색    나. 피보나치 탐색    다. 해싱 탐색    라. 블록 탐색

 

답 : 다. 해싱 탐색

 

 

 

5. 해싱 함수 기법 중 어떤 진법으로 표현된 주어진 레코드 키 값을 다른 진법으로 간주하고, 키 값을 변화하여 홈 주소로 취하는 방법은?

가. 숫자 분석 방법

나. 대수적 코딩 방법

다. 기수 변환 방법

라. 제곱법

 

답 : 다. 기수 변환 방법