Univ Study: 59개의 글

Data Structures in C (C언어로 쉽게 풀어쓴 자료구조) 2장 연습문제

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

1. 최대 5개의 활성 레코드가 존재할 수 있다.

2. (4)

3. (4)

4. (3)

5. (3)

6. 순환호출을 할때 파라미터의 값이 줄어들지 않았다.

return n*recursive(n);->return n*recursive(n-1)

7. 순환호출을 끝내는 문장이 빠져있다.

if( n==1 ) return 0;

8.

5

4

3

2

1

0

함수의 반환값=15

9.

5

4

3

2

1

0

함수의 반환값=95

10.

10

7

4

1

-2

함수의 반환값=3

11.

1

2

3

4

5

12. 7개

13. 오타: putchar()->putchar(ch)

evisrucer

14.

int recursive(int n)

{

if( n==1 ) return 1;

else return n+recursive(n-1);

}

15.

double recursive1(int n)

{

if( n==1 ) return 1.0;

else return (1.0/n)+recursive1(n-1);

}

16.

fib(6) is called

fib(5) is called

fib(4) is called

fib(3) is called

fib(2) is called

fib(1) is called

fib(0) is called

fib(1) is called

fib(2) is called

fib(1) is called

fib(0) is called

fib(3) is called

fib(2) is called

fib(1) is called

fib(0) is called

fib(1) is called

fib(4) is called

fib(3) is called

fib(2) is called

fib(1) is called

fib(0) is called

fib(1) is called

fib(2) is called

fib(1) is called

fib(0) is called

17.

int sum(int n)

{

if( n == 1 ) return 1;

else return (n + sum(n-1));

}

18. 이항계수

int bin(int n, int k)

{

if( k==0 || n==0 )

return 1;

else

return bin(n-1,k-1)+bin(n-1,k);

}

19. Ackermann 함수는 다음과 같이 순환적으로 정의된다.

(a) 와 의 값을 구하시오.

A(3,2)= 29

A(2,3)=9

(b) Ackermann 함수를 구하는 순환적인 프로그램을 작성하시오.

int ack(int m, int n) {

if (m == 0) return( n + 1 );

if (n == 0) return( ack(m - 1, 1) );

return( ack(m - 1, ack(m, (n - 1))) );

}

(c) 위의 순환적인 프로그램을 for, while, do와 같은 반복구조를 사용한 비순환적 프로그램으로 바꾸시오.

int ack2(int m, int n)

{

while (m != 0){

if (n == 0)

n = 1;

else

n = ack2(m, n-1);

m = m - 1;

}

return n+1;

}

20. 본문의 순환적인 피보나치 수열 프로그램과 반복적인 피보나치 수열 프로그램의 수행 시간을 측정하여 비교하라. 어떤 결론을 내릴 수 있는가?

-> 순환적인 피보나치 프로그램은 거의 사용하지 못할 정도로 많은 수행시간을 요구한다.

21. 순환호출에서는 순환호출을 할때마다 문제의 크기가 작아져야 한다.

(1) 팩토리얼 계산 문제에서 순환호출이 일어날 때마다 문제가 어떻게 작아지는가?

-> n! = n * (n-1)! 으로 n을 곱한 다음 (n-1)!을 구한다.

(2) 하노이의 탑에서 순환호출이 일어날 때마다 문제의 어떻게 작아지는가?

-> 하나의 원판은 이동시킨 다음에 나머지 원판에 대하여 순환호출을 한다.


Data Structures in C (C언어로 쉽게 풀어쓴 자료구조) 1장 연습문제

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

1. (3)

2. ADT Set

객체 정의: 집합은 원소(element)라 불리우는 데이터 요소들의 모임

연산 정의:

Create() := 집합을 생성하여 반환한다.

Insert(S, item) := 원소 item을 집합 S에 저장한다.

Remove(S, item) := 원소 item를 집합 S에서 삭제한다.

Is_In(S, item) := 집합 S에 item이 있는지를 검사한다.

Union(S1, S2) := S1과 S2의 합집합을 구한다.

Intersection(S1, S2) := S1과 S2의 교집합을 구한다.

Difference(S1, S2) := S1과 S2의 차집합을 구한다.

3. ADT Boolean

객체정의: 0과 1

연산정의:

And(b1, b2) := if b1=1 and b2=1 then return 1;

else return 0;

Or(b1, b2) := if b1=0 and b2=0 then return 0

else return 1;

Not(b) :=if b=0 return 1;

else return 0;

Xor(b1, b2) := if (b1=1 and b2=1) or (b1=0 and b2=0) then return 0;

else return 1;

4. 시간 복잡도 함수 를 빅오 표기법으로 나나내면? (3)

5. (1)

6. (3)

