본문 바로가기
CS/자료구조

자료구조 문제 풀이

by Renechoi 2023. 11. 26.

문제 : 다음 설명 중 틀린 것은 무엇인가?

1. 스택은 자료의 삽입과 삭제가 같은 변수를 통해 제어된다.
2. 스택은 객체와 객체가 저장되는 순서를 기억하는 방법에 관한 추상자료형이다.
3. 스택의 크기는 가변적이다.
4. 후위 표기식은 연산자를 피연산자의 뒤에 표기하는 방법이다.
정답 : 3번

정답 설명: 3번 "스택의 크기는 가변적이다."

  1. "스택은 자료의 삽입과 삭제가 같은 변수를 통해 제어된다." - 맞는 설명.
    • 스택에서는 데이터의 삽입과 삭제가 'top'이라는 동일한 위치(변수)에서 이루어진다. 이 'top'은 스택의 가장 위에 있는 요소를 가리킨다. 새로운 요소는 top에 추가되고(top을 증가시키고), 요소를 제거할 때는 top에서 제거된다(top을 감소시키고).
  2. "스택은 객체와 객체가 저장되는 순서를 기억하는 방법에 관한 추상자료형이다." - 맞는 설명.
    • 스택은 객체들을 저장하고, 이 객체들이 저장되는 순서를 추상적으로 관리한다. 스택의 주요 연산은 push(삽입), pop(삭제), peek(맨 위 요소 확인) 등이 있으며, 이를 통해 저장 순서를 관리한다.
  3. "스택의 크기는 가변적이다." - 틀린 설명.
    • 이 명제는 상황에 따라 다를 수 있다. 프로그래밍에서 스택은 보통 두 가지 유형으로 구현된다: 정적 스택과 동적 스택.
      • 정적 스택: 사전에 크기가 고정되어 있으며, 이 크기를 넘어서면 '스택 오버플로우'가 발생한다. 예를 들어, 크기가 10인 스택은 10개의 요소만 저장할 수 있다.
      • 동적 스택: 크기가 동적으로 변할 수 있습니다. 즉, 필요에 따라 자동으로 크기가 늘어나거나 줄어든다. 하지만 이러한 유연성에도 불구하고, 실제 메모리 한계에 의해 최대 크기에는 제한이 있다.
    • 따라서, 일반적인 컴퓨터 과학 교육에서는 스택을 고정된 크기를 가진 자료구조로 다루기 때문에, 이 보기는 오해의 소지가 있다.
  4. "후위 표기식은 연산자를 피연산자의 뒤에 표기하는 방법이다." - 맞는 설명.
    • 후위 표기식(postfix notation)에서는 연산자가 피연산자 뒤에 오는 표기법이다. 예를 들어, 일반적인 중위 표기법의 수식 "A + B"는 후위 표기식으로 "A B +"로 표현된다.

문제: 다음 전위 순회 스레드 트리의 전위 순회에서 빈칸 [ 가 ]에 알맞은 것은 무엇인가?

void preorderthr(struct TFNode *root){ 
    struct TFNode *p;
    p = root;
    while (p!=null){
        printf("%d", p->info);
        [ 가 ] 
    }
}
1. p = p->left;
2. p = p->right;
3. p=p->left->right;
4. p=p->right -> left;
정답: 1번

정답 설명: 1번 "p = p->left;"

전위 순회 (Preorder Traversal)

전위 순회는 다음 순서대로 트리를 탐색하는 방법이다:

  1. 현재 노드를 방문한다.
  2. 왼쪽 서브트리를 전위 순회한다.
  3. 오른쪽 서브트리를 전위 순회한다.

문제 해석

주어진 전위 순회 함수 preorderthr에서 p는 현재 방문하고 있는 노드를 가리키는 포인터이다. 전위 순회의 정의에 따라, 현재 노드의 정보를 출력한 후(printf("%d", p->info);)에 다음으로 방문할 노드로 p를 업데이트 해야 한다.

여기서 중요한 점은 전위 순회의 첫 번째 단계가 현재 노드의 방문이라는 것이다. 이 단계가 완료된 후, 전위 순회의 두 번째 단계는 현재 노드의 왼쪽 자식으로 이동하는 것이다. 따라서, p를 p->left로 업데이트하는 것이 전위 순회의 정의와 일치한다.

정답 선택

  1. p = p->left; - 정답
    • 이는 전위 순회의 정의에 따라 다음 노드로 왼쪽 자식을 선택하는 것이며, 현재 노드를 방문한 후 왼쪽 서브트리로 이동하는 것을 의미한다.
  2. p = p->right;
    • 이는 오른쪽 자식으로 이동하는 것.
  3. p = p->left->right;
    • 이는 왼쪽 자식의 오른쪽 자식으로 이동하는 것을 의미.
  4. p = p->right->left;
    • 이는 오른쪽 자식의 왼쪽 자식으로 이동하는 것을 의미.

