1. 자료구조 개념 (1) 자료구조의 개요 1) 자료구조 ① 일련의 자료들을 조직하고 구조화하는 것 ② 자료의 표현과 그것과 관련된 연산 2) 자료구조에 따라 저장공간의 효율성과 프로그램의 실행시간이 달라짐 3) 어떠한 자료구조에서도 필요한 모든 연산들을 처리하는 것이.

1. 자료구조 개념 (1) 자료구조의 개요 1) 자료구조 ① 일련의 자료들을 조직하고 구조화하는 것 ② 자료의 표현과 그것과 관련된 연산 2) 자료구조에 따라 저장공간의 효율성과 프로그램의 실행시간이 달라짐 3) 어떠한 자료구조에서도 필요한 모든 연산들을 처리하는 것이 가능함

(2) 자료구조의 분류

2. 선형 구조 (1) 리스트 (List) 1) 리스트의 종류 ① 선형 리스트 : “연속적” ⇨ Array(배열) ② 연결 리스트 : “비연속적” ⇨ 포인터 2) 선형 리스트 (Linear List) ① 연속적인 기억장소에 저장된 리스트 (순차리스트 또는 연접리스트 (Dense List) 라고 함) ② 형태 : 임의의 노드에 접근을 할 때는 인덱스(Index) 를 사용 하므로 포인터가 없음

③ 장점 • 간단한 자료구조 • 저장 효율이 뛰어남 (기록밀도 : 1) • 접근 속도(Access Time) 가 빠름 ④ 단점 • 삽입과 삭제가 어려움 (삽입 및 삭제 시 삽입하거나 삭제할 위치 이후의 모든 자료의 이동이 필요)

3) 연결리스트 (linked list) ① 자료들을 임의의 기억공간에 기억시키고, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서료 연결시킨 자료구조 ② 형태 • 각 노드는 다음 노드를 가리키는 링크(Link, Pointer) 정보를 가짐 • 마지막 노드는 포인터 정보를 Null 값을 가짐 DATA(X) LINK(X)

③ 장점 • 자료의 삽입 및 삭제가 용이 (30번지에 고소영 데이터를 추가) • 비연속적 (한 리스트를 여러 개의 리스트로 분리하기 쉬움) • 희소 행렬 (행렬의 요소들 중에서 많은 부분이 0으로 되어 있는 행렬) 연결리스트로 표현 시 기억장소 이용효율이 좋음 ④ 단점 • Access Time 이 느림 • 기억장소 이용 효율이 나쁨 (저장되지 않은 빈 공간 발생) • 포인터를 위한 추가 공간이 필요 • 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘듦

⑤ 종류 • 단순 연결 리스트 (단순 링크드 리스트) • 이중 연결 리스트 • 단순 환형 연결 리스트

(2) 스택 (Stack) 1) 스택의 정의 ① An ordered list in which insertions and deletions are made at one end called the top. (top 이라고 하는 리스트의 한쪽 끝에서만 삽입과 삭제가 일어나 는 자료구조) ② 자료의 후입선출 (last-in-first-out) 방법

• Overflow 발생 : 스택의 크기가 M 일때, TOP > M 이면 Overflow 발생
POP PUSH TOP D C B A TOP : 자료의 삽입과 삭제가 이루어지는 스택공간의 위치를 표시하는 포인터 PUSH : 스택에서 자료의 삽입 POP : 스택에서 자료의 삭제 TOP Pointer BOTTOM • 자료의 삽입: TOP = TOP + 1 • 자료의 삭제: TOP = TOP - 1 • Overflow 발생 : 스택의 크기가 M 일때, TOP > M 이면 Overflow 발생

2) 스택의 용도 ① 인터럽트의 처리 ② 수식의 계산 (산술식 표현) ③ 서브루틴의 복귀번지 저장 (함수 호출의 순서 제어) 3) 순환적 프로그램을 처리하기 위한 요소 ① 스택 ② 복귀주소 ③ 순환에서 탈출하는 조건

4) 삽입 알고리즘 Top = Top + 1 If(Top > M) Then Stack_overflow Else Stack(top) ← data 4) 삭제 알고리즘 If(Top = 0) Then Stack_underflow Else data ← Stack(top) top = top - 1

An ordered list in which all insertions take place at one end and
(3) 큐 (Queue) 1) 큐의 정의 An ordered list in which all insertions take place at one end and all deletions take place at the opposite end. ((rear) 라고 하는 리스트의 한쪽 끝에서 삽입이 일어나고 (front) 라 부르는 반대쪽 끝에서 삭제가 일어나는 자료구조 (FIFO 구조 )) 2) 형태 A B C OUT IN Front Rear 3) 운영체제의 작업 스케줄링 등에 응용되는 것으로 가장 적합한 자료구조

(4) 데크 (Deque, Double Ended Queue) 1) 서로 다른 방향에서 입· 출력이 가능한 구조
(삽입과 삭제가 양쪽 끝에서 일어남) 2) 입력이 한쪽에서만 발생하고 출력은 양쪽에서 일어날 수 있는 입력제한과 입력은 양쪽에서 일어나고 출력은 한곳에서만 이루어 지는 출력제한이 있음 3) 스택과 큐를 복합한 형태 입력제한 데크 : 입력이 한 쪽 끝으로 제한 (Scroll) 출력제한 데크 : 출력이 한 쪽 끝으로 제한 (Shelf) 4) A generalization of a queue because it allows insertions and deletions at both end. (양 끝에서 삽입과 삭제가 가능하게 하도록 큐를 일반화한 것)

