[C언어로 쉽게 풀어쓴 자료구조] 1장 연습문제
1. 2개의 정수를 서로 교환하는 알고리즘을 의사 코드로 작성해보자.
[의사코드]
swap(a, b)
temp <- a
a <- b
b <- temp
return (a, b);
2. 사용자로부터 받은 2개의 정수 중에서 더 큰 수를 찾는 알고리즘을 의사코드로 작성해보자.
[의사코드]
max(a, b)
if a > b then
return a;
else
return b;
3. 1부터 n까지의 합을계산하는 알고리즘을 의사 코드로 작성해보자.
[의사코드]
sum(n)
sum <- 0;
for i <- 1 to n do
sum <- sum + i
return sum;
4. Set(집합) 추상 자료형을 정의하라. 다음과 같은 연산자들을 포함시켜라.
Creat, Insert, Remove, Is_In, Union, intersection, Difference.
[정답]
5. Boolean 추상 자료형을 정의하고 다음과 같은 연산자들을 포함시켜라.
And, Or, Not, Xor
[정답]
6. 다음과 같은 코드의 시간 복잡도는? 여기서 n이 프로그램의 입력이라고 가정하자.
for(int i; i < n; i*=2)
printf("Hello");
[정답]
n = 2^t라고 가정.
총 t번의 연산이 필요하다.
t = log2_n 이므로, O(log n)의 복잡도를 갖는다.
7. 다음과 같은 코드의 시간 복잡도는? 여기서 n이 프로그램의 입력이라고 가정하자.
for(i = 0; i < n; i++)
for(j = 1; j < n; j*=2)
printf("Hello");
[정답]
1. 안쪽 for문
n = 2^t라고 가정
총 t번의 연산이 필요하다.
t = log2_n
2. 바깥족 for문
총 n번의 연산이 필요하다.
-> 1, 2에 의하여
O(nlog n) 시간복잡도를 가진다.
8. 시간 복잡도 함수 n^2 + 10n + 8을 빅오 표기법으로 나타내면?
(1) O(n) (2) O(nlog^2n)
(3) O(n^2) (4) O(n^2log2_n)
[정답]
(3)
9. 시간 복잡도 함수가 7n+10이라면 이것이 나타내는 것은?
(1) 연산의 횟수 (2) 프로그램의 수행시간
(3) 프로그램이 차지하는 메모리의 양 (4) 입력 데이터의 총개수
[정답]
(1)
10. O(n^2)의 시간복잡도를 가지는 알고리즘에서 입력의 개수가 2배가 되었다면 실행시간은 어떤 추세로 증가하는가?
(1) 변함없다. (2) 2배
(3) 4배 (4) 8배
[정답]
입력의 개수 = n, n^2의 연산 필요
입력의 개수 = 2n, 4n^2의 연산 필요
(3)
11. f(n)에 대하여 엄격한 상한을 제공하는 표기법은 무엇인가?
(1) 빅오메가 (2) 빅오
(3) 빅세타 (4) 존재하지 않는다.
[정답]
(2)
12. 다음의 빅오표기법들을 수행시간이 적게 걸리는 것부터 나열하여라.
O(n), O(1), O(log n), O(n^2), O(nlong n), O(n!), O(2^n)
[정답]
O(1) < O(log n) < O(n) < O(nlong n) < O(n^2) < O(2^n) < O(n!)
13. 두 함수 30n+4와 n^2를 여러 가지 n값으로 비교하라. 언제 30n+4가 n^2보다 작은 값을 갖는지를 구하여라. 그래프를 그려보라.
[정답]
n > 30, n < -30
14. 다음은 실제로 프로그램의 수행시간을 측정하여 도표로 나타낸 것이다. 도표로부터 이 프로그램의 시간복잡도를 예측하여 빅오 표기법으로 나타내라.
입력의 개수n 수행시간(초) 2 2 4 8 8 25 16 63 32 162
[정답]
|입력의 개수n|수행시간(초)|
|------|---|
|2|2x1|
|4|4x2|
|8|8x3|
|16|16x4|
|32|32x5|
따라서 O(n log n)
15. 빅오표기법의 정의를 사용하여 다음을 증명하라.
5n^2+3 = O(n^2)
[정답]
16. 빅오 표기법의 정의를 이용하여 6n^2+3n이 O(n)이 될 수 없을을 보여라.
[정답]
17. 배열에 정수가 들어 있다고 가정하고 다음의 작업의 최악, 최선의 시간복잡도를 빅오 표기법으로 말하라.
(1) 배열의 n번째 숫자를 화면에 출력한다.
(2) 배열안의 숫자 중에서 최소값을 찾는다.
(3) 배열의 모든 숫자를 더한다.
[정답]
(1) 최선: O(1), 최악: O(1)
(2) 최선: O(1), 최악: O(n)
(3) 최선: O(n), 최악: O(n)
Author And Source
이 문제에 관하여([C언어로 쉽게 풀어쓴 자료구조] 1장 연습문제), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@subin0214/C언어로-쉽게-풀어쓴-자료구조-1장-연습문제저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)