7. 100*100=10000

8. < < < < < <

9. (1) test(int n)

{

int i;

int total=1;1번의 대입연산

for(i=2;i<n;i++){루프 제어 문자은 무시

total *= n; n-2번의 곱셈과 대입연산

}

return n;

}

-> 1+n-2+n-2번의 연산 ->

(2)float sum(float list[], int n)

{

float tempsum;

int i;

tempsum = 0; 1번의 대입연산

for(i=0;i<n;i++) { 루프제어 연산 무시

tempsum += list[i]; n번의 대입연산, 덧셈연산

}

tempsum += 100; 1번의 대입연산, 덧셈연산

tempsum += 200; 1번의 대입연산, 덧셈연산

return tempsum;

}

-> 1+n+n+2+2 ->

(3)void sum(int n)

{

int i,b;

b=2; 1번의 대입연산

i=1; 1번의 대입연산

while(i <= n){ 루프 제어 연산 무시

i = i*b; 번의 곱셈, 대입 연산

}

}

-> 1+1++ ->

10. 알고리즘 A:

알고리즘 B:

이면

11. 와

이면

12. 인 경우에 임을 증명하라. (문제에 오타가 있었음)

의 성질을 이용하면

따라서

13.

14.

(1)

(2)

(3)

(4)

(5)

(6)

(7)

15.

16.

(1)

인 경우 이므로

(2),(3),(4) 도 동일하게 증명 가능

17. 일때 을 만족하는 와 를 찾을 수가 없으므로 은 이 될 수 없다.

18.

int i, k;

for(i=0; i<(n-2); i++){루프 제어 문장 무시

for(k=0; k<30; k++){루프 제어 문장 무시

buffer[i][k] = 0;30*(n-2)번 수행

}

}

(1) 따라서

(2) 이므로 수행속도는 입력에 정비례한다. 따라서 수행시간은 변함이 없다.

19.

answer = 1.0;1번

temp = a;1번

k = n;1번

while( k > 0 ) {루프제어문장 무시

if( (k % 2) != 0 ) answer *= temp;logn번의 비교연산,곱셈,대입연산(최대)

k = (int) k/2;1번

if( k != 0 ) temp *= temp;logn번의 비교연산,곱셈, 대입연산(최대)

}

T(n)= 6logn+4(최대)

따라서 O(logn)

20.

(1) 배열의 n번째 숫자를 화면에 출력한다.-> 최악 O(1) 최선 O(1)

(2) 배열안의 숫자 중에서 최소값을 찾는다.-> 최악 O(n) 최선 O(n)

(3) 배열의 모든 숫자를 더한다.-> 최악 O(n) 최선 O(n)

21. 1시간에 10개의 입력을 처리할 수 있는 프로그램이 있다. 만일 속도가 100배 빠른 컴퓨터를 구입하여 동일한 작업을 한다면 프로그램의 시간 복잡도가 다음과 같은 경우, 1시간에 처리할 수 있는 입력의 개수는 얼마가 되겠는가?

->

(1) ->

이므로 10개의 입력이라면 대략 10개의 연산이 수행되었다. 컴퓨터의 속도가 100배 빨라졌다면 단위시간당 수행하는 연산의 수가 100배가 된 것이므로 1시간에 10*100 연산을 수행할 수 있고 따라서 입력도 10*100개를 처리할 수 있다.

(2) ->

이므로 10개의 입력이라면 1시간당 =10개의 연산이 수행되었다. 컴퓨터가 100배 빨라졌으므로 1시간에 처리할 수 있는 연산의 수가 100배 증가했다고 보면 1시간에 수행될 수 있는 연산의 수는 =1000개가 된다. 을 만족하는 n을 구하면 된다.

(3)

역시 같은 식으로 이므로 10개의 입력이라면 1시간당 개의 연산이 수행되었다. 컴퓨터가 100배 빨라졌으므로 1시간에 처리할 수 있는 연산의 수가 100배 증가했다고 보면 1시간에 수행될 수 있는 연산의 수는 개가 된다. 을 만족하는 n을 구하면 된다.

(4)

같은 방법으로 해결한다.

(5)

같은 방법으로 해결한다.

22.

(1) void insert_array(int loc, int value){

int i;

for(i=items-1; i>=loc;i--)

array[i+1] = array[i];// items-loc개의 대입연산

array[loc] = value;// 1개의 대입연산

items++;// 1개의 산술연산

}

(2) 최선의 시간복잡도: 배열의 마지막에 삽입 2=

최악의 시간복잡도: 배열의 처음에 삽입

평균적인 시간복잡도: (2+3+4+...+(items+2))/items=O(items)=O(n)

23.

typedef struct {

float real;

float imaginary;

} complex;