다음은 구현하고자 하는 원형 큐(circular queue)에 대한 &… | [7급 국가직 자료구조론] 16년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 16년 1회차
다음은 구현하고자 하는 원형 큐(circular queue)에 대한 <조건>과 <설명>이다. <설명>의 괄호 안에 들어갈 수로 옳게 짝지어진 것은?<조 건>
○ 크기가 6이고 인덱스가 0부터 5까지인 배열로 구현된다.
○ 공백 상태에서만 front와 rear의 값이 서로 같으며, 그 외에는 값이 서로 다르다.
○ (front + 1) mod 6은 다음에 삭제할 원소 위치를 가리킨다.
○ (rear + 1) mod 6은 다음에 삽입할 원소 위치를 가리킨다.<설 명>
○ 최대 ( ㉠ )개의 원소를 저장할 수 있다.
○ front = 5이고 rear = 3인 경우 저장된 원소 수는 ( ㉡ )개이다.
○ front = ( ㉢ )이고 rear = 2인 경우는 포화 상태를 의미한다.
1
㉠ 6 ㉡ 5 ㉢ 1
2
㉠ 6 ㉡ 4 ㉢ 1
3
㉠ 5 ㉡ 5 ㉢ 3
4
㉠ 5 ㉡ 4 ㉢ 3
해설
괄호에는 ㉠ 5, ㉡ 4, ㉢ 3이 들어간다.
front = rear를 공백 상태 전용으로 쓰므로, 포화와 구분하려면 배열 한 칸을 비워 둔다. 따라서 크기 6 배열에 최대 5개만 저장한다.
원소 수 = (rear − front + 6) mod 6 = (3 − 5 + 6) mod 6 = 4
포화 조건은 (rear + 1) mod 6 = front이므로 rear = 2이면 front = 3이다.
- ㉠ 6, ㉡ 5, ㉢ 1 조합은 최대 원소 수와 원소 수가 모두 틀렸고, front = 1, rear = 2는 원소가 1개인 상태다.
- ㉠ 6, ㉡ 4, ㉢ 1 조합은 원소 수만 맞고, 6개를 모두 채우면 front = rear가 되어 공백과 구분되지 않는다.
- ㉠ 5, ㉡ 5, ㉢ 3 조합은 front = 5, rear = 3일 때 원소가 위치 0, 1, 2, 3의 4개뿐이라는 점과 맞지 않는다.
오류나 개정된 내용이 보이면 알려주세요