정보처리기사 필기시험 준비 [11]

소프트웨어개발 - 데이터입출력

자료구조

자료를 효율적으로 표현하고 저장하고 처리할 수 있도록 정리하는 것

 

선형구조

1. 순차리스트
   1. 리스트에 나열한 데이터들이 일정한 순서를 가지고 있는 구조
   2. 배열처럼 자료를 나열하여 메모리에 연속적으로 저장하는 형태
2. 연결리스트
   1. 각 노드가 데이터와 포인터를 가지고 한줄로 연결된 형태
   2. 순서가 매겨진 항목들을 모아놓은 구조 중 하나로 각 데이터를 연결하는 포인터까지 있는 구조
   3. 순차 자료구조 - 논리적인순서 = 물리적인 순서
   4. 연결리스트 - 논리적인순서 != 물리적인 순서
3. 스택
   1. 스택은 한쪽 긑에서만 자료를 넣거나 뺄 수 있는 선형구조(LIFO - Last In First Out)
4. 큐
   1. 한쪽 끝으로 자료를 넣고 반대쪽으로 자료를 뺄 수 있는 선형구조
5. 데크
   1. 삽입과 삭제가 리스트 양쪽 끝에서 모두 발생할 수 있는 자료구조

비선형구조

1. 트리
   1. 비선형 자료구조중 자료간 계층관계를 가진 계층형 자료구조
   2. 노드 - 트리의 원소
   3. 간선 - 노드를 연결하는 선
   4. 루트노드 - 트리의 시작
   5. 형제노드 - 노드같은 부모 노드의 자식 노드들
   6. 조상노드 - 간선을 따라 루트노드까지 이르는 경로에 있는 모든 조상노드
   7. 서브트리 - 부모 노드와 연결된 간선을 끊었을때 생성되는 트리
   8. 자손노드 - 서브 트리에 있는 하위 레벨이 노드들
   9. 차수
      1. 노드의 차수 - 노드에 연결된 자식의 노드수
      2. 트리의 차수 - 트리에 있는 노드의 차수 중에서 가장 큰 값
      3. 단말 노드 - 차수가 0인 노드 자식노드가 없는 노드
   10. 높이
       1. 노드의 높이 - 루트에서 노드에 이르는 간선의 수 , 노드의 레벨
       2. 트리의 높이 - 트리에 있는 노드의 높이 중 가장 큰 값

1. 이진트리
   1. 트리의 모든 노드의 차수를 2 이하로 제한하여 전체 트리의 차수가 2 이하가 되도록 정의
   2. 이진트리의 모든 노드는 왼쪽 자식 노드와 오른쪽 자식 노드만 가짐
   3. 이진트리순회 - 모든 원소를 빠트리거나 중복하지 않고 처리하는 연산
      1. 전위순회(DLR), 중위순회(LDR), 후위순회(LRD)
2. 그래프
   1. 연결할 객체를 나타내는 정점과 객체를 연결하는 간선의 집합으로 구성
   2. 무방향그래프 - 두 정점을 연결하는 간선의 방향이 없는 그래프, 최대 n(n-1)/2 개
   3. 방향그래프 - 간선에 방향이 있는 그래프, 최대 n(n-1)개