문제: 다음 중 m원 탐색 트리에 대한 설명으로 틀린 것은 무엇인가? (p0, p1, ..., pn은 서브트리에 대한 포인터이고 k0, ..., kn-1은 키값이다. 또한 n<=m-1이 성립한다)

  1. 노드 vi의 키를 ki라 할 때 vi의 왼쪽 서브트리에 있는 모든 노드의 키값은 vi의 킷값보다 작다.
  2. i =0, ..., n-2 인 i에 대해 ki < ki+1를 만족한다.
  3. i=0, ..., n-1인 i에 대해 pi가 가리키는 서브트리의 모든 킷값은 ki의 킷값보다 작다.
  4. pn이 가리키는 서브트리의 모든 킷값은 kn-1의 킷값보다 크다.

정답 설명: 1번 "노드 vi의 키를 ki라 할 때 vi의 왼쪽 서브트리에 있는 모든 노드의 키값은 vi의 키값보다 작다."

m원 탐색 트리의 특성

m원 탐색 트리는 이진 탐색 트리의 일반화된 형태로, 각 노드가 최대 m-1개의 키를 가질 수 있다. 각 노드는 m개의 자식 노드를 가질 수 있으며, 각 키 값은 자식 노드들을 구분하는 경계 역할을 한다.

각 보기의 분석

  1. 노드 vi의 키를 ki라 할 때 vi의 왼쪽 서브트리에 있는 모든 노드의 키값은 vi의 키값보다 작다.
    • 이 설명은 이진 탐색 트리에 적용되는 개념이다. m원 탐색 트리에서는 하나의 노드에 여러 개의 키 값이 있으며, 각 키 값에 대한 서브트리의 범위가 다르다. 따라서 이 설명은 m원 탐색 트리에 대한 잘못된 설명이다.
  2. i = 0, ..., n-2 인 i에 대해 ki < ki+1를 만족한다.
    • 이는 올바른 설명이다. m원 탐색 트리에서 노드 내의 키 값들은 정렬된 순서로 배열되어 있어야 한다.
  3. i = 0, ..., n-1인 i에 대해 pi가 가리키는 서브트리의 모든 키값은 ki의 키값보다 작다.
    • 이 설명도 올바르다. m원 탐색 트리에서 각 서브트리는 해당 노드의 키 값에 따라 범위가 결정된다.
  4. pn이 가리키는 서브트리의 모든 키값은 kn-1의 키값보다 크다.
    • 이는 올바른 설명이다. m원 탐색 트리에서 가장 오른쪽의 서브트리는 가장 큰 키 값(kn-1)보다 큰 값들로 이루어진다.

정답 선택

따라서, m원 탐색 트리에 대한 설명으로 틀린 것은 1번이다. 이진 탐색 트리에서는 노드의 왼쪽 서브트리에 있는 모든 노드의 키 값이 그 노드의 키 값보다 작지만, m원 탐색 트리에서는 각 서브트리가 노드 내의 특정 키 값에 따라 구분되며, 왼쪽 서브트리가 반드시 노드의 키 값보다 작은 것은 아니다.

문제: 다음은 깊이 우선 탐색 (DFS) 알고리즘의 의사코드이며 해당 코드는 순환 호출을 이용하는 경우이다. 이때 다음 그림의 v7 노드에 방문하기 위해선 몇 번의 7 코드가 실행되는가?

주어진 그래프 
v1 - v2, v3 
v2 - v4, v5 
v4 - v7 
v5 - v7
v6 - v7 
v3 - v6 
void DFS(int v) {
    int w;
    extern int VISTED[];
    VISITED[v] = 1; 
    while (v에 인접한 모든 노드 w)
        if(!VISITED[w])
        DFS(w);
    }

정답 설명: 3번 "3"

깊이 우선 탐색 (DFS) 알고리즘의 작동 방식

  • 깊이 우선 탐색은 그래프의 한 정점에서 시작하여, 갈 수 있는 한 깊숙이 탐색을 진행한 다음, 더 이상 탐색할 곳이 없으면 마지막으로 방문한 정점으로 돌아와 다른 경로를 탐색하는 방법이다.
  • 순환 호출(재귀)을 사용하여, 방문하지 않은 인접 정점을 찾아 탐색을 계속 진행한다.
  • 이미 방문한 정점은 방문하지 않는다.

v7에 도달하기 위한 경로

  • DFS는 깊이 우선 탐색 방식을 사용하므로, 가능한 경로 중 하나를 따라 v7에 도달할 때까지 탐색을 진행한다.
  • v1에서 시작하는 경우, 가능한 경로는 v1 -> v2 -> v4 -> v7, v1 -> v2 -> v5 -> v7, 또는 v1 -> v3 -> v6 -> v7이다.

코드의 실행 횟수 계산

  • v1에서 시작하여 v7에 도달하는 데 필요한 최소한의 경로는 v1 -> v2 -> v4 -> v7이다.
  • 이 경로를 따라가면서, DFS 함수는 다음 순서로 실행된다:
    1. v1에서 시작 (DFS(v1))
    2. v2 방문 (DFS(v2))
    3. v4 방문 (DFS(v4))
  • v7에 도달하기 전까지 DFS 함수는 총 3번 실행된다.

정답 선택

따라서, v7 노드에 방문하기 위해서는 DFS 함수가 3번 실행되므로 정답은 3번이다.

문제 : 다음은 큐를 이용한 너비 우선 탐색(BFS) 알고리즘의 의사코드이다. 아래의 코드에서 빈칸 ㄱ, ㄴ에 들어갈 알맞은 코드는 무엇인가?

