천인국: 11개의 글

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씩 증가시키고 로 해주어도 똑같은 결과를 얻을 수 있다.


신고

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

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

1. (4)

2. (1)

3. (2)

4.

0-------1

1-------0->2->3

2-------1

3-------1

5. (4)

6. (3)

7. (2)

8. (2)

9. (2)

10.

(1) 각 정점의 진입차수와 진출차수

정점 0---- 진입차수 1, 진출차수 3

정점 1---- 진입차수 1, 진출차수 3

정점 2---- 진입차수 3, 진출차수 1

정점 3---- 진입차수 2, 진출차수 2

정점 4---- 진입차수 3, 진출차수 2

정점 5---- 진입차수 0, 진출차수 1

(2)

정점 0---- {1,2,3}

정점 1---- {2,3}

정점 2---- {4}

정점 3---- {0,4}

정점 4---- {1,2}

정점 5---- {4}

(3) 인접행렬

50

45

10

10

15

30

20

15

20

35

3

(4) 인접리스트

1

50

2

45

3

10

0--------->->->NULL

2

10

3

15

1--------->->NULL

4

30

2--------->NULL

0

20

4

15

3--------->->NULL

1

20

2

35

4--------->->NULL

4

3

5--------->NULL

(5) 사이클

경로 (0,1,3,0) 길이: 3

경로 (1,2,4,1) 길이: 3

경로 (0,2,4,1,3,0) 길이: 5

경로 (1,3,4,1) 길이: 3

11.

12.

(1) 진출 차수를 계산하는 함수

int calculate_out_degree(GraphType *g, int v)

{

int i, degree=0;

for(i=0;i<g->n;i++)

if( g->adj_mat[v][i] != 0 ) degree++;

return degree;

}

시간복잡도:

(2) 진입 차수를 계산하는 함수

int calculate_in_degree(GraphType *g, int v)

{

int i, degree=0;

for(i=0;i<g->n;i++)

if( g->adj_mat[i][v] != 0 ) degree++;

return degree;

}

시간복잡도:

(3) 간선들의 개수를 계산하는 함수

int calculate_num_edges(GraphType *g)

{

int r, c, edges=0;

for(r=0;r<g->n;r++)

for(c=0;c<g->n;c++)

if( g->adj_mat[r][c] != 0 )

edges++;

return edges;

}

시간복잡도:

13. 만약 그래프가 인접 리스트로 표현되어 있다고 가정하고 12번 문제를 다시 작성하라.(문제 오타 수정해주십시오.)

(1) 진출 차수를 계산하는 함수

int calculate_out_degree(GraphType *g, int v)

{

int degree=0;

GraphNode *node=g->adj_list[v];

while(node != NULL){

degree++;

node = node->link;

}

return degree;

}

시간복잡도:

(2) 진입 차수를 계산하는 함수

int calculate_in_degree(GraphType *g, int v)

