정보처리기사 데이터베이스 요약 9

자격증/정보처리기사

IT grow. 2019. 7. 18. 17:20

9장

1. 자료 구조의 분류

- 비선형 구조 : 트리, 그래프 외 나머지는 모두 선형 구조

2. 연결 리스트 ( Linked List )

- 선형 리스트에 비해 노드의 삽입이나 삭제가 쉬움

- 노드들이 포인터로 연결되어 속도가 느리고 공간이 많이 필요

- 희소 행렬을 링크드 리스트(Linked List)로 표현하면 기억 장소가 절약

3. 스택

- Top (=스택 포인터)이라 불리는 한쪽 끝에서 삽입과 삭제가 일어나는 자료 구조

- Top이 0이면 더 이상 삭제할 자료가 없으므로 Underflow

- 스택 포인터가 스택의 크기보다 Overflow

- FILO or LIFO 방식

4. 스택의 이용

- 인터럽트 발생 시 복귀 주소를 기억시키는데 사용

- 재귀(Recursion) 프로그램 (한 루틴이 자기를 다시 호출하여 실행하는 프로그램)의 순서 제어

- 컴파일러를 이용한 언어 번역

- Postfix 형태의 수식을 계산

5. 큐 ( Queue )

- 노드의 삽입 작업은 선형 리스트의 한쪽 끝에서 , 제거 작업은 다른 한쪽 끝에서 수행되는 자료 구조

- 모든 삽입은 리어(Rear)라는 한쪽 끝에서 발생하고, 모든 삭제는 프론트(Front)라는 다른 한쪽 끝에서 발생하는 순서리스트

- 운영체제의 작업 스케줄링에 사용

- 택시 정거장에서 줄을 서서 순서대로 택시를 타는 것과 유사

6. 데크 ( Deque )

- Double Ended Queue의 약자

- 양방향에서 입/출력이 가능한 선형 자료 구조

- 2개의 포인터를 이용하여 양쪽 끝 모두에서 삽입/삭제가 가능

7. 트리

- 그래프의 특수한 형태로 노드와 선분으로 되어 있고, 정점 사이에 사이클이 형성되어 있지 않으며 자료 사이의 관계성이 계층 형식으로 나타나는 비선형 구조

8. 이진 트리 운행법

- Preorder(전위) : Root à Left à Right

- Inorder(중위) : Left à Root à Right

- Postorder(후위) : Left à Right à Root

9. 수식의 표기법

- PreFix ( 전위 표기법 ) : 연산자 à Left à Right

- InFix ( 중위 표기법 ) : Left à 연산자 à Right

- PostFix ( 후위 표기법 ) : Left à Right à 연산자