자료구조
-
자료구조 12장 연습문제 풀이자료구조 2021. 12. 7. 02:09
1. 다음의 키값에 대한 버킷 주소를 결정하여라. 해시 테이블의 버킷 수는 256개이며, 알파벳 'a~z'의 아스키 코드값 97~122를 사용하여라. [tree, heap, deap, list] ① 중간 제곱 함수를 이용하여 주소를 구하여라. tree = t + r + e + e = 116 + 114 + 101 + 101 = 432 (432)10 = (110110000)2 (110110000)2 = 101101100100000000 (11001000)2 = (200)10 이므로 tree의 주소는 200 heap = h + e + a + p = 104 + 101 + 97 + 112 = 414 (414)10 = (110011110)2 (110011110)2 = 101001110110000100 (111001..
-
자료구조 11장 연습문제 풀이자료구조 2021. 12. 7. 01:34
1. 다음의 자료들을 정렬하여라. 34, 27, 19, 51, 8, 24, 11 ① 선택 정렬을 사용하여 정렬하여라. 8-27-19-51-34-24-11 8-11-19-51-34-24-27 8-11-19-51-34-24-27 8-11-19-24-34-51-27 8-11-19-24-27-51-34 8-11-19-24-27-34-51 ② 버블 정렬을 사용하여 정렬하여라. (34, 27)-19-51-8-24-11 27-(34, 19)-51-8-24-11 27-19-(34, 51)-8-24-11 27-19-34-(51, 8)-24-11 27-19-34-8-(51, 24)-11 27-19-34-8-24-(51, 11) 27-19-34-8-24-11-51 (27, 19)-34-8-24-11-51 19-(27, 34..
-
자료구조 10장 연습문제 풀이자료구조 2021. 11. 26. 14:21
1. 정점이 8개인 무방향 완전 그래프의 간선의 수는 몇 개인가? 답 : 28개 ? : (8 x 7) / 2 = 28 2. 다음 그래프를 인접 행렬과 인접 리스트로 표현하여라. 답 : 인접행렬 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 인접 리스트 3. 다음 그래프의 깊이 우선 신장 트리와 너비 우선 신장 트리를 구하여라. 답 : 깊이 수선 = A-B-D-E-F-C-G / 너비 우선 = A-B-C-D-E-F-G 4. 다음 가중치 그래프의 최소 비용 신장 트리를 구하여라. 답 : 5. 비선형 구조와 선형 구조가 옳게 짝지어진 것은? ① 스택 ② 큐 ③ 트리 ④ 연결 리스트 ⑤ 그래프 가. 비선형 구조 : ①, ②, ⑤ 선형 구조 : ③, ④ 나. 비선형 구조 : ③, ⑤ . 선형 구조 : ①..
-
자료구조 9장 연습문제 풀이자료구조 2021. 11. 12. 14:08
1. 다음 중 선형 자료구조가 아닌 것은? 가. 리스트 나. 스택 다. 큐 라. 트리 답 : 라. 트리 ? : 트리는 비선형 자료구조이다. 2. 다음의 수식 이진 트리를 후위 순회하여 수식에 대한 후위 표기식을 구하여라. + * * A B C D 답 : AB*CD*+ 3. 다음 중 같은 개수의 노드를 트리로 저장하는 경우 트리의 높이가 가장 큰 트리는 무엇인가? 가. 이진 트리 나. 포화 이진 트리 다. 완전 이진 트리 라. 편향 이진 트리 답 : 라. 편향 이진트리 ? : 편향 이진 트리는 왼쪽이나 오른쪽 서브트리만 가지는 이진 트리이기 때문에 높이가 가장 높다. 4. 20개의 노드로 구성된 이진 트리에서 간선의 개수와 가능한 최대 높이와 최소 높이를 구하여라. 답 : 간선의 개수 = 19 최대 높이 ..
-
자료구조 8장 연습문제 풀이자료구조 2021. 10. 22. 00:51
1. 일상생활에서 발견할 수 있는 큐의 예를 설명하여라. 답 : 줄을 서서 기다리는 사람들 ? : 큐는 FIFO(First In First Out)의 방식이다. 2. 큐와 스택의 구조를 비교하여 설명하여라. 답 : 큐는 FIFO이기 때문에 먼저 들어간 자료가 먼저 나오고, 스택은 LIFO 구조이기 때문에 마지막에 들어간 자료가 먼저 나온다. 3. 1차원 배열의 선형 큐에서 잘못된 포화 상태 문제를 해결하는 방법을 설명하여라. 답 : 원소들을 비어 있는 앞 인덱스로 이동 4. [가→나→다→라] 순서로 큐에 원소를 삽입한 후에 모두 삭제하면 어떤 순서로 삭제되는지 설명하여라. 답 : [가→나→다→라] ? : 큐는 FIFO이기 때문에 삽입된 순서대로 삭제된다. 5. 원형 큐의 삭제 알고리즘을 순서대로 나열하여..
-
자료구조 7장 연습문제 풀이자료구조 2021. 10. 22. 00:19
1. 주변에서 LIFO(Last In First Out) 방식을 사용하는 스택의 예를 찾아 설명하시오. 답 : 웹 브라우저 뒤로 가기(가장 나중에 열린 페이지로 시작해서 되돌아간다. 2. 스택의 응용에서 다음의 수식을 후위 표기법으로 표기했을 때 옳은 것은? (((A / B) + C) - (D * E)) 가. A / B + C - D * E 나. AB / C + DE *- 다. A / B + C -* DE 라. AB / C + - DE * 답 : 나. AB / C + DE *- ? : 중위 표기법의 수식을 후위 표기법으로 변환하는 방법 1) 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다. 2) 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다. 3) 괄호를 제거한다. (..
-
자료구조 6장 연습문제 풀이자료구조 2021. 10. 21. 22:34
1. 순차 자료구조 방식과 연결 자료구조 방식을 비교 설명하시오. 답 : 순차 자료구조에서의 연산 시간에 대한 문제와 저장 공간에 대한 문제를 개선한 연결 자료구조는 다음 원소의 주소에 의해 순서가 연결되는 방식이기 때문에 순차 자료구조와 달리 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다. 2. 단순 연결 리스트와 원형 연결 리스트, 이중 연결 리스트의 특징을 설명하시오. 답 : 단순 연결 리스트는 단방향을 가리키고, 원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리킴, 이중 연결 리스트는 양방향을 가리키고 첫 번째, 마지막 노드가 서로를 가리키는 모습을 하고 있다. 3. 다음 참조 변수에 대한 연산의 의미를 설명하시오. ① p = p.link; ② p = q; ③ p.link = q; ..
-
자료구조 5장 연습문제 풀이자료구조 2021. 10. 21. 22:13
1. 8개의 원소가 있는 선형 리스트에서 3번 자리에 새로운 원소를 삽입하려면 몇 개의 원소를 이동해야 하는가? 답 : 5 ? : (마지막 원소의 인덱스 - 삽입할 자리의 인덱스) + 1 = (7 - 3) + 1 = 5 2. 선형 리스트 A를 2차원 배열 A[5][3]으로 표현했을 때, A[3][1] 원소는 몇 번째 원소인가? 행 우선 순서 방법과 열 우선 순서 방법에 따라 각각 구하시오. 답 : 행 우선 순서 방법 = 10 / 열 우선 순서 방법 = 8 ? : 2차원 배열 A[ni][nj]일 때 행 우선 순서 방법 = i x nj + j / 열 우선 순서 방법 = j x ni x i A[3][1] = 3 x 3 + 1 = 10 / 1 x 5 + 3 = 8 3. 시작위치가 100번지이고 원소의 길이가 5..