자료구조

- 희소행렬 : 원소값이 0인 원소가 그렇지 않은 원소보다 상대적으로 많은 행렬을 의미함

- 스택 : 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형

- 시스템 스택 : 변수에 대한 메모리의 할당과 수집을 위해 운영체제가 관리하는 스택

- 중위표기법 : 연산자를 피연산자의 사이에 표기하는 방법이며 일반적으로 가장 많이 사용되는 표기방법(A+B)

- 전위표기법 : 연산자를 피연산자의 앞에 표기하는 방법(+AB)

- 후위 표기법 : 연산자를 피연산자의 뒤에 표기하는 방법(AB+)

- RR스케줄링 기법 : 작업이 도착한 순서대로 CPU가 할당되지만, CPU의 시간 할당량 또는 시간 간격에 의해 제한을 받으며, 일정한 크기의 시간 할당량을 모든 작업에게 주고 그 시간동안 작업이 완료되지 못하면 준비 큐의 맨 뒤에 다시 배치되는 기법

- 원형큐 : 파이프의 입구와 출구 부분을 연결시킨 형태이며, 큐의 양 끝을 연결시켜서 원으로 만든 형태의 큐

- 리스트: 원소들 간의 순서가 지켜지며 유지되는 자료구조

- 리스트의 원소들 간의 순서 : 데이터가 저장되는 물리적인 위치와 상관없이 사람들의 머릿속에 인식되는 '논리적인 순서', 혹은 리스트에 나타나는 원소들 간의 '의미적인 순서' 

- 리스트의 노드 : 원소값과 다음 원소를 가리키는 위치의 주소값으로 구성된 자료단위. 데이터 요소(원소)와 리스트의 다음 원소를 지시하는 포인터(pointer, 주소)를 가지는 자료단위

- 포인터 : 메모리에 저장되는 값의 저장 위치에 대한 주소를 가리키는 데이터형

- 단항연산자 : 피연산자를 하나만 갖는 연산자

- 구조체(struct) : 다양한 데이터형의 변수를 하나의 상자안에 넣어서 선언하거나 사용하는 C프로그래밍 문법

- 단순 연결 리스트 : 링크 부분이 하나만 있고, 각각의 노드는 후행 노드만을 가리키는 구조

- 이중 연결 리스트 : 특정 노드에서는 선행 노드와 후행 노드에 대해 간단한 프로그램 코드를 통해 접근할 수 있는 구조

- 원형 연결 리스트 : null 값을 갖는 마지막 노드의 링크 부분을 활용하면서도 프로그램 성능에 도움을 주기 위해 제안되었으며, 한 방향으로 모든 노드가 원형으로 계속 연결되어 있기 때문에 한 노드에서부터 다른 어떤 노드로도 접근이 가능한 구조

- 트리 : 트리는 논리적 계층이 있는 구조이며, 트리를 구성하는 항목을 노드(node) 혹은 점(vertex)이라고 함

- 루트 : 트리에서 부모를 갖지 않은 노드

- 진입차수 : 트리에 있는 어떤 노드에 대해 그 노드로 들어오는 선의 개수

- 진출차수 : 트리에 있는 어떤 노드에 대해 그 노드에서 나가는 선의 개수

- 내부 노드 : 루트도 잎도 아닌 노드

- 형제 : 같은 부모를 갖는 노드들

- 완전이진 트리 : 이진 트리에서 각 레벨이 허용되는 최대 개수 노드를 가지는 트리

- 포화이진 트리 : 높이가 k인 이진 트리가 레벨 0부터 k-2까지 다 채우고 마지막 k-1레벨에서 왼쪽부터 오른쪽으로 노들들이 차례로 채워진 트리

- 순회(traverse) : 트리의 각 노드를 빠짐없이 한 번씩만 방문하는 것

- 스레드 : w정해진 순회 방법에 따른 방문순서를 유지하는 포인터

- 스레드 트리 : 스레드라는 포인터를 갖는 이진 트리

- 오른쪽 스레드 : 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리킴

- 왼쪽 스레드 : 그 노드의 선행노드를 가리킴

- 이진 트리의 null포인터 개수

2n- (n-1) = n+1

- 부모노드와 자식노드사이의 대소관계가 정의되어 구성되는 완전 이진트리이며 우선순위 큐와 같은 결과를 제공합니다.

 

- 승자트리 : 각 노드가 두 개의 자식노드 보다 더 작은 값(승자)을 갖는 완전 이진트리

- 최소힢 : 루트가 가장 작은 값을 갖고 부모는 자식보다 작은 값을 가지면 됩니다.

 

