C언어로 쉽게 풀어 쓴 자료구조 1장 연습문제

*독학하면서 푼 문제이니 정확한 답이 아닐 수도 있습니다. 참고만 해주세요!

 

 

1. 

change(A,B)
	temp<-A
    A<-B
    B<-temp
return(A,B)

 

2.

 

find_max(A,B)
	if A>B then
    	return A;
    else
    	return B;

 

 

3.

 

get_sum(n)
	temp<-0;
    for i<-1 to n do
    	temp<-temp+i;
    return temp;

 

sum(n)
	n*(n+1)/2;

 

4.

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

연산정의: 

create()::= 집합을 생성

Insert(s,item)::= 요소 item을 집합 s에 삽입

Remove(s,item)::= 요소 item을 집합 s에서 제거

Is_In(s,item)::=요소 item이 집합 s에 있는지 검사

Union(s1,s2)::= 집합 s1과 집합 s2의 합집합

Intersection(s1,s2)::= 집합 s1과 집합 s2의 교집합

Difference(s1,s2)::=집합 s1과 집합 s2의 차집합

 

5.

객제정의: 연산에 참여하는 요소들

연산정의:

And(a1,a2)::=a1과 a2 둘 다 참일 때만 참, 그외 거짓

Or(a1,a2)::= a1또는 a2 둘 중 하나라도 참이면 참, 그외 거짓

Not(a)::=a가 참이면 거짓, 거짓이면 참

Xor(a1,a2)::=a1과 a2가 둘 다 참 혹은 둘 다 거짓일 때 거짓, 그외 참

 

6. 

 

O(logn)

 

7.

 

내부 for문 -> logn 번의 연산

바깥 for문-> n번의 연산

=> O(nlogn)

 

8.

3번

 

9.

1번

 

10.

3번

 

11.

2번, 빅오메가는 하한을, 빅세타는 상한과 하한을 표시한다. 

 

12. 

 1,logn, n, nlogn, n^2, 2^n, n!

 

13.

n이 30보다 커지면 n^2이 더 커지고, 30보다 작거나 같으면 30n+4가 더 크다.