방송대 방통대 자료구조 4~6강 - 큐와 연결 리스트 - 요약 노트 시험족보 예상문제 - 올에이클래스

자료구조 4~6강 - 큐와 연결 리스트

4강부터 6강까지는 먼저 들어온 자료를 먼저 처리하는 큐와, 포인터로 노드를 연결하는 연결 리스트를 학습한다. 선형 큐와 원형 큐의 차이, 배열과 연결 리스트의 차이, 단순·원형·이중 연결 리스트의 구조 및 삽입·삭제 과정을 하나의 흐름으로 정리한다.

제1장 4강 큐의 개념과 추상 자료형

1. 큐의 의미

큐(queue)는 한쪽 끝에서는 삽입만 발생하고 다른 쪽 끝에서는 삭제만 발생하는 유한 순서 리스트이다. 택시 승강장의 대기 행렬, 병원의 접수대, 은행의 예금 인출기, 백화점 계산대의 상품처럼 먼저 도착한 대상이 먼저 처리되는 상황을 모델링한다. 이 처리 원칙을 선입선출(First-In First-Out, FIFO) 또는 선착순 서비스(First-Come First-Serve, FCFS)라고 한다.

큐에서 삭제가 이루어지는 쪽을 앞(front), 삽입이 이루어지는 쪽을 뒤(rear)라고 한다. 자료 A, B, C가 차례로 들어 있으면 다음 삽입 자료 D는 rear 쪽에 추가되고, 삭제할 때는 front 쪽의 A가 가장 먼저 제거된다. 스택이 같은 끝에서 삽입과 삭제를 수행하는 후입선출 구조인 것과 달리 큐는 서로 다른 두 끝을 사용한다.

시험 핵심: 큐는 FIFO 구조이며 front는 삭제 위치, rear는 삽입 위치를 나타낸다.

2. 큐의 추상 자료형

큐 객체는 0개 이상의 원소를 갖는 유한 순서 리스트로 정의할 수 있다. 추상 자료형은 실제 저장 방법과 관계없이 큐가 제공해야 할 연산을 명세한다. 강의록의 기본 연산은 생성, 삽입, 삭제, 공백 검사, 만원 검사로 구성된다.

연산	기능
Create_q(maxQueueSize)	주어진 최대 크기의 빈 큐를 생성한다.
Add_q(queue, item)	큐가 가득 차지 않았다면 rear 위치에 item을 삽입한다.
Delete_q(queue)	큐가 비어 있지 않다면 front 위치의 원소를 삭제하고 반환한다.
IsEmpty_q(queue)	rear와 front의 관계를 검사하여 빈 상태이면 TRUE를 반환한다.
IsFull_q(queue, maxQueueSize)	현재 원소 수가 최대 크기와 같으면 TRUE를 반환한다.

연산 실행 예를 보면 빈 큐에 A, B, C를 차례로 삽입한 뒤 세 번 삭제하면 A, B, C 순서로 제거되어 다시 빈 큐가 된다. 이후 D를 삽입하면 큐에는 D가 남는다. 이 순서는 큐의 논리적 순서가 삽입 시점에 의해 결정된다는 점을 보여 준다.

제2장 4강 큐의 응용과 배열 구현

1. CPU 스케줄링에서의 큐

큐는 운영체제의 준비 큐(Ready Queue)에서 CPU를 기다리는 작업을 관리하는 데 사용된다. FCFS 스케줄링은 준비 큐에 먼저 도착한 작업에 CPU를 할당하고 그 작업이 완료될 때까지 CPU를 사용하게 한다. 큐의 도착 순서가 곧 처리 순서가 되는 전형적인 FIFO 응용이다.

라운드 로빈(Round Robin, RR) 스케줄링은 대화형 시스템에 적합하다. 작업이 도착한 순서대로 CPU를 받지만, 일정한 시간 할당량 또는 시간 간격 안에서만 실행된다. 시간이 끝났는데 작업이 완료되지 않았다면 준비 큐의 뒤로 이동하여 다시 차례를 기다린다. 따라서 모든 작업에 일정 크기의 CPU 시간을 순환적으로 제공할 수 있다.

2. 배열을 이용한 선형 큐

배열로 큐를 구현할 때는 고정 크기의 배열과 front, rear 변수를 사용한다. 강의록의 예에서는 빈 상태를 나타내기 위해 front와 rear를 -1로 초기화한다. 삽입하면 rear를 하나 증가시킨 뒤 그 위치에 원소를 저장하고, 삭제하면 front를 하나 증가시킨 뒤 해당 위치의 원소를 반환한다.

#define QUEUE_SIZE 5
typedef int element;
element queue[QUEUE_SIZE];
int front = -1;
int rear = -1;

선형 배열 큐에서 삽입 연산은 queue[++rear] = item과 같이 rear를 오른쪽으로 이동시킨다. 삭제 연산은 return queue[++front]와 같이 front를 오른쪽으로 이동시킨다. 공백 상태는 front와 rear가 같은 상태로 판단할 수 있고, 배열 끝까지 rear가 이동하면 더 이상 삽입할 수 없다고 판단한다.

선형 배열 큐의 한계: 앞쪽 원소가 삭제되어 빈 공간이 생겨도 rear가 배열의 마지막 위치에 도달하면 그 공간을 다시 사용하지 못할 수 있다. 이 문제를 해결하기 위해 원형 큐가 제안된다.

제3장 4강 원형 큐

1. 원형 큐의 필요성