주어진 그래프 
v1 - v2, v3 
v2 - v4, v5 
v4 - v7 
v5 - v7
v6 - v7 
v3 - v6
void BFS(int v) {
    int w;
    extern struct queue *q;
    VISITED[v] = 1; 
    InitializeQueue(q);
    AddQueue(q,v);
    while ( ㄱ ) {
        v=DeleteQueue(q);
        while ( ㄴ) { 
            if(!VISITED[w]){
                AddQueue(q,w);
                VISITED[w] = 1;
             }
        }  
    }
}
1.

ㄱ: v에 인접한 모든 노드 w
ㄴ: !q_empty()

2.

ㄱ: !q_empty()
ㄴ: v에 인접한 모든 노드 w

3.

ㄱ: q_empty()
ㄴ: v에 인접한 모든 노드 w

4.

ㄱ: !VISITED[w]
ㄴ: v에 인접ㅎ한 모든 노드 w

정답 설명: 2번

너비 우선 탐색 (BFS) 알고리즘의 작동 방식

  • 너비 우선 탐색(BFS)은 그래프의 각 정점을 근접한 정점부터 차례대로 방문하는 방법이다.
  • 큐를 사용하여 이미 방문한 정점을 순서대로 관리하고, 방문하지 않은 인접 정점을 탐색한다.
  • 현재 정점의 모든 인접 정점을 큐에 추가한 후, 큐에서 다음 정점을 꺼내 탐색을 계속 진행한다.

BFS 알고리즘에서의 큐 사용

  • BFS에서는 큐를 사용하여 이미 방문한 정점들을 관리한다. 큐가 비어있지 않다면, 아직 탐색이 완료되지 않았음을 의미한다.

의사코드 분석

  • while ( ㄱ ): 큐가 비어있지 않는 동안 계속 탐색을 진행해야 한다. 따라서 ㄱ에는 !q_empty()가 들어가야 한다.
  • while ( ㄴ): 현재 정점 v에 인접한 모든 노드 w를 순회하며, 아직 방문하지 않은 정점을 큐에 추가한다. 따라서 ㄴ에는 v에 인접한 모든 노드 w가 들어가야 한다.

정답 선택

따라서, ㄱ에는 !q_empty(), ㄴ에는 v에 인접한 모든 노드 w가 들어가야 하므로 정답은 2번이다.

문제: 다음 설명 중 틀린 것은 ?

1. 컴퓨터는 주기억장치와 보조기억장치를 이용해 자료를 처리하고 저장한다.
2. 알고리즘은 컴퓨터에 일을 시키는 명령들의 모음이다.
3. 자료구조는 자료의 추상화를 통해 자료의 논리적 관계를 구조화한 것이다.
4. 정보(I)는 자료(D)를 처리해서(P) 얻어진 결과(R)다.
정답: 1

1번 설명은 "컴퓨터는 주기억장치와 보조기억장치를 이용해 자료를 처리하고 저장한다"라고 되어 있다. 이 설명에 오류가 있는데, 주요한 부분은 '자료를 처리한다'는 부분이다. 컴퓨터에서 자료의 처리는 중앙처리장치(CPU)가 담당한다. 주기억장치(예: RAM)와 보조기억장치(예: 하드 드라이브)의 역할은 자료를 저장하는 것이다. 즉, 주기억장치와 보조기억장치는 데이터를 저장하며, 처리는 CPU가 담당한다.

2번 설명인 "알고리즘은 컴퓨터에 일을 시키는 명령들의 모음"은 맞는 설명이다. 알고리즘은 특정 작업을 수행하기 위한 단계별 절차를 나타낸다. 이것은 컴퓨터 프로그래밍에서 중요한 역할을 한다.

3번 설명인 "자료구조는 자료의 추상화를 통해 자료의 논리적 관계를 구조화한 것"도 정확하다. 자료구조는 데이터를 효율적으로 저장하고 관리하는 방법을 제공한다. 예를 들어, 배열, 연결 리스트, 스택, 큐 등이 있다.

4번 설명인 "정보(I)는 자료(D)를 처리해서(P) 얻어진 결과(R)"는 정보 처리의 기본 개념을 잘 나타내고 있다. 이것은 데이터를 가공하고 분석하여 유용한 정보를 생성하는 과정을 말한다.

따라서, 1번 설명에 오류가 있으며, 그 오류는 자료의 '처리' 부분이 주기억장치와 보조기억장치의 역할이 아니라는 점이다. 처리는 CPU의 역할이다.

문제: 현재 리스트가 공백인 경우에 대한 삽입 처리를 위해 [ 가 ] 에 들어갈 코드는 무엇인가

void addNode(linkedList_h* H, int x){
    if ( H -> head == null ) { 
        H -> head = NewNode;
        return;    }
   LastNode = H -> head;
   while(LastNode -> link != null)
       LastNode = LastNode -> link;
    [ 가 ] }
1. LastNode -> data = NewNode -> data;
2. NewNode -> data = itdata;
3. NewNode -> link = LastNode;
4. LastNode -> link = NewNode;
정답: 4번

우선, 이 코드는 연결 리스트에 새 노드를 추가하는 함수다. 연결 리스트는 노드들이 연결로 이루어진 데이터 구조로, 각 노드는 데이터와 다음 노드를 가리키는 링크(또는 포인터)를 가진다.

