자료구조 5장 연습문제 풀이

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

 

답 : 5

? : (마지막 원소의 인덱스 - 삽입할 자리의 인덱스) + 1 = (7 - 3) + 1 = 5

 

 

 

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

 

답 : 행 우선 순서 방법 = 10 / 열 우선 순서 방법 = 8

? :

2차원 배열 A[n_i][n_j]일 때

행 우선 순서 방법 = i x n_j + j  /  열 우선 순서 방법 = j x n_i x i

A[3][1] = 3 x 3 + 1 = 10  /  1 x 5 + 3 = 8

 

 

 

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

 

답 : 140

? : 시작위치를 a, 원소 길이를 l이라 할 때 -> a + (i x l)

100 + (8 x 5) = 140

 

 

 

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

1	3	5	7
5	7	9	4
4	9	5	9

 

답 :

1	5	4
3	7	9
5	9	5
7	4	9

 

 

 

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

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

 

답 :

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

? : 0을 제외한 수를 <행 번호, 열 번호, 값>의 쌍으로 추출하면

9 = 0, 3, 9

1 = 1, 1, 1

7 = 3, 2, 7

3 = 5, 0 ,3

이고, 이때 원래의 희소행렬에 대한 정보를 저장하기 위해서 <전체 행의 개수, 전체 열의 개수, 0이 아닌 원소의 개수>의 쌍, 즉 7, 4, 4를 첫 번째 행에 저장한다.

 

 

 

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

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] ← v;
  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()

 

 

 

코드 : https://rap0d.github.io/study/2019/07/22/java_7_%ED%9D%AC%EC%86%8C%ED%96%89%EB%A0%AC%EC%97%B0%EC%82%B0%EC%9D%98java%EA%B5%AC%ED%98%84/

7. 희소 행렬 연산의 Java 구현

 

추천 사이트

 

 

 

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

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

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

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

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

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

 

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

? : 희소행렬은 원소의 대부분이 0인 행렬이기 때문에 실제 사용하는 공간보다 사용하지 않는 공간이 많아 공간복잡도가 커지므로 기억공간에 대한 사용 효율성이 떨어진다는 단점이 있다.