5급 공채 2차

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

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

제1문 (20점)

크기 13인 빈 해시 테이블에 해시 함수 f ( x )＝(2x＋3) mod 13을 이용하여 차례로 값을 입력하려고 한다. 만약 충돌이 발생하면 선형조사법(linear probing)을 이용하여 충돌을 해결한다. 다음 물음에 답하시오. (총 20점)
  1. (1) 26, 23, 88, 78, 57, 9, 44, 56, 82, 20이 입력되었을 때 해시 테이블을 보이시오. (10점)
  2. (2) 선형조사법 대신 다음과 같은 방법을 통해서 충돌을 해결할 수 있다. 26, 23, 88, 78, 57, 9, 44, 56, 20이 입력되었을 때 해시 테이블을 보이시오. (10점)
    ○충돌이 발생하면, f ( x ) 대신 두 번째 해시 함수 g ( x )를 이용하여 삽입 위치를 계산하고 이 위치가 비어있다면 여기에 값을 저장한다. 만약 f ( x ) 위치에서도 g ( x ) 위치에서도 모두 충돌이 발생한다면 새로운 해시 테이블을 생성하고 f ( x )와 g ( x )를 사용하여 충돌이 발생하지 않는 위치에 값을 저장한다.
    ○g ( x )＝(3x＋4) mod 13

제2문 (20점)

다음은 C언어로 구현한 정수 계수 다항식을 위한 구조체 표현들이다. 정수 계수 다항식을 저장할 때 PolyA 표현에서는 각 다항식별로 별도의 구조체가 만들어지고, PolyB 표현에서는 배열 terms 내에서 서로 다른 위치에 다항식들이 저장되어 별도의 인덱스 값들을 통해 접근이 가능하게 된다. 다음 물음에 답하시오. (총 20점)
#define MAX_DEGREE 101
typedef struct {
int degree; // 다항식의 차수
int coef[MAX_DEGREE]; // 각 차수별 계수
} PolyA;

#define MAX_TERMS 101
typedef struct {
int expon; // 각 항의 지수
int coef; // 각 항의 계수
} PolyB;
PolyB terms[MAX_TERMS];
int avail = 0; // terms 배열 내의 다음 가용 공간 위치
  1. (1) 공간사용 측면에서 PolyA의 표현이 PolyB의 표현보다 좋은 경우와 나쁜 경우를 각각의 다항식 예시로 제시하고, 그 이유를 설명하시오. (10점)
  2. (2) PolyA 표현으로 이루어진 2개의 정수 계수 다항식 C와 D를 입력받아 두 다항식의 합(C＋D) 차수를 구하기 위한 함수 int add_Poly_Dim(PolyA C, PolyA D)을 C언어 형식의 의사코드로 제시하고, 최악의 경우의 시간복잡도를 빅오(Big-Oh) 표기법으로 표현하시오. (단, 입력된 다항식 C와 D의 최고차항의 계수는 0이 아님을 가정하고, 가능한 효율적인 구현을 제시한다) (10점)

제3문 (30점)

다음 그래프는 도시와 도시의 도로 상태를 나타내고 있다. 다익스트라(Dijkstra)의 최단경로 알고리즘을 이용하여 도시들 사이의 최단경로를 구하고자 할 때, 다음 물음에 답하시오. (단, 각 정점은 도시를 의미하고, 각 간선의 숫자는 연결된 두 도시를 자동차로 이동할 때 소요되는 시간(분)을 의미한다) (총 30점)
[그림]
  1. (1) 자동차로 도시 A에서 도시 C까지 이동할 때 최단 경로를 구하는 과정을 그래프로 보이고, 최소시간을 구하시오. (단, distance가 동일한 경우, 알파벳 역순으로 도시를 선택한다) (15점)
  2. (2) 이 도시의 외곽순환도로는 AB, BC, CD, 그리고 DA와 같이 4개의 구간으로 나누어져 있고, 각 구간을 통과하는 시간은 30분으로 일정하다. 외곽순환도로의 개선작업을 통하여 4개 구간의 통행 시간을 기존 30분에서 m분으로 시간을 단축하고자 한다. 개선작업이 이루어진 후 도시 A에서 도시 C까지 가는 최소시간이 2분 줄어들었다고 할 때 m이 유도되는 과정과 값을 구하고, 새로운 최단 경로를 구하시오. (15점)

제4문 (30점)

다음과 같이 구성된 AVL 트리에 대한 다음 물음에 답하시오. (총 30점)
[그림]
  1. (1) 구성된 AVL 트리에서 아래 순서대로 8개의 노드를 삽입 및 삭제할 경우, AVL 트리에 추가되는 진행 과정을 쓰시오. (단, ‘[그림]’는 삽입, ‘[그림]’는 삭제를 의미한다) (15점)
    [그림]19, [그림]29, [그림]5, [그림]9, [그림]23, [그림]18, [그림]20, [그림]16
  2. (2) 다음은 C언어로 구현된 AVL 트리의 노드 구조이다.
    typedef struct avl {
    int data;
    struct avl *pLchild;
    struct avl *pRchild;
    } node;

    1)의 문제에서 8개의 노드에 대한 삽입 및 삭제를 진행하면서 각 과정 중 균형 유지를 위해 수행된 회전의 종류들을 명시하고, 해당 회전을 수행하는 함수들을 C 언어로 작성하시오. (단, 함수 작성 시 각 함수의 return 값은 회전된 서브 트리의 최상위 노드를 가리키는 포인터이며, 필요시 답을 작성하는 과정에서 정의된 함수를 재사용할 수 있다) (15점)
    끝