5급 공채 2차

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

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

제1문 (30점)

다음 방향 그래프 G＝(V, E)에 대해 위상 정렬을 수행하고자 한다. 다음 물음에 답하시오. (총 30점)
정점 집합 V＝{0, 1, 2, 3, 4, 5}
간선 집합 E＝{(0→2), (0→3), (1→2), (1→4), (2→3), (2→5), (3→5), (4→5)}
  1. (1) 그래프 G에 대한 위상 정렬 결과 3개를 제시하시오. (10점)
  2. (2) 위상 정렬의 2가지 주요 구현 방식인 진입차수 기반 알고리즘과 DFS 기반 알고리즘의 작동 원리를 설명하고, 각각의 장단점을 비교하시오. (10점)
  3. (3) 위상 정렬이 불가능한 방향 그래프의 조건을 설명하고, 그래프 G에 하나의 간선만 추가하여 위상 정렬이 불가능하도록 하는 서로 다른 방법 3가지를 제시하시오. (10점)

제2문 (30점)

10개의 정수가 저장된 배열 A＝[12, 5, 18, 20, 30, 8, 15, 25, 2, 10]가 있다. 이 배열의 원소를 순서대로 삽입하여 최대 힙(Max Heap)을 구성하고, 이를 이용하여 4번째로 큰 수를 추출하려고 한다. 다음 물음에 답하시오. (총 30점)
  1. (1) 배열 A의 원소를 순서대로 삽입하여 생성된 최종 최대 힙의 모습을 과정과 함께 트리로 그리고, 이를 저장하는 1차원 배열을 제시하시오. (5점)
  2. (2) 힙에서 원소를 삭제할 때 마지막 노드를 루트로 옮긴 후 수행하는 재구축(Heapify) 과정의 원리를 설명하시오. (5점)
  3. (3) 최대 힙에서 4번째로 큰 수를 찾기 위해 루트 노드를 삭제하는 과정을 3번 반복한 후, 4번째 삭제 직전의 힙 상태를 트리로 그리시오. (5점)
  4. (4) 원소의 개수가 n개인 임의의 배열에 대해 최대 힙을 이용하여 k번째로 큰 수를 찾는 알고리즘의 전체 시간복잡도를 분석하려 한다. 아래의 초기 힙 구성방식 각각에 대해 전체 시간복잡도를 빅오(Big-Oh) 표기법으로 표현하고, 그 이유를 n과 k를 사용하여 논리적으로 설명하시오. (15점)
    ①배열의 원소를 순서대로 삽입하여 최대 힙을 구성
    ②주어진 배열을 하나의 완전 이진 트리로 간주하여 이를 최대 힙으로 변환

제3문 (20점)

다음 C언어 형식의 구조로 스택(Stack)을 이용한 괄호 검사를 구현하고자 한다. 괄호의 종류는 소괄호 (), 중괄호 {}, 대괄호 [] 3가지이며, 각 여는 괄호에 대하여 대응하는 닫는 괄호는 중첩된 순서를 따라 짝지어져야 한다. 다음 물음에 답하시오. (단, 입력 문자열에서 공백 문자는 무시한다) (총 20점)
#define MAX_SIZE 20

typedef struct {
char data[MAX_SIZE];
int top;
} Stack;

void push(Stack *s, char item); /* 스택에 item을 삽입 */
char pop(Stack *s); /* 스택에서 원소를 삭제하고 반환 */
int isEmpty(Stack *s); /* 스택이 공백이면 1, 아니면 0 반환 */
  1. (1) 위에서 제시한 자료구조를 사용하여 괄호 검사를 수행하는 checkBracket() 함수의 ㉠～㉣에 들어갈 C언어 코드를 작성하시오. (단, checkBracket() 함수는 올바르게 짝지어진 괄호 문자열이 아닌 경우 0을 반환한다) (9점)
    int checkBracket(char *expr) {
    Stack s;
    s.top = -1;
    char ch, open;

    while (*expr) {
    ch = *expr++;
    if (ch == '(' || ch == '{' || ch == '[') {
    ㉠
    ; /* 여는 괄호 처리 */
    } else if (ch == ')' || ch == '}' || ch == ']') {
    if (
    ㉡
    )
    return 0;
    open =
    ㉢
    ;
    if ((ch == ')' && open != '(') ||
    (ch == '}' && open != '{') ||
    (ch == ']' && open != '['))
    return 0;
    }
    }
    return
    ㉣
    ; /* 스택이 비어 있으면 유효 */
    }
    ㉠
    ㉡
    ㉢
    ㉣
  2. (2) 아래 두 문자열 ①과 ② 각각에 대해 스택을 이용한 괄호 검사 과정을 단계별로 보이고, 최종적으로 올바른 괄호 문자열인지 판별하시오. (단, 각 단계에서 처리하는 문자와 스택의 상태를 명시해야 한다) (6점)
    ①{ ( [ ] ) } ( )
    ②{ ( [ ) ] }
  3. (3) 스택을 이용한 괄호 검사 알고리즘의 시간복잡도를 빅오 표기법으로 표현하고 그 이유를 설명하시오. (5점)

제4문 (20점)

다음은 오버플로우 방지를 위해 디렉터리를 이용한 동적 해싱을 수행하기 위한 조건이다. 다음 물음에 답하시오. (총 20점)
○t는 디렉터리의 깊이이고, 초기 값은 2이다. (t＝2)
○디렉터리의 크기는 2t이다.
○k는 해시함수의 키 값이다.
○디렉터리 인덱싱을 위한 해시함수 h(k,t)＝k mod 2t이다.
○버킷(bucket)당 슬롯(slot)은 2개이다.
  1. (1) 아래 10개의 데이터를 순서대로 동적 해시 테이블에 삽입할 때, ①디렉터리 크기가 첫 번째로 커지게 하는 데이터의 키 값을 제시하고, ②해당 키 값 삽입까지의 과정을 설명하고, ③삽입 후 동적 해시 테이블을 그림으로 보이시오. (단, 각 디렉터리 엔트리가 어떤 버킷을 가리키는지 그림에 표시해야 한다) (10점)
    32 33 40 41 19 18 21 38 36 17
  2. (2) 1)의 데이터를 모두 삽입한 후의 동적 해시 테이블을 그림으로 보이시오. (단, 각 디렉터리 엔트리가 어떤 버킷을 가리키는지 그림에 표시해야 한다) (5점)
  3. (3) 동적 해싱의 장점을 정적 해싱과 비교하여 설명하시오. (5점)
    끝