원형 큐는 배열의 마지막 위치와 첫 위치를 논리적으로 연결하여 큐의 양 끝을 원으로 만든 구조이다. 선형 큐에서 삭제로 생긴 앞부분의 빈 공간을 다시 사용하기 위해 나머지 연산을 활용한다. 인덱스가 마지막 위치를 지나면 0으로 돌아가므로 front와 rear가 배열 안을 순환한다.

크기가 n인 배열에서 다음 위치는 일반적으로 (현재 위치 + 1) % n으로 계산한다. 예를 들어 크기가 5일 때 위치 4의 다음은 (4 + 1) % 5 = 0이다. 이 순환 규칙 덕분에 물리적으로 떨어진 배열의 끝과 시작을 하나의 연속 공간처럼 사용할 수 있다.

2. 빈 상태와 만원 상태

원형 큐에서 front와 rear가 같으면 빈 상태로 판단한다. 그러나 삽입을 계속하여 rear가 front를 따라잡는 상황도 같은 모양이 될 수 있으므로, 보통 한 칸을 비워 두어 두 상태를 구분한다. 이 방식에서는 (rear + 1) % n == front이면 만원 상태이다. 따라서 크기가 n인 배열에 실제로 저장할 수 있는 원소 수는 n-1개이다.

상태	판정 조건	의미
빈 상태	front == rear	삭제할 원소가 없다.
만원 상태	(rear + 1) % n == front	구분용 한 칸을 제외한 모든 공간이 사용되었다.
삽입 위치 이동	rear = (rear + 1) % n	rear를 순환 이동한 뒤 원소를 저장한다.
삭제 위치 이동	front = (front + 1) % n	front를 순환 이동한 뒤 원소를 꺼낸다.

원형 큐는 연결된 부분의 데이터 공간을 계속 재사용한다. 예를 들어 뒤쪽까지 삽입한 뒤 앞쪽 원소를 삭제하면 rear가 0 쪽으로 되돌아가 비어 있는 위치에 새 원소를 넣을 수 있다. 배열을 이동시키지 않고도 공간 활용 문제를 해결한다는 점이 핵심이다.

제4장 5강 리스트와 배열 기반 구현

1. 리스트의 개념

리스트(list)는 원소들 사이에 순서가 지켜지며 유지되는 자료구조이다. 리스트의 순서는 데이터가 메모리에 저장된 물리적 위치와 관계없이 사람이 머릿속에서 인식하는 논리적인 순서, 즉 원소들 사이에 나타나는 의미적인 순서를 뜻한다. 예를 들어 역사적 사건을 연도 순서로 나열했다면 그 논리적 순서가 리스트의 순서가 된다.

배열도 원소가 연속된 메모리 공간에 저장되므로 물리적 순서를 갖는다. 그러나 리스트가 요구하는 논리적 순서는 저장 위치와 반드시 일치할 필요가 없다. 배열을 이용한 리스트에서는 논리적 순서가 배열 인덱스의 물리적 순서와 일치하도록 배치하지만, 연결 리스트에서는 포인터가 다음 원소를 지정하여 물리적 위치와 무관하게 논리적 순서를 만든다.

구분	배열을 이용한 리스트	포인터를 이용한 연결 리스트
저장 위치	연속된 메모리 공간	노드가 메모리 여러 위치에 분산될 수 있음
순서 표현	인덱스와 물리적 배치	링크 필드의 주소
중간 삽입·삭제	뒤 원소를 밀거나 앞으로 당겨야 함	관련 링크를 바꾸어 처리
크기	초기 선언 크기에 제약	필요할 때 노드를 동적으로 생성

2. 배열 리스트의 삽입과 삭제

배열 리스트의 중간에 원소를 삽입하려면 삽입 위치 이후의 원소를 뒤로 한 칸씩 이동하여 빈 자리를 만든다. 배열 공간이 부족하면 더 큰 배열을 새로 확보해야 하므로 메모리 낭비가 생길 수 있다. 삭제할 때는 빈자리를 없애기 위해 뒤쪽 원소를 앞으로 한 칸씩 이동한다.

따라서 원소 수가 많을수록 이동에 필요한 실행 시간이 증가한다. 프로그램 실행 중 메모리 할당이 추가로 필요한 경우도 생기며, 삽입과 삭제가 빈번한 실제 서비스 환경에서는 배열 기반 구현이 비효율적일 수 있다.

제5장 5강 포인터와 단순 연결 리스트

1. 노드와 포인터

연결 리스트의 노드(node)는 리스트 원소값을 저장하는 데이터 필드와 다음 원소를 가리키는 링크 필드로 구성된다. 링크에는 다음 노드의 메모리 주소가 저장된다. 헤드(head)는 첫 노드를 가리키며, 마지막 노드의 링크는 더 이상 다음 원소가 없음을 나타내는 NULL을 갖는다.

typedef struct ListNode {
    int data;
    struct ListNode *link;
} ListNode;

typedef struct {
    ListNode *head;
} linkedList_h;

포인터는 메모리의 저장 위치에 대한 주소를 가리키는 데이터형이다. 동적 노드는 malloc으로 필요한 크기의 메모리를 할당하고, 사용이 끝난 노드는 free로 반환한다. 단항 연산자 *는 포인터가 가리키는 값을 다루는 데 사용되며, 구조체 포인터의 멤버는 -> 연산자로 접근한다.

2. 연결 리스트 생성과 뒤 삽입

