1.reference(자료)구조와알고리즘
페이지 정보
작성일 19-01-01 07:37본문
Download : 1.자료구조와알고리즘.hwp
Insert(S, item) := 원소 item을 집합 S에 저장한다.
Is_In(S, item) := 집합 S에 item이 있는지를 검사한다.
Remove(S, item) := 원소 item를 집합 S에서 삭제한다.
Intersection(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. 10xxx0=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;
temps…(skip) um = 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 = ib; 번의 곱셈, 대입 연산
}
}
-` 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) 이므로 수행속도는 입력에 정비례한다.
Union(S1, S2) := S1과 S2의 합집합을 구한다.
Difference(S1, S2) := S1과 S2의 차집합을 구한다. 따라서 수행시간은 변함이 없다.1.자료구조와알고리즘 , 1.자료구조와알고리즘기타실험결과 , 자료구조와알고리즘
연습문제 해답
1. (3)
2. ADT Set
객체 정이: 집합은 원소(element)라 불리우는 데이터 요소들의 모임
연산 정이:
Create:= 집합을 생성하여 반환한다.
19.
answer = 1.0; 1번
temp = a; 1번
k = n; 1번
while( k ` 0 ) { 루프제어문장 무시
if( (k % 2) != 0 ) answer = temp; logn번의
순서
1.reference(자료)구조와알고리즘
설명
실험결과/기타
자료구조와알고리즘,기타,실험결과
Download : 1.자료구조와알고리즘.hwp( 90 )
1.reference(자료)구조와알고리즘
다.