[c로 배우는 쉬운 자료구조] 3장 연습문제

반응형

01. 순차 자료구조와 관련된 것은?                 Ans : 1번

 

① 디스크 조각 모으기                                    ② 재귀호출

③ 포인터                                                        ④ 백신 프로그램

 

 

 

 

 

02. 선형 리스트에 대한 설명으로 틀린 것은?             Ans : 2번

 

① 선형 리스트는 메모리에 연속된 공간을 사용한다.

② 삽입 연산에 효율적이다.

③ 배열을 사용해 구현하는 순차 자료구조이다.

④ 선형 리스트의 전체 원소를 순서대로 액세스하는 속도가 빠르다.

 

 

 

 

 

03. 선형 리스트를 L[m][n]의 2차원 배열로 구현할 때, 선형 리스트에 저장할 수 있 는 원소의 최대 개수는?                  

Ans : 2번

 

① (m + 1) × (n + 1)개                                     ② (m × n)개

③ (m - 1) × (n – 2)개                                      ④ (m × n) + 1개

 

 

 

 

 

04. 선형 리스트를 구현한 2차원 배열 L[5][7]에서 L[3][2]의 물리적 주소는? (단, 원

소  한 개의 크기는 4바이트이고, 행 우선 순서를 사용한다.)         Ans : 3번

 

①0+(3×7+2)4	②0+(3×5+2)4
③L+(3×7+2)4	④L+(2×5+3)4

 

 

 

 

05. 배열 int array[10][200]을 행 우선 순서로 저장하는 경우에 원소 array[7][12] 의시작 주소는 몇 번지인가?

(단, 배열 array의 시작 주소는 10840h로, int의 크기 는 4바이트로 가정한다. 배열 첨자는 0부터 시작하며 숫자에 붙은 h는 16진수 표기를 의미한다.)             Ans : 2번

① 10804h	② 11E50h
③ 16488h	④ 108BFh
⑤ 10A3Ch

 

 

 

 

 

06. 원소가 100개 있는 선형 리스트에서 열 번째 원소를 삭제하는 연산을 수행하였 다. 원소의 이동 횟수는?                   Ans : 1번

 

① 90	② 91
③ 92	④ 93

 

 

 

 

 

07. 3차원 배열 A(1:5, 2:4, 1:3)를 1차원 배열 B(1:45)에 행 우선으로 저장하는 경우 A(2, 3, 3)이 저장되는 B의 인덱스는?              Ans : 4번

 

① 12	② 13
③ 14	④ 15

 

 

 

 

 

08. 행 우선으로 저장되는 3차원 배열 a[4][5][3]이 있을 때, 이 배열의 첫 번째 원소 a[0][0][0]의 주소를 α라고 하면, a[2][3][1]의 주소를 α+i로 표현했을 때 i의 값 은? Ans : 2번

 

 

① 6	② 40
③ 56	④ 168

 

 

 

 

 

09. K [1: 2, 1: 3, 1: 2]로 선언된 3차원 배열을 행 우선으로 1차원 배열에 저장했을 때, 아홉 번째에 저장되는 요소는?  

  Ans : 3번

 

① K(1,	2,	2)	② K(1,	3,	2)
③ K(2,	2,	1)	④ K(2,	3,	2)

 

 

 

 

 

10. 행 우선 배열 A[3:6][2:7][8:12]에서 A[4][5][10]은 배열 A의 몇 번째 원소인가? (단, 첫 번째 원소는 A[3][2][8]이고 마지막 원소는 A[6][7][12]이다.)                  Ans : 4번

 

① 45	② 46
③ 47	④ 48

 

 

 

 

 

11. 행 우선으로 배열값을 저장하는 C 언어에서 3차원 배열 A[4][2][3]을 선언하였 다. A[0][0][0]부터 A[3][1][2]에 정수값 1~24를 행 우선 순서에 따라 차례대로 저장할 때, A[2][1][2]에 저장되는 값은?                                                   Ans : 2번

 

① 17	② 18
③ 19	④ 20

 

 

 

 

12. 희소행렬에 대한 설명으로 옳지 않은 것은?                     Ans : 4번

 

① 원소값이 대부분 0으로 구성되어 있다.

② 2차원 배열로 표현하면 특정 항목의 접근이 용이하다.

③ 연결 리스트 구조로 표현하더라도 행렬의 덧셈 연산을 할 수 있다.