1. 비선형 구조와 선형 구조가 옳게 짝지어진 것은? (0106, 0303)
① 스택 (Stack) ②큐(Queue) ③트리(Tree) ④ 연결 리스트(Linked List) ⑤ 그래프(Graph) 가. 비선형 구조 : ①, ②, ⑤ 선형 구조 : ③, ④ 나. 비선형 구조 : ③, ⑤ 선형 구조 : ①, ②, ④ 다. 비선형 구조 : ①, ②, ③ 선형 구조 : ④, ⑤ 라. 비선형 구조 : ③ 선형 구조 : ①, ②, ④, ⑤ 2. 선형 구조가 아닌 것은? ( ) 가. 배열(array) 나. 스택(stack) 다. 큐(queue) 라. 트리(tree) 3. 비선형 자료 구조에 해당하는 것은? (0405) 가. 큐(Queue) 나. 데크(Deque) 다. 그래프(Graph) 라. 리스트(List)

4. 자료구조에 관한 설명 중 옳지 않은 것은? 0509 가. 스택은 LIFO구조로 복귀주소 (return address) 등에 이용된다. 나. 큐는 FIFO 구조로 작업 스케줄링 등에 이용된다. 다. 트리는 선형 구조이다. 라. 데크 (Deque) 는 서로 다른 방향에서 입,출력이 가능한 구조이다. 5. 선형 자료구조에 해당하지 않는 것은? 0103 가. Binary tree 나. Dense list 다. Doubly linked list 라. Stack 6. 연결 리스트 에 대한 설명으로 거리 (Linked List)가 먼 것은? (0109) 가. 노드의 삽입이나 삭제가 쉽다. 나. 노드들이 포인터로 연결되어 검색이 빠르다. 다. 연결을 해주는 포인터 (Pointer) 를 위한 추가 공간이 필요하다. 라. 연결 리스트 중에는 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘들다.

7. 희소 행렬을 링크드 리스트 (linked list) 로 표현할 때 가장 큰 장점은?
(0003, 0209) 가. 기억장소가 절약된다. 나. 임의 위치 액세스 (random access) 가 가능하다. 다. 이진 검색 (binary search) 이 가능하다. 라. 행렬간의 연산시간을 줄일 수 있다. 8. 다음 설명이 의미하는 것은? (0003, 0303) An ordered list in which insertions and deletions are made at one end called the top. 가. stack 나. queue 다. array 라. tree 9. 스택의 응용 분야와 거리가 먼 것은? (0109, 0405) 가. 운영체제의 작업 스케줄링 나. 함수 호출의 순서 제어 다. 인터럽트의 처리 라. 수식의 계산

10. 다음은 Stack 에 자료를 삽입 (Insert) 하는 알고리즘이다. 빈칸에 적합한
내용은? (0409) procedure Insert(data, n, top, Stack) if top n then call Stack-Full; ≥ top = top + 1; Stack(top) = ( ); end Insert 가. Top 나. data 다. top 라. data-1 11. 다음 설명이 의미하는 것과 가장 관련된 것은? (0010, 0305) An ordered list in which all insertions take place at one end and all deletions take place at the opposite end. 가. stack 나. queue 다. graph 라. tree

12. 운영체제의 작업 스케줄링 등에 응용되는 것으로 가장 적합한 자료구조
는? (0203, 0205, 0509) 가. 스택(Stack) 나. 큐(Queue) 다. 연결리스트(Linked List) 라. 트리(Tree) 13. 데크(deque) 에 대한 옳은 설명으로만 짝지어진 것은? (0603) ① 양 끝에서 노드의 삽입과 삭제가 모두 가능하다. ② 하나의 포인터를 사용한다. ③ Double Ended Queue 의 약자이다. ④ 선형 구조이다. 가. ①, ② 나. ①, ② ,③ 다. ①, ③, ④ 라. ①, ④

3. 비선형 구조 (1) 트리 (Tree) 1) 트리의 정의 ① Linked List 로 표현할 때 가장 효율적임 ② 계층형 구조 (hierarchical structure) 를 나타내기 편리함

2) 트리 용어 정리 A B D F G H E C 노드(Node) : 트리의 기본 구성요소
(A, B, C, D, E, F, G, H) 근노드(Root Node) : 가장 상위 노드 (A) 레벨(Level) : 근노드를 기준으로 특정 노드 까지의 경로 길이 (E의 레벨은 3) 조상노드(Ancestors node) : 특정 노드에서 루트에 이르는 경로상의 모든 노드 (D의 조상노드는 B, A) 자식노드 (Son Node) : 특정노드에 연결된 다음 레벨의 노드 (B의 자식노드는 D, E) 부모노드 (Parent Node) : 특정노드에 연결된 이전 레벨의 노드 (F의 부모노드는 D) 형제노드(Sibling) : 같은 부모를 가진 노드 (F의 형제노드는 G, H) 깊이(Depth, Height) : 트리의 최대 레벨 (옆 트리의 깊이는 4) 차수(Degree) : 특정 노드에 연결된 자식노드의 수 (D의 차수는 3) 단말노드(Terminal Node, Leaf Node) 트리의 제일 마지막에 위치한 노드 (F,G,H,E,C) 트리의 차수 . 트리의 노드 중 가장 큰 차수 . 옆 트리의 차수는 3 (D의 차수가 가장 크므로 D의 차수가 트리의 차수) 2) 트리 용어 정리 A B D F G H E C

루트,조상 50 레벨 1 30 80 레벨 2 20 40 60 90 레벨 3 10 70 100 레벨 4

3) 트리의 운행법 (Traversal) ① 운행법 정의 • 컴퓨터 기억 공간에 표현된 트리의 각 노드를 중복되지 않게 정해진 순서대로 전부 검색하여 트리의 정보에 관한 사항을 알고자 함 • 이진 트리의 운행법은 산술식의 표기법과 관련됨 ② 운행법 종류 A B D F G H E C