리스트 생성 시 헤드 구조를 동적으로 할당한 뒤 H->head = NULL로 초기화한다. 새 노드를 만들 때는 메모리를 할당하고 데이터 값을 저장한 뒤 링크를 NULL로 둔다. 리스트가 비어 있으면 head가 새 노드를 직접 가리키게 한다. 비어 있지 않다면 LastNode가 마지막 노드까지 이동한 후 마지막 링크가 새 노드를 가리키게 한다.

3. 특정 위치 삽입

prevNode 뒤에 NewNode를 삽입하려면 링크 변경 순서가 중요하다. 먼저 NewNode->link = prevNode->link로 새 노드가 원래 후속 노드를 가리키게 한다. 그다음 prevNode->link = NewNode로 선행 노드가 새 노드를 가리키게 한다. 첫 단계보다 먼저 prevNode의 링크를 바꾸면 기존 후속 노드의 주소를 잃어 리스트가 끊길 수 있다.

4. 노드 삭제

단순 연결 리스트에서 delNode를 삭제하려면 prevNode의 링크를 delNode->link로 바꾸어 삭제 대상의 후속 노드를 직접 가리키게 한다. 그런 다음 free(delNode)로 삭제 노드의 메모리를 반환한다. 링크만 바꾸고 메모리를 반환하지 않으면 더 이상 접근할 수 없는 공간이 남는 메모리 누수가 발생한다.

링크 연산 핵심: 삽입은 새 노드가 후속 노드를 먼저 가리킨 뒤 선행 노드가 새 노드를 가리킨다. 삭제는 선행 노드가 삭제 노드의 후속 노드를 가리키게 한 뒤 삭제 노드를 반환한다.

제6장 5강 연결 리스트의 주요 연산

1. 리스트 뒤에 노드 삽입

새 노드를 리스트 뒤에 삽입하는 연산은 먼저 NewNode를 생성하고 데이터와 NULL 링크를 저장한다. 공백 리스트라면 head를 NewNode로 바꾸고 종료한다. 원소가 있다면 LastNode를 head부터 시작하여 LastNode->link != NULL인 동안 이동시킨 뒤, 마지막 노드의 링크가 NewNode를 가리키게 한다.

2. 특정 노드 검색과 삭제

특정 데이터 값을 찾으려면 prevNode와 delNode를 사용한다. prevNode는 삭제 후보의 선행 노드를, delNode는 현재 검사 중인 노드를 가리킨다. delNode의 데이터가 목표값과 같으면 삭제 함수를 호출하고, 다르면 두 포인터를 한 노드씩 전진시킨다. delNode가 NULL이 될 때까지 찾지 못했다면 검색은 실패한다.

3. 마지막 노드 삭제

공백 리스트라면 연산을 종료한다. 노드가 하나뿐이면 그 노드를 반환하고 head를 NULL로 바꾼다. 여러 노드가 있으면 prevNode와 delNode를 이동하여 delNode가 마지막 노드를 가리키게 만든다. 마지막 노드를 반환한 뒤 prevNode->link = NULL로 새 마지막 노드의 링크를 정리한다.

경계 조건: 연결 리스트 연산은 공백 리스트, 노드가 하나인 리스트, 첫 노드를 처리하는 경우를 별도로 확인해야 한다. 일반적인 중간 노드 처리만 구현하면 head가 잘못되거나 NULL 포인터를 참조할 수 있다.

제7장 6강 연결 리스트의 변형

1. 단순 연결 리스트의 한계

단순 연결 리스트는 노드마다 링크가 하나이고 각 링크가 후행 노드만 가리킨다. 특정 노드의 후행 노드는 쉽게 접근할 수 있지만, 선행 노드를 찾으려면 head부터 다시 탐색해야 한다. 이 한계를 보완하기 위해 원형 연결 리스트와 이중 연결 리스트가 사용된다.

2. 연결 리스트 변형의 비교

구조	링크 구성	마지막 연결	이동 방향
단순 연결 리스트	link 1개	마지막 link가 NULL	후행 방향
원형 연결 리스트	link 1개	마지막 link가 첫 노드	후행 방향으로 순환
이중 연결 리스트	Llink와 Rlink 2개	구조에 따라 끝을 연결 가능	선행·후행 양방향
이중 원형 연결 리스트	Llink와 Rlink 2개	양 끝이 원형으로 연결	양방향 순환

제8장 6강 원형 연결 리스트

1. 원형 연결 리스트의 구조

단순 연결 리스트의 마지막 노드는 링크값이 NULL이다. 원형 연결 리스트는 이 마지막 링크를 활용하여 첫 노드를 가리키게 한다. 그 결과 한 방향으로 모든 노드가 계속 연결되고, 어느 노드에서 출발해도 링크를 따라가면 모든 노드에 접근할 수 있다.

2. 첫 노드 삽입과 뒤 삽입

공백 원형 리스트에 첫 노드를 삽입하면 head가 NewNode를 가리키고 NewNode의 링크도 자기 자신을 가리켜 원을 만든다. 기존 원소가 있는 리스트의 앞에 삽입하려면 마지막 노드를 찾고, NewNode가 기존 첫 노드를 가리키게 한 다음 마지막 노드가 NewNode를 가리키게 하며 head를 NewNode로 변경한다.

리스트의 뒤에 삽입할 때는 새 노드가 첫 노드를 가리키게 하고, 기존 마지막 노드가 새 노드를 가리키게 한다. head는 그대로 유지된다. 중간 삽입은 단순 연결 리스트와 마찬가지로 NewNode가 prevNode의 후속 노드를 먼저 가리키고, prevNode가 NewNode를 가리키게 한다.

