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

[7급 국가직 자료구조론] 12년 1회차
    1[7급 국가직 자료구조론] 12년 1회차
    다음 함수를 이용하여 recursive(4)를 수행한 결과 값은?
    int recursive( int n ) {
    if(n<1) return 2;
    else return( 22 * recursive(n-1) + 1);
    }
    1
    149
    2
    265
    3
    373
    4
    597
    해설

    재귀식을 바닥부터 차례로 풀면 recursive(4)의 값은 597이다.

    n이 1보다 작으면 2를 반환하고, 그 외에는 22×r(n−1)+1=4r(n−1)+12^{2} \times r(n-1) + 1 = 4r(n-1) + 1을 반환하는 재귀 호출 구조이다.

    r(0) = 2
    r(1) = 4×2+1 = 9
    r(2) = 4×9+1 = 37
    r(3) = 4×37+1 = 149
    r(4) = 4×149+1 = 597

    • 149는 r(3)에서 멈춘 값으로, 한 단계를 덜 계산한 것이다.
    • 265는 점화식 어느 단계에서도 나오지 않는 값이다.
    • 373도 점화식 어느 단계에서도 나오지 않는 값이다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    2[7급 국가직 자료구조론] 12년 1회차
    if 문장에서 포인터 변수 pt1과 pt2에 대한 설명으로 옳지 않은 것은?
    1
    if (&pt1==&pt2)의 경우에 서로 다른 포인터 변수가 동일한 주소에 있을 수 있다.
    2
    if (pt1==pt2)는 같은 대상을 가리키는지를 검증한다.
    3
    if (*pt1==*pt2)의 경우에 가리키는 대상이 다를지라도 변수 값은 같을 수 있다.
    4
    if (pt1==pt2)는 가리키는 대상의 주소가 동일한 것인지를 검증한다.
    해설

    서로 다른 변수는 동일한 주소를 가질 수 없으므로, &pt1==&pt2 에서 서로 다른 포인터 변수가 같은 주소에 있을 수 있다는 설명이 옳지 않다.

    &pt1은 포인터 변수 자신의 주소, pt1은 그 변수에 저장된 값(가리키는 대상의 주소), *pt1은 가리키는 대상의 값이다.

    • pt1==pt2는 두 포인터가 같은 대상을 가리키는지 검증한다 — 옳다.
    • *pt1==*pt2는 값 비교이므로 대상이 달라도 값이 같으면 참이 될 수 있다 — 옳다.
    • pt1==pt2는 곧 가리키는 대상의 주소가 동일한지를 비교하는 것이다 — 옳다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    3[7급 국가직 자료구조론] 12년 1회차
    스택 수(stack number)란 다음 장치의 왼쪽 큐 LQ에 들어 갈 수 있는 숫자열을 말한다. 오른쪽 큐 RQ로부터 데이터가 하나씩 중간에 있는 스택 MS를 거치거나 바로 LQ로 입력될 수 있다. 즉, 데이터가 LQ에 입력될 때 RQ에서 직접 입력되거나 MS에서 한 데이터를 삭제해서 LQ에 추가할 수 있다. 다음 장치에서 생성할 수 있는 스택 수는?
    문제 이미지
    1
    1 8 5 6 7 4 9 3 10 2
    2
    3 4 6 7 8 5 9 2 1 10
    3
    3 4 8 5 6 7 2 9 1 10
    4
    9 4 7 5 6 3 8 1 2 10
    해설

    이 장치는 1부터 10까지 순서대로 들어오는 입력을 스택 하나로 재배열하는 것이므로, 출력열이 유효한 스택 순열이어야 하며 3 4 6 7 8 5 9 2 1 10만 가능하다.

    판정 요령은 어떤 수가 나올 때 그보다 작은데 아직 안 나온 수는 스택에 쌓여 있으므로, 이후에는 큰 수부터 역순으로만 나올 수 있다는 것이다. 정답열은 1·2를 쌓고 3·4를 바로 보내고, 5를 쌓은 뒤 6·7·8을 보내고 5를 꺼내며, 9를 보낸 뒤 2·1을 꺼내고 10을 보내면 만들어진다.

    • 1 8 5 6 7 4 9 3 10 2: 8이 나올 때 스택 top은 7인데 다음에 5가 나와야 하므로 불가능하다.
    • 3 4 8 5 6 7 2 9 1 10: 8이 나올 때 스택에 5·6·7이 쌓여 top이 7인데 5가 먼저 나오므로 불가능하다.
    • 9 4 7 5 6 3 8 1 2 10: 9가 나올 때 1~8이 모두 스택에 있어 top이 8인데 4가 나오므로 불가능하다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    4[7급 국가직 자료구조론] 12년 1회차
    합병정렬(merge sort)에 대한 설명으로 옳지 않은 것은?
    1
    점근분석(asymptotic analysis)할 때, 퀵정렬(quick sort)의 최악수행시간 보다 빠르다.
    2
    추가적인 메모리 사용없이 간단히 구현할 수 있다.
    3
    크기 n인 입력에 대한 최악수행시간을 T(n)이라 할 때, T(n)=2×T(n/2)+cnT(n) = 2 \times T(n/2) + cn으로 나타낼 수 있다. (단, c≥1c \ge 1 상수)
    4
    분할정복(divide and conquer) 기법을 사용한다.
    해설

    합병정렬은 병합 과정에서 입력 크기만큼의 추가 배열이 필요하므로, 추가 메모리 없이 구현할 수 있다는 설명이 옳지 않다.

    정렬된 두 부분 배열을 합칠 때 결과를 임시 배열에 옮겨 적은 뒤 되돌려 놓는 방식이라 공간복잡도는 O(n)O(n)이다.

    • 합병정렬의 최악 시간은 O(nlog⁡n)O(n \log n)으로, 퀵정렬의 최악 O(n2)O(n^{2})보다 빠르다 — 옳다.
    • 절반씩 두 번 재귀 호출하고 병합에 선형 시간이 들어 T(n)=2T(n/2)+cnT(n) = 2T(n/2) + cn이 성립한다 — 옳다.
    • 분할 → 정복 → 결합 단계를 거치는 대표적인 분할정복 알고리즘이다 — 옳다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    5[7급 국가직 자료구조론] 12년 1회차
    방향그래프의 행(row)은 출발 노드로 열(column)은 도착 노드로 매핑하여 다음과 같이 인접행렬로 표현될 때, 위상 정렬(topological sort)이 가능한 것은?
    1
    abcdef
    a11
    b11
    c11
    d11
    e11
    f
    2
    abcdef
    a11
    b11
    c11
    d1
    e111
    f
    3
    abcdef
    a11
    b11
    c11
    d1
    e11
    f
    4
    abcdef
    a11
    b11
    c11
    d1
    e11
    f1
    해설

    위상 정렬은 사이클이 없는 방향그래프(DAG)에서만 가능하므로, 사이클이 없는 인접행렬을 고르면 된다.

    d에서 c로, e에서 b로, f에서 a로 되돌아가는 간선 없이 d→f, e→d, e→f 만 있는 행렬은 사이클이 없으며, a, b, c, e, d, f 순으로 위상 정렬된다.

    • d→c 간선이 있는 행렬은 c→d와 함께 c→d→c 사이클이 생긴다.
    • e→b 간선이 있는 행렬은 b→c→e→b 사이클이 생긴다.
    • f→a 간선이 있는 행렬은 a→b→d→f→a 사이클이 생긴다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    6[7급 국가직 자료구조론] 12년 1회차
    다음 데이터를 이용하여 AVL 트리를 생성할 때, 이에 대한 설명으로 옳지 않은 것은?
    12, 11, 10, 5, 3, 7, 6, 1, 13, 2, 4
    1
    AVL트리에서 7을 검색하기 위해서는 4번의 비교가 필요하다.
    2
    AVL트리의 루트 값은 5이다.
    3
    4가 삽입될 때, AVL 트리의 균형이 깨져서 재구성이 발생한다.
    4
    6은 리프노드이다.
    해설

    완성된 AVL 트리에서 7은 5 → 10 → 7 순으로 세 번 비교로 찾으므로, 네 번의 비교가 필요하다는 설명이 옳지 않다.

    삽입 중 회전: 10 삽입 시 LL(루트 11) → 3 삽입 시 LL(노드 10 기준) → 7 삽입 시 LR(루트 10) → 13 삽입 시 RR(노드 11 기준) → 2 삽입 시 LR(노드 3 기준) → 4 삽입 시 루트 10에서 LL 회전이 일어나 루트가 5가 된다.

    최종 트리: 5의 왼쪽 2(자식 1, 3), 3의 오른쪽 4 / 5의 오른쪽 10(자식 7, 12), 7의 왼쪽 6, 12의 자식 11, 13.

    • 최종 루트 값은 5이다 — 옳다.
    • 4를 넣으면 루트 10의 균형인수가 2가 되어 재구성이 발생한다 — 옳다.
    • 6은 7의 왼쪽 자식이며 자식이 없는 리프노드이다 — 옳다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    7[7급 국가직 자료구조론] 12년 1회차
    다음 연결리스트(linked list)로 표현된 그래프를 위한 두 연산(A, B)에 대해 ‘최적으로 구현’한다고 할 때, 연산 A, B 각각에 대한 최악의 시간복잡도는? (단, 그래프의 노드의 개수를 n이라고 하고, 각 노드 쌍 사이에는 최대 1개의 간선(edge)이 존재할 수 있다)
    연산 (A) : 노드 i에서 노드 j로의 간선을 삽입한다. (단, 삽입 연산은 항상 간선이 존재하지 않는 노드 쌍에 대해서 수행된다)
    연산 (B) : 노드 i에서 노드 j로의 간선을 찾아 제거한다.
    연산 (A) 연산 (B)
    문제 이미지
    1
    O(1)O(1) O(n)O(n)
    2
    O(log⁡n)O(\log n) O(1)O(1)
    3
    O(1)O(1) O(log⁡n)O(\log n)
    4
    O(n)O(n) O(n)O(n)
    해설

    인접 리스트에서 간선 삽입은 O(1)O(1), 간선 제거는 O(n)O(n)이다.

    삽입은 해당 간선이 없음이 보장되므로 중복 검사 없이 노드 i(무방향이면 j도)의 리스트 맨 앞에 새 노드를 붙이면 되어 상수 시간이다. 제거는 정렬되지 않은 리스트에서 j를 찾아야 하므로 최악의 경우 차수만큼, 즉 최대 n−1개를 훑어야 해 선형 시간이 든다.

    • 삽입 O(log⁡n)O(\log n)·제거 O(1)O(1): 연결리스트는 이진 탐색이 불가하고, 제거는 탐색이 필요해 상수 시간이 될 수 없다.
    • 삽입 O(1)O(1)·제거 O(log⁡n)O(\log n): 연결리스트에서는 위치를 로그 시간에 찾을 수 없어 제거는 선형 탐색이 필요하다.
    • 삽입 O(n)O(n)·제거 O(n)O(n): 존재하지 않는 간선만 삽입한다는 조건이 있어 탐색 없이 맨 앞에 넣으면 되므로 삽입이 선형일 필요가 없다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    8[7급 국가직 자료구조론] 12년 1회차
    다음 행렬은 일곱 개의 정점(vertex)을 갖는 그래프의 간선(edge)들 간의 거리를 나타낸다. Dijkstra 알고리즘을 적용하여 정점 A로부터 나머지 정점들까지 최단경로를 찾을 때, 이에 해당하는 정점의 순서는? (단, ∞는 두 정점 간에 해당 간선이 없다)
    ABCDEFG
    A049∞∞∞∞
    B40410∞∞∞
    C940∞8∞1
    D∞10∞025∞
    E∞∞820∞6
    F∞∞∞5∞03
    G∞∞1∞630
    1
    A→B→C→G→D→E→F
    2
    A→B→C→G→E→D→F
    3
    A→B→C→G→E→F→D
    4
    A→B→C→G→F→D→E
    해설

    Dijkstra 알고리즘으로 확정되는 정점 순서는 A→B→C→G→F→D→E이다.

    매 단계 미확정 정점 중 최소 거리 정점을 확정하고 인접 거리를 갱신한다.
    A 확정: B=4, C=9
    B(4) 확정: C=min(9, 8)=8, D=14
    C(8) 확정: E=16, G=9
    G(9) 확정: E=min(16, 15)=15, F=12
    F(12) 확정: D=min(14, 17)=14
    D(14) 확정: E=min(15, 16)=15
    E(15) 확정

    • G 다음에 D를 고르는 순서는 F(12)가 D(14)보다 가깝다는 점을 놓친 것이다.
    • G 다음 E, D, F 순서는 E(15)보다 F(12)·D(14)가 먼저 확정되어야 하므로 틀리다.
    • G 다음 E, F, D 순서도 E(15)를 가장 가까운 F(12)보다 먼저 확정해 틀리다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    9[7급 국가직 자료구조론] 12년 1회차
    이진탐색트리의 노드 삽입에 대한 다음 C 프로그램의 ㉠ ~ ㉡에 들어갈 내용은? (단, T는 이진탐색트리, X는 이진탐색트리에 삽입할 값이다)
    struct TreeNode {
    int Element;
    struct TreeNode *Left;
    struct TreeNode *Right;
    };
    typedef struct TreeNode *SearchTree;

    SearchTree Insert( int X, SearchTree T )
    {
    if ( T == NULL ) {
    T = (SearchTree)malloc(sizeof(struct TreeNode));
    T->Element = X;
    T->Left = T->Right = NULL;
    } else if ( X < T->Element )
    ㉠
    else if ( X > T->Element )
    ㉡
    return T;
    }
    ㉠ ㉡
    1
    T->Left = Insert( X, T ); T->Right = Insert( X, T );
    2
    T->Left = Insert( X, T->Left ); T->Right = Insert( X, T->Right );
    3
    T->Left = Insert( X, T->Element ); T->Right = Insert( X, T->Element );
    4
    T->Left = Insert( X, T->Right ); T->Right = Insert( X, T->Left );
    해설

    ㉠에는 T->Left = Insert( X, T->Left );, ㉡에는 T->Right = Insert( X, T->Right );가 들어간다.

    X가 현재 노드 값보다 작으면 왼쪽 서브트리, 크면 오른쪽 서브트리에 재귀적으로 삽입하고, 반환된 서브트리 루트를 해당 자식 포인터에 다시 연결한다.

    • Insert( X, T )로 자기 자신을 다시 넘기면 T가 NULL이 되지 않아 무한 재귀에 빠진다.
    • T->Element는 정수 값이므로 트리 포인터 인자로 넘길 수 없다.
    • 왼쪽 자식 자리에 오른쪽 서브트리 삽입 결과를 연결하는 식으로 좌우를 뒤바꾸면 기존 서브트리가 엇갈려 이진탐색트리의 대소 규칙이 깨진다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    10[7급 국가직 자료구조론] 12년 1회차
    다음 데이터들을 공백힙(empty heap)에 차례대로 삽입하여 최대힙(max heap)을 생성하였다. 생성된 최대힙에 삭제 연산을 두 번 수행한 후의 결과는?
    2, 13, 55, 8, 35, 47, 23, 19
    1
    2
    3
    4
    해설

    두 번 삭제한 뒤의 최대힙은 레벨 순서로 35, 19, 23, 2, 8, 13이다(루트 35, 왼쪽 자식 19의 자식 2·8, 오른쪽 자식 23의 자식 13).

    차례로 삽입하며 상향 조정하면 힙 배열은 55, 35, 47, 19, 8, 13, 23, 2가 된다.
    첫 삭제: 55를 빼고 마지막 원소 2를 루트로 올려 하향 조정 → 47, 35, 23, 19, 8, 13, 2.
    둘째 삭제: 47을 빼고 2를 루트로 올려 더 큰 자식과 교환 → 35, 19, 23, 2, 8, 13.

    • 루트 35의 왼쪽이 23, 오른쪽이 19인 트리: 첫 삭제 뒤 23은 47의 오른쪽 서브트리에 있었으므로 오른쪽 자식 자리에 남아야 한다.
    • 19의 자식이 2·13이고 23의 자식이 8인 트리: 8과 13의 위치가 서로 바뀌어 하향 조정 경로와 맞지 않는다.
    • 왼쪽 23(자식 2·13)·오른쪽 19(자식 8)인 트리: 좌우 서브트리와 리프 배치가 모두 실제 결과와 다르다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    11[7급 국가직 자료구조론] 12년 1회차
    다음 연산식을 후위(postfix) 연산식으로 변환했을 때, 4번째 연산자는?
    1 + (2 - 3 * 4 / (5 + 6)) - 7
    1
    +
    2
    -
    3
    *
    4
    /
    해설

    후위 연산식은 1 2 3 4 * 5 6 + / - + 7 - 이며, 네 번째 연산자는 -이다.

    괄호 안은 3*4를 (5+6)으로 나눈 뒤 2에서 빼므로 2 3 4 * 5 6 + / - 가 된다.
    여기에 1을 더하고 7을 빼면 전체 식이 완성된다.

    연산자 등장 순서: * → + → / → - → + → -

    • +는 두 번째(5+6)와 다섯 번째(1과의 덧셈)에 나온다.
    • *는 첫 번째 연산자이다.
    • /는 세 번째 연산자이다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    12[7급 국가직 자료구조론] 12년 1회차
    다음 선형연결리스트(linear linked list)에서 LEE를 찾기 위한 비교 횟수는? (단, HEADER는 3 이다)
    IndexNamePointer
    1KIM6
    2PARK1
    3CHOI4
    4BAEK2
    5LEE7
    6MIN5
    7ANN8
    8JUNG-
    1
    4
    2
    5
    3
    6
    4
    7
    해설

    HEADER 3에서 출발해 포인터를 따라가면 LEE는 여섯 번째 노드에서 찾으므로 비교 횟수는 6회이다.

    탐색 경로: CHOI(3) → BAEK(4) → PARK(2) → KIM(1) → MIN(6) → LEE(5)

    선형연결리스트는 순차 탐색만 가능하므로 인덱스 순서가 아니라 포인터 순서대로 비교한다.

    • 비교 4회는 KIM까지만 비교한 경우이다.
    • 비교 5회는 MIN까지만 비교한 경우이다.
    • 비교 7회는 LEE를 지나 ANN까지 비교한 경우이다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    13[7급 국가직 자료구조론] 12년 1회차
    정렬(sort)에 대한 설명으로 옳지 않은 것은?
    1
    퀵정렬(quick sort)은 스택을 이용하여 수행한다.
    2
    쉘정렬(shell sort)은 최적의 경우에 선택정렬(selection sort) 보다 빠르다.
    3
    힙정렬(heap sort)은 배열을 이용한 포화 이진트리(full binary tree)를 사용한다.
    4
    10개 데이터의 버블정렬(bubble sort)은 최대 45번의 비교 연산을 수행한다.
    해설

    힙정렬은 배열로 표현한 완전 이진트리(complete binary tree)를 사용하므로, 포화 이진트리를 사용한다는 설명이 옳지 않다.

    포화 이진트리는 모든 레벨이 꽉 찬 트리라 노드 수가 2k−12^{k}-1일 때만 성립하지만, 힙은 마지막 레벨이 왼쪽부터 채워진 완전 이진트리면 된다.

    • 퀵정렬은 분할된 구간을 재귀 호출(스택)로 처리한다 — 옳다.
    • 쉘정렬은 이미 정렬된 최선의 경우 O(nlog⁡n)O(n \log n) 수준으로, 입력과 무관하게 항상 O(n2)O(n^{2})인 선택정렬보다 빠르다 — 옳다.
    • 10개 데이터의 버블정렬 최대 비교 횟수는 9+8+…+1 = 45이다 — 옳다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    14[7급 국가직 자료구조론] 12년 1회차
    해시함수(hash function)로 h(k)=k mod 7을 사용하고, 선형탐색(linear probing) 기법을 이용하여 충돌을 해결하고자 한다. 키가 3, 10, 5, 9, 12 순서대로 입력되었을 때, 생성된 해시테이블은?
    1
    [0][1][2][3][4][5][6]
    1293105
    2
    [0][1][2][3][4][5][6]
    1231059
    3
    [0][1][2][3][4][5][6]
    9103125
    4
    [0][1][2][3][4][5][6]
    9310512
    해설

    선형탐색으로 충돌을 해결하면 해시테이블은 [2]=9, [3]=3, [4]=10, [5]=5, [6]=12가 된다.

    3 → 3 mod 7 = 3, [3]에 저장
    10 → 10 mod 7 = 3, 충돌 → 다음 빈 칸 [4]에 저장
    5 → 5 mod 7 = 5, [5]에 저장
    9 → 9 mod 7 = 2, [2]에 저장
    12 → 12 mod 7 = 5, 충돌 → [6]에 저장

    • 12를 [0], 9를 [1]에 둔 테이블은 9의 해시값 2와 12의 다음 빈 칸 [6]을 무시했다.
    • 12를 [0], 9를 [6]에 둔 테이블은 9가 비어 있는 [2]에 바로 들어가야 함을 무시했다.
    • 10을 [2], 12를 [4]에 둔 테이블은 충돌 시 다음 칸으로 이동하는 선형탐색 규칙에 어긋난다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    15[7급 국가직 자료구조론] 12년 1회차
    비어있는 이진 탐색 트리(binary search tree)에 다음 키 값들을 차례로 삽입하여 동적으로 이진 탐색 트리를 구성하였을 때, 5를 탐색하는데 필요한 비교 횟수는?
    23, 18, 2, 16, 4, 10, 5, 39, 26, 15
    1
    3
    2
    5
    3
    7
    4
    9
    해설

    5를 찾으려면 23 → 18 → 2 → 16 → 4 → 10 → 5 순으로 7회 비교가 필요하다.

    삽입 결과 23의 왼쪽 18, 18의 왼쪽 2, 2의 오른쪽 16, 16의 왼쪽 4, 4의 오른쪽 10, 10의 왼쪽 5가 연결되어 한쪽으로 길게 늘어진 편향된 경로가 생긴다.

    • 비교 3회는 2까지만 내려간 경우이다.
    • 비교 5회는 4까지만 내려간 경우이다.
    • 비교 9회는 루트에서 5까지의 경로 길이보다 많아 성립하지 않는다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    16[7급 국가직 자료구조론] 12년 1회차
    다음 그래프를 이용하여 Kruskal 알고리즘을 적용하였을 때, 생성된 최소 비용 신장 트리의 비용은?
    문제 이미지
    1
    11
    2
    12
    3
    13
    4
    14
    해설

    Kruskal 알고리즘으로 만든 최소 비용 신장 트리의 비용은 13이다.

    정점 6개이므로 간선 5개가 필요하다. 가중치가 작은 간선부터 사이클이 생기지 않는 것만 고르면 1 → 2 → 2를 채택하고, 가중치 3인 간선은 이미 연결된 두 정점을 잇는 사이클이 되어 버린다. 이어서 가중치 4인 간선 두 개를 채택하면 모든 정점이 연결된다.

    1+2+2+4+4=131 + 2 + 2 + 4 + 4 = 13

    • 11: 합을 13보다 줄이려면 가중치 3 간선을 넣어야 하는데, 이 간선은 사이클을 만들므로 신장 트리에 쓸 수 없다.
    • 12: 가중치 4 간선 하나를 가중치 3 간선으로 바꾼 값이지만, 가중치 3 간선은 사이클을 만들어 채택되지 않는다.
    • 14: 가중치 5 이상 간선은 필요 없이 이미 모든 정점이 연결되므로 비용이 더 커지지 않는다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    17[7급 국가직 자료구조론] 12년 1회차
    다음과 같은 4개의 노드를 가진 2-3 트리에 키 값 6을 추가하였을 때, 트리의 전체 노드의 수는?
    문제 이미지
    1
    4개
    2
    5개
    3
    6개
    4
    7개
    해설

    키 6을 넣으면 분할이 루트까지 전파되어 높이가 늘고, 전체 노드는 7개가 된다.

    6은 오른쪽 리프 [7, 9]에 들어가 [6, 7, 9]로 넘치므로 분할되고 가운데 키 7이 부모로 올라간다. 루트가 [2, 4, 7]로 다시 넘쳐 분할되며 4가 새 루트가 된다.

    결과: 루트 [4] / 내부 노드 [2], [7] / 리프 [1], [3], [6], [9] → 1 + 2 + 4 = 7개.

    • 4개: 삽입 전 노드 수 그대로이며, 리프가 넘쳐 분할되는 것을 반영하지 않았다.
    • 5개: 리프 분할만 반영하고 루트 분할을 빠뜨린 경우다.
    • 6개: 루트 분할은 반영했으나 새 루트 노드 생성을 세지 않은 경우다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    18[7급 국가직 자료구조론] 12년 1회차
    다항식(polynomial) 표현을 위해 구조체 poly를 정의하였다. 이 구조체를 이용하여 A(x)=−3x999−2x888+1A(x) = -3x^{999} -2x^{888} + 1과 B(x)=x10+x9+x5B(x) = x^{10} + x^{9} + x^{5}을 저장하기 위한 최소 메모리 용량[byte]은? (단, 정수(int)를 표현하는 데 2 byte를 사용하고, 실수(float)를 표현하는 데 4 byte를 사용한다)
    typedef struct {
    int exp;
    float coef;
    } poly;
    1
    22
    2
    24
    3
    36
    4
    38
    해설

    0이 아닌 항만 (exp, coef) 쌍으로 저장하는 희소 다항식 표현을 쓰면 최소 메모리는 36 byte이다.

    poly 하나의 크기: int 2 byte + float 4 byte = 6 byte
    A(x)의 항 3개 + B(x)의 항 3개 = 6개
    6 × 6 = 36 byte

    • 22 byte는 poly 6개(36 byte)를 담기에 부족하다.
    • 24 byte는 poly 4개 분량에 불과하다.
    • 38 byte는 36 byte에 int 하나(2 byte)를 더 쓴 값으로 최소가 아니다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    19[7급 국가직 자료구조론] 12년 1회차
    다음 중 컴퓨터 프로그래밍을 통하여 문제를 해결하는데 최적의 시간복잡도가 가장 큰 것은?
    1
    임의의 정수 100,000개를 선택정렬(selection sort)로 정렬하는 문제
    2
    정렬된 100,000개의 정수에서 임의의 정수를 이진탐색하는 문제
    3
    반복 호출로 피보나치수열 F0F_{0}, F1F_{1}, F2F_{2}, … 에서 F100000F_{100000} 값을 구하는 문제
    4
    재귀호출로 하노이 탑(tower of Hanoi)의 100,000개 원판 이동 문제
    해설

    하노이 탑의 원판 이동 횟수는 2n−12^{n}-1로 지수 시간이므로 시간복잡도가 가장 크다.

    원판 n개를 옮기려면 n−1개를 두 번 옮기고 가장 큰 원판을 한 번 옮기므로 T(n)=2T(n−1)+1T(n) = 2T(n-1) + 1, 즉 O(2n)O(2^{n})이다.

    • 선택정렬은 O(n2)O(n^{2})로 다항 시간이다.
    • 정렬된 배열의 이진탐색은 O(log⁡n)O(\log n)이다.
    • 반복문으로 피보나치 수를 구하면 O(n)O(n)이다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    20[7급 국가직 자료구조론] 12년 1회차
    구조체 list를 이용한 두 개의 단순연결리스트 x, y의 후위노드(음영부분)들을 서로 스왑(swap)하기 위한 코드는? (단, 후위노드들의 next는 NULL이 아니다)
    struct list { int data; struct list *next; } *x, *y, *tmp;

    문제 이미지
    1
    tmp = x->next;
    x->next->next = y->next->next;
    y->next->next = tmp;
    tmp = y->next;
    x->next = y->next;
    y->next = tmp;
    2
    tmp = x->next->next;
    x->next->next = y->next->next;
    y->next->next = tmp;
    tmp = x->next;
    x->next = y->next;
    y->next = tmp;
    3
    tmp = x->next;
    x->next = y->next;
    y->next = tmp;
    tmp = x->next;
    x->next->next = y->next->next;
    y->next->next = tmp;
    4
    tmp = x->next->next;
    y->next->next = tmp;
    x->next->next = y->next->next;
    tmp = x->next;
    y->next = tmp;
    x->next = y->next;
    해설

    음영 노드를 바꾸려면 음영 노드의 next(뒤 연결)를 먼저 교환하고, 그다음 x->next와 y->next를 교환해야 한다. 즉 tmp = x->next->next로 시작해 뒤 연결을 맞바꾼 뒤 tmp = x->next로 앞 연결을 맞바꾸는 코드가 옳다.

    뒤 연결을 먼저 바꾸면 각 음영 노드가 상대 리스트의 세 번째 노드를 가리키게 되고, 이후 앞 연결을 바꾸면 x와 y 리스트에 상대 음영 노드가 끼워져 교환이 완성된다.

    • tmp = x->next로 시작하는 코드: y->next->next에 x의 음영 노드 자체를 넣어 x의 세 번째 노드 연결을 잃는다.
    • 앞 연결(x->next, y->next)을 먼저 교환하는 코드: 이후 x->next가 이미 y의 음영 노드를 가리키므로 뒤 연결 교환이 어긋나, y 리스트가 x의 음영 노드·y의 음영 노드·x의 세 번째 노드 순으로 이어지고 y의 세 번째 이후 노드를 잃는다.
    • y->next->next = tmp를 먼저 대입하는 코드: y의 세 번째 노드 주소를 저장 없이 덮어써 y 쪽 뒤 리스트를 잃는다.

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

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

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

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

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

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

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

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

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

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

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