• preorder - root → left → right - A B D C E G H F • inorder - left → root → right - D B A G E H C F - It moves down the tree toward the left until a null node is reached. The null node's parent is then "visited", and the traversal continues with the node that is one to the right. If there is no move to the right, the traversal continues with the last unvisited node at the next higher level of the tree. (루트에서 시작하여 널 노드가 나올 때까지 왼쪽으로 내려간다. 널 노드의 부모는 “방문완료” 가 되고, 운행은 오른쪽으로 진행된다. 만약 오른쪽으로 갈 수 없다면, 운행은 트리의 다음 상위 레벨의 마지막으로 방문하지 않은 노드에서 계속된다.)

• postorder - left → right → root - D B G H E F C A

③ 수식의 표기법 • 산술식을 계산하기 위해 기억공간에 기억시키는 방법으로 이진트리를 사용함 • 표기법의 종류 - 중위 표기법 (Infix notation) 연산자가 피연산자 사이에 있는 표기법 - 후위 표기법 (Postfix notation, reverse Polish notation) 피연산자 뒤에 연산자가 표기되는 표기법 - 전위 표기법 (Prefix notation) 피연산자들 앞에 연산자를 표시하는 표기법

X = A + ( B + C ) * D = X * A ▶ 중위 표기법 A+ B + C * D + D ▶ 후위 표기법
① ② ③ = X B * C + A D ▶ 중위 표기법 A+ B + C * D ▶ 후위 표기법 A B C + D * + ▶ 전위 표기법 + A * + B C D

④ 표기법 변환 • 현재의 표기법에서 우선순위가 가장 높은 두 개의 피연산자와 한 개의 연산자를 바꾸고자 하는 표기법으로 바꿈, 바뀐 연산은 하나의 피연 산자로 생각하고 앞의 과정 반복 • 중위 표기법 → 후위 표기법 예) A/B-(C*D)/E AB/ CD* CD*E/ AB/CD*E/-