함수 addNode는 새 노드를 리스트의 끝에 추가한다. 함수 시작 부분에서, 만약 현재 리스트가 비어있으면(즉, H -> head == null), 새 노드를 리스트의 첫 번째 노드로 설정하고 함수를 종료한다.

만약 리스트가 비어있지 않으면, LastNode 변수를 사용하여 리스트의 마지막 노드를 찾는다. LastNode -> link != null 조건을 사용하여, 리스트의 끝에 도달할 때까지 각 노드를 순회한다.

이제, LastNode는 리스트의 마지막 노드를 가리키고 있으므로, 새 노드를 리스트의 마지막에 추가해야 한다. 이를 위해서는 마지막 노드의 link 필드를 새 노드로 설정해야 한다.

선택지를 살펴보면:

  1. LastNode -> data = NewNode -> data; - 이는 데이터를 복사하는 것이지, 새 노드를 추가하는 것이 아니다.
  2. NewNode -> data = itdata; - 이는 새 노드의 데이터를 설정하는 것이지, 새 노드를 리스트에 연결하는 것이 아니다.
  3. NewNode -> link = LastNode; - 이는 새 노드의 링크를 마지막 노드로 설정하는 것으로, 순서가 반대다.
  4. LastNode -> link = NewNode; - 이는 마지막 노드의 link를 새 노드로 설정하여, 새 노드를 리스트의 끝에 추가한다.

따라서, 4번 선택지가 올바른 답이다. 이 코드 라인은 마지막 노드의 link 필드를 새 노드로 설정하여, 새 노드를 리스트의 끝에 연결한다.

문제 : 다음은 단일 연결 리스트를 정의하고 생성하는 프로그램이다. 다음 프로그램으로 생성된 헤드 노드의 그림으로 옳은 것은?

typedef struct ListNode { 
    int data[10];
    struct ListNode* link;
 } listNode;

 typedef struct {
     listNode* head;
 } linkedList_h;

 linkedList_h* createLinkedList_h(void) {
     linkedList_h* H;
    H = (linkedList_h*)malloc(sizeof(linkedList_h));
    H->head = null;
    return H;
}

*꺽쇠 괄호 = 노드를 표시

1. < null | head >
2. link -> head
3. H -> < head | null >
4. data -> < head | null>
정답 : 3번

먼저, 코드를 살펴보면 이 프로그램은 단일 연결 리스트를 정의하고 생성하는 것이다. listNode 구조체는 리스트의 각 노드를 나타내며, linkedList_h 구조체는 연결 리스트의 헤드 노드를 가리킨다.

createLinkedList_h 함수는 새로운 연결 리스트를 생성하고, 그 헤드를 null로 초기화 한 후에, 리스트의 헤드를 가리키는 포인터를 반환한다.

선택지를 분석해보자:

  1. < null | head > - 이 표현은 헤드 노드가 null을 가리키고 있음을 나타내지만, 이 구조체는 노드 자체를 나타내지 않는다.
  2. link -> head - 이 표현은 'link'가 'head'를 가리키고 있음을 나타내지만, 이는 리스트의 구조를 정확하게 반영하지 않는다.
  3. H -> < head | null > - 이 표현은 H라는 포인터가 헤드 노드를 가리키고 있고, 헤드 노드는 null을 가리키고 있음을 나타낸다. 이는 함수 createLinkedList_h가 생성한 연결 리스트의 상태를 정확하게 반영한다.
  4. data -> < head | null> - 이 표현은 'data'가 'head'를 가리키고 있음을 나타내지만, 이는 연결 리스트의 구조를 정확하게 나타내지 않는다.

따라서, 3번 선택지가 올바른 답이다. 이는 생성된 연결 리스트의 헤드 노드가 null을 가리키고 있으며, H 포인터가 이 헤드 노드를 가리키는 상태를 정확하게 나타낸다.

문제 : {1,2,3,4,6,8,9} 의 수를 최대 힙으로 나타낸 그림은 무엇인가?

1.

1-9,8
9-6,2
8-3,4

2.

9-6,8
6-,2,1
8-3,4

3.

9-1,8
1-2,6
8-3,4

4.

8-6,9
6-1,2
9-3,4

정답: 2번

최대 힙은 부모 노드가 자식 노드보다 항상 크거나 같아야 하는 완전 이진 트리다. 이 문제에서 주어진 숫자 {1,2,3,4,6,8,9}를 최대 힙으로 구성해야 한다.

각 선택지를 살펴보자:

  1. 첫 번째 선택지는 루트 노드가 1이며, 이는 최대 힙의 규칙을 위반한다. 최대 힙에서는 루트 노드가 가장 큰 값이어야 한다.
  2. 두 번째 선택지는 루트 노드가 9로, 최대 힙의 규칙을 만족한다. 또한, 모든 부모 노드는 자식 노드보다 크기 때문에, 이 구성은 최대 힙이다.
  3. 세 번째 선택지는 루트 노드가 9지만, 첫 번째 자식 노드(1)가 두 번째 자식 노드(8)보다 작다. 이는 최대 힙의 규칙을 위반한다.
  4. 네 번째 선택지는 루트 노드가 8로, 최대 힙의 규칙을 위반한다. 최대 힙에서는 루트 노드가 가장 큰 값이어야 한다.

