7급 국가직 자료구조론 2021년 기출문제

다음 탐색 알고리즘에 대한 설명으로 옳지 않은 것은?

int a_search(int list[], int key, int n) {
  int i;
  for(i=0; i<n; i++)
    if(list[i]==key) return i;
  return -1;
}

다음 C 코드의 실행 결과는?

#include <stdio.h>
int func (int n) {
  if(n <= 1) return 2;
  return func (n-1) + n;
}
int main (int argc, char* argv[]) {
  printf("%d\n", func (10) );
  return 0;
}

다음 그래프에 대해 위상 정렬(topological sort) 알고리즘을 수행했을 때 생성되는 위상 순서 중 옳지 않은 것은?

다음과 같이 배열을 이용하여 스택 자료구조를 정의하였다. ㉠, ㉡에 들어갈 내용을 바르게 연결한 것은?

#define MAX 10
int stack[MAX];
int top = -1;
int push(int t) {
  if (top >= MAX - 1) {
    printf("\n Stack overflow.");
    return -1;
  }
  stack[    ㉠    ] = t;
  return t;
}
int pop(void) {
  if (top < 0) {
    printf("\n Stack underflow.");
    return -1;
  }
  return stack[    ㉡    ];
}

㉠ ㉡

차수가 4이고 높이가 4인 m원 탐색 트리가 가질 수 있는 노드의 최대 수는? (단, 루트 노드만 있는 경우 트리의 높이는 1이다)

다음은 이진트리를 전위 순회하여 얻어진 전위표기식이다. 이 트리에 대한 설명으로 옳지 않은 것은?

＋ / * 6 2 — 3 1 * ＋ 5 8 — 7 4

이진트리의 성질에 대한 설명으로 옳은 것은? (단, 루트 노드의 레벨은 0이고, 차수가 0인 노드의 개수는 $n_0$, 차수가 1인 노드의 개수는 $n_1$, 차수가 2인 노드의 개수는 $n_2$로 한다)

다음 C 언어 코드를 실행한 후 5번째 및 7번째 줄에 출력되는 문장으로 옳은 것은?

#include <stdio.h>

void hanoi(int n, char from, char tmp, char to) {
  if( n==1 ) 
     printf("disk 1 from %c to %c\n", from, to);
  else {
     hanoi(n-1, from, to, tmp);
     printf("disk %d from %c to %c\n", n, from, to);
     hanoi(n-1, tmp, from, to);
  }
}

int main(int argc, char* argv[]) {
  hanoi(3, 'A', 'B', 'C');
} 

5번째 줄 7번째 줄

다음과 같이 이중연결리스트를 이용하여 큐 자료구조를 정의하였다. add는 큐의 삽입 알고리즘이고, delete는 큐의 삭제 알고리즘이다. ㉠, ㉡에 들어갈 내용을 바르게 연결한 것은?

typedef struct _dnode {
  int key;
  struct _dnode *prev, *next;
} dnode;
dnode *head = (dnode*)malloc(sizeof(dnode));
dnode *tail = (dnode*)malloc(sizeof(dnode));
head->prev = head;	   head->next = tail;
tail->prev = head;	   tail->next = tail;

int add(int k) {
  dnode *t = (dnode*)malloc(sizeof(dnode));
  if (t == NULL) { 
    printf("\n Out of memory.");  
    return -1;
  }
  t->key = k;
            ㉠          
  tail->prev = t;	 t->next = tail; 
  return k;
}

int delete(void) {
  dnode *t; int i;
  t = head->next;
  if (t == tail) {
    printf("\n Queue underflow."); 
    return -1;
  }
  i = t->key;
            ㉡          
  free(t);  return i;
}

다항식에서 하나의 항을 표현하기 위해 다음과 같은 구조체 poly를 정의하였다. 이 구조체를 이용하여 $A(x)=3x^{14}+2x^8+1$과 $B(x)=8x^{14}-4x^9+10x^3$을 저장하는 데 필요한 최소의 메모리 용량(byte)은? (단, 정수(int)를 표현하는 데 2 byte를 사용하고, 실수(float)를 표현하는 데 4 byte를 사용하며, 다항식의 모든 항은 poly 구조체를 이용하여 저장한다)

struct poly{
    int exp;
    float coef;
};

