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

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 à 연산자