따라서, 2번 선택지가 올바른 답이다. 이 구성은 최대 힙의 모든 조건을 만족한다: 루트 노드(9)가 가장 크고, 모든 부모 노드가 자신의 자식 노드보다 크거나 같다.

문제: 다음은 큐를 이용한 너비 우선 탐색 알고리즘(BFS)의 프로그램이다. 다음 프로그램 안에 [가], [나]에 들어갈 코드로 옳은 것은?

void BFS(int v){
    int w;
    extern struct queue *q;
    VISITED[v] = 1;
    Initialize Queue(q);
    AddQueue(q,v);
    while(!q_empty()){
        v = DeleteQueue(q);
        while (v에 인접한 모든 노드 w){
            if ( [가] ) {
                [나]
                VISITED[w] = 1;
            }
        }
    }
}
[가]            [나]
  1. !VISITED[v] AddQueue(q,w);
  2. !VISITED[v] DeleteQueue(q,w);
  3. !VISITED[w] DeleteQueue(q,w);
  4. !VISITED[w] ADDQueue(q,w);

너비 우선 탐색(BFS, Breadth-First Search)는 큐(queue)를 이용하여 그래프 또는 트리를 탐색하는 알고리즘이다. 이 알고리즘은 방문하지 않은 인접 노드를 큐에 추가하고, 방문한 노드를 표시하는 방식으로 작동한다.

이 프로그램에서 [가]와 [나]에 들어갈 코드를 살펴보자:

  1. !VISITED[v] AddQueue(q,w); - 이 코드는 현재 노드 v가 방문되지 않았을 경우 w를 큐에 추가하는 것을 의미한다. 그러나 BFS에서는 현재 노드 v의 방문 여부가 아니라 인접 노드 w의 방문 여부를 확인해야 한다.
  2. !VISITED[v] DeleteQueue(q,w); - 이 코드는 현재 노드 v가 방문되지 않았을 경우 w를 큐에서 삭제하는 것을 의미한다. 이것은 BFS의 원리에 어긋난다. BFS에서는 방문하지 않은 노드를 큐에서 삭제하는 것이 아니라 추가해야 한다.
  3. !VISITED[w] DeleteQueue(q,w); - 이 코드는 인접 노드 w가 방문되지 않았을 경우 w를 큐에서 삭제하는 것을 의미한다. 이것도 BFS의 원리에 어긋난다.
  4. !VISITED[w] ADDQueue(q,w); - 이 코드는 인접 노드 w가 방문되지 않았을 경우 w를 큐에 추가하는 것을 의미한다. 이것은 BFS 알고리즘의 올바른 작동 방식이다. 인접 노드가 아직 방문되지 않았다면, 그 노드를 큐에 추가하고, 방문했음을 표시한다.

따라서, 4번이 올바른 답이다.

문제: 다음 그래프는 사이클이 있는 방향 그래프이다. 그래프와 정점 2에서 출발하여 정점 4에서 끝나는 경로에 대한 표이다. 다음 중 1,3,4 번이 틀린 이유에 대해 설명하라.

path1: <2,4> 
path2: <2,3>, <3,4> 
path3: <2,1>, <1,3>, <3,4> 
path4: <2,1>, <1,2>, <2,4>
path5: <2,3>, <3,1>, <1,2>, <2,4>
path6: <2,2>, <2,4>
1. 무방향 그래프라 해도 경로 개수는 같다.
2. path2 경로는 <2,3>, <3,4>이다.
3. 경로중 path4, path5, path6은 단순 경로이다.
4. path1을 제외한 모든 경로가 기본 경로이다.

  1. "무방향 그래프라 해도 경로 개수는 같다." - 이 설명은 틀렸다. 무방향 그래프와 방향 그래프에서의 경로 개수는 다를 수 있다. 무방향 그래프에서는 어떤 두 정점 간에 양방향으로 이동이 가능하지만, 방향 그래프에서는 각 간선의 방향을 따라야 한다. 따라서, 방향 그래프에서 가능한 경로가 무방향 그래프에서는 불가능할 수 있다.

  2. "경로 중 path4, path5, path6은 단순 경로이다." - 이 설명은 틀렸다. 단순 경로는 같은 정점을 두 번 이상 거치지 않는 경로를 의미한다. path4는 2번과 1번 정점을 반복해서 거치고, path5도 2번, 3번, 1번 정점을 여러 번 거친다. path6은 2번 정점을 두 번 거친다. 따라서 이 세 경로는 단순 경로가 아니다.

  3. "path1을 제외한 모든 경로가 기본 경로이다." - 이 설명도 틀렸다. 기본 경로(basic path)는 그래프 내에서 반복되는 부분 없이 시작 정점에서 종료 정점까지 이어지는 경로를 의미한다. path4, path5, path6는 같은 정점을 반복하여 거치므로 기본 경로가 아니다.

문제: 다음은 힙(max heap)에서 데이터를 삽입하는 알고리즘이다. [가]에 들어갈 알맞은 코드는 무엇인가?