- 패자트리 : 각 노드가 두 개의 자식노드보다 더 큰 값(패자)을 가지며 최종 승자는 0번 노드에 저장하는 트리

- 최대힢 : 루트가 가장 큰 값을 갖고 부모는 자식보다 큰 값을 가지면 됩니다.

 

- 합병정렬 : 차례로 정렬된 데이터 리스트를 완전한 순서를 유지하는 하나의 리스트로 만드는 과정

- 선택트리 : 합병정렬에 사용하는 특수한 트리

 

- 숲 : 분리된 트리 모임,  n(=>0)개 이상의 분리된 트리집합

- 이진 탐색 트리 : 빠르게 탐색할 수 있도록 구성한 이진트리

- 키 : 각 노드를 식별하기 위해서는 별도의 간단한 이름을 붙여준 것

- Splay트리 : 자주 탐색하는 키를 가진 노드를 루트에 가깝게 위치하도록 구성한 이진 탐색 트리

- AVL트리 : 노드 vi의 왼쪽 서브트리 높이와 vi의 오른쪽 서브트리 높이가 최대 1만큼 차이가 난다는 조건을 만족하는 트리

- 트리의 높이 : 노드가 가질 수 있는 가장 높은 레벨에 1을 더한 값으로 루트로부터 잎까지 가장 긴 경로 길이

- 트리의 무게 : 트리에 속한 잎 노드의 개수

- 무게가 균형 잡힌 트리 : 각 노드의 양쪽 서브트리 무게가 균형을 유지하는 트리

[멀티웨이 탐색트리]

- m원 탐색 트리 : 트리의 노드가 m개 이하의 가지를 가질수 있는 탐색트리

- B트리 : 인덱스 구조를 구현하는데 가장 일반적으로 사용하는 방법으로 차수가 m인 트리

- B*트리 : 노드의 약 2/3이상이 차야하는 B트리

- B+ : 모든 키값이 잎 노드에 있고 그 키값에 대응하는 실제 데이터에 대한 주소를 잎 노드만이 가지고 있어서 인덱스된 순차 파일을 구성하는데 사용하는 트리

- 2-노드 : 차수가 2인 노드

- 2-3트리 : 2-노드와 3-노드만으로 구성한 트리로 B트리 계열과 거의 같은 성능을 유지하면서 상대적으로 삽입 삭제가 용이하다.

- 2-3-4 트리 : 2-노드, 3-노드 및 4-노드만으로 구성한 트리로 2-3트리와 같은 특성을 갖는다.

- 레드 블랙 트리 : 2-3-4 트리를 이진 트리로 나타낸 것으로 기억장소를 효율적으로 사용할 수 있다.

- 그래프 : 정점 집합 V와 간선 집합 E에 대하여 그래프는 G=(V,E)

- 정점 : 그래프를 구성하는 대상

- 간선 : 그래프에 있는 대상들의 관계

- 방향 그래프 : 간선의 방향이 유의미한 그래프

- 다중 그래프 : 두 정점쌍이 간선을 여러개 가질수 있는 그래프

- 경로 : 두 정점을 잇는 간선 열

- 루프 : 한 정점에서 출발하여 자신으로 연결하는 간선

- 사이클 : 시작점과 끝점이 같은 경로

- 무 사이클 그래프 : 사이클이 없는 그래프, 트리

- 인접 : 두 정점이 간선으로 연결되었을 때 두 정점은 인접함

- 인접행렬 : 그래프의 표현 방법의 하나로 정점 사이의 인접성을 행렬로 나타낸 것

- 인접 리스트 : 그래프의 표현방법의 하나로 정점 사이의 인접성을 연결 리스트로 나타낸 것

- 그래프 탐색 : 그래프 내 특정 정점을 찾는 연산, 트리와 다르게 루트노드가 없으므로 특정 정점에서 시작함(트리에서 노드로 부르는 것을 그래프에서 정점이라 함)

- 그래프 순회 : 특정 정점에서 시작하여 그래프의 모든 정점을 빠짐없이 그리고 중복 없이 방문하는 것

- 깊이 우선 탐색 : 그래프 순회 알고리즘의 하나로 특정 정점에서 시작하여 자손을 먼저 방문 한 후(더 이상 방문할 자손이 없으면) 전 단계 형제를 방문함

- 너비 우선 탐색 : 특정 정점에서 시작하여 모든 형제를 방문한 후 자손을 방문함

- 최소 비용 신장 트리 : 그래프의 모든 정점을 포함하는 사이클이 없는 부분 그래프 즉, 트리를 신장트리라 함. 가중 그래프에서 비용이 최소인 신장 트리를 최소 비용 신장트리라 함.