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

[7급 국가직 자료구조론] 13년 1회차
    1[7급 국가직 자료구조론] 13년 1회차
    깊이가 k인 포화이진트리(full binary tree)의 비단말노드의 개수에서 단말노드의 개수를 뺀 값으로 옳은 것은? (단, k > 0)
    1
    -1
    2
    0
    3
    1
    4
    k - 1
    해설

    포화이진트리에서는 항상 비단말노드 수 = 단말노드 수 − 1이므로 차이는 −1이다.

    깊이가 k이면 단말노드는 2k−12^{k-1}개, 비단말노드는 1+2+⋯+2k−2=2k−1−11+2+\cdots+2^{k-2}=2^{k-1}-1개다.

    따라서 (2k−1−1)−2k−1=−1(2^{k-1}-1)-2^{k-1}=-1로, 깊이와 무관하게 일정하다.

    • 0: 두 개수가 같아야 하는데, 비단말노드가 항상 하나 적다.
    • 1: 부호가 반대다. 단말노드 쪽이 하나 더 많다.
    • k − 1: 차이는 깊이 k와 무관한 상수다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    2[7급 국가직 자료구조론] 13년 1회차
    다음 ‘하노이타워’ 프로그램을 수행한 결과에서 8번째 줄에 출력되는 문장으로 옳은 것은?
    #include <stdio.h>
    void hanoi_tower(int n, char from, char tmp, char to)
    {
    if( n==1 ) printf("원판 1을 %c에서 %c로 옮긴다. \n", from, to);
    else {
    hanoi_tower(n-1, from, to, tmp);
    printf("원판 %d을 %c에서 %c로 옮긴다. \n", n, from, to);
    hanoi_tower(n-1, tmp, from, to);
    }
    }
    void main()
    {
    hanoi_tower(4, 'A', 'B', 'C');
    }
    1
    원판 1을 C에서 B로 옮긴다.
    2
    원판 4을 A에서 C로 옮긴다.
    3
    원판 3을 A에서 B로 옮긴다.
    4
    원판 2을 B에서 C로 옮긴다.
    해설

    원판 4개를 옮기는 하노이타워는 총 24−1=152^4-1=15회 이동하며, 여덟째 줄에는 가장 큰 원판 4을 A에서 C로 옮기는 문장이 출력된다.

    재귀 구조상 먼저 원판 3개를 A에서 B로 옮기는 7줄(23−12^3-1)이 출력되고, 그다음 줄이 원판 4의 이동이며, 이후 7줄은 원판 3개를 B에서 C로 옮기는 과정이다.

    • 원판 1을 C에서 B로: 전체 15줄 어디에도 나오지 않는 이동이다.
    • 원판 3을 A에서 B로: 앞쪽 과정의 넷째 줄에 출력된다.
    • 원판 2을 B에서 C로: 원판 2는 A→C, C→B, B→A, A→C로만 움직여 출력되지 않는다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    3[7급 국가직 자료구조론] 13년 1회차
    개수가 정해진 자연수를 크기순으로 저장하고 탐색하기에 가장 적절한 자료구조와 탐색방법으로 옳게 짝지어진 것은?
    1
    배열 - 순차탐색
    2
    배열 - 이진탐색
    3
    단순 연결 리스트 - 순차탐색
    4
    단순 연결 리스트 - 이진탐색
    해설

    개수가 정해진 정렬 데이터에는 배열 + 이진탐색이 가장 적절하다.

    크기가 고정이면 배열로 충분하고, 배열은 인덱스로 가운데 원소에 바로 접근할 수 있어 정렬된 상태에서 이진탐색으로 O(log⁡n)O(\log n)에 찾을 수 있다.

    • 배열 − 순차탐색: 가능하지만 O(n)O(n)이라 정렬된 순서를 활용하지 못한다.
    • 단순 연결 리스트 − 순차탐색: 크기가 고정이면 동적 삽입·삭제 장점이 필요 없고, 탐색도 O(n)O(n)이다.
    • 단순 연결 리스트 − 이진탐색: 가운데 노드에 바로 접근할 수 없어 이진탐색이 효율적으로 성립하지 않는다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    4[7급 국가직 자료구조론] 13년 1회차
    다음 배열에 저장된 데이터에 대해 내림차순으로 히프정렬(heap sorting)을 수행한다. 첫 번째 데이터를 출력하고 히프를 재구성한 후에 배열의 6번째에 있는 데이터로 옳은 것은? (단, 배열의 첫 번째 인덱스는 1이다)
    [1][2][3][4][5][6][7][8][9]
    2137221711305109
    1
    5
    2
    9
    3
    10
    4
    22
    해설

    배열을 최대 히프로 구성하고 루트를 출력·재구성하면 인덱스 6에는 9가 온다.

    히프 구성: 마지막 부모부터 올라가며 조정하면 인덱스 3의 22와 30이, 이어서 루트 21과 37이 교환되어 37, 21, 30, 17, 11, 22, 5, 10, 9가 된다.

    재구성: 루트 37을 출력하고 마지막 9를 루트로 올려 내린다. 9는 더 큰 자식 30과, 다시 22와 교환되어 30, 21, 22, 17, 11, 9, 5, 10이 된다.

    • 5: 인덱스 7에 그대로 남는다.
    • 10: 인덱스 8에 남는다.
    • 22: 인덱스 3으로 올라간다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    5[7급 국가직 자료구조론] 13년 1회차
    다음 구조체를 갖는 이중 연결 리스트에서 A, B, C는 각각 노드를 가리키는 포인터 변수이다. 노드 B를 삭제하기 위한 명령으로 옳지 않은 것은?
    struct Dlist { int data; struct Dlist *left; struct Dlist *right; };

    문제 이미지
    1
    B->right->left = B->left;
    B->left->right = B->right;
    2
    A->right = C;
    C->left = A;
    3
    A->right = A->right->right;
    B->right->left = B->left;
    4
    C->left->right = B->right;
    C->left = B->left;
    해설

    옳지 않은 명령은 C->left->right = B->right; C->left = B->left; 이다.

    C->left 는 B 이므로 첫 문장은 B 의 right 에 C 를 다시 넣을 뿐이고, 둘째 문장으로 C 의 left 만 A 로 바뀐다. 결국 A->right 가 여전히 B 를 가리켜 순방향 연결에서 B 가 빠지지 않는다.

    • B->right->left = B->left; B->left->right = B->right; : C 의 left 를 A 로, A 의 right 를 C 로 바꾸는 표준 삭제 연산이다.
    • A->right = C; C->left = A; : A 와 C 를 직접 양방향으로 연결하므로 B 가 제거된다.
    • A->right = A->right->right; B->right->left = B->left; : A 의 right 가 C 로, C 의 left 가 A 로 바뀌어 B 가 제거된다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    6[7급 국가직 자료구조론] 13년 1회차
    다음 정수들을 순서대로 삽입하여 AVL트리를 구성하였다. AVL트리의 구성 과정 중에 사용된 회전방법들로 옳은 것은?
    20, 16, 15, 9, 7, 12, 10, 1, 13, 5
    1
    LL 회전, RR 회전, RL 회전
    2
    RR 회전, RL 회전
    3
    LL 회전, LR 회전
    4
    LL 회전, LR 회전, RL 회전
    해설

    구성 과정에서 LL 회전과 LR 회전만 사용된다.

    20, 16, 15 삽입 시 20에서 LL 회전(16이 루트), 9, 7 삽입 시 15에서 LL 회전이 일어난다.

    12는 루트 16의 왼쪽 자식 9의 오른쪽 서브트리로 들어가 LR 회전(15가 루트)이 일어나고, 10, 1, 13은 균형을 유지하며, 5는 7의 왼쪽 자식 1의 오른쪽으로 들어가 다시 LR 회전이 일어난다.

    • LL·RR·RL 회전: RR과 RL 불균형은 한 번도 생기지 않는다.
    • RR·RL 회전: 실제로 쓰인 LL과 LR이 모두 빠져 있다.
    • LL·LR·RL 회전: 오른쪽 자식의 왼쪽으로 치우친 RL 불균형은 생기지 않는다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    7[7급 국가직 자료구조론] 13년 1회차
    다음은 방향성 그래프(directed graph)를 인접행렬로 표현한 것이다. 이에 대한 위상 정렬(topological sorting)의 결과로 옳은 것은? (단, 행(row)은 출발 노드로 열(column)은 도착 노드로 매핑된다)
    abcdef
    a11
    b11
    c11
    d1
    e11
    f
    1
    a, b, c, d, e, f
    2
    a, b, c, e, d, f
    3
    a, c, b, e, d, f
    4
    a, c, e, b, d, f
    해설

    위상 정렬 결과는 a, b, c, e, d, f이다.

    간선은 a→b, a→c, b→c, b→d, c→d, c→e, d→f, e→d, e→f이다. 진입차수가 0인 노드를 차례로 꺼내면 a → b → c → e → d → f로 순서가 하나로 정해진다.

    • a, b, c, d, e, f: e→d 간선이 있어 d가 e보다 앞설 수 없다.
    • a, c, b, e, d, f: b→c 간선이 있어 c가 b보다 앞설 수 없다.
    • a, c, e, b, d, f: 역시 c가 b보다 먼저 나와 b→c 간선을 어긴다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    8[7급 국가직 자료구조론] 13년 1회차
    다음은 A, B, C, D 네 개의 수가 사용된 후위 표기식이다. 이 수식을 스택을 이용하여 계산할 때, 스택에 여섯 번째로 저장(push)되는 값으로 옳은 것은?
    후위 표기식 : A B C + D * -
    1
    *
    2
    (B + C)
    3
    (B + C) * D
    4
    A - (B + C) * D
    해설

    스택에 여섯째로 push 되는 값은 (B + C) * D이다.

    후위식 계산에서는 피연산자를 push 하고, 연산자를 만나면 두 값을 pop 해 계산 결과를 push 한다. 연산자 자체는 저장되지 않는다.

    A, B, C가 첫째~셋째로 push → +에서 (B + C)가 넷째 → D가 다섯째 → *에서 (B + C) * D가 여섯째 → -에서 최종 결과가 일곱째로 push 된다.

    • *: 연산자는 스택에 저장되지 않는다.
    • (B + C): 넷째로 push 되는 값이다.
    • A - (B + C) * D: 마지막 일곱째로 push 되는 값이다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    9[7급 국가직 자료구조론] 13년 1회차
    다음 원형 큐(circular queue)에 대하여 연산들(가 ~ 바)이 차례대로 수행된 후에 큐의 상태로 옳은 것은? (단, front는 0이고 rear는 3이며, 원형 큐의 공백과 만원은 별도의 카운터를 두어서 처리한다)
    원형큐 :
    01234
    ABC
    가. D를 삽입  나. E를 삽입
    다. 두 개의 원소를 삭제  라. F를 삽입
    마. 하나의 원소를 삭제  바. G를 삽입
    1
    01234
    EFGD
    2
    01234
    FGD
    3
    01234
    FGCD
    4
    01234
    GBCD
    해설

    연산 후 큐에는 E, F, G, 빈칸, D(인덱스 0~4)가 남는다.

    front는 첫 원소 바로 앞을 가리키므로 A, B, C는 인덱스 1~3에 있다. 삽입은 rear를, 삭제는 front를 (x+1) mod 5(x+1) \bmod 5로 옮긴 자리에서 일어난다.

    D 삽입(인덱스 4) → E 삽입(인덱스 0) → A, B 삭제(front=2) → F 삽입(인덱스 1) → C 삭제(front=3) → G 삽입(인덱스 2).

    • F, G, 빈칸, 빈칸, D 상태: 삭제되지 않은 E가 빠져 있고 F, G 위치도 한 칸씩 어긋난다.
    • F, G, 빈칸, C, D 상태: C는 마지막 삭제에서 제거되었고 E가 빠져 있다.
    • G, 빈칸, B, C, D 상태: B와 C는 이미 삭제되었고 E, F가 빠져 있다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    10[7급 국가직 자료구조론] 13년 1회차
    이중해싱(double hashing)을 이용하는 크기가 5인 해시테이블(hash table)에 데이터 6, 3, 8, 18이 순서대로 입력된다. 마지막 데이터인 18이 입력될 때 발생하는 충돌의 횟수는? (단, 1차 해싱함수는 h(k) = k mod 5이고, 2차 해싱함수는 h'(k) = 5-(k mod 5) 이다)
    1
    0
    2
    1
    3
    2
    4
    3
    해설

    18을 넣을 때 충돌은 2회 발생한다.

    6은 6 mod 5=16 \bmod 5=1, 3은 3에 저장된다. 8은 3에서 충돌하고 2차 해싱 이동 폭 h′(8)=5−3=2h'(8)=5-3=2로 (3+2) mod 5=0(3+2) \bmod 5=0에 저장된다.

    18은 18 mod 5=318 \bmod 5=3에서 충돌(1회), 이동 폭 h′(18)=2h'(18)=2로 0에서 충돌(2회), 다음 (0+2) mod 5=2(0+2) \bmod 5=2는 비어 있어 저장된다.

    • 0회: 1차 해시 주소 3은 이미 3이 차지하고 있다.
    • 1회: 이동한 주소 0도 8이 차지하고 있다.
    • 3회: 세 번째 탐사 위치 2는 비어 있어 더 충돌하지 않는다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    11[7급 국가직 자료구조론] 13년 1회차
    완전 이진트리(complete binary tree)를 배열에 저장할 때, 루트 노드를 배열 A[1]에 저장하고 나머지 노드들은 트리의 레벨순서에 따라 왼쪽에서 오른쪽으로 연속적으로 저장한다. 노드 A[k]와 관계된 노드를 찾는 규칙이 바르게 짝지어지지 않은 것은?
    1
    부모 노드 - A[⌊k/2⌋]
    2
    왼쪽 자식 노드 - A[2k]
    3
    오른쪽 자식 노드 - A[2k+1]
    4
    형제 노드 - A[k+1]
    해설

    형제 노드를 항상 A[k+1]로 찾는 규칙은 틀렸다.

    k가 짝수면 왼쪽 자식이라 형제가 A[k+1]이지만, k가 홀수면 오른쪽 자식이라 형제는 A[k−1]이다(루트는 형제가 없다).

    • 부모 노드 − A[⌊k/2⌋]: 자식 2k와 2k+1을 2로 나눈 몫이 모두 k이므로 옳다.
    • 왼쪽 자식 노드 − A[2k]: 레벨순서 연속 저장의 정의대로 옳다.
    • 오른쪽 자식 노드 − A[2k+1]: 왼쪽 자식 바로 다음 칸이므로 옳다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    12[7급 국가직 자료구조론] 13년 1회차
    다음 C 코드에서 foobar 함수가 하는 일을 올바르게 설명한 것은?
    struct list_t {
    int data;
    struct list_t *link;
    };
    typedef struct list_t *list_p;

    void foobar(list_p *ptr, struct list_t *node)
    {
    if (*ptr == NULL) {
    *ptr = node;
    node->link = node;
    } else {
    node->link = (*ptr)->link;
    (*ptr)->link = node;
    }
    }
    1
    한 줄로 연결된 단순 연결 리스트에서 *ptr이 가리키는 노드의 뒤에 node를 삽입, 리스트가 비어 있으면 node로 새로 리스트를 만든다.
    2
    한 줄로 연결된 이중 연결 리스트에서 *ptr이 가리키는 노드의 뒤에 node를 삽입, 리스트가 비어 있으면 node로 새로 리스트를 만든다.
    3
    원형으로 연결된 단순 연결 리스트에서 *ptr이 가리키는 노드의 뒤에 node를 삽입, 리스트가 비어 있으면 node로 새로 리스트를 만든다.
    4
    원형으로 연결된 이중 연결 리스트에서 *ptr이 가리키는 노드의 뒤에 node를 삽입, 리스트가 비어 있으면 node로 새로 리스트를 만든다.
    해설

    foobar는 원형 단순 연결 리스트에서 *ptr이 가리키는 노드 뒤에 node를 삽입한다.

    구조체의 링크가 link 하나뿐이므로 단순 연결이고, 빈 리스트일 때 node->link = node로 자기 자신을 가리키게 하므로 원형이다. 비어 있지 않으면 node가 기존 다음 노드를 가리키게 한 뒤 (*ptr)->link를 node로 바꿔 뒤에 삽입한다.

    • 한 줄 단순 연결 리스트: 한 줄 리스트라면 마지막 link가 NULL이어야 하는데 자기 자신을 가리킨다.
    • 한 줄 이중 연결 리스트: 왼쪽·오른쪽 두 링크가 없고 원형 구조다.
    • 원형 이중 연결 리스트: 역방향 링크가 없어 이중 연결이 아니다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    13[7급 국가직 자료구조론] 13년 1회차
    다음 정수들을 순서대로 삽입하여 이진 탐색 트리(binary search tree)를 구성하였다. 구성된 이진 탐색 트리에서 단말 노드(leaf node)에 해당되는 값들로 옳은 것은?
    45, 36, 62, 2, 16, 51, 75, 69
    1
    2, 45, 62, 75
    2
    2, 16, 45, 51
    3
    16, 51, 69
    4
    36, 62, 69
    해설

    단말 노드는 16, 51, 69이다.

    45가 루트, 36은 왼쪽, 62는 오른쪽, 2는 36의 왼쪽, 16은 2의 오른쪽, 51은 62의 왼쪽, 75는 62의 오른쪽, 69는 75의 왼쪽에 놓인다. 자식이 없는 노드는 16, 51, 69뿐이다.

    • 2, 45, 62, 75 조합: 모두 자식이 있는 내부 노드다.
    • 2, 16, 45, 51 조합: 2는 16을, 45는 두 자식을 가진다.
    • 36, 62, 69 조합: 36과 62는 자식이 있다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    14[7급 국가직 자료구조론] 13년 1회차
    크기가 16인 다음 배열 E에 정수가 저장되어 있다.
    i[0][1][2][3][4][5][6][7][8][9][10][11][12][13][14][15]
    E[i]3568101315161721232627293133
    C언어로 표현된 함수 func를 이용하여 정수 K가 저장된 위치를 검색하려고 한다. func(E, 0, 15, 27)를 호출했을 때, 검색이 완료되기까지 ㉠ 문장이 수행되는 횟수는?
    int func(int E[ ], int first, int last, int K)
    {
    int mid;
    if (last < first) return -1;
    else {
    ㉠ mid = (first + last) / 2;
    if (K == E[mid]) return mid;
    else if (K < E[mid]) return func(E, first, mid-1, K);
    else return func(E, mid+1, last, K);
    }
    }
    1
    1회
    2
    2회
    3
    3회
    4
    4회
    해설

    func는 재귀 이진 탐색이며, 27을 찾을 때까지 ㉠은 4회 수행된다.

    (0, 15): mid = 7, E[7] = 16 < 27 → 오른쪽
    (8, 15): mid = 11, E[11] = 26 < 27 → 오른쪽
    (12, 15): mid = 13, E[13] = 29 > 27 → 왼쪽
    (12, 12): mid = 12, E[12] = 27 → 찾음

    • 1회: 첫 mid의 값이 16이라 바로 찾지 못한다.
    • 2회: 두 번째 mid의 값은 26이다.
    • 3회: 세 번째 mid의 값은 29로 아직 27이 아니다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    15[7급 국가직 자료구조론] 13년 1회차
    이중 연결 리스트(doubly linked list)에서 포인터 p가 가리키는 노드의 오른쪽에 포인터 newNode가 가리키는 노드를 삽입할 때, 연산의 순서가 바르게 나열된 것은? (단, llink는 왼쪽 노드를 가리키는 포인터이고 rlink는 오른쪽 노드를 가리키는 포인터이다)
    ㄱ. p->rlink = newNode;
    ㄴ. newNode->llink = p;
    ㄷ. newNode->rlink = p->rlink;
    ㄹ. p->rlink->llink = newNode;
    1
    ㄱ - ㄴ - ㄷ - ㄹ
    2
    ㄴ - ㄱ - ㄹ - ㄷ
    3
    ㄴ - ㄷ - ㄱ - ㄹ
    4
    ㄴ - ㄷ - ㄹ - ㄱ
    해설

    올바른 순서는 ㄴ − ㄷ − ㄹ − ㄱ이다.

    핵심은 p->rlink(기존 오른쪽 노드)를 덮어쓰는 ㄱ을 마지막에 두는 것이다. ㄷ과 ㄹ은 모두 p->rlink로 기존 오른쪽 노드에 접근하므로 ㄱ보다 먼저 실행되어야 한다.

    • ㄱ − ㄴ − ㄷ − ㄹ: ㄱ을 먼저 하면 기존 오른쪽 노드의 주소를 잃어 ㄷ에서 newNode가 자기 자신을 가리킨다.
    • ㄴ − ㄱ − ㄹ − ㄷ: ㄱ 이후라 ㄹ은 newNode의 llink를, ㄷ은 rlink를 자기 자신으로 만든다.
    • ㄴ − ㄷ − ㄱ − ㄹ: ㄱ 이후 p->rlink는 newNode라서 기존 오른쪽 노드의 llink가 갱신되지 않는다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    16[7급 국가직 자료구조론] 13년 1회차
    다음 AOE(Activity On Edge) 네트워크에서 작업의 완료시간을 단축하면 전체 프로젝트의 완료시간이 단축되는 단일 작업으로 옳은 것은?
    문제 이미지
    1
    a0
    2
    a5
    3
    a6
    4
    a9
    해설

    전체 완료시간을 줄이는 단일 작업은 유일한 임계경로 위의 a5 이다.

    각 사건의 가장 이른 시간을 구하면 0→2→4→3→5→8→9 경로(a1, a4, a5, a7, a10, a13)의 길이가 7+3+4+5+5+2=26 으로 가장 길고, 이 경로가 유일한 임계경로이다. 임계경로가 하나뿐이므로 그 위의 작업을 단축하면 프로젝트 완료시간이 줄어든다.

    • a0 : 0→1→3 경로는 사건 3 에 9 에 도착해 가장 이른 시간 14 보다 여유가 있어 임계작업이 아니다.
    • a6 : 3→6→9 경로는 사건 9 에 22 에 도착해 26 보다 여유가 있다.
    • a9 : 4→7 이후 경로는 사건 8·9 에 각각 16·17 에 도착해 여유가 크다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    17[7급 국가직 자료구조론] 13년 1회차
    다음 2-3 트리에 47을 삽입한 결과에 대한 설명으로 옳지 않은 것은?
    문제 이미지
    1
    노드 분할(split)이 3회 일어난다.
    2
    트리의 깊이는 3이다.
    3
    단말노드의 키 값은 (10, 20), (45), (50), (75, 80)이다.
    4
    루트 노드의 키 값은 47이다.
    해설

    옳지 않은 설명은 노드 분할이 3회 일어난다는 것으로, 실제 분할은 2회이다.

    47 은 단말 (45, 50) 에 들어가 (45, 47, 50) 이 되므로 분할되어 47 이 부모로 올라간다. 루트 (30, 60) 이 (30, 47, 60) 이 되어 다시 분할되고, 47 이 새 루트가 된다.

    • 트리의 깊이: 루트 (47), 중간 (30)·(60), 단말의 3단계이므로 깊이 3 이다.
    • 단말노드: (30) 아래 (10, 20)·(45), (60) 아래 (50)·(75, 80) 이 된다.
    • 루트 노드: 마지막 분할로 올라간 47 하나만 가진다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    18[7급 국가직 자료구조론] 13년 1회차
    다음 이진트리를 전위순회(preorder traversal), 중위순회(inorder traversal), 그리고 후위순회(postorder traversal) 순서로 각 노드를 방문하였다. 각각의 순회에서 7번째에 방문한 노드를 순서대로 나열한 것은?
    문제 이미지
    1
    G E C
    2
    H H E
    3
    E G E
    4
    G E H
    해설

    세 순회의 일곱째 방문 노드는 차례로 G, E, C 이다.

    전위순회는 A B D F C E G H, 중위순회는 B D F A C G E H, 후위순회는 F D B G H E C A 순으로 방문한다. 각 순서열의 일곱째 노드를 뽑으면 G, E, C 가 된다.

    • H H E : 전위의 일곱째는 H 가 아니라 G 이다.
    • E G E : 전위의 일곱째가 G, 중위의 일곱째가 E 이므로 앞의 두 값이 뒤바뀌었다.
    • G E H : 후위의 일곱째는 H 가 아니라 C 이다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    19[7급 국가직 자료구조론] 13년 1회차
    다음 그래프로부터 생성되는 최소 비용 신장 트리(minimum cost spanning tree)의 비용은?
    문제 이미지
    1
    31
    2
    32
    3
    34
    4
    42
    해설

    최소 비용 신장 트리의 비용은 32 이다.

    크루스칼 알고리즘으로 가중치가 작은 간선부터 사이클이 생기지 않게 고르면 1, 2, 3, 4, 5 가 차례로 채택되고, 7 은 이미 연결된 정점끼리라 사이클이 생겨 제외된다. 가중치 8 간선 중에는 왼쪽 위와 맨 위 정점을 잇는 것만 채택되고, 마지막으로 9 를 넣어 정점 8 개를 간선 7 개로 모두 잇는다.

    합계는 1+2+3+4+5+8+9=32 이다.

    • 31 : 최소 비용 32 보다 작아 어떤 신장 트리로도 만들 수 없다.
    • 34 : 왼쪽 정점을 잇는 데 9 대신 11 을 고르는 식으로 더 비싼 간선을 쓴 값이다.
    • 42 : 최소가 아닌 신장 트리의 비용이다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    20[7급 국가직 자료구조론] 13년 1회차
    다음은 원형 연결 리스트(circular linked list)의 길이를 구하는 함수이다. 원형 연결 리스트의 마지막 노드를 last가 가리키고 있을 때, ㉠에 들어갈 문장으로 옳은 것은?
    int length(listPointer last)
    {
    listPointer temp = last;
    int count = 0;
    if (last) {
    for(count = 1;   ㉠  ; count++)
    temp = temp->link;
    }
    return count;
    }
    1
    temp->link != last
    2
    temp == last->link
    3
    temp != last->link
    4
    temp->link == NULL
    해설

    ㉠에는 temp->link != last가 들어간다.

    temp는 last에서, count는 1에서 시작한다. 다음 노드가 last가 아닐 때마다 한 칸 이동하며 count를 늘리면, 한 바퀴를 돌아 last 직전 노드에서 멈출 때 count가 전체 노드 수가 된다. 예컨대 노드가 3개면 두 번 이동해 count = 3이다.

    • temp == last->link: 시작 시 temp는 last라 노드가 2개 이상이면 즉시 거짓이 되어 1로 끝난다.
    • temp != last->link: 첫 노드에 도달하자마자 멈춰 노드가 2개 이상이면 항상 2를 반환한다.
    • temp->link == NULL: 원형 리스트에는 NULL 링크가 없어 처음부터 거짓이 되고 1로 끝난다.

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

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

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

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

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

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

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

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

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

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

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