int inserHeap(HeapType *h, int item){
    int i;
    i = ++(h->heap_size);

    while (i!=1) && (item < h->heap[1/2])){
        [가]
        i/=2;
    }
    h->heap[i] = item;
}
  1. h->heap[i] = h->heap[i/2];
  2. h->heap[i] = h->heap[i+1];
  3. h->heap[i/2] = h->heap[i];
  4. h->heap[i] = temp;

정답: 1

힙은 완전 이진 트리를 기반으로 하는 데이터 구조로, 각 노드는 자식 노드보다 크거나 같은 값을 가져야 한다(최대 힙의 경우). 여기서는 최대 힙에서 데이터를 삽입하는 과정을 다루고 있다.

코드를 살펴보면, i = ++(h->heap_size);는 힙의 크기를 하나 증가시키고, 새로운 요소가 들어갈 위치를 i에 할당한다. 삽입하려는 요소 item이 부모 노드의 값보다 큰 경우, 힙의 조건에 따라 부모 노드와 위치를 바꿔야 한다. 이를 위해 부모 노드의 인덱스는 i/2이다.

이제 [가]에 들어갈 코드를 살펴보자:

  1. h->heap[i] = h->heap[i/2]; - 이 코드는 현재 노드(i)의 위치에 부모 노드(i/2)의 값을 할당한다. 이는 삽입할 값이 부모 노드의 값보다 클 때, 부모 노드를 아래로 내리는 것을 의미한다.
  2. h->heap[i] = h->heap[i+1]; - 이 코드는 현재 노드의 값을 다음 노드의 값으로 대체한다. 이것은 힙의 삽입 과정과 관련이 없다.
  3. h->heap[i/2] = h->heap[i]; - 이 코드는 부모 노드의 위치에 현재 노드의 값을 할당한다. 이것은 부모와 자식의 위치를 바꾸는 것이 아니라 단순히 값만 복사한다.
  4. h->heap[i] = temp; - 이 코드는 임시 변수 temp를 사용하지만, temp가 선언되지 않았고, 이 문맥에서는 의미가 명확하지 않다.

따라서, 1번이 정답이다. 이 코드는 삽입하려는 요소가 부모 노드보다 클 때까지, 부모 노드의 값을 아래로 내리며 삽입 위치를 조정하는 과정을 나타낸다.

문제: 그래프에 대한 설명으로 옳은 것은

1. 사이클이 없는 그래프를 트리라 한다.
2. 두 정점이 사이클로 연결되었을 때, 두 정점이 인접한다고 정의한다.
3. 시작점과 끝점이 같은 경로를 루프라고 한다.
4. 한 정점에서 출발하여 자신으로 연결하는 간선을 사이클이라고 한다.

정답: 1번

  1. "사이클이 없는 그래프를 트리라 한다." - 이 설명은 맞다. 트리는 사이클이 없는 연결 그래프로 정의된다. 트리는 하나의 루트 노드를 가지며, 모든 자식 노드는 단 하나의 부모 노드와 연결된다. 트리는 계층적인 구조를 갖고 있어, 어떤 두 노드 간에도 정확히 하나의 경로만 존재한다.

  2. "두 정점이 사이클로 연결되었을 때, 두 정점이 인접한다고 정의한다." - 이 설명은 잘못되었다. 인접한 두 정점이란, 직접 연결된 두 정점을 의미한다. 사이클이 있는 경우, 그 사이클에 속한 모든 정점이 서로 인접해 있는 것은 아니다.

  3. "시작점과 끝점이 같은 경로를 루프라고 한다." - 이 설명도 잘못되었다. 시작점과 끝점이 같은 경로를 일반적으로 사이클이라고 한다. 루프(loop)는 특정 정점에서 출발하여 같은 정점으로 돌아오는 경로를 의미한다.

  4. "한 정점에서 출발하여 자신으로 연결하는 간선을 사이클이라고 한다." - 이 설명도 잘못되었다. 한 정점에서 출발하여 자신으로 돌아오는 간선을 '루프' 또는 '자기 루프'라고 한다. 사이클은 그래프 내에서 한 노드로부터 출발하여 다른 노드들을 거쳐 처음 노드로 돌아오는 경로를 의미한다.

따라서, 1번 선택지가 정답이다. 트리는 사이클이 없는 연결 그래프로, 트리의 모든 노드는 다른 노드로부터 정확히 하나의 경로를 통해서만 접근할 수 있다.

문제: 다음 중 B 트리에 대한 설명으로 옳은 것은?

  1. 트리의 루트는 최소한 3개의 서브트리를 갖는다.
  2. 트리의 모든 잎 노드는 같은 레벨에 있다.
  3. 루트가 가장 작은 값을 갖고 부모는 자식보다 작은 값을 갖는다.
  4. 루트와 잎 노드를 제외한 트리의 각 노드는 최소 [m/3]개의 서브트리를 갖는다.

정답: 2번

