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

[7급 국가직 자료구조론] 18년 1회차
    1[7급 국가직 자료구조론] 18년 1회차
    다음 C 언어 함수에 의해 구현된 정렬 방식은?
    void whatsort(int a[ ], int size)
    {
    int i, j, temp;
    for (i = (size-1); i > 0; i--) {
    for (j = 1; j <= i; j++) {
    if (a[j-1] > a[j]) {
    temp = a[j-1];
    a[j-1] = a[j];
    a[j] = temp;
    }
    }
    }
    }
    1
    삽입 정렬(insertion sort)
    2
    선택 정렬(selection sort)
    3
    힙 정렬(heap sort)
    4
    버블 정렬(bubble sort)
    해설

    이 함수는 버블 정렬을 구현한 것이다.

    안쪽 반복에서 인접한 두 원소 a[j-1]과 a[j]를 비교해 앞쪽이 크면 교환하므로, 한 바퀴가 끝날 때마다 가장 큰 값이 구간 맨 뒤(i 위치)로 밀려난다. 바깥 반복은 이 구간을 한 칸씩 줄여 간다.

    • 삽입 정렬: 새 원소를 이미 정렬된 앞부분의 알맞은 위치에 끼워 넣는 방식으로, 구간 끝까지 인접 교환을 되풀이하는 이 구조와 다르다.
    • 선택 정렬: 한 바퀴에서 최솟값(또는 최댓값)의 위치를 찾은 뒤 한 번만 교환하므로, 비교할 때마다 교환하는 이 코드와 다르다.
    • 힙 정렬: 배열을 힙으로 구성한 뒤 루트를 꺼내며 부모·자식 인덱스 관계로 재조정하는 방식이다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    2[7급 국가직 자료구조론] 18년 1회차
    다음 중위 표현식(infix expression)을 후위 표현식(postfix expression)으로 변환한 후, 스택을 이용하여 후위 표현식을 계산하고자 한다. 후위 표현식의 계산 과정에서 스택에 여덟 번째로 삽입(push)되는 값은?
    ( 4 + 2 ) / 3 + ( 6 / 2 - 1 )
    1
    1
    2
    2
    3
    3
    4
    4
    해설

    후위 표현식 계산 중 여덟 번째로 push 되는 값은 3이다.

    중위식을 변환하면 4 2 + 3 / 6 2 / 1 - +가 된다. 피연산자는 그대로 push 하고, 연산자를 만나면 두 값을 pop 해 계산한 결과를 다시 push 한다.

    push 순서: 4 → 2 → 6(4+2) → 3 → 2(6/3) → 6 → 2 → 3(6/2) → 1 → 2(3-1) → 4(2+2)

    • 1: 아홉 번째로 push 되는 피연산자이다.
    • 2: 두 번째·다섯 번째·일곱 번째 등에 push 되는 값이다.
    • 4: 첫 번째로 push 되는 피연산자이자 마지막 계산 결과이다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    3[7급 국가직 자료구조론] 18년 1회차
    Prim 알고리즘을 사용하여 다음 가중 그래프(weighted graph)의 최소 비용 신장 트리(minimum cost spanning tree)를 구성할 때, 최소 비용과 마지막으로 선택되는 간선은? (단, 시작 정점은 A이다)
    문제 이미지
    1
    42, (A, G)
    2
    43, (A, G)
    3
    44, (F, G)
    4
    45, (F, G)
    해설

    A에서 Prim 알고리즘을 적용하면 최소 비용은 42이고, 마지막으로 선택되는 간선은 (A, G)이다.

    Prim 알고리즘은 이미 선택된 정점 집합과 나머지 정점을 잇는 간선 중 가중치가 가장 작은 간선을 하나씩 추가한다. 선택 순서는 (A, B) 10 → (B, C) 5 → (C, E) 3 → (E, F) 7 → (F, D) 6 → (A, G) 11 이다.

    합계는 10+5+3+7+6+11=4210+5+3+7+6+11=42 이다. G는 (A, G) 11과 (F, G) 13으로만 연결되므로 마지막에 더 가벼운 (A, G)가 선택된다.

    • 43, (A, G): 마지막 간선은 맞지만 최소 비용은 42이다.
    • 44, (F, G): (F, G)는 가중치 13으로 (A, G)의 11보다 커서 신장 트리에 포함되지 않고, 비용도 42가 아니다.
    • 45, (F, G): 마지막 간선과 비용이 모두 계산 결과와 다르다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    4[7급 국가직 자료구조론] 18년 1회차
    시작 정점이 6일 때, 다음 그래프에 대한 깊이 우선 탐색(DFS: Depth First Search)의 방문 순서는? (단, 인접한 정점들은 오름차순으로 방문한다)
    문제 이미지
    1
    6, 5, 3, 1, 0, 2, 4, 7, 8, 9
    2
    6, 5, 7, 3, 8, 9, 1, 4, 0, 2
    3
    6, 5, 3, 4, 2, 1, 0, 7, 8, 9
    4
    6, 5, 7, 3, 1, 4, 0, 2, 8, 9
    해설

    정점 6에서 인접 정점을 오름차순으로 방문하는 DFS의 방문 순서는 6, 5, 3, 1, 0, 2, 4, 7, 8, 9이다.

    6의 인접 정점(5, 7) 중 작은 5로 가고, 5에서 3, 3에서 1, 1에서 0으로 내려간다. 0은 더 갈 곳이 없어 되돌아가(backtracking) 1의 다음 인접 정점 2, 이어서 4를 방문한다.

    4의 인접 정점은 모두 방문했으므로 5까지 되돌아가 7을 방문하고, 7에서 8, 9 순으로 방문하면 탐색이 끝난다.

    • 6, 5, 7, 3, 8, 9, 1, 4, 0, 2: 시작 정점에서 가까운 정점부터 차례로 방문한 너비 우선 탐색(BFS)의 순서이다.
    • 6, 5, 3, 4, 2, 1, 0, 7, 8, 9: 3의 인접 정점 중 1이 4보다 작으므로 1을 먼저 방문해야 한다.
    • 6, 5, 7, 3, 1, 4, 0, 2, 8, 9: 5에서 3이 7보다 작은데 7을 먼저 방문해 오름차순 조건에 어긋난다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    5[7급 국가직 자료구조론] 18년 1회차
    C 언어 함수로 구현된 <정렬 알고리즘>과 크기가 5인 배열 list를 이용하여 sort(list, 5)를 수행하였다. <설명>에서 옳은 것만을 모두 고르면? (단, sort(list, 5) 수행 전에 list 배열에 4, 9, 8, 6, 3이 순서대로 저장되어 있다)
    <정렬 알고리즘>
    #define SWAP(x, y, t) ((t)=(x), (x)=(y), (y)=(t))
    void sort(int list[ ], int n)
    {
    int i, j, least, temp;
    for (i = 0; i < n - 1; i++) {
    least = i;
    for (j = i + 1; j < n; j++)
    if (list[j] < list[least]) least = j;
    SWAP(list[i], list[least], temp);
    }
    }
    <설 명>
    ㄱ. sort(list, 5)의 수행이 완료될 때까지 SWAP은 4회 수행된다.
    ㄴ. SWAP이 두 번째 수행된 후 배열 list에는 3, 4, 8, 6, 9가 순서대로 저장되어 있다.
    ㄷ. 정렬 알고리즘의 시간 복잡도를 빅세타(Θ) 표기법으로 표현한 것은 Θ(nlogn)이다.
    1
    ㄱ
    2
    ㄱ, ㄴ
    3
    ㄱ, ㄷ
    4
    ㄴ, ㄷ
    해설

    옳은 것은 ㄱ, ㄴ이다. 이 코드는 매 단계 최솟값을 골라 앞자리와 교환하는 선택 정렬이다.

    4, 9, 8, 6, 3 → (i=0, 최솟값 3) 3, 9, 8, 6, 4 → (i=1, 최솟값 4) 3, 4, 8, 6, 9 → (i=2, 최솟값 6) 3, 4, 6, 8, 9 → (i=3, 최솟값 8, 자기 자신과 교환) 3, 4, 6, 8, 9

    • ㄱ(옳음): SWAP은 바깥 반복마다 조건 없이 한 번씩 수행되므로 n−1=4n-1=4회이다.
    • ㄴ(옳음): 두 번째 SWAP 직후 배열은 3, 4, 8, 6, 9이다.
    • ㄷ(틀림): 입력 상태와 관계없이 비교가 n(n−1)2\dfrac{n(n-1)}{2}회 일어나므로 시간 복잡도는 Θ(n2)\Theta(n^2)이다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    6[7급 국가직 자료구조론] 18년 1회차
    공백 AVL 트리에 데이터를 순서대로 삽입하여 AVL 트리를 구성할 때, 나머지와 다른 모습의 AVL 트리가 구성되는 데이터 키(key)들의 순서는?
    1
    3, 4, 6, 5, 7, 8
    2
    5, 4, 7, 3, 6, 8
    3
    7, 5, 8, 6, 4, 3
    4
    8, 7, 5, 4, 6, 3
    해설

    나머지와 다른 AVL 트리가 만들어지는 순서는 3, 4, 6, 5, 7, 8이다.

    3, 4, 6 삽입 시 RR 회전으로 4가 루트가 되고, 5와 7을 넣은 뒤 8을 넣으면 루트 4에서 다시 불균형이 생겨 RR 회전이 일어난다. 결과는 루트 6, 왼쪽 4(자식 3, 5), 오른쪽 7(오른쪽 자식 8)이다.

    나머지 세 순서는 모두 루트 5, 왼쪽 4(왼쪽 자식 3), 오른쪽 7(자식 6, 8)인 같은 트리가 된다.

    • 5, 4, 7, 3, 6, 8: 회전 없이 바로 위 모양이 된다.
    • 7, 5, 8, 6, 4, 3: 7(5(4, 6), 8)에서 3을 넣으면 루트 7에서 LL 불균형이 생기고, 오른쪽 회전으로 5가 루트가 된다.
    • 8, 7, 5, 4, 6, 3: 8, 7, 5에서 LL 회전으로 7(5, 8)이 되고, 4, 6, 3을 넣은 뒤 다시 LL 회전으로 5가 루트가 된다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    7[7급 국가직 자료구조론] 18년 1회차
    다음 키(key) 값을 갖는 9개의 데이터를 순서대로 삽입하여 이진 탐색 트리(binary search tree)를 구성하였다. 구성된 이진 탐색 트리에서 루트 노드를 삭제한 후 구성되는 이진 탐색 트리에 대한 설명으로 옳지 않은 것은?
    5, 6, 2, 8, 4, 1, 9, 3, 7
    1
    루트 노드의 키는 4와 6 중 한 개의 값을 가진다.
    2
    중위 순회(inorder traversal)할 경우 키 값이 1, 2, 3, 4, 6, 7, 8, 9인 노드들을 순서대로 방문한다.
    3
    모든 단말 노드들의 키 값들의 합은 21이다.
    4
    모든 노드들의 차수(degree)들의 합은 7이다.
    해설

    옳지 않은 설명은 단말 노드 키 값의 합이 21이라는 것으로, 실제 합은 20이다.

    원래 트리는 루트 5, 왼쪽 2(자식 1, 4), 4의 왼쪽 자식 3, 오른쪽 6, 6의 오른쪽 자식 8(자식 7, 9)이다. 루트를 삭제하면 왼쪽 서브트리 최댓값 4 또는 오른쪽 서브트리 최솟값 6이 루트 자리로 올라온다.

    어느 쪽으로 대체해도 단말 노드는 1, 3, 7, 9로 같아 합은 20이다.

    • 루트 키가 4와 6 중 하나: 삭제 노드를 중위 선행자나 중위 후속자로 대체하므로 옳다.
    • 중위 순회 순서 1, 2, 3, 4, 6, 7, 8, 9: 이진 탐색 트리의 중위 순회는 남은 키의 오름차순이므로 옳다.
    • 차수의 합 7: 노드가 8개이면 간선은 7개이고, 각 간선이 부모의 차수를 1씩 늘리므로 옳다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    8[7급 국가직 자료구조론] 18년 1회차
    다음 인접 행렬은 5개 도시 간의 직접 거리를 보여준다. 인천-대구 구간 최단 경로 거리와 광주-대구 구간 최단 경로 거리 사이의 차이 값은? (단, ∞는 두 도시 간에 직접적인 연결이 없음을 의미한다)
    대전광주서울인천대구
    대전01015259
    광주1001820∞
    서울15180317
    인천252030∞
    대구9∞17∞0
    1
    1
    2
    2
    3
    3
    4
    4
    해설

    두 최단 경로 거리의 차이는 1이다.

    인천-대구는 직접 연결이 없으므로 경유 경로를 비교한다.

    • 인천→서울→대구: 3 + 17 = 20 (최단)
    • 인천→서울→대전→대구: 3 + 15 + 9 = 27
    • 인천→대전→대구: 25 + 9 = 34

    광주-대구도 직접 연결이 없으며, 광주→대전→대구 = 10 + 9 = 19가 광주→서울→대구(35) 등보다 짧다.

    따라서 차이는 20 − 19 = 1이다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    9[7급 국가직 자료구조론] 18년 1회차
    키(key) 집합에 속하는 각 키에 대해 탐색이 일어날 확률이 알려져 있을 때, 최적 이진 탐색 트리(optimal binary search tree)를 구성함으로써 한 번의 탐색에 대한 평균 비교 횟수를 최소화할 수 있다. p(x)p(x)를 키 xx에 대한 탐색 확률이라고 할 때, 키 집합 {1, 2, 3}에 속하는 각 키에 대한 탐색 확률은 다음과 같다. 키 값이 각각 1, 2, 3인 3개의 데이터를 사용하여 구성한 최적 이진 탐색 트리에서 탐색 1회당 평균 비교 횟수는? (단, p(1)+p(2)+p(3)=1p(1) + p(2) + p(3) = 1이므로, 1, 2, 3 외의 키를 탐색하는 경우는 없다)
    p(1)=0.6, p(2)=0.3, p(3)=0.1p(1) = 0.6,\ p(2) = 0.3,\ p(3) = 0.1
    1
    1.4
    2
    1.5
    3
    1.6
    4
    1.7
    해설

    최적 이진 탐색 트리의 평균 비교 횟수는 1.5이다.

    평균 비교 횟수는 각 키의 (깊이 × 탐색 확률)의 합이다. 확률이 큰 키를 루트 가까이 두어야 하므로 1을 루트로, 2를 그 오른쪽 자식, 3을 2의 오른쪽 자식으로 둔다.

    0.6×1+0.3×2+0.1×3=1.50.6 \times 1 + 0.3 \times 2 + 0.1 \times 3 = 1.5

    • 루트 2(자식 1, 3): 0.3×1+(0.6+0.1)×2=1.70.3 \times 1 + (0.6 + 0.1) \times 2 = 1.7
    • 루트 1, 오른쪽 자식 3, 3의 왼쪽 자식 2: 0.6×1+0.1×2+0.3×3=1.70.6 \times 1 + 0.1 \times 2 + 0.3 \times 3 = 1.7
    • 루트 3인 트리: 확률이 가장 큰 키 1이 깊이 2 이상에 놓여 평균이 2를 넘는다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    10[7급 국가직 자료구조론] 18년 1회차
    다음의 해시 함수들을 사용하는 이중 해싱(double hashing)에서 해시 테이블의 크기는 7이며 0부터 6까지의 인덱스를 가진다. h(x)h(x)는 첫 번째 조사 위치를 결정하는 기본적인 해시 함수이고 f(x)f(x)는 충돌 발생 시 조사 위치 간격을 결정하는 추가 해시 함수로서, ii번째 충돌 발생 시 다음 조사 위치를 결정하는 해시 함수는 hi(x)h_i(x)가 된다. 공백 해시 테이블에 일련의 키(key) 값 9, 10, 2, 3, 16, 13, 11을 가지는 레코드들을 순서대로 삽입한 후, 해시 테이블의 위치별 키 값을 보여주는 것은? (단, 해시 테이블 버킷(bucket)당 슬롯(slot) 수는 1개이다)
    h(x)=x mod 7h(x) = x \bmod 7
    f(x)=5−(x mod 5)f(x) = 5 - (x \bmod 5)
    hi(x)=(h(x)+i×f(x)) mod 7h_i(x) = (h(x) + i \times f(x)) \bmod 7
    [0][1][2][3][4][5][6]
    1
    13169101123
    2
    16139101123
    3
    31391011216
    4
    13119102316
    해설

    삽입 후 해시 테이블은 [0]부터 3, 13, 9, 10, 11, 2, 16이다.

    충돌이 없으면 h(x)h(x) 위치에 넣고, 충돌하면 f(x)f(x) 간격으로 다음 위치를 조사한다.

    9: h=2 → [2]
    10: h=3 → [3]
    2: h=2 충돌, f=3 → (2+3) mod 7 = 5 → [5]
    3: h=3 충돌, f=2 → [5] 충돌 → (3+4) mod 7 = 0 → [0]
    16: h=2 충돌, f=4 → (2+4) mod 7 = 6 → [6]
    13: h=6 충돌, f=2 → (6+2) mod 7 = 1 → [1]
    11: h=4 → [4]

    • [0]에 13, [6]에 3을 둔 배치: 13은 [1], 3은 [0]에 들어가므로 틀리다.
    • [0]에 16, [1]에 13을 둔 배치: 16은 첫 충돌 후 [6]에 들어가므로 틀리다.
    • [1]에 11, [4]에 2, [5]에 3을 둔 배치: 11은 충돌 없이 [4], 2는 [5]에 들어가므로 틀리다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    11[7급 국가직 자료구조론] 18년 1회차
    다음 일련의 스택 연산에 의해 스택에서 삭제되는 자료를 순서대로 바르게 나열한 것은? (단, push(xx)는 스택에 자료 xx를 삽입하는 연산이고, pop()은 스택에서 자료 한 개를 삭제하는 연산이다)
    push(9), pop(), push(5), push(7), push(2), pop(), push(9), pop(), push(4), pop(), pop(), push(6), push(3), pop(), push(2), pop(), pop()
    1
    9, 5, 7, 2, 9, 4, 6, 3
    2
    9, 2, 9, 4, 7, 3, 2, 6
    3
    2, 3, 6, 4, 9, 2, 7, 5
    4
    9, 5, 9, 4, 7, 6, 2, 2
    해설

    삭제되는 자료의 순서는 9, 2, 9, 4, 7, 3, 2, 6이다.

    스택은 후입선출(LIFO)이므로 pop()은 항상 가장 최근에 push 된 값을 꺼낸다.

    push(9)·pop() → 9
    push(5, 7, 2)·pop() → 2 (남은 스택 5, 7)
    push(9)·pop() → 9
    push(4)·pop() → 4
    pop() → 7 (남은 스택 5)
    push(6, 3)·pop() → 3
    push(2)·pop() → 2
    pop() → 6 (남은 스택 5)

    • 9, 5, 7, 2, 9, 4, 6, 3: 먼저 넣은 값부터 꺼내는 큐(FIFO) 방식으로 처리한 순서이다.
    • 2, 3, 6, 4, 9, 2, 7, 5: 첫 pop()의 결과가 9이어야 하므로 시작부터 맞지 않는다.
    • 9, 5, 9, 4, 7, 6, 2, 2: 두 번째 pop()에서 맨 위의 2가 아닌 바닥 쪽 5를 꺼낸 것으로 틀리다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    12[7급 국가직 자료구조론] 18년 1회차
    다음 이진 트리(binary tree)를 <보기>에서 제시한 방법을 사용하여 1차원 배열로 표현할 때, 필요한 배열의 최소 크기는? (단, 배열의 인덱스(index)는 0부터 시작하며 배열의 크기는 배열 원소의 개수이다)
    <보 기>
    ○ 루트 노드는 배열의 인덱스가 1인 위치에 저장된다.
    ○ 배열 인덱스가 kk인 위치에 있는 노드가 자식 노드를 가질 경우, 왼쪽 자식 노드는 인덱스가 2k2k인 위치에 있으며 오른쪽 자식 노드는 인덱스가 2k+12k+1인 위치에 있다.

    문제 이미지
    1
    17
    2
    18
    3
    34
    4
    35
    해설

    가장 큰 인덱스가 34이고 인덱스가 0부터 시작하므로 필요한 배열의 최소 크기는 35이다.

    루트 A가 1이면 B는 2, C는 3, D는 2×2=42\times2=4, E는 C의 왼쪽 자식이므로 2×3=62\times3=6이다.

    F는 D의 왼쪽 자식으로 8, G는 F의 오른쪽 자식으로 2×8+1=172\times8+1=17, H는 G의 왼쪽 자식으로 2×17=342\times17=34가 된다. 사용하지 않는 인덱스 0 자리를 포함해 0~34까지 칸이 있어야 한다.

    • 17: G의 인덱스 값일 뿐이며 H의 위치 34를 담지 못한다.
    • 18: G(인덱스 17)까지만 담는 크기로 H의 위치 34를 담지 못한다.
    • 34: 최대 인덱스 34를 담으려면 인덱스 0을 포함해 원소가 35개 필요하므로 하나 부족하다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    13[7급 국가직 자료구조론] 18년 1회차
    행 우선(row major) 순서로 저장되는 3차원 배열 a[3][30][10]이 있을 때, 첫 번째 원소인 a[0][0][0]의 메모리 주소가 2048이면 a[2][15][2]의 메모리 주소는? (단, 배열 a에서 각 원소의 크기는 4바이트이다)
    1
    2800
    2
    2804
    3
    5052
    4
    5056
    해설

    a[2][15][2]의 메모리 주소는 5056이다.

    행 우선 순서에서 a[i][j][k]까지 앞선 원소 수는 i×(30×10)+j×10+ki \times (30 \times 10) + j \times 10 + k이다.

    2×300+15×10+2=7522 \times 300 + 15 \times 10 + 2 = 752
    2048+752×4=2048+3008=50562048 + 752 \times 4 = 2048 + 3008 = 5056

    • 2800: 원소 수 752에 원소 크기 4를 곱하지 않고 그대로 더한 값이다.
    • 2804: 원소 크기 4를 곱하면 오프셋이 3008바이트이므로 3000 미만의 주소는 나올 수 없다.
    • 5052: 앞선 원소 수를 751로 잘못 세어 원소 하나만큼 앞선 주소이다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    14[7급 국가직 자료구조론] 18년 1회차
    다음은 C 언어 구조체와 이를 이용한 이중 연결 리스트(doubly linked list)이다. 포인터 current가 가리키는 노드의 왼쪽 노드를 삭제할 때 수행할 C 언어 문장을 순서대로 바르게 나열한 것은? (단, 삭제 전에 포인터 current가 가리키는 노드의 왼쪽에 최소 2개의 노드가 있다고 가정하며, 삭제 노드에 대한 메모리 할당 해제는 생략한다)
    struct Dnode {
    int key;
    struct Dnode *prev;
    struct Dnode *next;
    };

    문제 이미지
    1
    current->next = current->next->next;
    current->next->prev = current;
    2
    current->next->prev = current;
    current->next = current->next->next;
    3
    current->prev = current->prev->prev;
    current->prev->next = current;
    4
    current->prev->next = current;
    current->prev = current->prev->prev;
    해설

    current의 왼쪽 노드를 삭제하려면 먼저 current->prev = current->prev->prev;로 current가 두 칸 왼쪽 노드를 가리키게 하고, 이어서 current->prev->next = current;로 그 노드가 current를 가리키게 한다.

    첫 문장 뒤 current->prev는 삭제할 노드의 왼쪽 노드이므로, 두 번째 문장은 그 노드의 next를 current로 바꿔 삭제할 노드를 양방향 모두에서 건너뛰게 한다.

    • current->next = current->next->next; 를 먼저 수행하는 순서: current의 오른쪽 노드를 삭제하는 연산이라 문제의 대상과 다르다.
    • current->next->prev = current; 를 먼저 수행하는 순서: 역시 current의 오른쪽 노드를 다루며, 순서도 뒤바뀌어 오른쪽 노드 삭제로도 성립하지 않는다.
    • current->prev->next = current; 를 먼저 수행하는 순서: 이때 current->prev는 아직 삭제할 노드이므로 삭제할 노드의 next만 바뀌고, 두 칸 왼쪽 노드의 next는 계속 삭제할 노드를 가리킨다.

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

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

    int i;

    int RecFunc(int n)
    {
    i++;
    if (n <= 1)
    return 1;
    else
    return RecFunc(n-1) + RecFunc(n-2);
    }

    int main()
    {
    int result;
    i = 0;
    result = RecFunc(5);
    printf("%d, %d\n", i, result);
    }
    1
    13, 5
    2
    13, 8
    3
    15, 5
    4
    15, 8
    해설

    출력 결과는 15, 8이다.

    RecFunc의 반환값은 R(n)=R(n−1)+R(n−2)R(n)=R(n-1)+R(n-2), R(0)=R(1)=1R(0)=R(1)=1이다. 따라서 R(2)=2, R(3)=3, R(4)=5, R(5)=8이다.

    i는 호출될 때마다 1 증가하므로 호출 횟수는 C(n)=1+C(n−1)+C(n−2)C(n)=1+C(n-1)+C(n-2), C(0)=C(1)=1C(0)=C(1)=1이다. C(2)=3, C(3)=5, C(4)=9, C(5)=15이다.

    • 13, 5: 호출 횟수와 반환값을 모두 작게 센 값이다.
    • 13, 8: 반환값은 맞지만 호출 횟수를 15보다 적게 셌다.
    • 15, 5: 호출 횟수는 맞지만 5는 R(4)의 값이고 R(5)는 8이다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    16[7급 국가직 자료구조론] 18년 1회차
    다음은 키(key)의 오름차순으로 정렬된 배열을 보여준다. 키 24에 대한 보간 탐색(interpolation search)을 수행할 때, 첫 번째 탐색 위치는? (단, 배열에서 크기가 가장 작은 키와 가장 큰 키의 값은 미리 주어지고, 위치의 차이는 키 값의 차이에 비례한다는 가정 하에 탐색 위치를 계산하며, 소수점 이하는 반올림한다)
    위치012345678910111213
    키310151924304065707480828793
    1
    2
    2
    3
    3
    4
    4
    5
    해설

    보간 탐색의 첫 번째 탐색 위치는 3이다.

    보간 탐색은 키 값의 비율로 위치를 추정한다.
    pos=low+(key−a[low])×(high−low)a[high]−a[low]pos = low + \dfrac{(key - a[low]) \times (high - low)}{a[high] - a[low]}

    pos=0+(24−3)×1393−3=27390≈3.03pos = 0 + \dfrac{(24 - 3) \times 13}{93 - 3} = \dfrac{273}{90} \approx 3.03
    소수점 이하를 반올림하면 3이다.

    • 2: 계산값 3.03을 반올림한 결과보다 작다.
    • 4: 키 24가 실제로 저장된 위치일 뿐, 첫 탐색 위치는 비례 계산으로 정해진다.
    • 5: 계산값 3.03을 반올림한 결과보다 크다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    17[7급 국가직 자료구조론] 18년 1회차
    다음은 C 언어 구조체와 이를 이용한 원형 연결 리스트(circular linked list)이다. 원형 연결 리스트의 맨 마지막에 포인터 new_node가 가리키는 노드를 삽입할 때 수행할 C 언어 문장을 순서대로 바르게 나열한 것은? (단, new_node의 삽입 전에 원형 연결 리스트는 공백 리스트가 아니고, last는 원형 연결 리스트의 마지막 노드를 가리키는 포인터다)
    struct Cnode {
    int key;
    struct Cnode *link;
    };

    문제 이미지
    1
    new_node->link = last->link;
    last = new_node;
    last->link = new_node;
    2
    new_node->link = last->link;
    last->link = new_node;
    last = new_node;
    3
    last->link = new_node;
    new_node->link = last->link;
    last = new_node;
    4
    last = new_node;
    last->link = new_node;
    new_node->link = last->link;
    해설

    원형 연결 리스트의 끝에 삽입하려면 new_node->link = last->link; → last->link = new_node; → last = new_node; 순서로 수행한다.

    last->link는 처음 노드를 가리키므로, 이 값을 먼저 new_node->link에 보관해야 처음 노드를 잃지 않는다. 그다음 기존 마지막 노드를 new_node에 연결하고, 마지막으로 last를 new_node로 옮긴다.

    • last = new_node; 를 둘째로 수행하는 순서: 기존 마지막 노드가 new_node와 연결되지 않고, new_node가 자기 자신을 가리키게 된다.
    • last->link = new_node; 를 먼저 수행하는 순서: 처음 노드의 주소를 잃어 new_node->link가 자기 자신을 가리키게 된다.
    • last = new_node; 를 먼저 수행하는 순서: 기존 마지막 노드를 가리킬 방법이 없어져 리스트에 연결할 수 없다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    18[7급 국가직 자료구조론] 18년 1회차
    다음 5×5 희소 행렬(sparse matrix)을 구조체 배열로 표현하기 위해 <규칙>의 표현 규칙을 사용하여 <코드>의 C 언어 코드를 작성하였다. <코드>의 ㉠에 들어갈 내용은? (단, 행렬의 행 번호와 열 번호는 0부터 시작한다)
    [0520000010000003000000000]\begin{bmatrix} 0 & 5 & 2 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}
    <코 드>
    typedef struct {
    int row;
    int col;
    int val;
    } term;

    term A[ ] =    ㉠   ;
    <규 칙>
    ○ 첫 번째 구조체인 A[0]의 row, col, val에는 희소 행렬의 행 개수, 열 개수, 값이 0이 아닌 원소 개수를 순서대로 저장한다.
    ○ 두 번째부터의 나머지 구조체는 값이 0이 아닌 희소 행렬 원소를 표현하기 위해 사용되며, 각 구조체의 row, col, val에 해당 원소의 행 번호, 열 번호, 값을 순서대로 저장한다.
    ○ 값이 0이 아닌 희소 행렬 원소 정보는 행 번호의 오름차순으로 구조체 배열 A에 저장되며, 행 번호가 같은 경우에는 열 번호의 오름차순으로 저장된다.
    1
    {{4, 4, 4}, {0, 1, 5}, {0, 2, 2}, {1, 3, 1}, {3, 0, 3}}
    2
    {{4, 4, 4}, {3, 0, 3}, {0, 1, 5}, {0, 2, 2}, {1, 3, 1}}
    3
    {{5, 5, 4}, {0, 1, 5}, {0, 2, 2}, {1, 3, 1}, {3, 0, 3}}
    4
    {{5, 5, 4}, {3, 0, 3}, {0, 1, 5}, {0, 2, 2}, {1, 3, 1}}
    해설

    ㉠에 들어갈 내용은 {{5, 5, 4}, {0, 1, 5}, {0, 2, 2}, {1, 3, 1}, {3, 0, 3}}이다.

    A[0]에는 행 수 5, 열 수 5, 0이 아닌 원소 수 4를 저장한다. 나머지는 행 번호 오름차순(같으면 열 번호 오름차순)으로 (0, 1, 5), (0, 2, 2), (1, 3, 1), (3, 0, 3)을 저장한다.

    • {4, 4, 4}로 시작하고 행 순서로 나열한 것: 행·열 개수 자리에 최대 인덱스 4를 잘못 적었다.
    • {4, 4, 4}로 시작하고 (3, 0, 3)을 앞에 둔 것: 행·열 개수도 틀리고, 열 번호 기준으로 정렬해 규칙에도 어긋난다.
    • {5, 5, 4}로 시작하고 (3, 0, 3)을 앞에 둔 것: 첫 구조체는 맞지만 열 번호 기준으로 정렬해 행 번호 오름차순 규칙에 어긋난다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    19[7급 국가직 자료구조론] 18년 1회차
    정점이 4개인 무방향(undirected) 완전 그래프(complete graph)에서 만들어질 수 있는 신장 트리(spanning tree)의 총 개수는?
    1
    12
    2
    14
    3
    16
    4
    18
    해설

    만들 수 있는 신장 트리의 총 개수는 16이다.

    케일리 공식에 따르면 정점이 n개인 완전 그래프의 서로 다른 신장 트리 수는 nn−2n^{n-2}이다.

    44−2=42=164^{4-2} = 4^2 = 16
    검산: 간선 6개 중 3개를 고르는 20가지에서 사이클(삼각형)이 되는 4가지를 빼면 16이다.

    • 12: 일렬 경로 모양(12개)만 세고 한 정점에 나머지 셋이 붙는 별 모양(4개)을 빠뜨린 값이다.
    • 14: 사이클이 되는 조합은 삼각형 4가지뿐이므로 20에서 6을 뺀 이 값은 맞지 않는다.
    • 18: 사이클 조합을 2가지만 제외한 셈이 되어 맞지 않는다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    20[7급 국가직 자료구조론] 18년 1회차
    일련의 키(key) 값 2, 1, 8, 9, 7, 3, 6을 가지는 7개의 데이터를 순서대로 삽입하여 레드-블랙 트리(red-black tree)를 구성하였다. 구성된 레드-블랙 트리를 후위 순회(postorder traversal)할 경우 방문 노드들의 키 값을 방문 순서대로 바르게 나열한 것은?
    1
    1, 3, 6, 2, 9, 8, 7
    2
    1, 3, 7, 6, 9, 8, 2
    3
    1, 6, 3, 2, 9, 8, 7
    4
    1, 6, 3, 7, 9, 8, 2
    해설

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

    2(흑, 루트)에 1, 8을 적색으로 삽입한다. 9 삽입 시 부모 8과 삼촌 1이 모두 적색이라 색 변경(1, 8 흑)하고, 7은 8의 왼쪽 적색 자식이 된다.

    3 삽입 시 부모 7과 삼촌 9가 적색이라 색 변경(7, 9 흑, 8 적)한다. 6 삽입 시 부모 3은 적색, 삼촌(7의 오른쪽)은 흑색이고 꺾인 모양이므로 이중 회전을 하여 6(흑)이 3, 7(적)을 자식으로 갖는다.

    최종 트리: 2(1, 8(6(3, 7), 9))

    • 1, 3, 6, 2, 9, 8, 7: 루트를 7로 본 순서로, 루트 2는 회전 없이 그대로 유지된다.
    • 1, 6, 3, 2, 9, 8, 7: 루트를 7로 잘못 잡았고 6과 3의 부모·자식 관계도 뒤바뀌었다.
    • 1, 6, 3, 7, 9, 8, 2: 회전 없이 6을 3의 오른쪽 자식으로 둔 것으로, 이중 회전 후에는 6이 3과 7의 부모가 된다.

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

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

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

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

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

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

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

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

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

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

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