④ 연결 리스트 구조로 표현하면 기억 공간이 낭비된다.

 

 

 

 

 

13. m × n 크기의 정수값 희소행렬을 정수형 배열에 저장하려고 한다. 가장 효과 적인 저장 방법을 사용할 때, 필요한 배열 크기는? (단, t는 0이 아닌 희소행렬 원소의 개수이며, 배열 크기는 배열 원소의 수를 의미한다.)                  Ans : 4번

 

① m x n	② t
③ m + n + t	④ 3(t+1)

 

 

 

 

14. 값이 0인 원소들의 비율이 90%인 1000 × 1000 희소행렬 표현에 관한 설명 중 옳은 것은?     Ans : 4번

 

① 2차원 배열로 모든 원소들을 표현하는 것이 저장 관점에서 효율적이다.

 

②   2차원 배열로 0이 아닌 원소들만 표현하기 위해서 저장 공간이 1000개 필요하 다.

 

③   0이 아닌 원소들만 연결 리스트로 표현하는 것이 배열로 표현하는 것보다 전치 행렬 연산에 효율적이다.

 

④  0이 아닌 원소들만 3원소 쌍(행의 인덱스, 열의 인덱스, 값)으로 배열에 저장하는 것이 저장 관점에서 효율적이다.

 

 

 

 

 

15. X, Y, Z는 m×n 희소행렬에서 원소값이 0이 아닌 k개의 각 원소를 표현하기 위 해 <행, 열, 값> 3원소쌍을 사용하는 2차원 배열이며, 변환 규칙은 (가)와 같다. 행렬 P와 Q가 (나)와 같이 X, Y로 각각 표현되었을 때, P와 Q를 곱한 행렬 R을 Z로 표현할 경우, 이에 대한 설명으로 옳지 않은 것은? (단, 행렬의 행 번호와 열 번호는 0부터 시작한다.)                    Ans : 4번

 

 

① Z[0][1]	= 2이다.	② Z[0][2]	= 4이다.
③ Z[1][0]	= 0이다.	④ Z[3][2]	= 2이다.

*오타 수정: ④ Z[3][2] = 3이다. -> ④ Z[3][2] = 2이다.

 

 

 

 

 

16. 다항식을 표현하기 위하여 다음의 구조체를 정의하였다. 다항식 A(x)=   에대해 poly.degree=n, poly.coef[i]=an-i로 표현되며, 구조체 멤버 중 degree는 다 항식의 최고 차수를 저장하고 배열 coef[MAX_DEGREE]는 다항식의 최고 차수 항부터 최저 차수 항까지의 계수를 차례로 저장한다. 이때, 다항식 A(x)를 저장 하기 위한 구조체 변수 poly의 선언 과정에서 다항식 100x5 + 60x를 초기화하 기 위한 ㉠의 내용으로 옳은 것은?                                                                   Ans : 3번

 

 

①	{5,	{100,	1,	60}}	②	{5,	{100,	60, 0, 0, 0, 1}}
③	{5,	{100,	0,	0, 0, 60, 0}}	④	{5,	{100,	0, 60}}

 

 

 

 

 

17. 원소가 여덟 개 있는 선형 리스트에서 3번 자리에 새로운 원소를 삽입하려면 원소를 몇 개 옮겨야 하나?            

Ans : 6개

 

 

 

 

 

18. 선형 리스트 A를 C 프로그램에서 2차원 배열 A[5][3]으로 표현했을 때 A[3][1] 원소는 몇 번째 원소인가?

Ans : 11

 

 

 

 

 

19. 시작 위치가 100번지이고 원소 길이가 8바이트인 선형 리스트가 행 우선 순서 방법으로 저장되어 있을 때 아홉 번째 원소의 주소는?                   Ans : 164

 

 

 

 

 

 

20. 다음과 같은 2차원 배열에 대해서 답하시오.

 

int num[3][4] = { 1,2,3,4,5,6,7,8,9,10 };

① 2차원 배열 num의 논리적 구조를 [그림 3-6]과 같이 표현하시오.

Ans :

	[0]	[1]	[2]	[3]
[0]	1	2	3	4
[1]	5	6	7	8
[2]	9	10	0	0

 

 

② 배열 원소 num[1][3]이 저장된 메모리 주소를 행 우선 순서 방법을 이용해 구하 시오(단, 시작 주소는 1000이고, int 크기는 4바이트로 한다).                 Ans : 1028

 

