8장 연습문제

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

예) 은행에서 번호표 순서대로 처리하기

순서대로 미끄럼틀 내려오기

...

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

	삽입 연산		삭제 연산
	연산자	삽입위치	연산자	삭제위치
스택	Push	top	Pop	top
큐	enQueue	rear	deQueue	front

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

방법1) 원소들을 비어있는 앞자리로 당겨주기(이동하기)

방법2) 원형큐로 만들기

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

[가→나→다→라]

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

① item ← Q[front];

② front ← (front+1) mod n;

③ if(front = rear) then Q_Empty();

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

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

삭제 → F 삽입 → 삭제

큐가 포화상태이기 때문에 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)

⇒ BE

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

isEmpty(cQ)

if(front=rear) then return true;	else return false;

end isEmpty()

isFull(cQ)

if(((rear+1) mod n)=front) then return true;

else return false;

end isFull()

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

⇒ 덱

10. 운영체제의 작업 스케줄링 등에 응용되는 것으로 가장 적합한 자료구조는? (2000년, 2002년 기출문제)

① 스택        ② 큐        ③ 연결리스트        ④ 트리

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

가. 작업 스케줄링

나. 중위 표기식의 후위 표기식 변환

다. 함수 호출과 리턴

라. 이진트리의 중위 순회

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

① 양끝에서 노드의 삽입과 삭제가 가능하다.

② 하나의 포인터를 사용한다.

③ Delete ended queue의 약자다.

④ 선형 자료구조다.

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

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

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