[7급 국가직 자료구조론] 20년 1회차 기출문제 정답·해설 페이지

[7급 국가직 자료구조론] 20년 1회차
    1[7급 국가직 자료구조론] 20년 1회차
    다음의 D1 ~ D4에서 제시된 키(key) 값의 순서대로 공백(empty) 이진 탐색 트리(binary search tree)에 데이터를 삽입하여 T1 ~ T4를 만들었을 때, 모양이 다른 트리는? (단, 모양은 노드의 키 값과 간선의 연결 구조를 포함한다)
    D1: 4, 2, 3, 6, 8, 5, 7 → 이진 탐색 트리 T1
    D2: 4, 2, 6, 8, 5, 3, 7 → 이진 탐색 트리 T2
    D3: 4, 6, 3, 8, 2, 5, 7 → 이진 탐색 트리 T3
    D4: 4, 6, 8, 5, 7, 2, 3 → 이진 탐색 트리 T4
    1
    T1
    2
    T2
    3
    T3
    4
    T4
    해설

    모양이 다른 트리는 T3이다.

    이진 탐색 트리의 모양은 각 키가 들어갈 때 이미 있는 조상 노드와의 대소 관계로 정해진다. 루트 4의 왼쪽 부분에서 T1·T2·T4는 2가 먼저 들어가 2의 오른쪽 자식이 3이 되지만, T3는 3이 먼저 들어가 3의 왼쪽 자식이 2가 된다.

    • T1(D1): 루트 4, 왼쪽 2(오른쪽 자식 3), 오른쪽 6(왼쪽 5, 오른쪽 8), 8의 왼쪽 자식 7인 구조이다.
    • T2(D2): 삽입 순서만 다를 뿐 모든 키의 부모가 T1과 같아 같은 모양이다.
    • T4(D4): 오른쪽 키(6, 8, 5, 7)를 먼저 넣고 2, 3을 나중에 넣어도 부모 관계가 T1과 같아 같은 모양이다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    2[7급 국가직 자료구조론] 20년 1회차
    다음 최소 힙(min heap)에 대한 설명으로 옳지 않은 것은?
    문제 이미지
    1
    완전 이진 트리(complete binary tree)이다.
    2
    노드 A는 가장 작은 키 값을 가져야 한다.
    3
    노드 B와 노드 C가 같은 키 값을 가질 수 있다.
    4
    노드 C는 노드 D보다 작은 키 값을 가져야 한다.
    해설

    옳지 않은 것은 노드 C가 노드 D보다 작아야 한다는 설명이다.

    최소 힙은 부모 키 ≤ 자식 키라는 조건만 만족하면 되므로, C와 D처럼 서로 다른 서브트리에 있는 노드 사이에는 크기 관계가 정해지지 않는다.

    • 완전 이진 트리 — 힙은 완전 이진 트리 형태로 유지되므로 옳다.
    • 루트 A의 최솟값 — 모든 노드의 조상인 루트가 가장 작은 키를 가지므로 옳다.
    • B와 C의 동일 키 — 형제 노드끼리는 제약이 없어 같은 키를 가질 수 있으므로 옳다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    3[7급 국가직 자료구조론] 20년 1회차
    다음 인접 행렬(adjacency matrix)에 의해 표현되는 그래프에 대한 설명으로 옳은 것은? (단, 인접 행렬에서 [i]는 정점 i를 의미한다)
    [0][1][2][3][4]
    [0]01000
    [1]00110
    [2]00001
    [3]00001
    [4]01000
    1
    간선의 개수가 5개인 무방향 그래프(undirected graph)이다.
    2
    정점 0에서 정점 4까지의 단순 경로(simple path) 길이는 2이다.
    3
    정점 3에 도달하기 위한 경로가 없는 정점이 있다.
    4
    사이클(cycle)이 존재하는 방향 그래프(directed graph)이다.
    해설

    주어진 그래프는 사이클이 존재하는 방향 그래프이다.

    행렬이 대칭이 아니므로 방향 그래프이고, 간선은 0→1, 1→2, 1→3, 2→4, 3→4, 4→1의 6개이다. 이 중 1→2→4→1(또는 1→3→4→1)이 사이클을 이룬다.

    • 간선 5개인 무방향 그래프: 행렬이 비대칭인 방향 그래프이고 간선도 6개이다.
    • 정점 0에서 정점 4까지 단순 경로 길이 2: 0→1→2→4 또는 0→1→3→4로 길이가 3이다.
    • 정점 3에 도달할 경로가 없는 정점: 0→1→3, 2→4→1→3, 4→1→3처럼 모든 정점이 정점 1을 거쳐 정점 3에 도달한다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    4[7급 국가직 자료구조론] 20년 1회차
    다음 가중 그래프(weighted graph)에 Kruskal 알고리즘을 적용하여 구성한 최소 비용 신장 트리(minimum cost spanning tree)의 최소 비용은?
    문제 이미지
    1
    36
    2
    39
    3
    44
    4
    46
    해설

    Kruskal 알고리즘으로 구한 최소 비용 신장 트리의 비용은 39이다.

    가중치가 작은 간선부터 고르되 사이클을 만드는 간선은 버린다. A-B(2), A-C(3), C-D(4), D-G(4)를 고른 뒤 B-D(5)는 A-B-D-C 사이클을 만들어 제외한다.

    이어서 G-I(5), D-H(6), B-E(7), H-F(8)를 고르면 정점 9개에 간선 8개가 되어 완성된다.
    2+3+4+4+5+6+7+8=392+3+4+4+5+6+7+8=39

    • 36 — 최소 합 39보다 작아, 사이클 없이 9개 정점을 모두 잇는 방법으로는 얻을 수 없다.
    • 44 — D-G(4) 대신 E-G(9)로 G를 연결한 신장 트리의 비용으로, 최소가 아니다.
    • 46 — 최소 비용보다 큰 값으로, 더 무거운 간선을 포함한 신장 트리의 비용이다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    5[7급 국가직 자료구조론] 20년 1회차
    키 값이 1, 2, 3, 4, 5, 6, 7, 8인 8개의 노드로 구성된 이진 탐색 트리를 전위 순회(preorder traversal)하면, 키 값 6, 2, 1, 4, 3, 5, 8, 7 순서로 노드를 방문한다. 이 트리를 후위 순회(postorder traversal)할 경우 방문 노드의 키 값을 방문 순서대로 바르게 나열한 것은?
    1
    1, 2, 3, 4, 5, 6, 7, 8
    2
    1, 3, 2, 6, 5, 8, 7, 4
    3
    1, 3, 5, 4, 2, 7, 8, 6
    4
    8, 7, 6, 5, 4, 3, 2, 1
    해설

    후위 순회 결과는 1, 3, 5, 4, 2, 7, 8, 6이다.

    전위 순회의 첫 키 6이 루트이고, 이진 탐색 트리이므로 6보다 작은 2, 1, 4, 3, 5는 왼쪽, 8, 7은 오른쪽 서브트리이다. 같은 방식으로 왼쪽은 2(왼쪽 1, 오른쪽 4(왼쪽 3, 오른쪽 5)), 오른쪽은 8(왼쪽 7)로 복원된다.

    후위 순회는 왼쪽 → 오른쪽 → 루트 순이므로 1, 3, 5, 4, 2를 방문한 뒤 7, 8, 마지막에 루트 6을 방문한다.

    • 1부터 8까지 오름차순: 이진 탐색 트리의 중위 순회 결과이다.
    • 1, 3, 2, 6, 5, 8, 7, 4: 루트 6이 마지막에 오지 않아 후위 순회가 될 수 없다.
    • 8부터 1까지 내림차순: 오른쪽 → 루트 → 왼쪽으로 도는 역방향 중위 순회 결과이다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    6[7급 국가직 자료구조론] 20년 1회차
    차수(m)가 3인 공백 B-트리에 19, 18, 2, 15, 6, 13, 7을 순서대로 삽입하여 구성한 B-트리에 대한 설명으로 옳은 것은?
    1
    트리의 높이(height)가 1이다.
    2
    15는 루트(root) 노드에 저장되어 있다.
    3
    3개의 자식(child) 노드를 가지는 노드가 존재한다.
    4
    6이 저장된 노드와 18이 저장된 노드는 형제(sibling) 관계이다.
    해설

    6이 저장된 노드와 18이 저장된 노드는 형제 관계이다.

    차수 3인 B-트리는 노드당 키가 최대 2개이므로 키가 3개가 되면 가운데 키를 부모로 올려 분할한다. 2 삽입 때 18이, 6 삽입 때 6이 올라가 루트가 [6, 18]이 되고, 7 삽입 때 [7, 13, 15]에서 13이 올라가 루트 [6, 13, 18]이 다시 분할되면서 13이 새 루트가 된다.

    최종 트리는 루트 13 아래 6과 18이 있고, 6의 자식은 2와 7, 18의 자식은 15와 19이다.

    • 트리의 높이가 1: 루트 아래로 두 단계가 더 있는 3레벨 트리이므로 높이가 1이 아니다.
    • 15가 루트에 저장: 루트에는 13만 있고 15는 리프에 있다.
    • 자식 3개인 노드가 존재: 모든 내부 노드가 키 1개와 자식 2개만 가진다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    7[7급 국가직 자료구조론] 20년 1회차
    스택을 이용하여 다음 후위 표현식(postfix expression)의 연산을 수행하였다. 최종 결과 값과 연산 과정에서 스택 내 피연산자의 최대 개수를 바르게 연결한 것은? (단, *은 곱셈 연산자이고 /은 나눗셈 연산자이다)
    9 1 - 2 / 1 2 1 + * - 1 -
    최종 결과 값 / 스택 내 피연산자의 최대 개수
    1
    0 / 3
    2
    0 / 4
    3
    1 / 3
    4
    1 / 4
    해설

    최종 결과 값은 0이고, 스택 내 피연산자의 최대 개수는 4이다.

    9 1 − 로 8, 이어서 2 / 로 4가 되어 스택에는 4만 남는다. 다음에 1, 2, 1을 차례로 넣으면 스택이 [4, 1, 2, 1]로 피연산자 4개가 쌓여 최대가 된다.

    이후 2 1 + 로 3, 1 3 * 로 3, 4 3 − 로 1, 마지막 1 1 − 로 0이 된다.

    • 0 / 3: 결과 값은 맞지만 덧셈 직전에 피연산자 4개가 쌓인다.
    • 1 / 3: 마지막 뺄셈 전의 중간 값이고 최대 개수도 4이다.
    • 1 / 4: 최대 개수는 맞지만 마지막 뺄셈까지 수행하면 결과는 0이다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    8[7급 국가직 자료구조론] 20년 1회차
    다음의 표는 단순 연결 리스트(singly linked list)를 표현한 것으로 각 행은 각 노드의 주소, 데이터 및 다음 노드 주소로 구성되어 있다. <다음 노드 주소 값>은 주소가 102인 노드를 삭제한 후 다음 노드 주소의 값을 설명한 것이다. ㉠ ~ ㉣에 들어갈 값을 바르게 연결한 것은? (단, 특정 노드의 다음 노드가 없을 때 그 노드의 다음 노드 주소 값은 NULL이다)
    주소데이터다음 노드 주소
    100LEENULL
    101PARK104
    102KIM101
    103JUNG102
    104SEO100
    <다음 노드 주소 값>
    ○ 주소가 100인 노드의 다음 노드 주소는 ( ㉠ )이다.
    ○ 주소가 101인 노드의 다음 노드 주소는 ( ㉡ )이다.
    ○ 주소가 103인 노드의 다음 노드 주소는 ( ㉢ )이다.
    ○ 주소가 104인 노드의 다음 노드 주소는 ( ㉣ )이다.
    ㉠ / ㉡ / ㉢ / ㉣
    1
    NULL / 104 / 101 / 100
    2
    NULL / 103 / 101 / 104
    3
    101 / 103 / 102 / 104
    4
    101 / 104 / 102 / 100
    해설

    주소 102인 노드를 삭제하면 주소 103 노드의 다음 주소만 101로 바뀌므로 NULL / 104 / 101 / 100이 된다.

    링크를 따라가면 리스트는 103(JUNG) → 102(KIM) → 101(PARK) → 104(SEO) → 100(LEE) → NULL 순서이다. 단순 연결 리스트의 삭제는 선행 노드의 링크를 삭제 노드의 다음 노드로 바꾸는 것이므로 나머지 링크는 그대로 유지된다.

    • NULL / 103 / 101 / 104: 주소 101, 104 노드의 링크는 삭제와 무관해 바뀌지 않는다.
    • 101 / 103 / 102 / 104: 마지막 노드(주소 100)는 NULL을 유지해야 하고, 주소 103 노드가 삭제된 노드를 계속 가리키게 된다.
    • 101 / 104 / 102 / 100: 마지막 노드의 NULL을 바꾸었고, 주소 103 노드가 삭제된 노드를 계속 가리키게 된다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    9[7급 국가직 자료구조론] 20년 1회차
    다음 C 언어 프로그램의 출력 결과는? (단, 배열 h의 시작 주소는 6487296이고, 자료형 int와 float는 4바이트의 크기를 가진다)
    #include <stdio.h>

    int main()
    {
    struct human {
    char sextype;
    union t {
    char children[3];
    char beard[3];
    } u;
    int age;
    struct date {
    int month;
    int day;
    int year;
    } dob;
    int personalID;
    float salary;
    } h[10];
    printf("%d, %d, %d", sizeof(struct human),
    &h[3].u.children[0] - &h[0].sextype,
    &h[5].u.beard[1] - &h[0].sextype);
    }
    1
    28, 85, 142
    2
    28, 86, 143
    3
    31, 94, 157
    4
    31, 95, 158
    해설

    출력 결과는 28, 85, 142이다.

    int는 4의 배수 오프셋에 정렬되므로 sextype(1바이트)이 오프셋 0, 공용체 u(가장 큰 멤버 기준 3바이트)가 오프셋 1~3, age가 4, dob(12바이트)가 8~19, personalID가 20, salary가 24에 놓여 구조체 크기는 28바이트이다.

    char 주소의 차는 바이트 거리이고, 공용체의 children과 beard는 같은 시작 주소를 공유한다.
    3×28+1=853 \times 28 + 1 = 85
    5×28+1+1=1425 \times 28 + 1 + 1 = 142

    • 28, 86, 143: 구조체 크기는 맞지만 u는 오프셋 1에서 시작하므로 차이는 85, 142이다.
    • 31, 94, 157: 공용체를 두 멤버 크기의 합인 6바이트로 보고 정렬 패딩 없이 더한 크기(31바이트)로 계산한 값이다.
    • 31, 95, 158: 구조체 크기를 잘못 본 데다 오프셋도 한 바이트씩 어긋난 값이다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    10[7급 국가직 자료구조론] 20년 1회차
    다음 C 언어 프로그램의 출력 결과는?
    #include <stdio.h>

    #define SWAP(x, y, t) ((t)=(x), (x)=(y), (y)=(t))

    void recursive(char *list, int i, int n) {
    int j, temp;
    if (i == n) {
    for (j = 0 ; j <= n ; j++)
    printf("%c", list[j]);
    printf(" ");
    }
    else {
    for (j = i ; j <= n ; j++) {
    SWAP(list[i], list[j], temp);
    recursive(list, i + 1, n);
    SWAP(list[i], list[j], temp);
    }
    }
    }

    int main()
    {
    char list[3] = {'a', 'b', 'c'};
    recursive(list, 0, 2);
    }
    1
    ab ac bc
    2
    ab bc ca
    3
    abc acb bac bca cba cab
    4
    abc acb bca bac cab cba
    해설

    출력 결과는 abc acb bac bca cba cab이다.

    함수는 위치 i의 문자를 i부터 n까지의 문자와 차례로 교환하고 나머지 자리를 재귀로 처리한 뒤 다시 교환해 원상 복구하는 순열 생성 알고리즘이므로 3글자 순열 6개가 모두 출력된다.

    첫 자리는 a(교환 없음) → b(0·1 교환, bac) → c(0·2 교환, cba) 순이고, 각 경우 둘째 자리 교환으로 abc·acb, bac·bca, cba·cab가 차례로 나온다.

    • ab ac bc: i == n일 때 인덱스 0부터 n까지 세 글자를 출력하므로 두 글자 조합이 나올 수 없다.
    • ab bc ca: 마찬가지로 두 글자 출력은 불가능하며 출력 개수도 6개이다.
    • abc acb bca bac cab cba: b가 맨 앞으로 오면 bac가 먼저, c가 맨 앞으로 오면 abc에서 0·2를 교환한 cba가 먼저 출력된다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    11[7급 국가직 자료구조론] 20년 1회차
    행 우선(row major) 순서로 저장되는 C 언어 2차원 배열 A[5][5]에서 다른 값을 갖는 것은? (단, 임의의 배열 인덱스(index) i(0≤i≤40 \le i \le 4)와 j(0≤j≤40 \le j \le 4)에 대해 A[i][j]가 (i−ji - j)의 값을 가진다)
    1
    A[3][1]
    2
    *(*(A + 3) + 1)
    3
    *(A[3] + 1)
    4
    **((A + 3) + 1)
    해설

    다른 값을 갖는 것은 **((A + 3) + 1)로, A[4][0]의 값인 4가 된다.

    A + 3은 3행을 가리키는 행 포인터이고 *(A + 3)은 A[3], *(A + 3) + 1은 A[3][1]의 주소이다. 반면 (A + 3) + 1은 행 단위로 한 번 더 이동한 A + 4이므로 두 번 역참조하면 A[4][0]이 된다.

    • A[3][1]: 3−1=23 - 1 = 2이다.
    • *(*(A + 3) + 1): A[3][1]의 포인터 표기로 2이다.
    • *(A[3] + 1): A[3] 행의 둘째 원소인 A[3][1]로 2이다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    12[7급 국가직 자료구조론] 20년 1회차
    다음 가중치 그래프에 Prim 알고리즘을 적용하여 최소 비용 신장 트리(minimum cost spanning tree)를 만들 때, 최소 비용과 세 번째로 선택된 간선의 가중치의 합은? (단, A를 시작 정점으로 한다)
    문제 이미지
    1
    13
    2
    14
    3
    15
    4
    16
    해설

    최소 비용 12와 세 번째 간선 가중치 3을 더한 15가 답이다.

    Prim 알고리즘은 현재 트리에 인접한 간선 중 최소 가중치를 하나씩 추가한다. A에서 A-B(2), 이어서 B-F(1), 그다음 후보 중 최소인 B-E(3)가 세 번째로 선택된다.

    이후 E-D(2), 마지막으로 C를 잇는 B-C(4)를 고른다.
    2+1+3+2+4=122+1+3+2+4=12
    12+3=1512+3=15

    • 13 — 세 번째 간선을 1로 잘못 잡은 경우의 값이다.
    • 14 — 세 번째 간선을 2로 잘못 잡은 경우의 값이다.
    • 16 — 세 번째 간선을 4로 보거나 C를 C-F(5)로 연결한 경우의 값이다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    13[7급 국가직 자료구조론] 20년 1회차
    다음 그래프에 대한 너비 우선 탐색(BFS: Breadth First Search)의 방문 순서는? (단, 시작 정점은 A이고, 인접한 정점들은 알파벳 순서로 방문한다)
    문제 이미지
    1
    A, C, D, E, G, I, B, H, F
    2
    A, C, D, E, I, G, H, B, F
    3
    A, C, D, G, B, E, F, H, I
    4
    A, C, D, G, I, B, E, H, F
    해설

    BFS 방문 순서는 A, C, D, E, G, I, B, H, F이다.

    BFS는 큐를 사용해 가까운 정점부터 방문한다. A의 인접 정점 C, D, E를 알파벳 순으로 넣고, C에서 G, D에서 I, E에서 B와 H를 차례로 추가한다.

    마지막으로 B에서 아직 방문하지 않은 F가 추가되어 탐색이 끝난다.

    • A, C, D, E, I, G, … — C가 D보다 먼저 꺼내지므로 C의 이웃 G가 D의 이웃 I보다 앞서야 한다.
    • A, C, D, G, B, … — E는 A와 직접 연결된 1단계 정점이므로 G보다 먼저 방문해야 한다.
    • A, C, D, G, I, B, E, … — 역시 1단계 정점 E가 2단계 정점들보다 뒤에 놓여 BFS 순서가 아니다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    14[7급 국가직 자료구조론] 20년 1회차
    다음에 주어진 최대 힙(max heap)에 키 값이 2, 14, 49, 3, 30, 41, 27, 17인 8개의 데이터를 순서대로 삽입하여 최대 힙을 구성하였다. 구성된 최대 힙에서 모든 리프(leaf) 노드의 키 값의 합은?
    문제 이미지
    1
    63
    2
    73
    3
    108
    4
    113
    해설

    구성된 최대 힙의 리프 키 합은 108이다.

    초기 힙 72, 35, 42에 각 키를 맨 끝에 넣고 부모보다 크면 교환하는 상향 조정을 반복한다. 49는 42와, 30은 2와, 41은 30·35와, 27은 14와 교환된다.

    최종 배열은 72, 41, 49, 35, 27, 42, 3, 2, 30, 14, 17이고, 노드가 11개이므로 여섯째 위치부터 끝까지가 리프이다.
    42+3+2+30+14+17=10842+3+2+30+14+17=108

    • 63 — 최종 리프 여섯 개의 합보다 작아, 리프 일부가 빠진 값이다.
    • 73 — 상향 조정 결과와 다른 리프 구성에서 나오는 값이다.
    • 113 — 최종 리프 합보다 커서, 리프가 아닌 노드의 키가 섞인 값이다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    15[7급 국가직 자료구조론] 20년 1회차
    <조건>을 만족하고 front와 rear의 값이 모두 0인 원형 큐(circular queue)에서 <동작>에 나열된 연산을 순서대로 모두 수행하였다. 연산 완료 후 원형 큐에 존재하는 모든 유효 데이터와 front 및 rear의 값을 바르게 연결한 것은? (단, enqueue(x)에 의해 삽입된 후 dequeue()에 의해 삭제되지 않은 데이터만 유효 데이터로 인정한다)
    <조 건>
    ○ 원형 큐는 원소 개수가 6개인 1차원 배열로 구현되었다.
    ○ front와 rear의 값이 같을 때 원형 큐는 공백 상태이다.
    ○ front와 ((rear + 1) mod 6)의 값이 같을 때 원형 큐는 포화 상태이다.
    ○ enqueue(x)에 의해 rear의 값을 ((rear + 1) mod 6)로 변경한 후 rear가 가리키는 위치에 데이터 x를 삽입한다. 단, 포화 상태일 때에는 데이터 삽입이 이루어지지 않아 원형 큐의 상태가 변하지 않는다.
    ○ dequeue()에 의해 front의 값을 ((front + 1) mod 6)로 변경한 후 front가 가리키는 위치에서 데이터를 빼내어 삭제한다. 단, 공백 상태일 때에는 데이터 삭제가 이루어지지 않아 원형 큐의 상태가 변하지 않는다.
    <동 작>
    enqueue(2) → enqueue(5) → enqueue(7) → enqueue(10) → dequeue() → enqueue(11) → enqueue(15) → enqueue(17) → dequeue() → dequeue() → enqueue(20)
    모든 유효 데이터 / front / rear
    1
    10, 11, 15, 17, 20 / 3 / 1
    2
    10, 11, 15, 20 / 3 / 1
    3
    10, 11, 15, 17, 20 / 4 / 2
    4
    10, 11, 15, 20 / 4 / 2
    해설

    연산 후 유효 데이터는 10, 11, 15, 20이고 front는 3, rear는 1이다.

    enqueue(2), (5), (7), (10)으로 rear가 4, dequeue()로 front가 1이 된다. enqueue(11)로 rear가 5, enqueue(15)로 rear가 0으로 돌아온다.

    이때 front와 (0 + 1) mod 6이 모두 1로 같아 포화 상태이므로 enqueue(17)은 무시된다. 이후 dequeue() 두 번으로 5와 7이 삭제되어 front가 3, enqueue(20)으로 rear가 1이 되어 위치 4, 5, 0, 1에 10, 11, 15, 20이 남는다.

    • 10, 11, 15, 17, 20 / 3 / 1: 포화 상태에서 17은 삽입되지 않는다.
    • 10, 11, 15, 17, 20 / 4 / 2: 17은 삽입되지 않으며 front는 3, rear는 1이다.
    • 10, 11, 15, 20 / 4 / 2: 데이터는 맞지만 dequeue()가 세 번 수행되어 front는 3이고, 17이 무시되므로 rear는 1이다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    16[7급 국가직 자료구조론] 20년 1회차
    키 값 1, 2, 3, 4, 5를 가지는 5개의 레코드로 이루어진 리스트를 퀵 정렬(quick sort)로 오름차순 정렬하고자 한다. 정렬 과정에서 총 비교 횟수가 가장 많은 리스트는? (단, 피봇(pivot)은 정렬하고자 하는 대상의 첫 번째 레코드로 선택한다)
    1
    1, 2, 3, 4, 5
    2
    2, 3, 1, 4, 5
    3
    3, 1, 2, 4, 5
    4
    3, 1, 2, 5, 4
    해설

    총 비교 횟수가 가장 많은 리스트는 이미 정렬된 1, 2, 3, 4, 5이다.

    첫 레코드를 피봇으로 쓰면 정렬된 입력에서는 피봇이 항상 최솟값이 되어 한쪽이 비고 다른 쪽이 하나만 줄어드는 최악의 분할이 반복된다. 분할 한 번에 피봇을 나머지 원소와 비교한다고 보면 다음과 같다(구현에 따라 세부 횟수는 달라도 대소 순서는 같다).
    4+3+2+1=104 + 3 + 2 + 1 = 10

    • 2, 3, 1, 4, 5: 피봇 2로 [1]과 [3, 4, 5]로 나뉘어 4+2+1=74 + 2 + 1 = 7회이다.
    • 3, 1, 2, 4, 5: 피봇 3이 가운데 값이라 두 원소씩 균형 있게 나뉘어 4+1+1=64 + 1 + 1 = 6회이다.
    • 3, 1, 2, 5, 4: 마찬가지로 피봇 3으로 균형 분할되어 6회이다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    17[7급 국가직 자료구조론] 20년 1회차
    다음의 키 값을 가지는 7개의 데이터를 순서대로 삽입하여 AVL 트리를 구성한 후 후위 순회를 수행하였다. 방문 노드들의 키 값을 방문 순서대로 바르게 나열한 것은?
    10, 4, 7, 12, 3, 13, 15
    1
    3, 4, 10, 15, 13, 12, 7
    2
    3, 7, 4, 12, 15, 13, 10
    3
    3, 7, 4, 15, 13, 12, 10
    4
    3, 10, 13, 15, 4, 12, 7
    해설

    후위 순회 결과는 3, 4, 10, 15, 13, 12, 7이다.

    10, 4, 7 삽입 시 LR 불균형이 생겨 7이 루트(왼쪽 4, 오른쪽 10)가 된다. 12, 3을 넣은 뒤 13을 넣으면 10에서 RR 불균형이 생겨 회전 후 12(왼쪽 10, 오른쪽 13)가 7의 오른쪽 자식이 된다.

    마지막 15는 13의 오른쪽에 붙고 모든 노드의 균형 인수가 −1~1 범위라 회전이 없다. 이 트리를 왼쪽 → 오른쪽 → 루트 순으로 방문한다.

    • 3, 7, 4, 12, 15, 13, 10: 회전 후 루트는 7이므로 마지막 방문 노드가 10일 수 없다.
    • 3, 7, 4, 15, 13, 12, 10: 회전 없이 일반 이진 탐색 트리로 삽입했을 때의 결과이다.
    • 3, 10, 13, 15, 4, 12, 7: 리프 3 다음에는 그 부모 4를 방문해야 하는데 10이 먼저 온다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    18[7급 국가직 자료구조론] 20년 1회차
    다음 C 언어 프로그램의 출력 결과는?
    #include <stdio.h>

    void func(char s[], int size) {
    if (size <= 0) return;
    s[size-1] = s[size-1] + 1;
    func(s,size-2);
    }

    int main()
    {
    char str[] = "window";
    func(str, 6);
    printf("%c", str[3]);
    }
    1
    d
    2
    e
    3
    n
    4
    o
    해설

    출력 결과는 e이다.

    func는 s[size-1]을 1 증가시킨 뒤 size를 2씩 줄여 재귀 호출하므로 size가 6, 4, 2일 때 인덱스 5, 3, 1의 문자가 바뀐다.

    문자열 window에서 str[3]은 'd'이고, size가 4인 호출에서 1 증가해 'e'가 된다(str[5]는 'x', str[1]은 'j'로 함께 바뀐다).

    • d: str[3]의 원래 문자로, 재귀 과정에서 1 증가하므로 그대로 남지 않는다.
    • n: str[2]의 원래 문자이며 출력 대상이 아니다.
    • o: str[4]의 원래 문자이며 출력 대상이 아니다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    19[7급 국가직 자료구조론] 20년 1회차
    다음은 1차원 배열 arr에서 두 번째로 큰 수를 찾는 C 언어 함수이다. ㉠, ㉡에 들어갈 내용을 바르게 연결한 것은? (단, 배열 arr의 모든 원소는 서로 다른 양의 정수이고, n은 배열의 크기이며 2보다 크거나 같다)
    void Largest2nd(int *arr, int n){
    int i, max1 = 0, max2 = 0;

    for (i = 0; i < n; i++){
    if (___㉠___){
    max2 = max1;
    max1 = arr[i];
    }
    else if (_____㉡_____)
    max2 = arr[i];
    }

    printf("Second Largest Number = %d\n", max2);
    }
    ㉠ / ㉡
    1
    arr[i] > max1 / arr[i] > max2 && arr[i] < max1
    2
    arr[i] > max1 / arr[i] < max2 && arr[i] > max1
    3
    arr[i] < max1 / arr[i] > max2 && arr[i] < max1
    4
    arr[i] < max1 / arr[i] < max2 && arr[i] > max1
    해설

    ㉠은 arr[i] > max1, ㉡은 arr[i] > max2 && arr[i] < max1이다.

    현재 값이 최댓값보다 크면 기존 최댓값을 max2로 내리고 max1을 갱신하므로 ㉠은 max1보다 큰 경우이다. 그렇지 않으면서 max2보다 크고 max1보다 작은 값일 때만 max2를 갱신해야 한다.

    • arr[i] > max1 / arr[i] < max2 && arr[i] > max1: ㉠이 거짓이면 arr[i]가 max1 이하이므로 ㉡을 만족하는 값이 없어 max2가 갱신되지 않는다.
    • arr[i] < max1 / arr[i] > max2 && arr[i] < max1: max1이 0에서 시작하고 원소가 모두 양수라 ㉠과 ㉡이 모두 거짓이 되어 0이 출력된다.
    • arr[i] < max1 / arr[i] < max2 && arr[i] > max1: 두 조건 모두 성립하지 않아 max1, max2가 0에 머문다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    20[7급 국가직 자료구조론] 20년 1회차
    다음은 원형 연결 리스트(circular linked list)의 맨 앞에 insert_node가 지정하는 노드를 삽입하는 C 언어 함수이다. ㉠, ㉡에 들어갈 내용을 바르게 연결한 것은? (단, last_ptr은 마지막 노드를 지정하는 포인터 변수를 가리키는 주소 값을 가진다)
    struct node {
    int data;
    struct node *link;
    };
    typedef struct node *node_ptr;

    void InsertFront(node_ptr *last_ptr,
    node_ptr insert_node){
    if (*last_ptr == NULL) {
    *last_ptr = insert_node;
    _______㉠_______
    }
    else {
    insert_node->link = (*last_ptr)->link;
    _______㉡_______
    }
    }
    ㉠ / ㉡
    1
    insert_node = insert_node->link; / (*last_ptr) = insert_node;
    2
    insert_node = insert_node->link; / (*last_ptr)->link = insert_node;
    3
    insert_node->link = insert_node; / (*last_ptr) = insert_node;
    4
    insert_node->link = insert_node; / (*last_ptr)->link = insert_node;
    해설

    ㉠은 insert_node->link = insert_node;, ㉡은 (*last_ptr)->link = insert_node;이다.

    빈 리스트에 노드 하나를 넣으면 그 노드가 처음이자 마지막이므로 자기 자신을 가리켜 원형을 이뤄야 한다. 원형 연결 리스트의 맨 앞 노드는 마지막 노드의 link가 가리키는 노드이므로, 새 노드가 기존 첫 노드를 가리키게 한 뒤 마지막 노드의 link를 새 노드로 바꾸면 맨 앞 삽입이 된다.

    • insert_node = insert_node->link; / (*last_ptr) = insert_node;: ㉠은 포인터 변수만 바꿀 뿐 자기 순환을 만들지 못하고, ㉡은 마지막 노드의 link를 갱신하지 않아 새 노드가 순환에 들어가지 않는다.
    • insert_node = insert_node->link; / (*last_ptr)->link = insert_node;: ㉡은 맞지만 ㉠이 노드의 link를 설정하지 않아 단일 노드 원형이 만들어지지 않는다.
    • insert_node->link = insert_node; / (*last_ptr) = insert_node;: ㉠은 맞지만 ㉡이 last 포인터만 새 노드로 옮겨, 기존 마지막 노드가 여전히 옛 첫 노드를 가리키므로 원형이 깨진다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.

[7급 국가직 자료구조론] 20년 1회차 시험지 PDF 다운로드·인쇄 →

전 회차를 한 권으로 — 7급 국가직 자료구조론 기출문제 PDF 전자책(문제집·정답해설집) →

[7급 국가직 자료구조론] 20년 1회차 정답과 해설은 무료인가요?

이 페이지의 20문항 정답과 해설은 로그인 없이 무료로 볼 수 있습니다. 무제한 풀이·실전 모의고사·PDF 출력·전자책 다운로드는 베이직 플랜에 포함됩니다.

이 회차를 CBT 로 직접 풀어볼 수 있나요?

7급 국가직 자료구조론 기출문제 암기장에서 이 회차를 회차별·랜덤으로 풀고 오답노트에 자동으로 모을 수 있습니다. 7급 국가직 자료구조론 기출문제 풀러 가기 →

시험지 PDF 나 전자책으로도 볼 수 있나요?

이 회차의 인쇄용 시험지 PDF 와, 전 회차를 문제집·정답해설집으로 묶은 PDF 전자책을 제공합니다. 7급 국가직 자료구조론 기출문제 PDF 전자책 보기 →

[7급 국가직 자료구조론] 20년 1회차 문항별 상세 페이지 전체 보기