3. 원형 리스트 탐색과 삭제

원형 리스트에는 NULL이 없으므로 단순 연결 리스트의 while(node != NULL) 조건을 그대로 사용할 수 없다. 첫 노드에서 시작한 tempNode가 다시 head를 가리키게 되는지를 기준으로 한 바퀴의 탐색 종료를 판단한다. 강의록의 삭제 탐색은 do-while 구조를 사용하여 첫 노드도 반드시 한 번 검사한다.

노드를 삭제할 때는 먼저 마지막 노드를 찾아 둔다. prevNode가 삭제 노드의 다음 노드를 가리키게 한 뒤, 삭제 노드가 첫 노드였다면 마지막 노드의 링크와 head를 새 첫 노드로 조정한다. 마지막으로 삭제 노드를 free한다.

제9장 6강 이중 연결 리스트

1. 이중 연결 리스트의 구조

이중 연결 리스트는 각 노드에 선행 노드를 가리키는 Llink와 후행 노드를 가리키는 Rlink를 둔다. 양쪽 방향으로 순회할 수 있으므로 특정 노드에서 바로 이전 노드와 다음 노드에 접근할 수 있다. 헤드 구조에는 첫 노드를 가리키는 Fhead와 마지막 노드를 가리키는 Lhead가 사용된다.

typedef struct ListNode {
    struct ListNode *Llink;
    int data;
    struct ListNode *Rlink;
} ListNode;

typedef struct {
    ListNode *Lhead;
    ListNode *Fhead;
} linkedList_h;

2. 이중 연결 리스트의 삽입

prevNode 뒤에 NewNode를 삽입하는 경우 네 개의 연결을 조정한다. NewNode의 Rlink는 prevNode의 기존 Rlink를, prevNode의 Rlink는 NewNode를 가리킨다. NewNode의 Llink는 prevNode를 가리키고, NewNode 뒤 노드의 Llink는 NewNode를 가리키게 한다. 한쪽 링크만 바꾸면 정방향과 역방향 연결이 서로 일치하지 않으므로 모든 링크를 함께 갱신해야 한다.

3. 이중 연결 리스트의 삭제

delNode를 삭제할 때는 선행 노드의 Rlink가 delNode의 Rlink를 가리키게 하고, 후행 노드의 Llink가 delNode의 Llink를 가리키게 한다. 즉 삭제 대상을 사이에서 건너뛰도록 양쪽 연결을 동시에 복구한 뒤 free(delNode)를 수행한다.

구분 포인트: 단순 연결 리스트는 후행 링크 하나, 원형 연결 리스트는 마지막 노드에서 첫 노드로 이어지는 링크, 이중 연결 리스트는 선행·후행 링크 두 개가 핵심이다.

핵심 개념 정리

4강 핵심

• 큐는 front에서 삭제하고 rear에서 삽입하는 FIFO 자료구조이다.
• FCFS는 도착 순서대로 완료까지 실행하고, RR은 시간 할당량이 끝난 미완료 작업을 준비 큐 뒤로 보낸다.
• 선형 배열 큐는 삭제된 앞 공간을 재사용하기 어렵지만, 원형 큐는 나머지 연산으로 배열을 순환하여 공간을 재사용한다.
• 한 칸을 비우는 원형 큐는 front == rear일 때 비고, (rear + 1) % n == front일 때 가득 찬다.

5강 핵심

• 리스트의 순서는 물리적 위치와 구별되는 논리적·의미적 순서이다.
• 연결 리스트의 노드는 데이터와 다음 노드 주소를 저장하는 링크로 구성된다.
• 삽입에서는 기존 후속 노드의 주소를 잃지 않도록 NewNode의 링크를 먼저 설정한다.
• 삭제에서는 선행 노드가 삭제 노드의 후속 노드를 가리키게 한 뒤 메모리를 반환한다.

6강 핵심

• 원형 연결 리스트는 마지막 노드의 링크가 첫 노드를 가리키며 NULL 대신 head로의 복귀를 탐색 종료 조건으로 사용한다.
• 이중 연결 리스트는 Llink와 Rlink로 양방향 순회를 지원한다.
• 원형 구조의 삽입·삭제는 마지막 노드와 첫 노드의 연결을 유지해야 한다.
• 이중 연결 리스트의 삽입·삭제는 선행 방향과 후행 방향 링크를 모두 일관되게 갱신해야 한다.

최종 정리: 큐는 처리 순서를, 연결 리스트는 원소 사이의 논리적 연결을 표현한다. 구현 문제에서는 front·rear의 이동과 공백·만원 조건, 링크 변경의 순서, head와 마지막 노드의 경계 처리, 동적 메모리 반환을 함께 추적해야 한다.

4강 예상문제 20선 - 큐

1. 큐의 처리 원칙으로 옳은 것은?

① 후입선출 ② 우선순위가 높은 원소부터 처리 ③ 먼저 들어온 원소를 먼저 처리 ④ 가장 최근 원소와 가장 오래된 원소를 동시에 처리

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
큐는 먼저 들어온 원소를 먼저 꺼내는 선입선출(FIFO) 자료구조이다.

2. 큐에서 원소의 삭제가 이루어지는 위치는?

① front ② rear ③ top ④ middle

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
큐는 front에서 삭제하고 rear에서 삽입한다.