다음은 행렬 연산을 하는 C 코드와 transpose함수 호출 후 행렬의 상태이다. ㉠에 들어갈 코드로 옳은 것은?

#include <stdio.h> #define R 3 #define C 3 void transpose(int A[R][C], int B[R][C]) { for(int r = 0; r < R; r++) for(int c = 0; c < C; c++) ㉠ } int main(int argc, char* argv[]) { int array1[R][C] = {{1,2,3},{4,5,6},{7,8,9}}; int array2[R][C] = {0}; transpose(array1, array2); return 0; }
transpose함수 호출 후 행렬의 상태:
array1:	1 2 3 4 5 6 7 8 9	array2:	1 4 7 2 5 8 3 6 9

열 우선(column major) 순서로 저장되는 3차원 배열 student[2][3][4]가 있을 때, 첫 번째 원소인 student[0][0][0]의 주소가 1024이면 student[1][2][2]의 주소는? (단, 배열 student의 각 원소의 크기는 24byte이고, 저장 순서는 [0][0][0],…,[0][2][3],[1][0][0],…,[1][2][3] 순서로 저장한다)

다음 C 코드에서 함수 A와 B는 최대 공약수를 구하는 함수이다. 함수 B가 함수 A와 같은 결과를 출력하도록 ㉠, ㉡에 들어갈 내용을 바르게 연결한 것은?

int A(int x, int y){
  int r;
  while (y != 0){
    r = x % y;  x = y;  y = r;
  }
  return x;
}

int B(int x, int y) {
  int r;
  if (          ㉠          ) return x;
  else {
    r = x % y;
    return           ㉡          
  }
}

㉠ ㉡

C 언어에서 배열과 연결리스트에 대한 설명으로 옳지 않은 것은?

다음은 기수정렬 알고리즘이다. ㉠이 두 번 실행된 후의 결과로 옳은 것은?

	<조 건>
○ LSD(Least Significant Digit)는 가장 낮은 자릿수이고, MSD(Most Significant Digit)는 가장 높은 자릿수이다. 135의 경우 LSD 위치의 값은 5이고 MSD 위치의 값은 1이다. ○ 버킷은 10개 큐로 구현한다. ○ list는 배열로 구현하며 초깃값은 (437, 125, 85, 7, 632, 194)이고 n은 6이다.
RadixSort(list, n) { for(d ← LSD의 위치에서 MSD위치로 한 자리씩 이동){ for(i ← list의 0번째 원소부터 n-1까지 반복){ list의 i번째 원소를 d의 위칫값에 따라 0번부터 9번 사이의 버킷에 삽입한다. } for(b ← 0번 버킷부터 9번 버킷까지 반복){ b번째 버킷에서 원소들을 순차적으로 읽어서 list에 재배정한다. } ㉠ list의 원소를 순서대로 출력한다. } }

데이터 <1, 3, 5, 7, 8, 10, 9>를 차례대로 하나씩 입력받아 이진 탐색 트리와 AVL 트리를 각각 만들었을 때, 두 트리 간의 높이 차는?

초기 빈 상태의 트리에 다섯 개의 키 <1, 5, 3, 2, 6>를 차례대로 입력받아 디지털 탐색 트리를 만든 후, 전위 순회한 결과로 옳은 것은? (단, 각 키는 3비트 이진수로 표현한다)

입력받은 수식의 괄호쌍이 맞는지 스택 $S$를 이용하여 판단하는 알고리즘 DDD를 작성하였다. 수식에 존재하는 괄호는 소괄호 ‘()’이며, 다른 괄호는 수식에 존재하지 않는다. 수식의 길이는 n이며, 배열 X에 저장되어 입력된다. 알고리즘 DDD는 X를 입력받아 X에 저장된 수식의 괄호쌍이 맞으면 true, 그렇지 않으면 false를 반환하는 함수이다. ㉠ ～ ㉢에 들어갈 코드를 바르게 연결한 것은? (단, $S.push(c)$는 스택 $S$에 문자 $c$를 삽입하는 연산, $S.pop()$은 $S$에서 삭제하는 연산, $S.empty()$는 $S$가 비어 있으면 true, 아니면 false를 반환하는 함수이다)

