[C언어로 쉽게 풀어쓴 자료구조] 5장

01 문자 A, B, C, D, E를 큐에 넣었다가 다시 꺼내어 출력하면 어떻게 되는가?

(a)A, B, C, D, E

(b)E, D, C, B, A

(c)A, B, C, E, D

(d)B, A, C, D, E

 

02 원형큐에서 front가 3이고 rear가 5라고 하면 현재 원형큐에 저장된 요소들의 개수는?(단, MAX_QUEUE_SIZE는 8이다.)

(a)1

(b)2

(c)3

(d)4

 

03 10, 20, 30, 40, 50 을 큐에 넣었다고 가정하고 3개의 항목을 삭제하였다. 남아 있는 항목은?

 

04 다음 중 원형큐에서 공백상태에 해당하는 조건은?

(a)front==0 && rear==0

(b)front==(MAX_QUEUE_SIZE-1)&&rear==(MAX_QUEUE_SIZE-1)

(c)front==rear

(d)front==(rear+1) %MAX_QUEUE_SIZE

 

05 크기가 10이고 front가 3, rear가 5인 원형큐에서 새로운 항목이 삽입되었을 경우, front와 rear의 새로운 값은?

(1)front은 4, rear는 5

(2)front는 3, rear는 6

(3)front는 4, rear는 6

(4)포화상태가 된다.

 

06 다음과 같은 원형큐에서 (a)에서 (c)까지의 연산을 차례로 수행한다고 하자. 수행이 완료된 후의 큐의 상태를 그려라. 현재 front는 0이고, rear는 2라고 하자.

[0]                                    [1]                                   [2]                                       [3]                                      [4]

B

C

(a)A추가

(b)D추가

(c)삭제

 

07 큐에 항목들을 삽입하고 삭제하는 연산은 시간 복잡도가 어떻게 되는가?

(a) O(1)

(b) O(log₂n)

(c) O(n)

(d) O(n²)

 

08 원형큐에 큐에 존재하는 요소의 개수를 반환하는 연산 get_count를 추가하려 보라. C언어를 이용하여 구현하여 보라.

 

09 2개의 스택을 사용하여 큐를 구현할 수 있을까? 2개의 스택을 사용하여 큐를 구현해보자. 입력이 들어오면 스택 #1에 넣는다. 출력 요청이 들어오면 스택 #2에서 요소를 꺼낸다. 스택 #2가 비어있을 때는 스택 #1의 모든 요소를 꺼내서 스택 #2에 넣는다. 프로그램으로 작성해보자.

 

10 피보나치 수열을 효과적으로 계산하기 위하여 큐를 이용할 수 있다. 만일 피보나치 수열을 순환에 의하여 계산하게 되면 경우에 따라서는 많은 순환 함수의 호출에 의해 비효율적일 수 있다. 이를 개선하기 위하여 큐를 사용하는데 ㅔ큐에는 처음에는 F(0)과 F(1)의 값이 들어가있어 다음에 F(2)를 계산할 때 F(0)을 큐에서 제거한다. 그 다음에 계산된 F(b)를 다시 큐에 넣는다. 피보나치 수열은 다음과 같이 정의된다. 큐를 이용하여 피보나치 수열을 계산하는 프로그램을 작성하라.

F(0)=0, F(1)=1

F(n)=F(n-1)+F(n-2)

 

11 회문 (Palindrome)이란 앞뒤 어느 쪽에서 읽어도 같은 말・구・문 등을 의미한다. 예를들면 "eye","madam","radar"
등이다. 여기서 물론 구두점이나 스페이스, 대소문자 등은 무시하여야한다. 덱을 이용하여 주어진 문자열이 회문인지 아닌지를 결정하는 프로그램을 작성하라. 다음 그림을 참조한다. 

 

 

12 태스크 스케줄링 알고리즘으로 A-steal 알고리즘이 있다. A-steal 알고리즘에서 각각의 CPU는 자신이 실행할 태스크가 저장된 덱을 가지고 있다. 하나의 CPU가 자신의 태스크를 종료했다면 다른 CPU가 실행할 태스크를 훔쳐서 실행할 수 있다. 이 때 다른 CPU의 덱의 끝에 있는 요소를 가져온다. 간단하게 A-Steal 알고리즘을 구현해보자.