두근두근 자료구조 2장 연습문제

어떤 것들은 심심할 때마다 다시 공부하곤 하는데, 자료구조도 그 중 하나다. 개인적으로 공부하면서 정리한 것들이고 답이 틀렸을 수도 있기 때문에 지적은 언제나 환영한다.

1. int a[10][20]에서 배열이 차지하는 메모리 공간의 크기는 얼마인가? int형은 4바이트라고 하자.

(4) 800 바이트, 10x20x4

2. float a[100]으로 선언된 배열의 시작 주소를 1000번지라고 할 때, 배열의 10번째 요소의 주소는 몇 번지인가?

(4) 1040번지, 1000+10x4

3. 다음 배열 중에서 크기가 가장 큰 배열은?

메모리 크기 기준

(2) double array2[10]; 10x8 = 80바이트

인덱스 크기 기준

(3) char array3[40]; 40

4. 크기가 10인 배열 two[]를 선언하고 여기에 2의 제곱 값들을 저장해보자. 즉 배열의 첫 번째 요소에는 2^0을 저장하고 두 번째 요소에는 2^1값을 저장한다. 마지막 요소에는 2^9값을 저장한다. for 루프를 이용하여 two[] 배려의 전체 요소의 값을 출력하는 프로그램을 작성하라.

int two[10]={1,}, i;

for(i=1;i<10;i++)

two[i]=two[i-1]*2;

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

printf("%d ",two[i]);

5. 본문에서 구조체로 복소수를 나타낸바 있다(프로그램 2.3 참조). 여기서는 복소수 a와 복소수 b를 받아서 a+b를 계산하는 함수를 작성해보자. 함수는 구조체를 반환할 수 있다. 알다시피 복소수는 real+imag*i와 같은 형태를 갖는다.

Complex add_comple(Complex a, Complex b)

{

Complex result;

result.real=a.real+b.real;

result.imag=a.imag+b.imag;

return result;

}

6. 크기가 n인 배열 array에서 임의의 위치 loc에 정수 value를 삽입하는 함수 insert()를 작성하라. 정수가 삽입되면 그 뒤에 있는 정수들은 한 칸씩 뒤로 밀려야 한다. 현재 배열에 들어 있는 원소의 개수는 items개라고 하자(items는 n에 비해 충분히 작다고 가정한다).

void insert(int array[], int loc, int value)

{

int i;

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

array[i+1]=array[i];

array[loc]=value;

}

7. 앞의 문제에서 구현한 insert() 함수의 시간 복잡도는?

최선의 경우 O(1)

최악의 경우 O(n)

8. 크기가 n인 배열 array에서 임의의 위치 loc에 있는 정수를 삭제하는 함수 delete()를 작성하라. 정수가 삭제되면 그 뒤에 있는 정수들은 한 칸씩 앞으로 이동하여야 한다. 현재 배열에 들어있는 원소의 개수는 items개라고 하자(items는 n에 비해 충분히 작다고 가정한다).

int delete(int array[], int loc)

{

int value=array[loc];

for(i=loc;i<items;i++)

array[i]=array[i+1];

items--;

return value;

}

9. 앞의 문제에서 구현한 delete() 함수의 시간 복잡도는?

최선의 경우 O(1)

최악의 경우 O(n)