[자료구조 프로그래밍 연습문제] 희소행렬 전치

1. sparse matrix transpose

 

교재에서는 그림 2.4(b)의 6×6 matrix를 그림 2.5(a)의 a 배열로 표현하였다.

A. 그림 2.5(a)의 a 배열의 값은 정확한가?

 

정확하다.

B. 그림 2.5(b)의 b 배열은 그림 2.4(b)의 6×6 matrix를 transpose 한 결과이다. 그림 2.5(b)의 b 배열의 값은 정확한가?

 

정확하다.

C. 교재 2.5.3절의 마지막 부분에는 2.5(a)의 a 배열에 대해 프로그램 2.9 fastTranspose()의 3번째 for loop 수행 직후 시점의 rowTerms 배열과 startingPos 배열의 값을 보이고 있다. 이들 값은 정확한가?

 

정확하다.

D. 프로그램 2.9 fastTranspose()로 그림 2.5의 a 배열로부터 b 배열을 구할 때, 다음에 답하시오.

 

• 3번째 for loop 수행 직후 시점의 rowTerms 배열과 startingPos 배열의 값을 구하는 과정을 보이시
  오.

두번째 for loop i	a.col[i]	rowTerms
1	0	rowTerms[0]++
2	3	rowTerms[3]++
3	5	rowTerms[5]++
4	1	rowTerms[1]++
5	2	rowTerms[2]++
6	3	rowTerms[3]++
7	0	rowTerms[0]++
8 (numTerms)	2	rowTerms[2]++

rowTerms == { 2, 1, 2, 2, 0, 1 }

• 4번째 for loop에서 그림 2.5(a)의 a[4]의 triple <1, 1, 11>에 대한 loop 내 문장의 수행이 끝난 직후 시점의 b 배열 및 startingPos 배열의 값을 보이시오.

index	rowTemrs	startingPos
[0]	2	1
[1]	1	3 (rowTerms[0] + startingPos[0] = 2+0)
[2]	2	4 (rowTerms[1] + startingPos[1] = 1+2)
[3]	2	6 (rowTerms[2] + startingPos[2] = 2+3)
[4]	0	8 (rowTerms[3] + startingPos[3] = 2+5)
[5]	1	8 (rowTerms[4] + startingPos[4] = 0+7)

startingPos == { 1, 3, 4, 6, 8, 8 }

• 프로그램 종료 후 rowTerms 배열의 값을 보이시오.

b[]	row	col	val
0	6	6	8
1	0	0	15
2	default	default	default
3	1	1	11
4	default	default	default
5	default	default	default
6	3	0	22
7	default	default	default
8	5	0	-15

startingPos = { 2, 4, 4, 7, 8, 9 }

• 프로그램 종료 후 startingPos 배열의 값을 보이시오.
  • rowTerms = { 2, 1, 2, 2, 0, 1 }
  • startingPos = { 3, 4, 6, 8, 8, 9 }