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

[7급 국가직 자료구조론] 16년 1회차
    1[7급 국가직 자료구조론] 16년 1회차
    후위 표기법(postfix notation)으로 표현된 다음 수식의 계산 결과는?
    2 3 + 2 * 2 1 + 3 / -
    1
    7
    2
    8
    3
    9
    4
    10
    해설

    수식의 계산 결과는 9이다.

    후위 표기식은 스택으로 계산한다. 피연산자는 push 하고, 연산자를 만나면 두 값을 pop 해(먼저 꺼낸 값이 오른쪽 피연산자) 계산한 뒤 다시 push 한다.

    2 3 + → 5
    5 2 * → 10
    2 1 + → 3
    3 3 / → 1
    10 1 - → 9

    • 7은 나눗셈 3 / 를 빠뜨리고 10에서 3을 뺀 값이다.
    • 8은 스택 계산의 어느 단계에서도 나오지 않는 값이다.
    • 10은 마지막 뺄셈을 하기 전 스택 아래에 남아 있던 중간값이다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    2[7급 국가직 자료구조론] 16년 1회차
    노드의 개수가 177인 완전 이진 트리(complete binary tree)에서 마지막 레벨(level)에 위치한 노드의 개수는? (단, 루트 노드는 첫 번째 레벨에 위치한다)
    1
    49
    2
    50
    3
    78
    4
    127
    해설

    마지막 레벨에는 50개의 노드가 있다.

    완전 이진 트리는 마지막 레벨 직전까지 꽉 차 있다. 레벨 k까지의 노드 수는 2k−12^k - 1이고 27−1=127≤177<28−1=2552^7 - 1 = 127 \le 177 \lt 2^8 - 1 = 255이므로, 레벨 1~7이 포화 상태이고 레벨 8이 마지막 레벨이다.
    177−127=50177 - 127 = 50

    • 49는 177−27177 - 2^7로, 레벨 7까지의 노드 수를 128로 잘못 센 값이다.
    • 78은 레벨 8의 최대 노드 수 128에서 50을 뺀 값, 즉 마지막 레벨의 빈 자리 수이다.
    • 127은 레벨 7까지 포화된 노드 수로, 마지막 레벨 위쪽 전체의 노드 수이다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    3[7급 국가직 자료구조론] 16년 1회차
    다음 C 언어 함수를 이용하여 asterisk(9)를 수행할 때 출력되는 ‘*’의 개수는?
    #include <stdio.h>

    void asterisk(int i)
    {
    if(i > 1){
    asterisk(i/3);
    asterisk(i/3);
    }
    printf("*");
    }
    1
    6
    2
    7
    3
    8
    4
    9
    해설

    asterisk(9)는 '*'를 7개 출력한다.

    i > 1이면 asterisk(i/3)을 두 번 재귀 호출한 뒤 자신도 '*'를 1개 출력하고, i ≤ 1이면 '*'만 1개 출력한다. 출력 개수를 T(i)라 하면 T(i) = 2T(i/3) + 1이다.

    T(1) = 1
    T(3) = 2T(1) + 1 = 3
    T(9) = 2T(3) + 1 = 7

    • 6은 재귀 호출 수만 세고 최초 호출 asterisk(9) 자신의 출력을 빠뜨린 값이다.
    • 8은 호출마다 '*'를 정확히 1개씩 출력하는데 전체 호출이 7회뿐이라는 점과 맞지 않는다.
    • 9는 인자 값을 그대로 개수로 본 것으로, 출력 개수는 인자가 아니라 호출 횟수와 같다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    4[7급 국가직 자료구조론] 16년 1회차
    가장 낮은 자릿수(LSD : Least Significant Digit) 우선 방식의 기수 정렬(radix sort)을 이용하여, 다음과 같이 배열에 저장된 10진수 데이터를 오름차순으로 정렬하고자 한다. 오른쪽에서 두 번째 자릿수(digit) 기준의 정렬 단계 후에 위치 [3]에 있는 데이터로 옳은 것은? (단, 각 단계별 정렬의 기준이 되는 자릿수는 0에서 9까지의 값을 가진다)
    위치[0][1][2][3][4][5][6][7]
    데이터307424132216241835546630
    1
    630
    2
    546
    3
    132
    4
    216
    해설

    두 번째 자릿수 정렬 후 위치 [3]에는 630이 온다.

    LSD 기수 정렬은 일의 자리부터 자릿수별로 안정 정렬을 반복하므로, 같은 자릿값끼리는 이전 단계의 순서를 유지한다.

    일의 자리 정렬: 630, 241, 132, 424, 835, 216, 546, 307
    십의 자리 정렬: 307, 216, 424, 630, 132, 835, 241, 546
    십의 자리가 3인 630, 132, 835 중 앞 단계에서 먼저 있던 630이 위치 [3]에 놓인다.

    • 546은 십의 자리 정렬 후 맨 마지막 위치 [7]에 있다.
    • 132는 십의 자리가 630과 같지만 일의 자리 단계에서 630 뒤에 있었으므로 위치 [4]에 놓인다.
    • 216은 십의 자리가 1이라 위치 [1]에 놓인다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    5[7급 국가직 자료구조론] 16년 1회차
    해시 테이블 HT의 크기는 11이고 0부터 10까지의 인덱스를 가진다. 해시 함수 h(x)는 제산 함수로서 h(x) = x mod 11로 표현된다. 충돌 해결책으로는 이차 조사법(quadratic probing)을 사용한다. 해싱을 통해 해시 테이블에 저장할 레코드들의 키 값 순서는 다음과 같다. 마지막 레코드가 저장되는 해시 테이블 위치는? (단, 첫 번째 레코드가 저장되기 전에 해시 테이블은 비어 있고, 해시 테이블 버킷(bucket)당 슬롯(slot) 수는 1개이다)
    51, 27, 70, 55, 13, 2, 37, 23, 33
    1
    HT[1]
    2
    HT[4]
    3
    HT[6]
    4
    HT[9]
    해설

    마지막 키 33은 HT[9]에 저장된다.

    이차 조사법은 충돌 시 (h(x)+i2) mod 11, i=1,2,3,…(h(x) + i^2) \bmod 11,\ i = 1, 2, 3, \dots 순서로 빈 자리를 찾는다.

    51→7, 27→5, 70→4, 55→0, 13→2
    2→2 충돌 → 3
    37→4 충돌 → 5 충돌 → 8
    23→1
    33→0 충돌 → 1 충돌 → 4 충돌 → 9

    • HT[1]은 33의 첫 조사 위치(0 + 1)로, 이미 23이 차지하고 있다.
    • HT[4]는 그다음 조사 위치(0 + 4)로, 70이 차지하고 있다.
    • HT[6]은 비어 있지만 33의 조사 순서(0, 1, 4, 9)에 들어가지 않는다.

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

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

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

    DFS는 알파벳 순으로 가장 앞선 미방문 인접 정점으로 계속 내려가므로 A→B→C→F→H→G→D→E로 진행하고, E에서 더 갈 곳이 없어 H까지 되돌아간 뒤 I를 방문한다.

    BFS는 A의 인접 정점 B, D, E를 먼저 방문하고, 이어서 C(B에서), G(D에서), F(C에서), H(G에서), I(F에서) 순으로 방문한다.

    • DFS가 G 다음에 E, D 순으로 방문한다는 순서: G의 미방문 인접 정점 중 알파벳 순으로 D가 E보다 앞서므로 D를 먼저 방문해야 한다.
    • BFS가 A, B, C, D, E 순으로 진행한다는 순서: C는 A와 인접하지 않고 B를 거쳐 발견되므로, A와 직접 인접한 D, E보다 먼저 방문될 수 없다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    7[7급 국가직 자료구조론] 16년 1회차
    다음 C 프로그램의 실행 결과로 첫 번째 줄에 출력되는 값과 두 번째 줄에 출력되는 값의 차이 값은? (단, int로 선언된 정수형 변수는 4바이트를 차지하고 char로 선언된 문자형 변수는 1바이트를 차지한다)
    #include <stdio.h>

    void main()
    {
    struct node {
    int id;
    char name[8];
    int score;
    } A[10];

    printf("%d\n", &A[0]);
    printf("%d\n", &A[4]);
    }
    1
    56
    2
    64
    3
    72
    4
    80
    해설

    두 출력 값의 차이는 64이다.

    구조체 node 하나의 크기는 int 4 + char[8] 8 + int 4 = 16바이트이고, 모든 멤버가 4바이트 경계에 맞아 패딩이 생기지 않는다.
    &A[4] − &A[0] = 4 × 16 = 64

    • 56은 구조체 크기를 14바이트로 잘못 본 값이다.
    • 72는 구조체 크기를 18바이트로 잘못 본 값이다.
    • 80은 A[0]부터 A[4]까지 원소 5개 분량(5 × 16)으로 센 값으로, 주소 차이는 원소 4개 분량이다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    8[7급 국가직 자료구조론] 16년 1회차
    다음 AVL 트리에 정수 23을 삽입하면 AVL 트리로서의 균형이 깨진다. 회전을 통해 이 트리를 AVL 트리로 변환한 후에 전위 순회(preorder traversal)를 수행하였을 때 노드 방문 순서는?
    문제 이미지
    1
    30, 19, 7, 23, 41, 27
    2
    30, 7, 19, 23, 27, 41
    3
    27, 19, 7, 23, 30, 41
    4
    27, 19, 7, 30, 23, 41
    해설

    23을 삽입한 뒤 LR 회전으로 균형을 맞추면 전위 순회 결과는 27, 19, 7, 23, 30, 41이다.

    23은 30의 왼쪽, 19의 오른쪽, 27의 왼쪽 자식으로 삽입된다. 이때 30의 균형 인수가 +2(왼쪽 높이 3, 오른쪽 높이 1)이고 그 왼쪽 자식 19의 균형 인수가 -1이므로 LR 불균형이다.

    회전 결과 27이 루트가 되고, 왼쪽에 19(자식 7, 23), 오른쪽에 30(오른쪽 자식 41)이 놓인다. 이를 루트→왼쪽→오른쪽 순으로 방문한다.

    • 30, 19, 7, 23, 41, 27: 루트가 30으로 그대로 남아 있어 회전으로 균형을 복구한 트리의 순회가 아니다.
    • 30, 7, 19, 23, 27, 41: 역시 루트가 30으로 남아 있고, 전위 순회라면 7보다 부모인 19가 먼저 나와야 한다.
    • 27, 19, 7, 30, 23, 41: 23은 27보다 작아 27의 왼쪽 서브트리(19의 오른쪽 자식)에 있으므로 30보다 먼저 방문되어야 한다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    9[7급 국가직 자료구조론] 16년 1회차
    다음 가중 그래프(weighted graph)는 9개의 정점과 1부터 19까지의 가중치(비용)를 갖는 19개의 간선으로 구성되어 있다. Kruskal 알고리즘을 사용하여 최소 비용 신장 트리(minimum cost spanning tree)를 구성할 때, 최소 비용과 마지막으로 선택되는 간선을 순서대로 나열한 것은?
    문제 이미지
    1
    43, (G, E)
    2
    43, (B, F)
    3
    44, (G, E)
    4
    44, (B, F)
    해설

    Kruskal 알고리즘의 최소 비용은 44이고, 마지막으로 선택되는 간선은 (B, F)이다.

    가중치가 작은 간선부터 사이클이 생기지 않으면 채택한다. 1(H, C), 2(I, G), 3(G, H)를 채택하고 4(I, H)는 사이클이 생겨 버린다. 이어서 5(H, E), 6(A, C), 7(A, B), 8(B, D)를 채택한다.

    9(E, C), 10(D, A), 11(G, E)는 모두 사이클을 만들어 버리고, 12(F, B)를 채택하면 정점 9개에 간선 8개가 되어 종료한다.
    1+2+3+5+6+7+8+12=441+2+3+5+6+7+8+12=44

    • 최소 비용 43: 채택된 8개 간선 가중치의 합은 44이다.
    • 마지막 간선 (G, E): G와 E는 이미 H를 통해 연결되어 있어 가중치 11인 이 간선은 사이클을 만들므로 채택되지 않는다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    10[7급 국가직 자료구조론] 16년 1회차
    허프만 코딩(Huffman coding) 알고리즘을 이용하여 다음 19개 문자로 구성된 문자열을 압축하였다. 압축된 문자열에 사용된 비트 수는?
    ababadcdabacdabcdde
    1
    39
    2
    42
    3
    44
    4
    46
    해설

    압축된 문자열은 42비트를 사용한다.

    문자별 빈도는 a 6, d 5, b 4, c 3, e 1이다. 허프만 트리는 빈도가 가장 작은 두 노드를 반복해 합친다.

    e(1) + c(3) → 4
    4 + b(4) → 8
    d(5) + a(6) → 11
    8 + 11 → 19
    코드 길이는 a·b·d 2비트, c·e 3비트이므로 6×2 + 5×2 + 4×2 + 3×3 + 1×3 = 42

    • 39는 42보다 짧은데, 허프만 코드는 접두어 코드 중 총 비트 수가 최소이므로 이보다 짧은 접두어 코드는 만들 수 없다.
    • 44는 42보다 길어 최적 코드인 허프만 코드의 결과가 될 수 없다.
    • 46도 42보다 길어 허프만 코드의 결과가 될 수 없다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    11[7급 국가직 자료구조론] 16년 1회차
    C 언어에서 행 우선(row major) 순서로 저장되는 2차원 배열 a[4][5]가 있을 때, 나타내는 원소가 다른 것은?
    1
    *(*(a+1)+2)
    2
    *(a[1]+2)
    3
    **((a+1)+2)
    4
    a[1][2]
    해설

    **((a+1)+2)만 a[3][0]을 가리키고, 나머지는 모두 a[1][2]를 나타낸다.

    a+1은 1행을 가리키고 *(a+1)은 a[1](1행 첫 원소의 주소)이 되며, 여기에 +2를 하면 a[1][2]의 주소가 된다.

    반면 (a+1)+2는 행 단위로 2를 더해 a+3, 즉 3행이 되고, 두 번 역참조하면 a[3][0]이 된다.

    • *(*(a+1)+2)는 *(a[1]+2)와 같아 a[1][2]이다.
    • *(a[1]+2)는 포인터 산술 정의상 a[1][2]이다.
    • a[1][2]는 1행 2열 원소 그 자체이다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    12[7급 국가직 자료구조론] 16년 1회차
    다음 알고리즘의 시간 복잡도를 빅세타(Θ\Theta) 표기법으로 표현한 것은? (단, n > 0)
    int iterate(int n)
    {
    int i, count = 0;
    for (i = 1; i < n; i *= 2)
    count++;
    return count;
    }
    1
    Θ(log⁡n)\Theta(\log n)
    2
    Θ(n)\Theta(n)
    3
    Θ(nlog⁡n)\Theta(n \log n)
    4
    Θ(n2)\Theta(n^2)
    해설

    시간 복잡도는 Θ(log⁡n)\Theta(\log n)이다.

    i는 1, 2, 4, 8, …처럼 매 반복 2배로 커지고 i < n 동안만 반복하므로, 반복 횟수는 2k≥n2^k \ge n이 되는 최소 k, 즉 ⌈log⁡2n⌉\lceil \log_2 n \rceil이다.

    • Θ(n)\Theta(n)은 i가 1씩 증가할 때의 반복 횟수이다.
    • Θ(nlog⁡n)\Theta(n \log n)은 로그 반복 루프를 바깥 루프가 n번 감쌀 때의 복잡도이며, 이 함수에는 바깥 루프가 없다.
    • Θ(n2)\Theta(n^2)은 선형 루프 두 개가 중첩될 때의 복잡도이다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    13[7급 국가직 자료구조론] 16년 1회차
    다음은 동적 메모리 할당을 통해 구조체 공간을 확보하고 이름과 학번을 입력받아 구조체에 저장하는 C 언어 함수이다. ㉠, ㉡에 들어갈 내용으로 옳게 짝지어진 것은?
    #include <stdio.h>
    #include <stdlib.h>

    struct student{
    char name[20];
    int id;
    };

    struct student *alloc()
    {
    struct student *p;
    p = ㉠ ;
    if(p==NULL){
    printf("Memory allocation error.");
    return p;
    }
    printf("Student name?\n");
    gets(p->name);
    printf("Student id?\n");
    scanf("%d", ㉡ );
    return p;
    }
    1
    ㉠ (struct student)malloc(sizeof(struct student)) ㉡ &((*p).id)
    2
    ㉠ (struct student *)malloc(sizeof(struct student)) ㉡ p->id
    3
    ㉠ (struct student)malloc(sizeof(struct student)) ㉡ (*p).id
    4
    ㉠ (struct student *)malloc(sizeof(struct student)) ㉡ &(p->id)
    해설

    ㉠에는 (struct student *)malloc(sizeof(struct student)), ㉡에는 &(p->id)가 들어간다.

    malloc은 void * 를 반환하므로 p의 자료형인 구조체 포인터로 형변환해야 하고, 구조체 값 자료형 (struct student)로는 포인터를 변환할 수 없다. scanf의 %d는 정수를 저장할 주소를 받아야 하므로 id 멤버의 주소를 넘긴다.

    • (struct student) 형변환과 &((*p).id) 조합은 ㉡은 맞지만, ㉠에서 포인터를 구조체 값 자료형으로 변환할 수 없다.
    • (struct student *) 형변환과 p->id 조합은 ㉠은 맞지만, scanf에 주소가 아닌 정수 값을 넘긴다.
    • (struct student) 형변환과 (*p).id 조합은 ㉠, ㉡ 모두 틀렸다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    14[7급 국가직 자료구조론] 16년 1회차
    다음 그래프의 위상 정렬(topological sorting) 결과로 나올 수 있는 위상 순서(topological order)로 옳지 않은 것은?
    문제 이미지
    1
    A, B, C, D, E, F
    2
    C, A, B, E, D, F
    3
    A, C, B, E, D, F
    4
    C, A, D, B, E, F
    해설

    위상 순서로 옳지 않은 것은 C, A, D, B, E, F이다.

    그래프의 간선은 A→B, B→D, B→E, B→F, C→D, C→E, E→F이다. 위상 순서는 모든 간선 u→v에 대해 u가 v보다 앞서야 하는데, 이 순서는 B→D 간선이 있음에도 D가 B보다 먼저 나온다.

    • A, B, C, D, E, F: 모든 간선의 선후 관계를 만족한다.
    • C, A, B, E, D, F: 진입 차수가 0인 C, A가 먼저 오고 B 다음에 E, D, 마지막에 F가 와 모든 조건을 만족한다.
    • A, C, B, E, D, F: A→B, C→D, C→E, B→D, B→E, E→F 조건을 모두 만족한다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    15[7급 국가직 자료구조론] 16년 1회차
    공백 상태인 이진 탐색 트리(binary search tree)에 1부터 5까지의 정수를 삽입하고자 한다. 삽입 결과, 이진 탐색 트리의 높이가 가장 낮은 삽입 순서는?
    1
    1, 2, 3, 4, 5
    2
    1, 3, 2, 4, 5
    3
    3, 1, 2, 4, 5
    4
    4, 3, 5, 2, 1
    해설

    3, 1, 2, 4, 5 순서로 삽입할 때 트리 높이가 가장 낮다(3레벨).

    이진 탐색 트리의 높이는 삽입 순서에 따라 달라지며, 루트가 중앙값에 가까울수록 좌우가 고르게 나뉜다. 3을 루트로 하면 왼쪽에 1-2, 오른쪽에 4-5가 각각 두 레벨로 달려 전체 3레벨이 된다.

    • 1, 2, 3, 4, 5는 계속 오른쪽 자식으로만 이어져 5레벨의 편향 트리가 된다.
    • 1, 3, 2, 4, 5는 1 → 3 → 4 → 5 경로가 생겨 4레벨이 된다.
    • 4, 3, 5, 2, 1은 4 → 3 → 2 → 1 경로가 왼쪽으로 이어져 4레벨이 된다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    16[7급 국가직 자료구조론] 16년 1회차
    다음 최대 힙(max heap)에 13을 삽입하는 연산을 수행한 후에 루트 노드를 삭제하는 연산을 수행하였다. 그 결과, 루트 노드의 오른쪽 자식 노드의 값으로 옳은 것은? (단, 삽입 및 삭제 연산은 최대 힙으로의 복원 과정을 포함한다)
    문제 이미지
    1
    9
    2
    10
    3
    13
    4
    18
    해설

    13 삽입 후 루트를 삭제하면 루트의 오른쪽 자식은 9가 된다.

    삽입: 13은 마지막 위치인 9의 오른쪽 자식으로 들어간 뒤 부모와 비교해 올라간다. 13은 9, 10보다 크므로 두 번 교환되어 21의 왼쪽 자식이 된다(배열 21, 13, 18, 10, 5, 7, 3, 4, 9).

    삭제: 루트 21을 제거하고 마지막 노드 9를 루트로 옮긴 뒤, 두 자식 13, 18 중 큰 18과 교환한다. 9는 새 자리의 자식 7, 3보다 크므로 멈춘다(배열 18, 13, 9, 10, 5, 7, 3, 4).

    • 10: 삽입 과정에서 13에 밀려 왼쪽 서브트리 아래로 내려가며, 루트의 오른쪽 자식과는 무관하다.
    • 13: 삭제 후 루트의 왼쪽 자식이다.
    • 18: 삭제 후 새 루트가 된다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    17[7급 국가직 자료구조론] 16년 1회차
    다음은 구현하고자 하는 원형 큐(circular queue)에 대한 <조건>과 <설명>이다. <설명>의 괄호 안에 들어갈 수로 옳게 짝지어진 것은?
    <조 건>
    ○ 크기가 6이고 인덱스가 0부터 5까지인 배열로 구현된다.
    ○ 공백 상태에서만 front와 rear의 값이 서로 같으며, 그 외에는 값이 서로 다르다.
    ○ (front + 1) mod 6은 다음에 삭제할 원소 위치를 가리킨다.
    ○ (rear + 1) mod 6은 다음에 삽입할 원소 위치를 가리킨다.
    <설 명>
    ○ 최대 ( ㉠ )개의 원소를 저장할 수 있다.
    ○ front = 5이고 rear = 3인 경우 저장된 원소 수는 ( ㉡ )개이다.
    ○ front = ( ㉢ )이고 rear = 2인 경우는 포화 상태를 의미한다.
    1
    ㉠ 6 ㉡ 5 ㉢ 1
    2
    ㉠ 6 ㉡ 4 ㉢ 1
    3
    ㉠ 5 ㉡ 5 ㉢ 3
    4
    ㉠ 5 ㉡ 4 ㉢ 3
    해설

    괄호에는 ㉠ 5, ㉡ 4, ㉢ 3이 들어간다.

    front = rear를 공백 상태 전용으로 쓰므로, 포화와 구분하려면 배열 한 칸을 비워 둔다. 따라서 크기 6 배열에 최대 5개만 저장한다.

    원소 수 = (rear − front + 6) mod 6 = (3 − 5 + 6) mod 6 = 4
    포화 조건은 (rear + 1) mod 6 = front이므로 rear = 2이면 front = 3이다.

    • ㉠ 6, ㉡ 5, ㉢ 1 조합은 최대 원소 수와 원소 수가 모두 틀렸고, front = 1, rear = 2는 원소가 1개인 상태다.
    • ㉠ 6, ㉡ 4, ㉢ 1 조합은 원소 수만 맞고, 6개를 모두 채우면 front = rear가 되어 공백과 구분되지 않는다.
    • ㉠ 5, ㉡ 5, ㉢ 3 조합은 front = 5, rear = 3일 때 원소가 위치 0, 1, 2, 3의 4개뿐이라는 점과 맞지 않는다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    18[7급 국가직 자료구조론] 16년 1회차
    다음 C 언어 함수를 이용하여 do_something(660, 735)를 수행한 결과 값은?
    unsigned int do_something(unsigned int x, unsigned int y)
    {
    while (y!=0) {
    int temp;
    temp = x % y;
    x = y;
    y = temp;
    }
    return x;
    }
    1
    5
    2
    9
    3
    15
    4
    25
    해설

    do_something(660, 735)의 결과는 15이다.

    이 함수는 나머지 연산을 반복하는 유클리드 호제법으로 두 수의 최대공약수를 구한다.

    (660, 735) → (735, 660) → (660, 75) → (75, 60) → (60, 15) → (15, 0)
    y가 0이 되는 순간의 x인 15를 반환한다.

    • 5는 660과 735의 공약수이지만 최대공약수는 아니다.
    • 9는 735의 약수가 아니므로 공약수가 될 수 없다.
    • 25는 660의 약수가 아니므로 공약수가 될 수 없다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    19[7급 국가직 자료구조론] 16년 1회차
    다음 이진 트리에 대하여 전위순회(preorder traversal), 중위순회(inorder traversal), 후위순회(postorder traversal)를 수행하였다. 3가지 순회 방법 중 2가지 이상에서 방문 순서가 동일한 노드 수는? (예를 들어, 3개의 노드 A, B, C를 갖는 이진 트리에서 전위순회 : B-A-C, 중위순회 : A-B-C, 후위순회 : A-C-B의 결과를 얻었다면, 중위순회 및 후위순회에서 노드 A에 대한 방문 순서가 동일하고 전위순회 및 중위순회에서 노드 C에 대한 방문 순서가 동일하므로, 2가지 이상에서 방문 순서가 동일한 노드 수는 2개이다)
    문제 이미지
    1
    2
    2
    3
    3
    4
    4
    5
    해설

    2가지 이상의 순회에서 방문 순서가 같은 노드는 B, D, E, G, I의 5개이다.

    세 순회 결과는 전위 A, B, D, E, H, C, F, G, I / 중위 D, B, H, E, A, F, C, G, I / 후위 D, H, E, B, F, I, G, C, A이다. 각 노드의 방문 위치를 비교하면 다음과 같다.

    노드전위중위후위
    A159
    B224
    C678
    D311
    E443
    F765
    G887
    H532
    I996

    B·E·G·I는 전위와 중위에서, D는 중위와 후위에서 위치가 같다. A, C, F, H는 세 순회의 위치가 모두 다르다.

    • 2개: 일치하는 노드 5개 중 일부만 센 값이다.
    • 3개: 전위·중위가 같은 노드만 일부 세고 D를 빠뜨린 값이다.
    • 4개: 전위·중위가 같은 B, E, G, I만 세고 중위·후위가 같은 D를 빠뜨린 값이다.

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

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    20[7급 국가직 자료구조론] 16년 1회차
    Dijkstra 알고리즘을 이용하여 다음 그래프의 정점 A에서 각 정점으로의 최단경로를 구할 때, 최단경로 발견 순서가 정점 G 바로 다음인 정점은? (단, 간선 옆의 수는 각 정점들 사이의 거리를 나타낸다)
    문제 이미지
    1
    정점 C
    2
    정점 D
    3
    정점 E
    4
    정점 F
    해설

    정점 G 바로 다음으로 최단경로가 확정되는 정점은 C이다.

    A에서 시작해 거리가 최소인 정점을 차례로 확정하면 B(4) → F(5, A–B–F) → G(9, F 경유) → C(10, B 경유) → E(11, G 경유) → D(12, C 경유) 순이다.

    • 정점 D: B 경유 13이었다가 C 확정 후 12로 갱신되며, 가장 마지막에 확정된다.
    • 정점 E: G 확정 후 거리가 11로 갱신되지만 C의 10보다 커서 C 다음에 확정된다.
    • 정점 F: A–B–F 경로 5로 G보다 먼저 확정된다.

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

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

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

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

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

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

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

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

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

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

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