B트리는 균형 잡힌 트리 구조로, 효율적인 검색, 삽입, 삭제 연산을 위해 사용된다.

  1. "트리의 루트는 최소한 3개의 서브트리를 갖는다." - 이 설명은 잘못되었다. B트리의 루트 노드가 반드시 3개 이상의 서브트리를 가져야 하는 것은 아니다. B트리의 루트는 최소 2개의 자식을 가질 수 있다(m이 트리의 차수일 때, 루트 노드는 최소 2개에서 최대 m개의 자식을 가질 수 있다).

  2. "트리의 모든 잎 노드는 같은 레벨에 있다." - 이 설명은 맞다. B트리의 모든 잎(리프) 노드는 같은 레벨에 위치한다. 이는 B트리가 항상 균형을 유지하는 특징 중 하나로, 모든 리프 노드가 같은 깊이를 갖는다.

  3. "루트가 가장 작은 값을 갖고 부모는 자식보다 작은 값을 갖는다." - 이 설명은 잘못되었다. B트리에서는 루트가 가장 작은 값을 갖지 않으며, 부모 노드의 값이 자식 노드의 값보다 반드시 작을 필요도 없다. B트리에서는 노드 내의 키가 정렬되어 있으며, 부모 노드의 키는 자식 노드들의 키 범위를 분할한다.

  4. "루트와 잎 노드를 제외한 트리의 각 노드는 최소 [m/3]개의 서브트리를 갖는다." - 이 설명도 잘못되었다. B트리에서 노드의 최소 자식 수는 트리의 차수(m)에 따라 달라진다. 일반적으로, 각 내부 노드는 최소 m/2개의 자식을 가져야 한다.

따라서, 정답은 2번이다. B트리의 중요한 특성 중 하나는 모든 리프 노드가 같은 레벨에 있다는 것이며, 이로 인해 검색, 삽입, 삭제 작업이 균형 잡힌 방식으로 이루어진다.

문제: 다음 프로그램은 이중 연결 리스트에 새 노드를 삽입하는 연산이다. 프로그램 흐름상 다음 빈칸 ㄱ에 들어갈 알맞은 코드는 무엇인가

void addDNode(linkedList_h* listNode* prevNode, int x){
    // newNode를 prevnode 오른쪽에 삽입 
    listNode* NewNode;
    NewNode = (listNode*)malloc(sizeof(listNode));
    NewNode->Link = null;
    NewNode->data = x;
    NewNode->Rlink = null;

    NewNode->Rlink = prevNode->Rlink;
    prevNode->Rlink= NewNode;
    NewNode->Llink = prevNode;
    [ ㄱ ] 
}
  1. NewNode -> Rlink -> Llink = NewNode;
  2. prevNode -> Llink -> Rlink = NewNode;
  3. prevNode -> Rlink -> Llink = NewNode;
  4. NewNode -> Rlink -> Llink = prevNode;

정답 : 1 번

이중 연결 리스트에서 새 노드를 삽입하는 과정을 살펴보면, 각 노드는 두 개의 링크(왼쪽 링크와 오른쪽 링크)를 가진다. 새 노드(NewNode)를 특정 노드(prevNode)의 오른쪽에 삽입할 때, 다음과 같은 순서로 연결을 조정해야 한다:

  1. NewNode의 오른쪽 링크(Rlink)를 prevNode의 오른쪽 링크로 설정한다.
  2. prevNode의 오른쪽 링크를 NewNode로 설정한다.
  3. NewNode의 왼쪽 링크(Llink)를 prevNode로 설정한다.

이제 빈칸 [ ㄱ ]에 들어갈 코드를 확인해야 한다. 여기서는 NewNode가 삽입된 후, NewNode의 오른쪽 노드의 왼쪽 링크를 NewNode로 설정해야 한다.

선택지를 살펴보면:

  1. NewNode -> Rlink -> Llink = NewNode; - 이 코드는 NewNode의 오른쪽 노드의 왼쪽 링크를 NewNode로 설정한다. 이는 삽입된 NewNode와 그 오른쪽 노드 간의 연결을 올바르게 설정하는 것으로, 정답이다.
  2. prevNode -> Llink -> Rlink = NewNode; - 이 코드는 prevNode의 왼쪽 노드의 오른쪽 링크를 NewNode로 설정하는 것으로, 이 문맥에서는 맞지 않다.
  3. prevNode -> Rlink -> Llink = NewNode; - 이 코드는 prevNode의 오른쪽 노드의 왼쪽 링크를 NewNode로 설정하는 것으로, 현재의 문맥에서 의미가 없다.
  4. NewNode -> Rlink -> Llink = prevNode; - 이 코드는 NewNode의 오른쪽 노드의 왼쪽 링크를 prevNode로 설정하는 것으로, 이는 삽입 과정에서 필요한 연결이 아니다.

따라서, 정답은 1번이다.

문제: 다음은 깊이 우선 탐색 (DFS) 알고리즘의 슈도코드이며 해당 코드는 순환 호출을 이용하는 경우이다. 다음 알고리즘에서 ㄱ과 ㄴ에 들어갈 알맞은 명령어는 ?

void DFS(int v) { 
    int w;
    extern int VISITED[];
    [ ㄱ ] 
    while (v에 인접한 모든 노드 w) 
        [ ㄴ ] 
        DFS(w);
    }
  1. ㄱ: VISITED[v] = 0;
    ㄴ: if(!q_empty())
  2. ㄱ: VISITED[v] = 0;
    ㄴ: if(VISITED[w])
  3. ㄱ: VISITED[v] = 1;
    ㄴ: if(!VISITED[w])
  4. ㄱ: VISITED[v] = 1;
    ㄴ: if(!VISITED[v])

