[정처산기_필기]Chapter03-1_데이터베이스 이해/02

스택(Stack)의 응용분야로 거리가 먼 것은?

- 작업 스케줄링

스택 응용 분야는 인터럽트 처리, 함수 호출, 후위표현연산(수식 계산), 깊이 우선 탐색(DFS)이 있다.

자료구조의 특성을 고려할 때 다음 중 큐의 응용 분야로 가장 적합한 작업은?

- 운영체제의 작업 스케줄링

큐의 응용 분야는 운영체제의 작업 스케줄링, 메시지 전송 등이 있다.

다음 트리를 전위 순회(Proder Traversal) 한 결과는?

- +**/ABCDE

전위 순회는 먼저 노드를 방문하고 왼쪽 서브 트리를 방문한 후, 오른쪽 서브트리를 방문하는 순으로 순회 하는 방식이다.
전위 순회 계산식은 '루트 > 좌 > 우' 순서대로 노드 방문
따라서 +**/ABCDE

노드의 수가 N개인 이진 트리를 연결 리스트로 표현한 경우 NULL 포인터 수는?

- N+1

노드의 수가 N 개인 이진트리를 연결 리스트로 표현한 경우 NULL 포인터 수는 N+1 개이다.

다음 중 최악의 경우 검색 효율이 가장 나쁜 트리 구조는 ?

- 이진 탐색 트리

트리의 경우 노드가 왼쪽이나 오른쪽 한 곳만 노드가 존재하게 될 경우 효율이 매우 나쁘다.
AVL, 2-3 트리, 레드-블랙 트리를 통해서 전체 트리 균형을 맞춰주지만, 이진 탐색 트리는 균형을 맞춰주지 않으므로 최악의 경우 이진 탐색 트리의 검색 효율이 가장 나쁘다.

분할과 정복(Divide and Conquer)방법에 의한 정렬은?

- 퀵 정렬

퀵 정렬, 합병 정렬은 분할과 정복 방법에 의한 정렬 알고리즘이다.

n개의 원소를 정렬하는 방법 중 평균 수행시간 복잡도와 최악 수행시간 복잡도가 모두 O(nlog2n)인 정렬은?

- 힙 정렬

정렬에서 최악의 상황인 경우에 수행 속도가 가장 빠른 것은?

- 힙 정렬

위의 표 참고!

힙 정렬(Heap Sort)에 대한 설명으로 틀린것은?

- 최악의 수행시간은 O(2n 4승)이다.

힙 정렬은 정렬할 입력 레코드 들로 힙을 구성하고 가장 큰 키 값을 갖는 루트 노드를 제거하는 과정을 반복하여 정렬하는 알고리즘이다.
왼전이진 트리로 입력 자료의 레코드를 구성한다.

해싱 함수 기법중 주어진 모든 킷값을 이루는 숫자의 분포를 분석하여 비교적 고른 분포를 보이는 자릿수들을 필요한 만큼 선택해서 홈 주소로 사용하는 방식은?

- 계수 분석법(Digit Analysis Method)

제산법 (Division Method)	나머지 연산자(%)를 사용하여 테이블 주소를 계산하는 방식
폴딩법 (Folding Method)	레코드 키를 여러부분으로 나누고, 나눈 부분의 각 숫자를 더하거나 XOR 한 값을 홈 주소로 사용하는 방식
기수 변환법 (Radix Conversion Method)	어떤 진법으로 표현된 주어진 레코드 키를 다른 진법으로 간주하고 키를 변환하고 홈 주소를 얻는 방식
숫자분석법(= 계수 분석법) (Digit Analysis Method)	레코드 키를 구성하는 수들이 모든 키들 내에서 자리별로 어떤 분포인지를 조사하여 비교적 고른 분포를 나타내는자릿수를 필요한 만큼 선택하여, 레코드의 홈 주소로 사용하는 방법

입력데이터가 R =(71, 2, 38, 5, 7, 61, 11, 26, 53, 42)일 때 2-Way Merge Sort 를 2회전 한 후 결과는?