3. 큐의 rear가 나타내는 것은?

① 가장 먼저 삭제될 원소의 앞 위치 ② 큐의 최대 크기 ③ 공백 상태를 나타내는 값 ④ 원소의 삽입이 이루어지는 쪽

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
rear는 새 원소가 들어가는 큐의 뒤쪽을 나타낸다.

4. 큐의 추상 자료형에서 공백 상태를 검사하는 연산은?

① Add_q ② IsEmpty_q ③ Delete_q ④ IsFull_q

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
IsEmpty_q는 큐에 삭제할 원소가 없는지를 검사한다.

5. 큐가 가득 찬 상태에서 Add_q를 호출했을 때의 처리로 강의록과 맞는 것은?

① front 원소를 자동 삭제한다 ② rear를 -1로 초기화한다 ③ 큐를 스택으로 변환한다 ④ queueFull을 출력한다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
Add_q는 IsFull_q가 참이면 queueFull을 알리고 삽입하지 않는다.

6. A, B, C를 차례로 삽입한 큐에서 한 원소를 삭제하면 반환되는 것은?

① A ② B ③ C ④ 삽입 순서에 따라 알 수 없음

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
FIFO 원칙에 따라 가장 먼저 삽입된 A가 먼저 삭제된다.

7. FCFS 스케줄링의 설명으로 옳은 것은?

① 시간 할당량이 끝날 때마다 작업을 뒤로 보낸다 ② 가장 짧은 작업을 먼저 처리한다 ③ 준비 큐에 도착한 순서대로 CPU를 할당하고 완료까지 실행한다 ④ 가장 최근 도착 작업을 먼저 처리한다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
FCFS는 준비 큐에 먼저 도착한 작업을 먼저 선택하고 그 작업이 완료될 때까지 CPU를 사용하게 한다.

8. 라운드 로빈 스케줄링의 특징은?

① 한 작업이 완료될 때까지 CPU를 독점한다 ② 일정한 시간 할당량이 끝난 미완료 작업을 준비 큐 뒤로 보낸다 ③ 도착 순서를 무시하고 무작위로 실행한다 ④ 큐를 사용하지 않는다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
RR은 작업마다 일정한 시간 할당량을 주고 미완료 작업을 준비 큐 뒤로 이동시킨다.

9. 배열을 이용한 선형 큐의 초기 공백 상태로 강의록에서 사용한 값은?

① front = rear = -1 ② front = 0, rear = 배열 크기 ③ front = rear = 1 ④ front = -1, rear = 0

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
강의록의 배열 큐 구현은 front와 rear를 모두 -1로 초기화한다.

10. 선형 배열 큐의 삽입 연산에서 수행되는 동작은?

① front를 감소시킨 뒤 저장한다 ② 모든 원소를 왼쪽으로 이동한다 ③ front와 rear를 서로 바꾼다 ④ rear를 증가시킨 뒤 그 위치에 저장한다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
삽입은 rear를 한 칸 오른쪽으로 이동시키고 새 원소를 저장한다.

11. 선형 배열 큐의 삭제 연산에서 삭제 원소를 가리키기 위해 이동하는 변수는?

① rear ② front ③ maxQueueSize ④ QUEUE_SIZE

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
삭제는 front를 증가시킨 뒤 그 위치의 원소를 반환한다.

12. 선형 배열 큐에서 앞부분에 빈 공간이 있어도 더 삽입하지 못하는 원인은?

① front가 항상 0이기 때문 ② 배열 원소의 자료형이 다르기 때문 ③ rear가 배열의 마지막 위치에 도달하여 앞의 빈 공간을 재사용하지 못하기 때문 ④ 삭제 연산이 rear를 감소시키기 때문

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
선형 구현은 rear가 끝에 도달하면 삭제로 생긴 앞 공간을 바로 재사용할 수 없다.

13. 원형 큐가 선형 큐의 공간 문제를 해결하는 방법은?

① rear를 고정한다 ② 모든 삭제 원소를 별도 배열에 저장한다 ③ front를 사용하지 않는다 ④ 배열의 마지막과 처음을 논리적으로 연결하여 위치를 순환시킨다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
원형 큐는 배열의 양 끝을 연결하고 나머지 연산으로 인덱스를 순환시킨다.

14. 크기가 n인 원형 큐에서 다음 인덱스를 계산하는 식은?

① 현재 위치 + n ② (현재 위치 + 1) % n ③ 현재 위치 / n ④ n - 현재 위치

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
나머지 연산을 사용한 (현재 위치 + 1) % n이 마지막 다음을 0으로 되돌린다.

15. 한 칸을 비워 두는 원형 큐의 공백 조건은?

① front == rear ② rear == n - 1 ③ front == 0 ④ (rear + 1) % n == front

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
원형 큐에서 front와 rear가 같으면 저장된 원소가 없는 상태이다.

16. 한 칸을 비워 두는 원형 큐의 만원 조건은?

① front == rear ② rear == n ③ (rear + 1) % n == front ④ front == -1

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
rear의 다음 위치가 front이면 구분용 빈 칸만 남았으므로 만원이다.

17. 크기가 5인 배열을 한 칸 비워 구분하는 원형 큐의 최대 저장 원소 수는?

① 5개 ② 4개 ③ 3개 ④ 6개

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
공백과 만원을 구분하기 위해 한 칸을 비우므로 실제 용량은 n-1, 즉 4개이다.

18. 원형 큐에서 rear가 4이고 배열 크기가 5일 때 다음 삽입 위치는?