Algorithm $DDD(X,n)$
Let $S$ be an empty stack
for $i\leftarrow 0$ to $n-1$ do
  if $X[i]$ = ‘(’ then 
    $S.push(X[i])$
  else if $X[i]$ = ‘)’ then
    if $S.empty()$ then
             ㉠       
    end if
    $S.pop()$
  end if
end for
if $S.empty()$ then
         ㉡       
else 
         ㉢       
end if

㉠ ㉡ ㉢

다음과 같은 2－3－4 트리에 키 6과 7을 차례로 삽입한 이후의 트리 상태에 대한 설명으로 옳은 것은?

다음 행렬은 그래프(graph)를 인접 행렬(adjacency matrix)로 나타낸 것이다. 이 그래프에서 솔린 알고리즘(Sollin algorithm)을 이용하여 최소 비용 신장 트리(minimum spanning tree)를 찾고자 한다. 알고리즘 수행 과정에서 나타나는 부분 그래프에 해당하지 않는 것은? (단, 부분 그래프는 간선의 집합으로 표현하며, 간선은 그래프에 포함된 두 정점 v, k에 대응하여 (v, k)의 형태로 표현한다)

정점	0	1	2	3	4	5	6
0	0	20	15	∞	∞	8	∞
1	20	0	5	12	∞	∞	∞
2	15	5	0	25	35	28	6
3	∞	12	25	0	7	∞	∞
4	∞	∞	35	7	0	∞	11
5	8	∞	28	∞	∞	0	9
6	∞	∞	6	∞	11	9	0

다음은 방향그래프를 인접 리스트로 표현한 것이다. 이 그래프에 대한 설명으로 옳지 않은 것은?

승자 트리는 단말 노드(leaf node)에서부터 시작해서, 가장 작은 키 값을 갖는 노드(승자)를 찾아 부모로 올려서 루트 노드로부터 가장 작은 값을 찾아내는 방식이다. 승자 트리의 단말 노드에는 정렬된 배열(run)이 각각 달려 있고, 이 run에서 첫 번째 값을 읽어 가장 작은 값을 올려 내는 방식으로 모든 run을 비우면서 값을 정렬하게 된다. 8개의 run이 있는 아래 승자 트리에서 6, 8, 9 순서대로 3개의 레코드를 출력하고 난 뒤 run이 생략된 승자 트리의 형태로 옳은 것은?

다음 코드는 C 언어를 이용하여 주어진 연결 리스트 구조의 데이터에 대한 삽입 정렬 함수를 구현한 것이다. ㉠ ～ ㉤에 들어갈 코드를 바르게 연결한 것은?

typedef struct _node { int data; struct _node *next; }node; void Insert(node **headRef, node *newNode) { if (*headRef == NULL || (*headRef)->data >= newNode->data) { newNode->next = *headRef; *headRef = newNode; } else { node *current = *headRef; while (current->next != NULL && current->next->data < newNode->data){ ㉠ } ㉡ ㉢ } } void Sort(node **headRef) { node *result = NULL, *current = *headRef; node *next; while (current!=NULL) { ㉣ Insert(&result, current); ㉤ } *headRef = result; }

A : current->next = current; B : current = current->next; C : current->next = newNode; D : next = current->next; E : current->next = next; F : current = next; G : newNode->next = current->next;

㉠ ㉡ ㉢ ㉣ ㉤

단순 무방향 그래프(simple undirected graph) G가 주어졌을 때, 정점(vertex)의 중복 방문을 허용하되, 간선(edge)의 중복은 허용하지 않는 경로(path)를 트레일(trail)이라고 한다. 그래프의 모든 간선들을 단 한 번씩만 통과하되 출발점과 도착점이 일치하지 않는 것을 오일러 트레일(Euler trail)이라고 할 때, 다음 그래프 중에서 오일러 트레일이 존재하지 않는 그래프는?

비어 있는 레드－블랙(red-black) 트리에 <19, 18, 2, 15, 6, 13, 7>을 순서대로 입력한 결과 생성되는 레드-블랙 트리로 옳은 것은? (단, 점선 노드는 레드 노드, 점선 링크는 레드 링크이며, 실선 노드는 블랙 노드, 실선 링크는 블랙 링크이고, 리프 노드에 연결된 사각형의 단말은 외부 노드를 의미한다)