c로 배우는 자료구조 연습문제

 

C로 배우는 쉬운 자료구조 출처 나름 연습문제 풀이

 

자료구조 연습문제

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

>> 영화예매시, 화장실, 병원 접수 창구 등

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

>> 스택은 후입선출형 자료구조로 캔에서 물건을 꺼낼때 나중에 들어간 데이터가 제일

먼저 빠져나오고, 큐는 선입선출형 자료구조로 입력은 뒤에서 받고 출력은 앞으로 빠진다.

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

>> rear가 배열의 끝에 도달하면 다시 배열의 처음으로 포인터를 이동시키는 환형큐를

사용해서 앞에 비워지게 되는 front자리를 채워준다.

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

>> 삽입과 마찬가지로 가->나->다->라 순으로 삭제된다 [삽입->가->나->다->라->출력]부분 이기 때문에 나올때도 [라]부터 빠지고 [가]가 제일 나중에 빠져나간다.

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

① item <- Q(front);

② front <- (front+1)mod n;

③ if(front = rear) then Q Empty();

>> 3번 -> 2번 -> 1번 순 으로 진행 된다.

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

예) A삽입 -> B삽입 -> 삭제 -> C삽입 -> 삭제 -> 삭제 -> D삽입 -> E삽입 -> 삭제 -> F삽입 -> 삭제

>>Ｆ삽입에서 작업을 할수없게된다 이유는 5개인 선형큐이기 때문에 ABCDE가 다들어가고 그다음 삭제가 되도 빈공간에 들어갈수가 없기 때문에 F는 못들어가게된다.

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

예)insertFront(DQ,A)->insertFront(DQ,B)->insertRear(DQ,C)->deleteRear(DQ)-> insertFront(DQ,D)->deleteRear(DQ)->getRear(DQ)->insertrear(DQ,E)->deleteFront(DQ)

>>A->AB->CAB->AB->ABD->BD->(값을리턴)->EBD->EB

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

>>공백상태는 front와 rear가 같을때 이고, ((rear+1)mod n) 상태는 rear위치가 front위치가 되어서 포화상태가 된다.

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

>> 리스트에서 나열한 원소들간에 순서를 가지고 있는 리스트를 선형 리스트 라고 한다.

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

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

>> 나. 큐