{

int i, degree=0;

GraphNode *node;

for(i=0;i<g->n;i++){

node=g->adj_list[i];

while(node != NULL){

if( node->vertex == v ) degree++;

node = node->link;

}

return degree;

}

시간복잡도:

따라서 방향 그래프에서 진입차수를 구하는 것은 상당히 복잡해진다. 따라서 역인접 리스트(inverse adjacency list)라고 하는 별도의 리스트를 따로 만들기도 한다.

(3) 간선들의 개수를 계산하는 함수

int calculate_num_edges(GraphType *g)

{

int i, edges=0;

GraphNode *node;

for(i=0;i<g->n;i++){

node=g->adj_list[i];

while(node != NULL){

degree++;

node = node->link;

}

return edges;

}

시간복잡도:

14. 특정한 정점에 인접한 정점들을 알고 싶은 경우에는 인접행렬로 표현되어 있는 경우는 , 인접리스트로 표현되어 있는 경우는 평균적으로 의 시간이 걸린다. 일반적으로 하나의 정점에 연결된 간선의 개수는 정점의 개수보다는 적다. 따라서 인접 리스트 표현이 유리하다.

15. 3개의 정점을 가지는 무방향 완전 그래프->간선의 개수==3*2/2=3

3개의 정점을 가지는 무방향 완전 그래프->간선의 개수==4*3/2=6

19. 4개의 정점을 갖는 완전그래프에 대하여 깊이우선탐색과 너비우선탐색의 결과

깊이우선탐색: 0->1->2->3

너비우선탐색: 0->1->2->3

탐색의 결과는 인접리스트로 표현되었을 경우, 달라질 수 있다.

20. 그래프는 인접행렬로 표현되어 있다고 가정한다.

(1) 정점 3에서 출발하여 깊이 우선탐색했을 경우의 방문순서: 3->1->0->2->4->5->6->7->8->9

(2) 정점 6에서 출발하여 깊이 우선탐색했을 경우의 방문순서

6->5->3->1->0->2->4->7->8->9

(3) 정점 3에서 출발하여 너비 우선탐색했을 경우의 방문순서

3->1->4->5->0->2->6->7->8->9

(4) 정점 6에서 출발하여 너비 우선탐색했을 경우의 방문순서

6->5->7->3->8->9->1->4->0->2

22. 가능한 깊이우선 신장트리 나열

만약 그래프가 인접행렬로 표현되어 있고 깊이우선 탐색을 이용하여 신장트리를 만든다면 다음과 같은 신장트리만이 가능하다.

23. Kruskal 알고리즘

(0,1) 선택

(1,3) 선택

(2,4) 선택

(3,4) 선택

24. Prim 알고리즘

0번 정점 선택

1번 정점 선택

3번 정점 선택

4번 정점 선택

2번 정점 선택

26. 최단경로 알고리즘

단계

선택된 정점

found 배열

distance 배열

1

0

1,0,0,0,0,0

0,50,45,10,∞,∞

2

3

1,0,0,1,0,0

0,50,45,10,25,∞

3

4

1,0,0,1,1,0

0,45,45,10,25,∞

4

1

1,1,0,1,1,0

0,45,45,10,25,∞

5

2

1,1,1,1,1,0

0,45,45,10,25,∞

6

5

1,1,1,1,1,0

0,45,45,10,25,∞

31. 많은 위상정렬중에서 하나의 예는 다음과 같다.

cs1->cs2->cs3->cs5->cs4->cs6->cs7->cs8


신고

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

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

1. (2), (3) 선택 정렬과 히프정렬은 안정적이지 않다.

2. (3) 멀리 떨어진 요소들을 삽입정렬한다.

3. (2) 어느정도 정렬이 되어 있다.

4. (4) 합병정렬

5. (2) 최선의 경우는 이다 ->최선의 경우에는 이다.

6. (1) 히프정렬을 구현하기 위해서는 포인터를 가진 노드구조가 필요하다.->1차원 배열을 이용하여 구현한다.

7. (2) 합병정렬은 분할하는 과정에서 정렬이 이루어진다.->합병정렬은 합병하는 과정에서 정렬이 이루어진다.

8. (1) 레코드간의 비교만 가능하면 적용할 수 있다.->레코드들을 서로 비교하지 않는다.

9. (2) 선택정렬 -> 하나의 레코드의 크기가 크다면 이동횟수가 적은 정렬 방법이 바람직하다

10.

(1) 선택정렬

(7 4 9 6 3 8 7 5)->

(3 4 9 6 7 8 7 5)->

(3 4 9 6 7 8 7 5)->

(3 4 5 6 7 8 7 9)->

(3 4 5 6 7 8 7 9)->

(3 4 5 6 7 8 7 9)->

(3 4 5 6 7 7 8 9)

(3 4 5 6 7 7 8 9)

(2) 삽입정렬

(7 4 9 6 3 8 7 5)->

(4 7 9 6 3 8 7 5)->

(4 7 9 6 3 8 7 5)->

(4 6 7 9 3 8 7 5)->

(3 4 6 7 9 8 7 5)->

*(3 4 6 7 8 9 7 5)->

(3 4 6 7 7 8 9 5)->

(3 4 5 6 7 7 8 9)

(3) 버블정렬

(7 4 9 6 3 8 7 5)->

(4 7 6 3 8 7 5 9)->

(4 6 3 7 7 5 8 9)->

(4 3 6 7 5 7 8 9)->

(3 4 6 5 7 7 8 9)->

(3 4 5 6 7 7 8 9)->

(4) 쉘정렬

(7 4 9 6 3 8 7 5)->

(7 4 5 6 3 8 7 9)->

(6 3 5 7 4 8 7 9)->

(3 4 5 6 7 7 8 9)

11.

(1) 퀵정렬(숫자가 변경되는 경우만 기록)

(71 49 92 55 38 82 72 53)->

(38 49 53 55 71 82 72 92)->

(38 49 53 55 71 72 82 92)

(2) 합병정렬

(71 49 92 55 38 82 72 53)->

(49 71 92 55 38 82 72 53)->

(49 71 55 92 38 82 72 53)->

(49 55 71 92 38 82 72 53)->

(49 55 71 92 38 82 72 53)->

(49 55 71 92 38 82 53 72)->

(38 49 53 55 71 72 82 92) 정렬 완료

(3) 히프정렬

숫자를 하나씩 삽입하여 히프 생성

92

5582

53 38 71 72

49

0

92

55

82

53

38

71

72

49

82

5572

53 38 71 49

92

0

82

55

72

53

38

71

72

92

72

5571

53 38 49 82

92

0

72

55

71

53

38

49

82

92

71

5549

53 38 72 82

92

0

71

55

49

53

38

72

82

92

55

5349

38 71 72 82

92

0

55

53

49

38

71

72

82

92

53

3849

55 71 72 82

92

0

53

38

49

55

71

72

82

92

49

3853

55 71 72 82

92

0

49

38

53

55

71

72

82

92

38

4953

55 71 72 82

92

0

38

49

53

55

71

72

82

92

12. 퀵정렬에서의 피봇 선택 문제

(1) 왼쪽 첫 번째 요소를 피봇으로 하는 경우(노란색은 피봇을 나타냅니다.)

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

(2) 왼쪽, 중간, 오른쪽 가운데 중간(노란색은 피봇을 나타냅니다.)

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

13. 퀵정렬

(1) (5 3 4 5 8 9 6 7)

(2) 7번의 비교연산이 수행됨

(3) 피봇값은 이미 정렬된 위치에 있기 때문에 피봇값의 위치는 변경되지 않는다.

(4) quick_sort(list, 0, 2)와 quick_sort(list, 4, 7)

14. 히프 정렬의 불안정성

예를 들어 다음의 2개의 리스트를 정렬하는 경우를 생각해보자.

(1) 99 80(A) 80(B) 70

(2) 99 95 80(A) 80(B)

위의 2개의 리스트는 다음 그림처럼 히프로 생성되고

99

80(A)80(B)

70

99

9580(A)

80(B)

히프정렬을 하면 결과는 다음과 같이 된다.

(1)99 80(A) 80(B) 70

(2)99 95 80(B) 80(A)

즉 같은 값을 갖는 레코드들의 위치가 정렬후에 변경될 수 있다.

15. 기수정렬의 각 단계

* 1단계

QUEUE [0] --- 210 220

QUEUE [1] ---

QUEUE [2] ---

QUEUE [3] --- 123 003 513

QUEUE [4] --- 294

QUEUE [5] ---

QUEUE [6] ---

QUEUE [7] ---

QUEUE [8] --- 398 528

QUEUE [9] --- 019 129

210 220 123 003 513 294 398 528 019 129

* 2단계

QUEUE [0] --- 003

QUEUE [1] --- 210 513 019

QUEUE [2] --- 220 123 528 129

QUEUE [3] ---

QUEUE [4] ---

QUEUE [5] ---

QUEUE [6] ---

QUEUE [7] ---

QUEUE [8] ---

QUEUE [9] --- 294 398

003 210 513 019 220 123 528 129 294 398

* 3단계

QUEUE [0] --- 003 019

QUEUE [1] --- 123 129

QUEUE [2] --- 210 220 294

QUEUE [3] --- 398

QUEUE [4] ---

QUEUE [5] --- 513 528

QUEUE [6] ---

QUEUE [7] ---

QUEUE [8] ---

QUEUE [9] ---

003 019 123 129 210 220 294 398 513 528

16. 문제를 다음과 같이 보완하여야 합니다.

데이터의 수가 100개일 때 삽입정렬과 퀵정렬이 동일하게 1초에 정렬을 완료하였다. 데이터의 수가 1000,10000,100000,1000000등으로 증가할 때 평균적인 경우에, 두 정렬방법이 필요로 하는 시간을 계산하고 비교하라.

(답)

평균의 경우에 삽입정렬의 이론적인 시간복잡도는 이고 퀵정렬은 이다. 따라서 필요로 하는 연산의 개수는 대략적으로 다음의 표에 비례하여 늘어날 것이 예상된다.

n=100

n=1000

n=10000

n=100000

n=1000000

삽입정렬

연산의 수

수행시간

1초

100초

10000초

퀵정렬

연산의 수

수행시간

1초

약 15초

약 200초

약 2501초

약 30017초

17.

알고리즘 A: 전체 배열을 순차적으로 탐색하므로 항상 의 시간 복잡도를 가진다.

알고리즘 B: 배열을 정렬하기 위하여 사용하는 정렬방법에 따라 시간복잡도가 달라진다. 만약 합병정렬을 사용한다고 가정하면 의 시간이 소요된다.

18. 수정된 삽입정렬 코드

#define MAX_SIZE 100

#define NAME_SIZE 32

typedef struct {

int key;

char name[NAME_SIZE];

} record;

record list[MAX_SIZE];

int n;

//

insertion_sort(record list[], int n)

{

int i, j;

record current_record;

for(i=1; i<n; i++){

current_record = list[i];

for(j=i-1; j>=0 && list[j].key>current_record.key;j--)

list[j+1]=list[j];

list[j+1]=current_record;

}

}

19. 삽입정렬의 각 단계출력

//

insertion_sort(int list[], int n)

{

int i, j, k;

int key;

for(i=1; i<n; i++){

// 정렬된 리스트 출력

printf("(");

for(k=0;k<i;k++)

printf("%d ", list[k]);

printf(")");

// 정렬해야할 리스트 출력

printf("(");

for(k=i;k<n;k++)

printf("%d ", list[k]);

printf(")\n");

key = list[i];

for(j=i-1; j>=0 && list[j]>key;j--)

list[j+1]=list[j];

list[j+1]=key;

}

}

20. 함수 포인터를 이용한 삽입정렬

//

insertion_sort(int list[], int n, int (*f)())

{

int i, j;

int key;

for(i=1; i<n; i++){

key = list[i];

for(j=i-1; j>=0 && f(list[j],key);j--)

list[j+1]=list[j];

list[j+1]=key;

}

}

int ascend(int x, int y)

{

if( x<y ) return 1;

else return 0;

}

int descend(int x, int y)

{

if( x>y ) return 1;

else return 0;

}


신고