자료구조 8장 연습문제 풀이

1. 일상생활에서 발견할 수 있는 큐의 예를 설명하여라.

 

답 : 줄을 서서 기다리는 사람들

? : 큐는 FIFO(First In First Out)의 방식이다.

 

 

 

2. 큐와 스택의 구조를 비교하여 설명하여라.

 

답 : 큐는 FIFO이기 때문에 먼저 들어간 자료가 먼저 나오고, 스택은 LIFO 구조이기 때문에 마지막에 들어간 자료가 먼저 나온다.

 

 

 

3. 1차원 배열의 선형 큐에서 잘못된 포화 상태 문제를 해결하는 방법을 설명하여라.

 

답 : 원소들을 비어 있는 앞 인덱스로 이동

 

 

 

4. [가→나→다→라] 순서로 큐에 원소를 삽입한 후에 모두 삭제하면 어떤 순서로 삭제되는지 설명하여라.

 

답 : [가→나→다→라]

? : 큐는 FIFO이기 때문에 삽입된 순서대로 삭제된다.

 

 

 

5. 원형 큐의 삭제 알고리즘을 순서대로 나열하여라.

① item ← Q[front]; ② front ← (front + 1) mod n; ③ if(front = rear) then Q_Empty();

 

답 : ②→③→①

? : front의 위치를 하나 뒤로 이동 → 맨 앞 위치와 맨 뒤 위치가 같을 경우 큐는 공백일 경우 큐는 공백 → front 인덱스에 있는 데이터 삭제

 

 

 

6. 크기가 5인 선형 큐에서 다음의 연산을 수행한다. 큐가 포화상태가 되어 더 이상 작업을 할 수 없게 되는 시점을 설명하여라.

A 삽입 → B 삽입 → 삭제 → C 삽입 → 삭제 → 삭제 → D 삽입 → E 삽입 → 삭제 → F 삽입 → 삭제

 

답 : F 삽입이 불가능

? : 크기가 5인 선형 큐가 이미 포화 상태이기 때문에 F 삽입을 수행할 수 없다.

 

 

 

7. 공백 덱에 대하여 다음의 연산이 모두 수행된 후에 덱에 남아있는 원소를 순서대로 나타내어라.

insertFront(DQ, A) → insertFront(DQ, B) → insertRear(DQ, C) → deleteRear(DQ) → insertFront(DQ, D) → deleteRear(DQ) → peekRear(DQ) → insertRear(DQ, E) → deleteFront(DQ)

 

답 : B E

? : A 삽입 → A 앞에 B 삽입 (현재 B A) → rear 뒤로 C 삽입 (현재 B A C) → rear 삭제 (현재 B A) → B 앞에 D 삭제 (현재 D B A) → rear 삭제 (D B) → rear 뒤로 E 삽입 (D B E) → front 삭제 (B E)

 

 

 

8. 원형큐에서 포화상태와 공백상태의 조건을 설명하여라.

 

답 : rear가 한 바퀴 돌면서 원소를 삽입하여 큐를 모두 채워서 rear의 위치가 front의 위치와 같아져서 더 이상 원소를 삽입할 수 없는 상태를 포화 상태라고 한다.

마지막에 삽입한 rear 원소가 삭제되고, front가 rear 위치에 있는 상태를 공백 상태라고 한다.

 

 

 

9. 리스트의 양쪽에서 정보를 삽입하거나 삭제할 수 있는 선형리스트는 무엇인가?

 

답 : 덱

 

 

 

10. 운영체제의 작업 스케줄링 등에 응용되는 것으로 가장 적합한 자료구조는?

가. 스택    나. 큐    다. 연결 리스트    라. 트리

 

답 : 나. 큐

? : 운영체제의 작업 스케줄링에 응용되는 자료구조는 큐이다.

 

 

 

11. 다음 중 큐를 필요로 하는 작업은?

가. 작업 스케줄링    나. 중위 표기식의 후위 표기식 변환    다. 함수 호출과 리턴    라. 이진트리의 중위 순회

 

답 : 가. 작업 스케줄링

? : 10번 참고

나, 다 - 스택    /    라 - 트리

 

 

 

12. 덱에 대한 옳은 설명으로 짝지어진 것은?

① 양끝에서 노드의 삽입과 삭제가 가능하다. ② 하나의 포인터를 사용한다. ③ Delete ended queue의 약자다. ④ 선형 자료구조다.

가. ①, ②    나. ①, ②, ③    다. ①, ③, ④    라. ①, ④

 

답 : 라. ①, ④

? : ②는 단순 연결 리스트의 설명이다.

③ Delete ended Queue가 아닌 Double eneded Queue의 약자이다.

 

 

 

13. 리스트에서 FIFO(First In First Out)의 특성을 지닌 추상적 자료형으로서, 시작과 끝을 표시하는 두 개의 포인터를 갖는 자료구조는?

가. 스택    나. 트리    다. 그래프    라. 큐

 

답 : 라. 큐