정답: 3번

순환 호출을 이용한 깊이 우선 탐색(DFS, Depth-First Search)은 방문하지 않은 인접 노드를 찾아 탐색을 계속 진행하고, 방문한 노드를 표시하는 방식으로 작동한다.

  1. ㄱ: VISITED[v] = 0; - 이 명령어는 노드 v를 방문하지 않았다고 표시한다. 그러나 DFS에서는 노드를 방문할 때 방문했다고 표시해야 하므로 이 명령어는 적절하지 않다.
    ㄴ: if(!q_empty()) - 이 조건문은 큐가 비어 있지 않을 때만 참이 되는데, DFS에서 큐를 사용하지 않으므로 이 명령어는 적절하지 않다.

  2. ㄱ: VISITED[v] = 0; - 이 명령어는 노드 v를 방문하지 않았다고 표시한다. DFS에서는 노드를 방문할 때 방문했다고 표시해야 하므로 적절하지 않다.
    ㄴ: if(VISITED[w]) - 이 조건문은 노드 w가 이미 방문되었을 때만 참이 되므로, DFS의 원리와 맞지 않다.

  3. ㄱ: VISITED[v] = 1; - 이 명령어는 노드 v를 방문했다고 표시한다. DFS에서는 노드를 방문할 때 방문했다고 표시해야 하므로 적절하다.
    ㄴ: if(!VISITED[w]) - 이 조건문은 노드 w가 아직 방문되지 않았을 때만 참이 되며, 이는 DFS의 원리와 일치한다.

  4. ㄱ: VISITED[v] = 1; - 이 명령어는 노드 v를 방문했다고 표시한다. 이 부분은 적절하다.
    ㄴ: if(!VISITED[v]) - 이 조건문은 노드 v가 방문되지 않았을 때만 참이 되는데, 이는 논리적으로 모순된다.

따라서, 정답은 3번이다. 이 선택지는 노드를 방문할 때 방문했다고 표시하고, 아직 방문되지 않은 인접 노드를 찾아 계속 탐색하는 DFS의 원리와 부합한다.

문제 : 다음 프로그램은 최소 힙에서 데이터를 삽입하는 프로그램이다. 아래 그림은 최소 힙에서 새 노드를 삽입하기 위해 마지막 노드에 새 노드인 '7'이 위치한 모습이다. 새 노드인 '7'이 삽입한 후 완전한 최소 힙이 되도록 하려면 [가] 부분이 몇 번 이루어져야 하는가?

최소힙 구성
5-15,10
15-20,16
20-25,30
16-17,18
10-12,19
12-23,7
int insertHeap(HeapType *h, int item){
    int i;
    i = ++(h->heap_szie);

    while ( i !=1) && (item < h->heap[i/2])){
[가] >>        h->Heap[i] = h->heap[i/2];
[가] >>      i/=2;
    }
    h->Heap[i]=item;
 }
  1. 0
  2. 1
  3. 2
  4. 3

정답 : 3

최소 힙은 부모 노드가 자식 노드보다 항상 작거나 같아야 하는 완전 이진 트리다. 새 노드를 삽입할 때, 최소 힙의 속성을 유지하면서 적절한 위치를 찾기 위해 부모 노드와 비교하여 필요한 경우 위치를 교환하는 과정을 반복한다.

주어진 힙 구성에서 새 노드 '7'이 마지막에 삽입되었다. 이제 '7'이 최소 힙의 속성을 만족할 위치로 이동해야 한다.

  1. 첫 번째 비교: '7'은 부모 노드인 '12'보다 작다. 따라서 '7'과 '12'의 위치를 교환한다.
  2. 두 번째 비교: 이제 '7'은 '10'의 자식이 되었다. '7'은 '10'보다 작으므로, '7'과 '10'의 위치를 교환한다.
  3. 세 번째 비교: 이제 '7'은 '5'의 자식이 되었다. '7'은 '5'보다 크므로, 더 이상의 위치 교환은 필요하지 않다.

따라서, 새 노드 '7'을 올바른 위치로 이동시키기 위해 [가] 부분이 총 2번 실행되어야 한다. '7'이 '12'와 위치를 바꾸고, 다시 '10'과 위치를 바꾸는 과정을 거친다.

따라서, 정답은 3번이다.

반응형
저작자표시 비영리 변경금지

'CS > 자료구조' 카테고리의 다른 글

자료구조 슈도 코드 및 개념 요약 정리 : 트리, 이진 트리 (바이너리 서치 트리), 스레드 트리, AVL/2-3트리, B 트리, 그래프, 프림/크루스칼/솔린 알고리즘  (2) 2023.12.02
자료구조 슈도 코드 및 개념 요약 정리 : 배열, 스택, 큐, 연결 리스트, 이중 연결 리스트, 원형 연결 리스트  (0) 2023.12.02
멀티웨이 탐색 트리 2 : 2-3 트리, 2-3-4 트리, 레드 블랙 트리  (1) 2023.11.26
멀티웨이 탐색 트리 1 - m원 탐색 트리, B 트리, B*트리, B+ 트리  (2) 2023.11.26
이진 탐색 트리Bs) - Splay, Avl, BB 트리  (1) 2023.11.25

관련글

티스토리툴바