Data Structures in C (C언어로 쉽게 풀어쓴 자료구조) - 천인국 11장 연습문제

Posted by Patchman
2009.05.01 00:34 Univ Study/자료구조와 실습

1. (1)

2. (2)

3. (4)

4. (3)

5. (1) 예상한 것보다 더 적은 자료를 받았을 때: 해시 테이블의 많은 공간이 낭비된다.

(2) 예상한 것보다 더 많은 자료를 받았을 때: 충돌이 많이 발생하게 되어 탐색의 효율성이 떨어지게 된다.

6. 체이닝이 선형 조사법보다는 더 많은 자료를 잘 처리할 수 있다.

7. 문자의 코드는 보통 아스키 코드이고 아스키 코드값은 65에서 122이기 때문에 만약 3자리로 이루어진 탐색 키의 경우, 195에서 366으로 코드가 집중된다. 따라서 더 좋은 방법은 교과서 p.464에 나온대로 아스키 코드값의 위치에 기초한 값을 곱하는 것이다.

8.

* 모든 픽셀의 값을 더한다.

* 모든 픽셀의 값을 비트별로 XOR한다.

* 전체의 픽셀 중 몇 개의 픽셀만을 선택한다.

9. h(k)= k mod 11

(1)

0

44

1

12

2

13

3

88

4

23

5

11

6

94

7

39

8

16

9

20

10

5

(2)

0

44

1

12

2

13

3

16

4

88

5

23

6

94

7

39

8

5

9

11

10

20

(3)

0

44

1

12

2

13

3

88

4

39

5

20

6

23

7

5

8

16

9

11

10

94

(4)

0

44->

88->

11->

1

12->

23->

2

13->

3

4

5->

5

16->

6

94->

39

7

8

9

20->

10

10. 이차조사법

(1) 3, 4, 7, 12, 2, 11

(2) 번째 인덱스가 이라면 번째 인덱스는 이 되고 이것을 풀어서 정리하면 이 되어 번째 인덱스에 을 더한 형태가 된다.

(3) 항은 를 증가시킬 때마다 2씩 증가하게 된다. 따라서 를 2씩 증가시키고 로 해주어도 똑같은 결과를 얻을 수 있다.