① 1 ② 2 ③ 3 ④ 0

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
(4 + 1) % 5는 0이므로 rear는 배열의 처음으로 돌아간다.

19. 다음 중 큐의 실제 응용으로 강의록에서 제시된 것은?

① 재귀 호출의 복귀 주소 관리 ② 수식의 괄호 검사 ③ CPU 준비 큐의 작업 관리 ④ 후위 표기식 계산

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
FCFS와 라운드 로빈의 준비 큐는 큐의 대표적인 응용이다.

20. 큐와 스택을 비교한 설명으로 옳은 것은?

① 큐는 서로 다른 끝에서 삽입과 삭제를 수행한다 ② 큐는 항상 후입선출이다 ③ 스택은 front와 rear를 반드시 사용한다 ④ 큐는 삭제만 가능하고 삽입은 불가능하다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
큐는 rear에서 삽입하고 front에서 삭제하지만 스택은 같은 끝에서 삽입과 삭제가 이루어진다.

5강 예상문제 20선 - 연결 리스트

21. 리스트의 정의로 가장 적절한 것은?

① 모든 원소가 같은 주소에 저장되는 구조 ② 원소들 사이의 순서가 지켜지며 유지되는 자료구조 ③ 삽입만 가능하고 삭제는 불가능한 구조 ④ 항상 물리적 위치 순서만 의미하는 구조

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
리스트는 원소들 사이의 논리적 순서가 지켜지며 유지되는 자료구조이다.

22. 리스트의 논리적 순서와 물리적 순서에 관한 설명으로 옳은 것은?

① 두 순서는 언제나 동일해야 한다 ② 논리적 순서는 오직 주소의 크기로 결정된다 ③ 연결 리스트는 물리적 순서를 갖지 않는다 ④ 논리적 순서는 물리적 저장 위치와 관계없이 의미적으로 정해질 수 있다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
리스트의 순서는 메모리의 물리적 위치와 무관하게 사람이 인식하는 의미적 순서가 될 수 있다.

23. 배열로 리스트를 구현했을 때 중간 삽입에 필요한 작업은?

① 삽입 위치 이후의 원소를 뒤로 이동하여 자리를 만든다 ② head를 NULL로 바꾼다 ③ 모든 포인터를 해제한다 ④ 마지막 원소를 첫 위치로 순환시킨다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
배열 중간 삽입은 빈자리를 만들기 위해 뒤쪽 원소들을 한 칸씩 밀어야 한다.

24. 배열 기반 리스트에서 삽입과 삭제가 빈번할 때 비효율적인 주된 이유는?

① 원소의 자료형을 알 수 없어서 ② 동적 메모리를 전혀 사용할 수 없어서 ③ 많은 원소를 이동해야 하므로 실행 시간이 증가해서 ④ 항상 원소를 두 번 저장해서

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
중간 삽입과 삭제는 뒤쪽 원소들을 이동시키므로 원소 수가 많을수록 시간이 증가한다.

25. 포인터를 이용한 연결 리스트 구현의 특징은?

① 원소와 다음 원소의 위치 정보를 함께 저장한다 ② 노드는 반드시 연속 주소에 놓인다 ③ 삽입할 때 모든 원소를 이동한다 ④ 논리적 순서를 표현할 수 없다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
연결 리스트의 노드는 데이터와 다음 노드의 주소를 함께 저장한다.

26. 연결 리스트 노드의 데이터 필드가 저장하는 것은?

① 다음 노드의 주소 ② 헤드 구조체의 크기 ③ 메모리 해제 횟수 ④ 리스트의 원소값

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
데이터 필드는 원소값을 저장하고 링크 필드는 다음 노드 주소를 저장한다.

27. 단순 연결 리스트 노드의 링크 필드 역할은?

① 리스트의 원소 개수를 저장한다 ② 다음 노드의 주소를 저장한다 ③ 현재 노드의 데이터형을 바꾼다 ④ 배열의 최대 크기를 저장한다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
링크 필드는 논리적으로 다음에 오는 노드의 메모리 주소를 가리킨다.

28. 단순 연결 리스트의 마지막 노드가 갖는 링크값은?

① head ② 자기 자신의 주소 ③ NULL ④ 배열의 첫 인덱스

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
후속 노드가 없으므로 단순 연결 리스트의 마지막 링크는 NULL이다.

29. 연결 리스트의 head가 가리키는 것은?

① 마지막 노드 ② 할당되지 않은 메모리 ③ 삭제할 노드의 후속 노드 ④ 첫 번째 노드

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
head는 리스트에 접근하기 위한 시작점으로 첫 노드를 가리킨다.

30. C에서 동적 메모리를 할당하는 데 사용하는 함수는?

① malloc ② delete ③ release ④ free

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
malloc은 필요한 크기의 메모리 공간을 동적으로 할당한다.

31. 동적으로 할당한 노드의 사용이 끝났을 때 호출해야 하는 함수는?

① sizeof ② malloc ③ free ④ printf

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
free는 더 이상 사용하지 않는 동적 메모리를 시스템에 반환한다.

32. 구조체 포인터 p가 가리키는 노드의 data 멤버에 접근하는 표현은?

① p.data ② p->data ③ *p.data ④ p::data

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
구조체 포인터의 멤버는 화살표 연산자 ->로 접근한다.

33. 빈 연결 리스트를 생성할 때 head의 초기값은?