- R = (2, 5, 38, 71, 7, 11, 26, 61, 42, 53)

앞에서부터 순서대로 2개씩 그룹으로 묶은 후 각각의 그룹 안에서 정렬한다.(그룹이 홀수개일 경우 맨 마지막 그룹을 제외하고 2개씩 묶는다.)

키 값을 여러 부분으로 분류하여 각 부분을 더하거나 XOR하여 주소를 얻는 해싱 함수 기법은?

- Folding

정렬 알고리즘 중 다음의 설명에 해당하는 것은?

n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고, 나머지(n-1)개 중에서 다시 최솟값을 찾아 두번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 알고리즘이다.

- Selection Sort

선택정렬 (Selection Sort)	n 개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고 나머지 (n -1)개 중에서 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 알고리즘
삽입 정렬 (Insertion Sort)	2번째키와 첫 번째 키를 비교하여 순서대로 나열하고, 이어서 3번째 키를 1,2 번째 키와 비교해 순서대로 나열하고 계속해서 n번째 키를 앞의 (n-1)개 키와 비교하여 알맞은 순서에 삽입하는 알고리즘
거품 정렬 (Bubble Sort)	인접한 2개의 레코드 키값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 알고리즘
힙 정렬 (Heap Sort)	정렬할 입력 레코드들로 힙을 구성하고 가장 큰 키 값을 갖는루트 노드를 제거하는 과정을 반복하여 정렬하는 알고리즘

다음 자료를 버블 정렬을 이용하여 오름차순으로 정렬할 경우 PASS 2의 수행 결과는?

9,6,7,3,5

- 6,3,5,7,9

초깃값	9,6,7,3,5	첫 번째 값과 두 번째 값을 비교하여 큰 값을 뒤로 이동
PASS1	6,9,7,3,5	두 번째 값과 세 번째 값을 비교하여 큰 값을 뒤로 이동
	6,7,9,3,5	세 번째 값과 네 번째 값을 비교하여 큰 값을 뒤로 이동
	6,7,3,9,5	네 번째 값과 다섯 번째 값을 비교하여 큰 값을 뒤로 이동
	6,7,3,5,9	다시 첫 번쨰 값과 두 번째 값을 비교하여 큰 값을 뒤로 이동
PASS2	6,7,3,5,9	두번째 값과 세번째 값을 비교하여 큰 값을 뒤로 이동
	6,3,7,5,9	세번째 값과 네번째 값을 비교하여 큰 값을 뒤로 이동
	6,3,5,7,9	마지막 값(5번째 값)은 PASS 1 때 가장 큰 값이므로 PASS2 종료

다음 자료를 삽입 정렬을 이용하여 오름차 순으로 정렬할 경우 "pass 5"의 결과는?

32,14,15,38,27,6,21

- 6,14,15,27,32,38,21

초깃값	32,14,15,38,27,6,21	처음에 첫 번째에 있는 32는 정렬되어 있다고 가정
pass1	14,32,15,38,27,6,21	두 번째 있는 14를 이미 정렬되어 있는(32)에 삽입 (32보다 작으므로 32 앞으로 이동)
pass2	14,15,32,38,27,6,21	세 번째 있는 15를 이미 정렬되어 있는 (14,32)에 삽입 (14보다 크고 32 보다 작으므로 32 앞으로 이동)
pass3	14,15,32,38,27,6,21	네 번째 있는 38을 이미 정렬되어있는곳에 삽입 (32 보다 크므로 32 뒤로 이동)
pass4	14,15,27,32,38,6,21	다섯 번째 있는 27을 삽입 (15보다는 크고, 32 보다 작으므로 32 앞으로 이동)
pass5	6,14,15,27,32,38,21	여섯 번째 있는 6을 삽입 (14보다 작으므로 14앞으로 이동)

다음 자료에 65를 찾기 위하여 2진 검색할 경우 비교해야 할 횟수는??

3,18,47,54,65,83,94,97

- 3