5장 연습문제

1. 8개의 원소가 있는 선형 리스트에서 3번 자리에 새로운 원소를 삽입하려면 몇 개의 원소를 이동해야 하는가?

(마지막원소의 인덱스 - 삽입할 자리의 인덱스)+1

= 7-3+1 = 5

☞ 5개의 원소를 이동해야한다.

(※ 8개의 원소가 있으므로, 마지막 원소의 인덱스는 7이 된다.)

2. 선형 리스트 A를 2차원 배열 A[5][3]으로 표현했을 때, A[3][1]원소는 몇 번째 원소인가? 행우선 순서 방법과 열 우선 순서 방법에 따라 각각 구하시오.

행 우선 순서 방법 >>

A[3][1]원소가 저장되는 인덱스 = i x nj + j = 3x3 + 1 = 10

인덱스가 10이므로 11번째 저장원소가 된다.

(※ 인덱스는 0부터 시작!)

열 우선 순서 방법 >>

[3][1]원소가 저장되는 인덱스 = j x ni + i = 1x5 + 3 = 8

인덱스가 8이므로 9번째 저장원소가 된다.

(※ 인덱스는 0부터 시작!)

3. 시작위치가 100번지이고 원소의 길이가 5바이트인 선형 리스트가 행 우선 순서 방법으로 저장되어있을 때, 9번째 원소의 주소는 얼마인가?

(※ 9번째 원소의 인덱스는 8이 된다. 인덱스는 0부터 시작!)

a+(ixℓ)

= 100 + (8x5)

= 140

4. 다음 행렬에 대한 전치행렬을 구하시오.

A =

A의 전치행렬 =

A =	0	0	0	9
	0	1	0	0
	0	0	0	0
	0	0	7	0
	0	0	0	0
	3	0	0	0
	0	0	0	0

5. 다음의 희소 행렬을 2차원 배열의 논리적 구조로 표현하시오.

희소행렬 A에 대한 2차원 배열 표현

☞

7	4	4
0	3	9
1	1	1
3	2	7
5	0	3

6. [알고리즘5-2]의 희소행렬의 전치연산을 수행하는 자바 프로그램을 작성하시오.
[해답제공 x]

transposeSM(a[])

m ← a[0,0];

n ← a[0,1];

v ← a[0,2];

b[0,0] ← n;

b[0,1] ← m;

b[0,2] ← t;

if (v > 0) then {

p ← 1;

for (i←0; i < n; i←i+1) do {

for (j←1; j <= v; j←j+1) do {

if (a[j,1]←i) then  {

b[p,0] ← a[j,1];

b[p,1] ← a[j,0];

b[p,2] ← a[j,2];

p ← p+1;

}

}

}

}

return b[];

End transposeSM()

7. 희소행렬에 저장된 원소 중 0이 아닌 원소들을 각각 <행, 열, 값> 3원소 쌍으로 구성하는 경우, 1차원 배열로 저장한 경우와 비교하여 가장 큰 장점은?

가. 규모가 큰 희소행렬에서 기억공간을 절약할 수 있다.

나. 행렬의 덧셈 및 곱셈을 구하는 알고리즘의 작성이 쉽다.

다. 행렬의 전치행렬을 구하는 알고리즘의 작성이 쉽다.

라. 행렬의 역행렬을 구하는 알고리즘의 작성이 쉽다.

마. 희소행렬의 임의 원소를 검색하기가 용이하다.