• 중위 표기법 → 전위 표기법 예) A/B-(C*D)/E AB/ *CD /CD*E -/AB/*CDE • 후위나 전위 표기법에서 중위 표기법으로 바꾸려면 산술식의 앞쪽에서 부터 연속된 2개의 피연산자와 하나의 연산자를 찾아 중위 표기법으로 바꾸는 과정을 반복함 예) -/AB/*CDE A/B C*D C*D/E A/B-C*D/E

4) 트리의 종류 ① 이진 트리 • 정의 - Degree 가 2 이하로 구성된 트리 • 특성 - 깊이가 k 인 이진 트리의 최대노드의 수 : 2k-1 - 이진 트리의 레벨 i 에서 최대노드의 수 : 2(i-1) - n0 = n2 + 1 (n0 : 이진 트리의 터미널노드, n2 :차수가 2인 노드 수)

②스레드(thread) 이진 트리 • 다음 중 비순환적인 이진트리 운행 알고리즘에서 스택을 사용하지 않고 낭비되는 널(NULL) 연결 필드를 활용하여 트리 운행에 필요한 다른 노드의 포인터로 사용하도록 고안된 이진트리 ③ AVL 트리 • 각 노드의 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1 이하인 이진 탐색 트리 • AVL : 트리의 장점 탐색시간이 빠름 ④ 균형 트리 • 트리의 단말노드의 레벨이 모두 같게 만든 트리 • 실제 레코드까지의 탐색 길이가 동일하게 색인부를 완전 균형트리로 구성

⑤ B-트리 • 한 노드 안에 있는 키 값은 오름차순을 유지함 • 루트와 리프(leaf) 를 제외한 모든 노드는 최소 (m/2) 개, 최대 m개의 서브트리를 가짐 • 루트(root) 노드는 리프(leaf)가 아닌 이상 적어도 두 개의 서브트리를 가짐 • 탐색, 추가, 삭제는 루트로부터 시작함 • 삽입과 삭제를 하여도 데이터 구조의 균형을 유지해야 함 • 순차 탐색은 각 노드를 중위 순회함으로써 좋은 성능을 발휘하지 못함 • B-트리는 인덱스 파일에서 인덱스를 구성하는 방법 중의 하나임

⑥ B+트리 • B-트리의 추가, 삭제 시 발생하는 노드의 분열과 합병 연산 과정을 줄일 수 있는 트리구조 • 단말노드가 아닌 인덱스 세트와 단말로드로 구성된 데이터 세트로 이루 어짐 ⑦ m-원 트리 • 한 노드가 최대 (m-1) 개의 키와 m 개의 를 subtree 갖도록 구성됨 • m-원 트리 구조는 키값의 일부분이 동일한 문자열이나 숫자로 구성된 자료를 표현하는데 효율적 ⑧ 신장트리 • 그래프에서 간선들이 사이클이 되지 않도록 만든 트리

6) 그래프 (Graph) ① 그래프의 정의 • 각각의 단위 정보를 링크로 연결하여 구조화시킨 자료 구조 • 정점 (vertex) : 노드들의 집합 • 간선(edge) : 정점들 사이의 상호 연결의 집합 임의의 점들의 쌍을 연결 ② 인접행렬 (Adjacency Matrix)

③ 인접 리스트

1. 다음 Tree의 Degree 와 터미널 노드의 수는? (0109, 0305)

2. 아래 그림에서 트리의 차수(degree)를 구하면? (0303, 0609)
가 나 다 라. 5

3. 아래 트리구조에 대하여 preorder 순서로 처리한 결과는? (0203, 0403)
가. a → b → d → c → e → g → h → f 나. d → b → g → h → e → f → c → a 다. a → b → c → d → e → f → g → h 라. a → b → d → g → e → h → c → f

4. 다음은 무엇에 대한 설명인가? (0203) It moves down the tree toward the left until a null node is reached. The null node's parent is then "visited", and the traversal continues with the node that is one to the right. If there is no move to the right, the traversal continues with the last unvisited node at the next higher level of the tree. 가. preorder traversal 나. postorder traversal 다. inorder traversal 라. BFS traversal

5. 다음 그림과 같은 이진트리를 후위 순회(postorder traversal) 한 결과는?
(0609) 가. + * * / A B C D E 나. A / B * C * D + E 다. + * A B / * C D E 라. A B / C * D * E +

6. 다음과 같이 주어진 후위표기방식의 수식을 중위표기방식으로 나타낸 것
은? (0305) ABC - / DEF + * + 가. A / (B - C) + F * E + D 나. A / (B - C) + D * ( E + F ) 다. A / (B - C) + D + E * F 라. A / (B - C) * D + E + F 7. 중위 표기식(Infix) 으로 표현은 아래 식에 대하여 후위 표기식(Postfix) 으로 옳게 기술한 것은? 0605 (A * B) + (C * D) 가. + A B * * C D 나. + * A B * C D 다. A B * C D * 라. * A B + * C D

8. Let us consider a binary tree with 6 leaf nodes. How many nodes
of degree two are in the binary tree? (0103) 가 나 다 라. 7 9. 이진트리의 특성에 대한 설명으로 옳지 않은 것은? (0106) (단 n0 = 단말 노드 수, n1 = 차수 1인 노드수 n2 = 차수 2인 노드 수, n = 노드의 총수, e = 간선의 총수) 가. n = e 나. e = n1 + 2n2 다. n = n0 + n1 + n2 라. n0 = n2 + 2 10. 다음 중 비순환적인 이진트리 운행 알고리즘에서 스택을 사용하지 않 고 낭비되는 널 (NULL) 연결 필드를 활용하여 운영하도록 고안된 이진 트리는? (9904, 0205) 가. 전 이진 트리 나. B+ 트리 다. 사향 이진 트리 라. 스레드(thread) 이진 트리

11. B- 트리가 가지는 성질이 아닌 것은 ? (9908, 0305) 가. 한 노드 안에 있는 키 값은 오름차순을 유지하다. 나. 모든 리프(leaf) 노드는 리프가 아닌 이상 적어도 두 개의 서브트리 를 갖는다. 다. 루트 (root) 노드는 리프가 아닌 이상 적어도 두 개의 서브트리를 갖는다. 라. 키 값의 삽입이나 삭제 시 트리의 총 노드 수는 변함이 없다.

4 정렬 (1) 정렬의 정의 (Sort) 1) To arrange items of information according to rules dependent upon a key of field contained in the items or records. (레코드나 데이터에 담긴 키 값에 따라 순서대로 나열하는 것) 2) Sort is the process by which list of items or records, normally disordered, is put into order according to some criterion base on the content of each record. (정렬은 정렬되지 않은 항목 또는 레코드의 리스트를 각 레코드의 값에 기초한 기준에 따라 순서 있게 나열하는 것이다.) 3) The process of rearranging an initially unordered sequence of records until they ordered. (초기에 정렬되지 않은 레코드의 순서를 정렬될 때까지 재배치 하는 과정)

(2) 정렬기법 1) 내부정렬기법 ① 정의 데이터량이 적을 때 주기억장치 내에서 정렬하는 방법 ② 특징 속도는 빠르나 정렬할 자료의 양이 많은 경우 부적합 ③ 종류 • 히프 정렬(heap sort) • 기수 정렬(radix sort) • 선택 정렬(selection sort) • 버블 정렬(bubble sort) • 퀵 정렬(quick sort) • 삽입 정렬 (insertion sort) • 쉘 정렬(shell sort)

2) 외부 정렬 기법 ① 정의 대용량의 데이터를 몇 개의 서브 파일로 나누어 각각 내부 정렬을 한 후에, 테이프나 디스크 내에서 각 서브 파일을 합병하는 방법 ② 특징 속도는 느리지만 정렬하고자 하는 자료의 양이 많을 경우 효과적 (주기억장치 + 보조기억장치) ③ 종류 • 진동 병합 정렬(oscillating merge sort) • 밸런스 병합 정렬(balanced merge sort) • 캐스캐이드 병합 정렬(cascade merge sort) • 폴리파즈 병합 정렬(polyphase merge sort)

(3) 정렬기법 종류 1) 버블 정렬 (bubble sort) The bubble sort arranges the adjacent record keys as a result of comparing these. That is, if they are not ordered, the two keys are exchanged each other. (버블정렬은 인접한 두 키를 비교한 결과로 정렬하는데 만약 비교 하였을 때 두 키의 순서가 다르다면 교환하고 그렇지 않다면 그대로 두는 방법이다.)

2) 삽입 정렬 (insertion sort)
① 이미 순서화된 파일에 새로운 하나의 레코드를 추가하여 순서에 맞게 배치 ② This sort algorithm is likely to occur to anyone who has sorted cancelled checks or playing cards by simply holding them in the hand and inserting them one by one into the proper position in the stack or hand of already sorted items. (이 정렬 알고리즘은 지급 완료 수표나 카드를 정렬된 채로 손에 쥐고 서 그것들 사이에 적당한 위치에 정렬되지 않은 것을 한 개씩 삽입할 때 발생할 수 있다.)

3) 선택 정렬 (insertion sort)
레코드의 최소값을 찾아 첫 번째 위치에 놓고 다음 최소값을 찾아 두 번째 위치에 놓는 방법을 반복하여 정렬함

4) 히프정렬 (heap sort) ① 연산 시간이 최악과 평균의 경우, 모두 0(nlogn) 으로 빠른 속도를 가짐 ② 전이진 트리(complete tree) 를 이용한 정렬 방식 ③ 이진 트리를 힙 정렬로 변환 • 주어진 레코드들을 순서대로 넣어 전이진 트리로 구성 • 전이진 트리의 노드의 역순으로 자식 노드와 부모 노드를 비교하여 큰 값을 위로 올림 • 교환된 노드들을 다시 검토하여 위의 과정 반복

예) 이진트리의 레코드 R=(88,74,63,55,37,25,33,19,26,14,9) 에 대하여 힙 (heap) 정렬을 만들 때, 37의 왼쪽과 오른쪽의 자식노드 (child node) 의 값은? < 37의 자식노드는 왼쪽 14, 오른쪽 9 >

5) 퀵 정렬 (quick sort) 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법으로 키를 기준으로 작은 값은 왼쪽에 큰 값은 오른쪽에 모이도록 서로 교환시키는 부분 교환 정렬법 6) 기수정렬 (radix sort) 레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬하는 기법

① 주어진 입력 파일을 크기가 2인 서브 파일로 모두 나누어서 각 서브 파일들을 정렬하는 방법 ② 정렬 방법
7) 2-way 합병 정렬 ① 주어진 입력 파일을 크기가 2인 서브 파일로 모두 나누어서 각 서브 파일들을 정렬하는 방법 ② 정렬 방법 • 두개의 키들을 한 쌍으로 하여 각 쌍에 대하여 순서를 정함 • 순서대로 정렬된 각 쌍의 키들을 합병하여 하나의 정렬된 서브 리스트로 만듬 • 위 과정의 정렬된 서브 리스트들을 하나의 정렬된 파일이 될 때까지 반복함 예) 입력 데이터가 R=(71, 2, 38, 5, 7, 61, 11, 26, 53, 42) 일 때 2-Way Merge Sort 를 한 후 결과는? 71 2 38 5 7 61 11 26 53 42

<1회전> 71, 2 38, 5 7, 61 11, 26 53, 42 정렬 정렬 정렬 2, 71 5, 38 7, 61 11, 26 42, 53 <2회전> 2, 71, 5, 38 7, 61, 11, 26 42, 53 정렬 정렬 2, 5, 38, 71 7, 11, 26, 61 42, 53

<3회전> 2, 5, 38, 71, 7, 11, 26, 61 42, 53 정렬 2, 5, 7, 11, 26, 38, 61, 71 42, 53 <4회전, 완료> 2, 5, 7, 11, 26, 38, 61, 71, 42, 53 정렬 2, 5, 7, 11, 26, 38, 42, 53, 61, 71

(4) 정렬 알고리즘의 선택 시 고려사항 1) 키 값들의 분포상태 2) 소요 공간 및 작업시간 3) 정렬에 필요한 기억공간의 크기 4) 데이터의 양 5) 초기 데이터의 배열상태 6) 사용 컴퓨터 시스템의 특성

1. 다음 영문이 의미하는 것은? (0209) To arrange items of information according to rules dependent upon a key of field contained in the items or records. 가. sort 나. overflow 다. matching 라. search 2. 주기억장치 내에서 이루어지는 정렬이 아닌 것은? (0109) 가. insertion sort 나. selection sort 다. cascade sort 라. shell sort 3. 다음 영문의 괄호 안에 적합한 정렬 방법은? (0106) The ( ) arranges the adjacent record keys as a result of comparing these. That is, if they are not ordered, the two keys are exchanged each other. 가. bubble sort 나. insert sort 다. heap sort 라. radix sort

4. 자료가 아래와 같이 주어졌을 때, 선택 정렬 (selection sort) 을 적용하
여 오름차순으로 정렬할 경우 pass 2 를 진행한 후의 정렬된 값으로 옳은 것은? (0503) 자료 : 9, 4, 5, 11, 8 가. 4, 5, 9, 8, 나. 4, 5, 9, 11, 8 다. 4, 5, 8, 11, 라. 4, 5, 8, 9, 11 5. 연산 시간이 최악과 평균의 경우, 모두 0(nlogn)으로 빠른 속도를 갖는 정렬 방식은? 0003 가. 퀵 정렬(quick sort) 나. 버블 정렬(bubble sort) 다. 히프 정렬(heap sort) 라. 선택 정렬(selection sort)

6. 이진트리의 레코드 R=(88,74,63,55,37,25,33,19,26,14,9) 에 대하여 힙 (heap) 정렬을 만들 때, 37의 왼쪽과 오른쪽의 자노드 (child node) 의 값은? (0303) 가. 55, 나. 63, 33 다. 33, 라. 14, 9 7. 정렬(Sort) 알고리즘의 선택 시 고려사항으로 거리가 먼 것은? (0007) 가. 증가 데이터의 배열상태 나. 키 값들의 분포상태 다. 소요 공간 및 작업시간 라. 정렬에 필요한 기억공간의 크기

5. 검색 (1) 검색기법 종류 1) 이진 검색 (binary search) ① 일정한 순서로 배열된 레코드를 2 개 부분으로 되풀이하여 나누어서, 한 부분은 버리고 남은 부분을 검색하는 방법 ② 자료가 반드시 정렬되어 있어야 함 (이진 검색의 선행 조건) ③ A quick method for searching an ordered, dense list for a particular record by successively looking at that half of the remaining portion of the list in which the record is known to be, is called a binary search. (정렬된 연접 리스트에서, 특정 레코드가 있다고 알려진 리스트의 남겨진 반쪽 부분을 되풀이하여 보면서 특정 레코드를 찾는 빠른 방법)

예) 1~10 사이의 수에서 9 를 찾고자 할 때 (1+10) / 2 = 5.5 → 5와 9를 비교, 9가 더 크므로 1~5 는 버림, 6~10 에서 다시 9를 검색 (6+10) / 2 = 8 → 8 과 9를 비교, 9가 더 크므로 은 6~8 버림, 9~10 에서 다시 9 검색 (9+10) / 2 = 9.5 → 9와 9비교, 같은 값이므로 검색 성공 총 3회 시도 2) 보간 검색 (Interpolation) 찾고자 하는 레코드 키가 있음직한 위치를 추정하여 검색하는 방법

(2) 해싱 (Hashing) 1) 키 값으로부터 레코드가 저장되어 있는 주소를 직접 계산하여, 산출된 주소로 바로 접근하는 방법, 키-주소 변환 방법이라고도 함 , 2) 검색 방법 중 속도는 가장 빠르지만 충돌현상 시 오버플로 해결의 부담이 과중되며, 많은 기억공간을 요구하는 검색 방법 3) 버킷 (bucket) 하나의 주소를 갖는 파일의 한 구역을 의미하며, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미 4) 슬롯 (slot) 한 개의 레코드를 저장할 수 있는 공간으로 n 개의 슬롯이 모여 하나의 버킷을 형성 5) 충돌 (collision) 레코드를 삽입할 때 2개의 상이한 레코드가 똑같은 주소로 해싱 되는 것을 의미 6) 동의어 (synonym) 해싱 함수의 값이 같은 키들의 집합

(3) 해싱함수의 종류 1) 중간제곱 방법 (mid-square) 레코드의 키를 제곱한 후 그 중간 부분의 값을 목적 주소로 사용하는 방법 2) 숫자분석 방법 (digit analysis) 레코드 키를 구성하는 수들이 모든 키들 내에서 각 자리별로 어떤 분포 인지를 조사하여 비교적 고른 분포를 나타내는 자릿수를 필요한 만큼 선택하여, 목적 주소로 사용하는 방법 3) 제산 방법 (division) 레코드의 키를 해시테이블의 크기보다 큰 소수로 나누는 방법 4) 중첩(접지) 방법 (Folding method) 주어진 키를 여러 부분으로 나누고, 각 부분의 값을 더하거나 배타적 논리합(XOR : Exclusive OR) 연산을 통하여 나온 결과로 주소를 취하 는 방법

5) 계수 분석 방법 (Digit Analysis Method)
주어진 모든 키 값들에서 그 키를 구성하는 자릿수들의 분포를 조사하여 비교적 고른 분포를 보이는 자릿수들을 필요한 만큼 택하는 방법 6) 기수 변환법 (Radix) 어떤 진법으로 표현된 주어진 레코드 키 값을 다른 진법으로 간주하고 키 값을 변환하여 홈 주소로 취하는 방식

(4) 오버플로 처리 방법 ① 재해싱 방법(Rehashing) 여러 개의 해싱함수를 준비하였다가 충돌 발생 시 새로운 해싱함수를 적용하여 새로운 해시표를 생성하는 방법 ② 개방 주소법(Open Addressing) 충돌(Collision) 이 발생했을 때 순서대로 다음 버킷에 저장하는 방법 ③ 체인 방법 오버플로우 발생 시 이를 별도의 기억 공간에 두고 링크로 연결하여 사용하는 방법

1. 괄호 속 내용으로 가장 적합한 것? (0603) A quick method for searching an ordered, dense list for a particular record by successively looking at that half of the remaining portion of the list in which the record is known to be, is called a ( ). 가. tree search 나. block search 다. binary search 라. sequential search 2. 다음과 같이 레코드가 구성되어 있을 때, 이진 검색 방법으로 14 를 찾을 경우 비교되는 횟수는? (0007, 0205, 0409) “ ” 가. 2번 나. 3번 다. 4번 라. 5번

3. 탐색 방법 중 키 값으로부터 레코드가 저장되어 있는 주소를 직접 계산하
여, 산출된 주소로 바로 접근하는 방법으로 키-주소 변환 방법이라고도 하는 것은? (0603) 가. 이진 탐색 나. 피보나치 탐색 다. 해싱 탐색 라. 블록 탐색 4. 해싱(Hashing) 에 관한 설명으로 옳지 않은 것은? (0103, 0405) 가. 버킷 (bucket) 이란 하나의 주소를 갖는 파일의 한 구역을 의미하며 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미한다. 나. 슬롯 (slot) 이란 한 개의 레코드를 저장할 수있는 공간으로 n 개의 슬롯이 모여 하나의 버킷을 형성한다. 다. 충돌 (collision) 이란 레코드를 삽입할 때 2 개의 상이한 레코드가 똑같은 버킷으로 해싱 되는 것을 의미한다. 라. 해싱은 충돌 (collision) 이 발생하면 항상 오버 플로우 (overflow) 가 발생한다.

5. 해싱함수 중 주어진 키를 여러 부분으로 나누고, 각 부분의 값을 더하거
나 배타적 논리합 (XOR : Exclusive OR) 연산을 통하여 나온 결과로 주 소를 취하는 방법은? (0505) 가. 중간 제곱 방법 (Mid-square method) 나. 제산 방법 (Division method) 다. 중첩 방법 (Folding method) 라. 기수 변환법 (Radix conversion method) 6. 해싱함수(Hashing Function) 의 종류가 아닌 것은? (0405) 가. 제곱 (mid-square) 방법 나. 숫자분석 (digit analysis) 방법 다. 체인 (chain) 방법 라. 제산 (division)방법

6. 파일조직 기법 (1) 파일조직 1) 막대한 양의 자료를 각종 매체에 저장하는 기법 2) 파일 편성 혹은 파일 구성 방법이라 함 (2) 인덱스 (Index) 1) 인덱스의 정의 ① 검색을 빠르게 하기 위해 만든 보조적인 데이터 구조 ② B트리, B+트리, 트라이 등의 자료구조를 사용하여 구현함 ③ 인덱스 파일 • 검색수를 줄이기 위해 다단계 인덱스를 사용 2) 인덱스의 특징 ① 인덱스는 하나 이상의 필드로 만들어도 됨 ② 인덱스를 통해서 테이블의 레코드에 대한 액세스를 빠르게 수행 할 수 있음

3) 트라이 (trie) ① 검색을 위한 키값을 직접 표현하지 않고 키를 구성하는 문자나 숫자 자체의 순서로 키값을 구성하는 구조 ② 트라이의 차수는 키 값을 표현하기 위해 사용하는 문자의 수(radix) 에 의해 결정함 ③ 키 값의 분포를 미리 예측할 수 있다면 기억장소를 절약할 수 있음 ④ 트라이의 크기는 나타내려고 하는 키 값의 기수와 키 필드 길이에 의해 결정됨 ⑤ 키 값이 문자열 또는 숫자일 경우 일련의 키 값들에 대해 일부분이 같은 문자나 숫자로 구성되었을 때, 즉 전체 키 값의 길이보다 키 값들 사이에 별개의 전위(prefix) 수가 작을 때 적합함 ⑥ 가변 길이의 키 값을 효과적으로 나타낼 수 있으며, 삽입 및 삭제 시 노드의 분열과 병합이 없음

4) 인덱스 구분 ① 정적 인덱스 • 데이터 파일의 레코드가 삽입되거나 삭제됨에 따라 인덱스의 내용 은 변하지만 구조 자체는 변하지 않음 ② 동적 인덱스 • 인덱스나 데이터파일을 블록으로 구성하고 각 블록에는 추가로 삽입될 레코드를 감안하여 빈 공간을 미리 예비해두는 인덱스 방법 • 레코드의 삽입으로 인해 블록에 레코드가 가득 차면 동적으로 분열 됨 • 레코드의 삭제로 인해 일정 수의 레코드가 블록에 유지되지 않으면 블록의 합병이 일어남

(3) 파일 편성 종류 1) 순차 파일 (Sequential file) ① 생성되는 순서에 따라 레코드를 순차적으로 저장하므로, 저장 매체 의 효율이 가장 높음 ② 프로그래밍이 쉬움 ③ 여러 개의 기록 매체에 기록이 가능 2) 직접파일 (Direct file) ① 특정 레코드에 접근하기 위해서 디스크의 물리적주소로 변환할 수 있는 함수를 사용 ② 해싱을 이용한 파일구조 ※ 직접 접근 방식(DAM: Directed Access Method) • 데이터의 입/출력이 빈번히 발생하는 곳에 응용 • 해싱 함수를 이용하여 레코드의 저장 위치를 결정 • 다른 레코드를 참조하지 않고 어떤 레코드를 접근할 수 있음

3) 인덱스 순차 파일 (ISAM, Indexed sequential access-method)
① 키 값에 따라 순차적으로 정렬된 데이터를 저장하는 데이터 지역 (Data Area) 과 이 지역에 대한 포인터를 가진 색인 지역 (Index Area) 으로 구성된 파일 ② 인덱스를 저장하기 위한 공간과 오버플로우 처리를 위한 별도의 공간 이 필요(기본 구역 (Prime data area), 색인 구역(Index area), 오버플로 구역(Overflow area) 으로 구성) • 기본 데이터 구역은 데이터 레코드를 저장 • 인덱스 구역은 데이터 구역에 대한 인덱스를 저장 • 독립된 오버플로우 구역은 기본 데이터 구역에서 오버플로우 된 레코드를 저장 ③ 데이터 파일은 기본구역과 오버플로 구성으로 구성

③ 데이터 파일은 기본구역과 오버플로 구성으로 구성
④ 실제 데이터 처리 외에 인덱스를 처리하는 추가적인 시간이 소모되므로 파일 처리 속도가 느림 ⑤ 순차 처리와 직접(랜덤) 처리가 모두 가능하지만 기억장소의 낭비 초래 ⑥ 인덱스 영역 구분 • 트랙 인덱스 • 마스터 인덱스 • 실린더 인덱스 ⑦ 레코드를 추가 및 삽입하는 경우 파일 전체를 복사할 필요가 없음

4) VSAM (Virtual Storage Access Method)
① 동적 인덱스 방법을 이용한 색인 순차 파일 ② 기본 데이터 영역과 오버플로우 영역을 구분하지 않음 ③레코드를 삭제하면 그 공간을 재사용 할 수 있음 ④ 제어 구간에 가변 길이 레코드를 쉽게 수용할 수 있음 5) 다중 키 파일 (multi key file) ① 하나의 데이터 파일에 여러 개의 접근 방법을 제공하는 구조 ② 다중 키 파일의 특징 • 하나의 데이터 파일에 여러 개의 접근 방법을 지원함 (순차처리와 임의처리 모두 가능) • 파일의 중복성이 제거되고 자료의 무결성이 유지됨

6) 다중 키 파일의 종류 ① 역파일 (inverted file) • 여러 개의 역 인덱스를 통해서 자료에 접근할 수 있도록 된 파일 • 역색인 (index) 은 레코드의 필드와 주소 또는 필드와 기본키의 쌍으로 구성 • 역 인덱스만을 검색해 많은 질의에 바로 응답할 수 있음 • 역파일의 특징 - 검색 속도가 빠름 - 데이터 파일에 접근하지 않아 질의응답 시간이 줄어들고, 처리가 비교적 쉬움 - 질의를 만족하는 레코드 검색 시 한번 씩만 접근하면 됨

② 다중 리스트 파일 (multi-list file)
• 각 키에 대하여 인덱스를 만든 후 각 데이터 레코드들 간에 다중 리스트를 구축하여 구성 • 자료파일에서 특정항목(필드) 의 같은 자료 값들을 가진 레코드들을 포인터로 연결한 리스트 형태의 파일 • 필드의 항목 값과 시작 포인터 쌍으로 된 인덱스에서 자료검색이 시작 • 레코드에 포인터 필드가 추가됨

• 역 인덱스 방식은 질의문 처리 능력에서 더 우월할 수가 있음 • 역 인덱스 방식은 이 인덱스를 사용하지 않는 프로그래머에게
③ 역파일과 다중 리스트 파일의 비교 구 분 역파일 다중 리스트 파일 포인터 수 데이터 레코드 수만큼 데이터 레코드 중에서 한 개의 레코드 인덱스 형태 가변 길이 고정 길이 데이터 레코드 파일 구조 영향 없음 포인터 필드추가 • 다중 리스트 방식은 인덱스 관리가 더 용이 • 역 인덱스 방식은 질의문 처리 능력에서 더 우월할 수가 있음 • 역 인덱스 방식은 이 인덱스를 사용하지 않는 프로그래머에게 더 투명함

(4) 파일의 구조 결정시 고려사항 1) 사용할 보조 기억장치의 유형 2) 응용이 필요로 하는 파일 연산의 유형 3) 파일 활동 비율 (file activity ratio) 4) 트랜잭션이나 검색 요청에 대한 응답 시간 5) 파일저장 매체의 접근 특성 6) 자료처리의 주기 7) 자료처리 순서

1. 인덱스 파일에서 다단계 인덱스를 사용하는 주된 이유는? (9910)
가. 탐색수를 줄인다. 나. 인덱스 크기를 줄인다. 다. 인덱스에 삽입 삭제가 편리하다 , . 라. 논리적으로 관련된 데이터들을 물리적으로 집중시킨다. 2. 인덱스 에 대한 설명으로 부적절한 것은 (Index) ? (0007) 가. 인덱스는 데이터베이스의 물리적 구조와 밀접한 관계가 있다. 나. 인덱스는 하나 이상의 필드로 만들어도 된다. 다. 레코드의 삽입과 삭제가 수시로 일어나는 경우는 인덱스를 최소화 한다. 라. 인덱스를 통해서 테이블의 레코드에 대한 액세스를 빠르게 수행할 수 있다.

3. 트라이 색인에 대한 설명으로 옳지 않은 것 (trie)은? (0103, 0209)
가. 키 탐색을 위해 키 값을 직접 표현한다. 나. 트라이의 차수는 키 값을 표현하기 위해 사용하는 문자의 수 (radix) 에 의해 결정한다. 다. 키 값의 분포를 미리 예측할 수 있다면 기억장소를 절약할 수 있다. 라. 트라이의 크기는 나타내려고 하는 키 값의 기수와 키 필드 길이에 의 해 결정된다. 4. 키 값이 문자열 또는 숫자일 경우 일련의 키 값들에 대해 일부분이 같은 문자나 숫자로 구성되었을 때, 즉 전체 키 값의 길이보다 키 값들 사이에 별개의 전위 (prefix) 수가 작을 때 적합하고, 가변 길이의 키 값을 효과적 으로 나타낼 수 있으며, 삽입 및 삭제 시 노드의 분열과 병합이 없는 특징 을 가진 색인구조는? (0106) 가. B* - 트리 색인 나. 트라이 (trie) 색인 다. B - 트리 색인 라. B+ - 트리 색인

5. 파일에 대한 설명 중 옳지 않은 것은? (0103, 0209) 가. 순차 파일 (Sequential file) 은 생성되는 순서에 따라 레코드를 순차적으로 저장하므로, 저장 매체의 효율이 가장 높다. 나. 직접파일 (Direct file) 은 특정 레코드에 접근하기 위해서 디스크의 물리적인 주소로 변환할 수 있는 함수를 사용한다. 다. 색인 순차 파일 (Indexed sequential file) 은 순차 및 직접 접근 형태를 모두 지원할 수 있으나, 기억 장소의 낭비를 초래한다. 라. VSAM 파일 (Virtual storage access method file) 은 검색속도를 빠르게 하기 위하여, 기본 데이터 구역과 오버플로우 구역을 구분 하여 갖추어야 한다. 6. 직접 접근 방식(DAM: Directed Access Method)에 대한 설명으로 거리 가 먼 것은? (0603) 가. 데이터의 입/출력이 빈번히 발생하는 곳에 응용하는 것이 좋다. 나. 해싱 함수를 이용하여 레코드의 저장 위치를 결정한다. 다. 다른 레코드를 참조하지 않고 어떤 레코드를 접근할 수 있다. 라. 기억 공간의 효율성이 매우 좋다.

7. 인덱스 순차 파일 (ISAM : Indexed sequential access-method) 에 대한
설명으로 옳지 않은 것은? (0503) 가. 인덱스를 저장하기 위한 공간과 오버플로우 처리를 위한 별도의 공간 이 필요하다. 나. 실제 데이터 처리 외에 인덱스를 처리하는 추가적인 시간이 소모되므 로 파일 처리 속도가 느리다. 다. 인덱스 영역은 실린더 색인 영역 섹터 색인 영역, 트랙 색인 영역으로 구분 된다. 라. 순차 처리와 직접 처리가 모두 가능하다. 8. 파일에 대한 설명으로 거리가 먼 것은 VSAM ? (0305) 가. 기본 데이터 영역과 오버플로우 영역을 구분하지 않는다. 나. 레코드를 삭제하면 그 공간을 재사용 할 수 있다. 다. 제어 구간에 가변 길이 레코드를 쉽게 수용할 수 있다. 라. 특정 레코드에 대해 빠르고 직접적인 접근을 지원할 수 있기 때문에 대화형 처리에 많이 이용된다.

9. 역파일 (inverted file) 에 관한 설명으로 옳지 않은 것은? (0003)
가. 검색 속도가 빠르다. 나. 데이터 파일에 접근하지 않아 질의응답 시간이 줄어들고, 처리가 비교 적 쉽다. 다. 질의를 만족하는 레코드 검색 시 한번 씩만 접근하면 된다. 라. 색인의 각 항의 길이가 고정적이므로 기억 공간이 절약된다. 10. 다양한 파일 조직 방법 중에서 응용에 적합한 파일 조직을 선택하는데 영향을 주는 요인들로만 구성된 것은? (0403) ㉠사용할 보조 기억장치의 유형 ㉡ 응용이 필요로 하는 파일 연산의 유형 ㉢ 파일 활동 비율(file activity ratio) ㉣ 트랜잭션이나 검색 요청에 대한 응답 시간 가. ㉠㉡㉢㉣ 나. ㉡㉢㉣ 다. ㉠㉡㉢ 라. ㉠㉡

Similar presentations

Similar presentations

About project

지원

로그인

Auth with social network:

Similar presentations

Similar presentations

About project

지원