5급 공채 2차

2024년 5급 공채 기술 2차 자료구조론

문제 4개 · 100점. 참고 답안·채점 기준은 앱에서 볼 수 있습니다.

제1문 (20점)

다음 C언어 형식의 구조로 최대 MAX_QUEUE_SIZE-1개의 원소를 저장할 수 있는 원형 큐 queue를 구현하고자 한다. 아래의 그림은 구현하는 원형 큐의 최초 공백 상태(front = 0, rear = 0)에서 세 원소 A, B, C를 순서대로 삽입한 후의 상태를 보여준다. 다음 물음에 답하시오. (단, rear는 큐에서 원소가 삽입되는 위치이고 front는 삭제되는 위치이다) (총 20점)
#define MAX_QUEUE_SIZE 8

typedef char element;
element queue[MAX_QUEUE_SIZE];
int rear = 0;
int front = 0;

[그림]
  1. (1) 위에서 제시한 C언어 형식의 변수만을 사용하여 원형 큐에 하나의 원소 item을 삽입하는 addq() 함수의 ㉠, ㉡, ㉢과 하나의 원소를 삭제하는 deleteq() 함수의 ㉣, ㉤, ㉥에 들어갈 C언어 코드를 작성하시오. (단, queueIsFull()는 원형 큐가 포화 상태에서 원소 삽입 시 오류처리 함수이고 queueIsEmpty()는 공백 상태에서 원소 삭제 시 오류처리 함수이다) (12점)
    void addq(element item)
    {
    if(
    ㉠
    )
    queueIsFull();
    else {
    ㉡
    ;
    ㉢
    ;
    }
    }

    element deleteq()
    {
    if(
    ㉣
    )
    return queueIsEmpty();
    ㉤
    ;
    ㉥
    ;
    }
    ㉠
    ㉡
    ㉢
    ㉣
    ㉤
    ㉥
  2. (2) 위에서 제시한 C언어 형식의 구조에 하나의 정수형(int) 전역 변수 flag만을 추가하여 원형 큐 queue가 최대 MAX_QUEUE_SIZE개의 원소를 저장할 수 있도록 두 함수 addq()와 deleteq()를 C언어 형식의 의사코드(pseudo code)로 작성하시오. (단, flag는 두 정수 0과 1중 하나의 값만 가질 수 있으며, 초깃값은 0이다) (8점)

제2문 (30점)

다음 가중 방향 그래프(weighted directed graph)에 대한 물음에 답하시오. (총 30점)
[그림]
  1. (1) 위 그래프를 인접 행렬(adjacency matrix)로 표현하시오. (단, 행과 열의 순서는 알파벳 순이다) (7점)
  2. (2) 정점 A에서 정점 D로의 경로는 여러 가지가 존재한다. 해당 경로 상의 간선의 개수가 k개 이하인 모든 경로의 길이 중 가장 작은 값을 ‘k -최단 경로의 길이’라고 할 때, Bellman-Ford 알고리즘을 이용하여 1 \, \le k \le 4인 k에 대해 정점 A에서 정점 D로의 k -최단 경로의 길이를 각각 구하시오. (단, 하나의 경로 상에 같은 정점이 여러 번 나올 수 있고, 경로의 길이는 경로 상의 간선의 가중치 합이며, k -최단 경로의 길이가 존재하지 않으면 \infty(무한대)로 표현한다) (14점)
  3. (3) 위 그래프에는 길이가 음인 사이클이 존재한다. Bellman-Ford 알고리즘을 활용하여 이를 확인하는 방법을 제시하고 그 이유를 설명하시오. (사이클의 길이는 사이클 상의 간선의 가중치 합이다) (9점)

제3문 (30점)

허프만 코딩(Huffman coding)은 데이터를 압축하는 알고리즘 중 하나로, 빈도가 높은 문자에는 짧은 비트를 할당하고, 빈도가 낮은 문자에는 긴 비트를 할당하여 데이터를 효율적으로 압축하는 방법이다. 다음과 같은 문자와 빈도수로 이루어진 메시지에 허프만 코딩을 적용할 때, 다음 질문에 답하시오. (총 30점)
문자(빈도수):A(2), B(3), C(7), D(11), E(15)
  1. (1) 허프만 트리를 그리시오. (단, 상대적으로 작은 값을 가진 노드로의 간선에 작은 값을 배정한다) (10점)
  2. (2) 1)의 허프만 트리에서 각 문자에 대한 허프만 코드를 생성하시오. (6점)
  3. (3) 2)의 허프만 코드를 활용하여 문자열 "ABCADEAE"를 압축한 결과의 비트 수를 계산하시오. (6점)
  4. (4) 2)의 허프만 코드에 의해 압축된 비트열 "011001101010110010100100"을 해독하여 원래 문자열을 찾으시오. (8점)

제4문 (20점)

AVL 트리에 대한 다음 물음에 답하시오. (총 20점)
  1. (1) 아래와 같이 왼쪽에서 오른쪽으로 데이터를 순서대로 삽입하는 경우 AVL 트리가 만들어지는 과정을 단계별로 작성하시오. (15점)
    789215364
  2. (2) 1)에서 최종적으로 구축된 AVL 트리를 후위순회(postorder traversal) 시 방문하는 노드를 순서대로 쓰시오. (5점)