[ 방송통신대학교 2학년 2학기 자료구조 중간, 기말고사 대비 요약본 ]
안녕하세요^^
오늘은 방송통신대학교 2학년 2학기 과목인 자료구조의
중간고사, 기말고사를 위한 주요 키워드나 개념 등을 정리해보는 포스팅을 해보려고 합니다!
오늘은 그 4번째 시간입니다!
이전 포스팅은 블로그에서 태그로 검색해주시거나, 아래 URL을 참조해주세요!
2019/10/12 - [방송통신대학교] - 방송통신대학교 2학년 2학기 자료구조 중간,기말고사 대비 요약본 #1
2019/10/12 - [방송통신대학교] - 방송통신대학교 2학년 2학기 자료구조 중간, 기말고사 대비 요약본 #2
2019/10/12 - [방송통신대학교] - 방송통신대학교 2학년 2학기 자료구조 중간, 기말고사 대비 요약본 #3
자료 출처는 아래와 같습니다.
1. 방송통신대학교 공식 교과서
2. 유노 캠퍼스에 정리된 "주요 용어"
3. 해당 강의에서 제공되는 "연습문제"
4. 출석수업, 강의 등에서 교수님이 특별히 강조하신 개념
5. "기말고사" 등 문제에서 실제로 반복적으로 나오는 개념
6. 지극히 개인적인 제 주관상 넣고 싶은 것
공부하실 때 참고하시면 좋을 것 같습니다!
[ 자료구조 요약 정리본 ]
1. 큐 : 한쪽에서는 삽입이 발생하고 다른 한쪽에서는 삭제가 발생하도록 정의되었으며,
먼저 삽입된 원소가 먼저 삭제되므로 선입 선출(First-In-First-Out: FIFO) 또는
선착순 서브(First-Come-First-Serve: FCFS) 알고리즘을 갖는 순서 리스트
- 에스칼레이터, 택시 기다리는줄, 급식 기다리는 줄 등을 생각하시면 됩니다.
- 스택 과는 정반대입니다.
2. 큐의 앞(front) : 원소의 삭제연산이 이루어지는 곳
- 밑에 rear 와 같이 시험 단골 문제입니다.
- 소스코드 형식으로도, 개념으로도 자주 나옵니다.
3. 큐의 뒤(rear) : 원소의 삽입 연산이 이루어지는 곳
4. FCFS(First-Come First-Served) 스케줄링(또는 FIFO 스케줄링) : 작업(프로그램)이 준비 큐에 도착한 순서대로 CPU를 할당받도록 해 주는 기법
5. RR(Round Robin) 스케줄링 기법 : 작업이 도착한 순서대로 CPU가 할당되지만,
CPU의 시간 할당량 또는 시간 간격에 의해 제한을 받으며,
일정한 크기의 시간 할당량을 모든 작업에게 주고 그 시간 동안 작업이 완료되지 못하면
준비 큐의 맨 뒤에 다시 배치되는 기법
6. 원형 큐 : 파이프의 입구와 출구 부분을 연결시킨 형태이며, 큐의 양 끝을 연결시켜서 원으로 만든 형태의 큐
- RR 이 원형 큐와 비슷한 방식이라고 보시면 편합니다.
7. 자료 구조의 유형 중 선형 구조에 해당하는 것은 무엇인가? > 큐
- 원형 큐 등이 대표적인 선형 구조입니다.
8. 큐에서 노드를 삽입할 경우 어떻게 해야 하는가? rear의 위치를 증가시킨 후 원소를 삽입
- 바로 아래 지문 확인하시는 게 좋습니다. 시험 단골 문제로 아래처럼 소스코드로 나옵니다.
9. 아래 지문은 큐에 원소를 삽입하는 알고리즘이다. (가)와 (나)에 알맞은 내용은?
void Add_q(int *rear, element item) {
if ( (가) )
{ printf(“Queue is full !!”);
return; }
queue[(나)] = item;
return; }> (가) : *rear == QUEUE_SIZE-1 ｜ (나) : ++(*rear)
- 위 지문처럼 단골 문제로 나옵니다.
- 먼저 QUEUE_SIZE 가 여유가 있는지를 체크합니다.
- 이때 QUEUE_SIZE 가 아니라 QUEUE_SIZE-1 인걸 유의하셔야 합니다.
- 그 후에 ++(*rear) 하여 rear을 증가시킨 후에 원소를 삽입합니다.
10. 큐 생성 함수(Create_q(maxQueueSize))를 호출하기만 하면
프로그래머가 지정한 크기의 새로운 큐를 생성할 수 있습니다.
Create_q(maxQueueSize) 함수의 매개변수인 maxQueueSize는
큐가 저장할 수 있는 최대 개수의 원소(element)를 의미합니다.
- 이때 maxQueueSize를 가지고 IsFull 등 Check 함수를 실행합니다.
11. Boolean IsFull_q(queue, maxQueueSize) 연산은 큐가 가득 찼는지를 확인합니다.
즉, 큐에 저장된 원소(element)의 개수가 maxQueueSize와 같다면,
그 큐는 가득 찼으며 큐에 자료(원소)를 더 이상 저장시킬 수 없다는 것을 의미합니다.
12. Queue Add_q(queue, item) 연산은 큐에 새로운 원소를 삽입합니다.
만일 큐가 가득 찼다(Full) 면 더 이상의 원소를 큐에 삽입할 수 없으며, ‘queueFull‘ 메시지를 출력합니다.
13. Boolean IsEmpty(queue) 연산은 큐 상태가 빈 상태인지를 확인합니다.
만일 큐가 빈 상태이면 ‘TRUE’ 값을 반환하고, 큐에 하나이상의 원소라도 있다면 ‘FALSE’ 값을 반환합니다.
14. Element Delete_q(queue) 연산자는 큐가 빈 상태라면 삭제할 원소가 없으므로 ‘queueEmpty‘를 출력합니다.
하지만, 빈 상태가 아니라면 삭제할 원소가 있으므로, 큐의 front가 가리키는 원소를 삭제하고 그 원소를 반환합니다.
- 원소가 삭제되고 나면 front 가 1 감소합니다.
15. 큐의 추상 자료형에서 정의된 연산은 시스템 개발자에 따라 다르게 정의되고 구현될 수도 있고, 컴파일러 설계자에 따라 프로그래밍 언어에서 다르게 제공될 수도 있습니다.
- 스택과 동일합니다. 시험 단골 문제입니다.
16. 원형 큐는 파이프의 입구와 출구 부분을 연결시킨 형태입니다.
연결된 부분의 데이터 공간을 연속적으로 사용하기 위해 ‘나머지 연산자‘를 사용합니다.
- 원형 큐의 첫 번째와 마지막 요소는 서로 연결되어 있습니다.
/*
혹시나 제가 잘못 포스팅하였거나,
더 상세한 설명이 필요하시거나 등
어떠한 의견도 좋으니 자유롭게 덧글 부탁드립니다!
*/
'방송통신대학교' 카테고리의 다른 글
| 방송통신대학교 1학년 2학기 대학영어 중간, 기말고사 대비 요약본 #2 (0) | 2019.10.24 |
|---|---|
| 방송통신대학교 1학년 2학기 대학영어 중간, 기말고사 대비 요약본 #1 (0) | 2019.10.23 |
| 방송통신대학교 2학년 2학기 자료구조 중간, 기말고사 대비 요약본 #3 (0) | 2019.10.12 |
| 방송통신대학교 2학년 2학기 자료구조 중간, 기말고사 대비 요약본 #2 (0) | 2019.10.12 |
| 방송통신대학교 2학년 2학기 자료구조 중간,기말고사 대비 요약본 #1 (0) | 2019.10.12 |