자료구조 ★★

p.162, 2-2

1) 자료 구조의 분류

▶ 선형 구조(Linear Structure)

- 배열(Array)

- 스택(Stack)

- 큐(Queue)

- 데크(Deque)

- 선형 리스트(Linear List) = 연속 리스트(순차적임), 연결 리스트(순차적이지 않음)

 

▶ 비선형 구조(Non-Linear Structure)

- 트리(Tree)

- 그래프(Graph)

 

 

2) 배열(Array)

- 정적인 자료 구조로 기억장소의 추가가 어렵고 메모리의 낭비가 발생함

- 첨자를 이용

- 반복적인 데이터 처리 작업에 적합한 구조

- 데이터마다 동일한 이름의 변수를 사용해 처리가 간편함

 

 

3) 스택(Stack)

- 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이뤄지는 자료 구조

- 후입선출(LIFO; Last In First Out) 방식

 

 

4) 큐(Queue)

- 리스트의 한쪽에서는 삽입 작업, 다른 한쪽에서는 삭제 작업이 이뤄지는 자료 구조

- 선입선출(FIFO;First In First Out) 방식

- 시작(F, Front)과 끝(R, Rear)을 표시하는 두 개의 포인터가 있음

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

 

 

5) 데크(Deque)

- 리스트의 양쪽 끝에서 삽입과 삭제작업을 할 수 있는 자료 구조

 

 

6) 선형 리스트(Linear List)

▶ 연속 리스트(Contiguous List)

- 배열과 같이 연속되는 기억장소에 저장되는 자료 구조

- 기억장소를 연속적으로 배정받아, 기억장소 이용 효율은 밀도가 1로서 가장 좋음

- 중간에 데이터를 삽입하기 위해 연속된 빈 공간이 있어야함

- 삽입, 삭제 시 자료의 이동이 필요함

 

▶ 연결 리스트(Linked List)

- 자료들을 반드시 연속적으로 배열시키지 않고 임의의 기억공간을 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용해 서로 연결시킨 자료 구조

- 노드의 삽입, 삭제 작업이 용이

- 기억공간이 연속적으로 놓여 있지 않아도 저장가능

- 연결을 위한 포인터가 필요하기 때문에 순차 리스트에 비해 기억 공간의 효율이 좋지 않음

- 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느림

- 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘듦

 

 

7) 트리(Tree) ★★

- 정점(Node, 노드)과 선분(Branch, 가지)을 이용해 사이클을 이루지 않도록 구성한 그래프(Graph)의 특수한 형태

▶ 노드(Node): 트리의 기본 요소, 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것

▶ 근 노드(Root Node): 트리의 맨 위에 있는 노드

▶ 디그리(Degree, 차수): 각 노드에서 뻗어 나온 가지의 수 ★

▶ 단말 노드(Terminal Node): 자식이 하나도 없는 노드, Degree가 0인 노드 ★

▶ 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들

▶ 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들

▶ 형제 노드(Brother Node, Sibling): 동일한 부모를 갖는 노드들

▶ 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수

 

# 차수(Degree)와 단말(Terminal)의 수를 물어보는 기출문제 多 __ 1, 2, 3회 기출문제

차수(Degree): 3 - D, E, F (B의 자식 노드)

단말(Terminal): 5 - D, E, H, I, G (자식이 하나도 없는 노드)

 

 

8) 그래프(Graph)

▶ 방향 그래프

- 정점을 연결하는 선에 방향이 있는 그래프

- n개의 정점으로 구성된 방향 그래프의 최대 간선 수 = n(n-1)

 

▶ 무방향 그래프

- 정점을 연결하는 선에 방향이 없는 그래프

- n개의 정점으로 구성된 무방향 그래프의 최대 간선 수 = n(n-1)/2

 

 

wook-2124.tistory.com/275

2020 정보처리기사 필기 총정리 (시나공, 수제비)

wook-2124.tistory.com/206

정보처리기사 필기 실기 공부방법 및 기출문제 무료 공유