다음은 C 언어 구조체를 이용하여 배열과 단순 연결 리스트로 큐를 표현… | [7급 국가직 자료구조론] 24년 1회차 기출문제 상세 페이지

다음은 C 언어 구조체를 이용하여 배열과 단순 연결 리스트로 큐를 표현한 것이다.
(가) 배열을 이용한 큐 구조체
(나) 연결 리스트를 이용한 큐 구조체
typedef struct _Queue {
    int front;
    int rear;
    int numOfData;
    int queArr[50];
} QType;
typedef struct _node {
    int data;
    struct _node *next;
} Node;
typedef struct _Queue {
    Node *front;
    Node *rear;
    int numOfData;
} QType;

아래의 <조건>에 따라 (가), (나) 각각에 대해 Enqueue 함수를 세 번 호출하고 Dequeue 함수를 한 번 호출한 후, 큐에 할당된 메모리 공간의 크기(byte)를 계산한 값으로 바르게 연결한 것은?
<조  건>
○ 큐 변수는 QType q; 형태로 선언한다.
○ Enqueue 함수는 큐의 front에 데이터를 추가하는 함수로 함수 원형은 void Enqueue(QType *q, int value)이다.
○ Dequeue 함수는 큐의 rear에서 데이터를 삭제하는 함수이며, 함수 원형은 void Dequeue(QType *q)이다.
○ int형 자료의 경우 4바이트, 포인터형 자료의 경우 8바이트의 메모리 공간을 사용한다.
○ Enqueue와 Dequeue 함수에서는 배열 및 연결 리스트 특성에 맞게 필요한 메모리를 할당ㆍ회수하는 동작이 적절히 일어난다.
○ 연결 리스트에서 삭제 연산은 메모리 회수를 포함한다.
○ 구조체 변수를 메모리에 할당할 때 바이트 패딩 없이 할당한다.

24 / 44

24 / 56

212 / 44

212 / 56

(가)는 212바이트, (나)는 44바이트이다.
배열 큐는 선언 시 QType 크기가 고정되므로 연산과 관계없이 int 3개와 int 배열 50칸으로 $4 \times 53 = 212$바이트이다.
연결 리스트 큐는 QType(포인터 2개 + int 1개) $8 \times 2 + 4 = 20$바이트에, 노드(int + 포인터) $4 + 8 = 12$바이트가 남은 노드 수만큼 더해진다. 세 번 삽입·한 번 삭제 후 노드는 2개이므로 $20 + 12 \times 2 = 44$바이트이다.
24바이트는 배열 큐의 크기가 될 수 없다. 배열 큐는 삽입 횟수와 관계없이 50칸 배열을 처음부터 포함한다.
56바이트는 삭제된 노드의 메모리 회수를 반영하지 않고 노드 3개분을 더한 값이다.