① NULL ② 0번째 배열 원소 ③ 자기 자신의 주소 ④ 첫 노드의 임의 주소

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
아직 첫 노드가 없으므로 생성 직후 head는 NULL로 초기화한다.

34. 리스트 끝에 새 노드를 삽입할 때 새 노드의 초기 link 값은?

① head ② LastNode의 주소 ③ NULL ④ prevNode의 주소

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
새 노드는 새 마지막 노드가 되므로 생성 시 link를 NULL로 둔다.

35. 공백 연결 리스트에 첫 노드를 삽입하는 올바른 처리는?

① 모든 링크를 자기 자신으로 설정한다 ② NewNode를 즉시 free한다 ③ head를 마지막 노드 뒤로 이동한다 ④ head가 NewNode를 가리키게 한다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
공백 리스트에는 기존 노드가 없으므로 head를 NewNode에 연결하면 된다.

36. 비어 있지 않은 연결 리스트의 끝에 삽입하려면 LastNode를 어디까지 이동해야 하는가?

① head가 NULL이 될 때까지 ② link가 NULL인 마지막 노드까지 ③ 데이터가 0인 노드까지 ④ 두 번째 노드까지만

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
마지막 노드는 link가 NULL인 노드이며 그 링크에 NewNode를 연결한다.

37. prevNode 뒤에 NewNode를 삽입할 때 가장 먼저 해야 할 링크 변경은?

① prevNode를 free한다 ② prevNode->link = NULL ③ NewNode->link = prevNode->link ④ head = NULL

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
기존 후속 노드의 주소를 보존하기 위해 NewNode가 prevNode의 기존 후속 노드를 먼저 가리켜야 한다.

38. 단순 연결 리스트에서 delNode를 삭제할 때 prevNode의 올바른 링크 변경은?

① prevNode->link = delNode->link ② prevNode->link = prevNode ③ prevNode->link = head ④ prevNode->link = NULL만 수행한다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
선행 노드는 삭제 노드의 후속 노드를 직접 가리켜 삭제 노드를 건너뛰어야 한다.

39. 노드 삭제 후 free(delNode)를 하지 않으면 생길 수 있는 문제는?

① 배열 자동 확장 ② 메모리 누수 ③ FIFO 위반 ④ rear 초기화

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
연결에서 제외된 동적 메모리를 반환하지 않으면 접근할 수 없는 메모리가 남는다.

40. 노드가 하나뿐인 연결 리스트에서 마지막 노드를 삭제한 뒤의 상태는?

① head는 삭제된 주소를 계속 가리킨다 ② head가 두 번째 노드를 가리킨다 ③ 마지막 노드의 link가 head를 가리킨다 ④ head가 NULL이 된다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
유일한 노드를 반환한 뒤 리스트는 공백이므로 head를 NULL로 바꾼다.

6강 예상문제 20선 - 연결 리스트의 응용

41. 단순 연결 리스트의 구조적 한계로 옳은 것은?

① 후행 노드에도 접근할 수 없다 ② 노드를 동적으로 만들 수 없다 ③ 리스트의 첫 노드를 표현할 수 없다 ④ 선행 노드를 찾으려면 head부터 다시 탐색해야 한다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
단순 연결 리스트는 후행 링크만 가지므로 특정 노드의 선행 노드를 바로 찾을 수 없다.

42. 단순 연결 리스트와 원형 연결 리스트의 가장 중요한 차이는?

① 노드의 데이터형 ② 마지막 노드 링크가 NULL인지 첫 노드를 가리키는지 ③ head 사용 여부 ④ 동적 할당 가능 여부

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
원형 연결 리스트의 마지막 링크는 NULL 대신 첫 노드를 가리킨다.

43. 원형 연결 리스트가 제안된 이유로 가장 적절한 것은?

① 마지막 노드의 링크를 활용하고 원형 순회를 지원하기 위해 ② 모든 노드의 데이터 필드를 제거하기 위해 ③ 배열 인덱스를 사용하기 위해 ④ 링크를 두 개씩 없애기 위해

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
마지막 노드의 비어 있던 링크를 첫 노드에 연결하면 계속 순환할 수 있다.

44. 공백 원형 연결 리스트에 첫 노드를 삽입한 뒤 NewNode의 link가 가리켜야 하는 것은?

① NULL ② 기존 마지막 노드 ③ NewNode 자신 ④ 헤드 구조체의 주소

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
원소가 하나인 원형 리스트에서는 그 노드가 첫 노드이자 마지막 노드이므로 자기 자신을 가리킨다.

45. 기존 원형 연결 리스트의 맨 앞에 NewNode를 삽입할 때 반드시 함께 변경해야 하는 것은?

① 모든 노드의 데이터 ② 마지막 노드의 link와 head ③ 배열의 rear ④ 모든 노드의 주소

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
새 첫 노드를 넣으면 마지막 노드가 NewNode를 가리키고 head도 NewNode로 바뀌어야 한다.

46. 원형 연결 리스트의 뒤에 새 노드를 삽입할 때 새 노드의 link가 가리키는 것은?

① NULL ② 자기 자신만 ③ 기존 마지막 노드 ④ 첫 번째 노드

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
새 노드는 마지막 노드가 되며 원형 연결을 유지하려고 첫 노드를 가리킨다.

47. 원형 연결 리스트를 탐색할 때 NULL을 종료 조건으로 사용할 수 없는 이유는?