③ 배열 원소 num[1][3]이 저장된 메모리 주소를 열 우선 순서 방법을 이용해 구하 시오(단, 시작 주소는 1000이고, int 크기는 4바이트로 한다).                 Ans : 1040

 

 

 

 

21. 두 다항식을 입력 받아 다항식의 곱을 구하는 multPoly 함수를 작성하시오.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#define MAX(a,b) ((a>b)?a:b)

#define MAX_COEF 50

 

typedef struct polynomial

{

      int degree;

      int ceof[MAX_COEF];

}POLY;

 

POLY initpoly();

POLY multipoly(POLY a, POLY b);

void print(POLY p);

 

void main()

{

      POLY A, B, C;

      A = initpoly();

      B = initpoly();

 

      C = multipoly(A, B);

 

      printf("A : "); print(A);

      printf("B : "); print(B);

      printf("C : "); print(C);

}

 

void print(POLY p) {

      int i;

      int degree = p.degree;

      for (i = 0; i <= p.degree; i++) {

           printf("%3dx^%d", p.ceof[i], degree--);

      }

      printf("\n");

}

 

POLY initpoly()

{

      static int num = 65;

      int i;

      POLY p;

      printf("%c의 다항식의 차수 : ", num);

      scanf("%d", &p.degree);

 

      printf("%c의 다항식의 계수 : ", num);

      for (i = p.degree; i >= 0; i--)

      {

           scanf("%d", &p.ceof[p.degree - i]);

      }

 

      num++;

      return p;

}

 

POLY multipoly(POLY a, POLY b)

{

      POLY c;

      int a_index = 0;

      int b_index = 0;

      int c_index = 0;

      int a_degree = a.degree, b_degree = b.degree;

      c.degree = MAX(a.degree, b.degree);

 

      while (a_index <= a.degree && b_index <= b.degree)

      {

           if (a_degree > b_degree)

           {

                     c.ceof[c_index++] = a.ceof[a_index++];

                     a_degree--;

           }

           else if (a_degree == b_degree)

           {

                     c.ceof[c_index++] = a.ceof[a_index++] * b.ceof[b_index++];

                     a_degree--;

                     b_degree--;

           }

           else

           {

                     c.ceof[c_index++] = b.ceof[b.ceof[b_index++]];

                     b_degree--;

           }

      }

      return c;

}

 

 

 

 

22. 다음 희소행렬의 논리적 구조를 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

Ans:

             0 3 9

             1 1 1

A=        3 2 7

             5 0 3

 

 

 

 

 

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

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

Ans:

             1 5 4

             3 7 9

A=        5 9 5

             7 4 9

 

 

 

 

24. 희소행렬의 메모리 효율성을 높이기 위해 0이 아닌 원소만 뽑아 2차원 배열로 저장하는 함수를 작성하시오.

 

 

#include <stdio.h>

#include <stdlib.h>

 

#define ROW 8

#define COLUMN 7

 

typedef struct s {

    int row;

    int col;

    int val;

}SM_t;

 

int main(void) {

    int A[ROW][COLUMN] = {0,};

    int count = 0;

    int k = 1;

    SM_t* smB;

 

    for (int i = 0; i < ROW; i++) {

        for (int j = 0; j < COLUMN; j++) {

            if (rand() % 2) {

                A[i][j] = rand() % 50;

                count++;

            }

        }

    }

 

    printf("%d\n", count);

 

    for (int i = 0; i < ROW; i++) {

        for (int j = 0; j < COLUMN; j++) {

            printf("%d ", A[i][j]);

        }

        printf("\n");

    }

 

    smB = (SM_t*)malloc((count + 1) * sizeof(SM_t));

 

    smB[0].row = ROW;

    smB[0].col = COLUMN;

    smB[0].val = count;

 

    for (int i = 0; i < ROW; i++) {

        for (int j = 0; j < COLUMN; j++) {

            if (A[i][j]) {

                smB[k].row = i;

                smB[k].col = j;

                smB[k].val = A[i][j];

                k++;

            }

        }

    }

    for (int i = 0; i < count + 1; i++) {

        printf("%d ", smB[i].row);

        printf("%d ", smB[i].col);

        printf("%d ", smB[i].val);

        printf("\n");

    }

 

    free(smB);

 

    return 0;

}