[자바로 배우는 자료구조] 5장 솔루션 해답

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차원 배열로 저장한 경우와 비교하여 가장 큰 장점은?

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

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

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

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

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

 자바로 배우는 자료구조의 해답을 더 보고싶다면? https://chuinggun.tistory.com/category/%EC%9E%90%EB%B0%94%20%EC%86%94%EB%A3%A8%EC%85%98/%EC%9E%90%EB%B0%94%EB%A1%9C%20%EB%B0%B0%EC%9A%B0%EB%8A%94%20%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0