① head가 없기 때문에 ② 노드에 데이터가 없기 때문에 ③ 마지막 노드가 첫 노드를 가리켜 NULL 링크가 없기 때문에 ④ 모든 링크가 NULL이기 때문에

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
원형 리스트는 링크가 계속 이어져 있으므로 head로 되돌아왔는지 검사해야 한다.

48. 원형 연결 리스트에서 do-while 탐색이 적합한 이유는?

① 첫 노드를 한 번 검사한 뒤 head로의 복귀를 종료 조건으로 삼을 수 있어서 ② 항상 무한 반복하기 위해 ③ 링크를 사용하지 않기 위해 ④ 배열 인덱스를 증가시키기 위해

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
do-while은 첫 노드를 먼저 검사하고 한 바퀴 뒤 시작점으로 돌아오는 조건을 확인하기 좋다.

49. 원형 연결 리스트에서 첫 노드를 삭제할 때 추가로 조정해야 하는 연결은?

① 삭제 노드의 data만 0으로 바꾼다 ② head만 NULL로 바꾼다 ③ 모든 노드를 free한다 ④ 마지막 노드의 link와 head가 새 첫 노드를 가리키게 한다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
첫 노드 삭제 후에는 마지막 노드와 head 모두 새 첫 노드를 가리켜 원형 연결을 유지해야 한다.

50. 원형 연결 리스트에서 삭제 대상을 찾지 못했음을 판단하는 시점은?

① 탐색 포인터가 다시 head로 돌아왔을 때 ② 탐색 포인터가 NULL일 때만 ③ 첫 노드를 검사하기 전 ④ 노드를 하나 삭제한 뒤

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
원형 구조에는 NULL 끝이 없으므로 시작점인 head로 다시 돌아오면 한 바퀴 탐색을 마친 것이다.

51. 이중 연결 리스트의 각 노드에 필요한 링크 필드는?

① rear와 front ② Llink와 Rlink ③ top과 bottom ④ head와 tail 데이터

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
Llink는 선행 노드, Rlink는 후행 노드를 가리킨다.

52. 이중 연결 리스트의 장점은?

① 노드마다 링크가 전혀 필요 없다 ② 항상 배열보다 메모리를 적게 쓴다 ③ 선행 노드와 후행 노드에 양방향으로 접근할 수 있다 ④ 삭제 시 링크를 변경하지 않는다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
두 링크를 이용하면 특정 노드에서 앞뒤 노드로 직접 이동할 수 있다.

53. 강의록의 이중 연결 리스트 헤드 구조에 포함되는 포인터는?

① Fhead와 Lhead ② front와 rear ③ top 하나만 ④ prevNode와 delNode만

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
Fhead는 첫 노드, Lhead는 마지막 노드를 가리키는 헤드 포인터이다.

54. 이중 연결 리스트에서 prevNode 뒤에 NewNode를 삽입할 때 NewNode의 Llink가 가리켜야 하는 것은?

① NULL ② head만 ③ NewNode 자신 ④ prevNode

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
새 노드의 선행 링크인 Llink는 바로 앞 노드인 prevNode를 가리킨다.

55. 이중 연결 리스트 삽입에서 NewNode 뒤 노드의 Llink가 가리켜야 하는 것은?

① prevNode의 이전 노드 ② NULL ③ NewNode ④ head 구조체

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
후속 노드의 선행 링크를 NewNode로 바꾸어 역방향 연결도 일관되게 만든다.

56. 이중 연결 리스트에서 delNode를 삭제할 때 선행 노드의 Rlink는 무엇을 가리켜야 하는가?

① delNode 자체 ② delNode의 후행 노드 ③ 항상 NULL ④ head

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
선행 노드의 Rlink가 delNode의 Rlink를 이어받아 삭제 대상을 건너뛴다.

57. 이중 연결 리스트 삭제에서 후행 노드의 Llink는 무엇을 가리켜야 하는가?

① NULL만 가능 ② delNode 자신 ③ delNode의 선행 노드 ④ 마지막 노드

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
후행 노드의 Llink는 delNode의 Llink, 즉 삭제 대상의 선행 노드를 가리켜야 한다.

58. 이중 연결 리스트에서 한쪽 방향 링크만 수정하면 생기는 문제는?

① 원소의 자료형이 자동으로 변한다 ② 정방향과 역방향 연결이 서로 불일치한다 ③ 원형 큐가 된다 ④ 모든 노드가 자동 삭제된다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
Llink와 Rlink를 함께 고치지 않으면 어느 방향으로 순회하느냐에 따라 다른 연결이 나타난다.

59. 이중 원형 연결 리스트의 설명으로 옳은 것은?

① 모든 노드의 링크가 NULL이다 ② 두 링크를 가지지만 순환할 수 없다 ③ 단순 연결 리스트와 완전히 같다 ④ 양방향 링크를 가지며 양 끝도 원형으로 연결된다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
이중 원형 연결 리스트는 Llink와 Rlink를 사용하면서 양 끝을 연결해 양방향 순환을 지원한다.

60. 단순·원형·이중 연결 리스트를 비교한 설명으로 옳은 것은?

① 단순 리스트는 후행 링크 하나, 원형 리스트는 마지막에서 첫 노드로 연결, 이중 리스트는 양방향 링크를 갖는다 ② 세 구조는 모두 마지막 링크가 반드시 NULL이다 ③ 원형 리스트만 동적 메모리를 사용할 수 있다 ④ 이중 리스트는 head를 사용할 수 없다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
세 구조는 링크 수와 마지막 연결 방식에서 구분된다.