새발블로그

01 해싱에서 충돌은 언제 발생하는가? (1) 키가 같은 경우 (2) 해시 함수의 값이 같은 경우 (3) 같은 해시 함수를 사용하는 경우 (4) 키의 길이가 같은 경우 02 크기가 13인 해쉬 테이블에서 입력 자료 27과 130은 어떤 인덱스로 매핑되는가? 해싱 함수는 h(key)=key%13라고 하자. (A)1, 10 (B)13, 0 (C)1,0 (D)2,3 03 크기가 11인 해싱테이블을 가정하자. 해시함수로는 다음을 사용한다. h(k)=k mod 11 입력 자료가 다음과 같은 순서로 입력된다고 하면 아래의 각 경우에 대하여 해시테이블의 내용을 그려라. 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, 5 (1) 충돌을 선형조사법을 사용하여 처리한다. (2) 충돌을 이차조사법을 ..

01 이진 탐색 알고리즘의 특징이 아닌 것은? ① 탐색 효율이 좋고 탐색 시간이 적게 소요된다. ② 검색할 데이터가 정렬되어 있어야 한다. ③ 피보나치 수열에 따라 다음에 비교할 대상을 선정하여 검색한다. ④ 비교를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어든다. 02 키 값 28을 가지고 아래의 리스트를 탐색할 때 다음의 탐색 방법에 따른 탐색 과정을 그리고 탐색 시에 필요한 비교 연산 횟수를 구하여라. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 8 11 12 15 16 19 20 23 25 28 29 31 33 35 38 40 (1) 순차 탐색 (2) 이진 탐색 (3) 보간 탐색 03 AVL 트리에서 회전은 언제 이루어지는가? (1) 삽입 전 (2) 삽입 후..

01 다음 초기 자료에 대하여 삽입 정렬(Insertion Sort)을 이용하여 오름차순 정렬한 경우 PASS 1의 결과는? 초기 자료 : 8, 3, 4, 9, 7 ① 3, 4, 8, 7, 9 ② 3, 4, 9, 7, 8 ③ 7, 8, 3, 4, 9 ④ 3, 8, 4, 9, 7 02 다음 자료를 버블 정렬을 이용하여 오름차순으로 정렬할 경우 PASS 1의 결과는? 9, 6, 7, 3, 5 ① 3, 5, 6, 7, 9 ② 6, 7, 3, 5, 9 ③ 3, 5, 9, 6, 7 ④ 6, 3, 5, 7, 9 03 다음 자료에 대하여 "선택 정렬"을 사용하여 오름차순으로 정렬할 경우 PASS 3의 결과는? 초기 상태 : 8, 3, 4, 9, 7 ① 3, 4, 7, 9, 8 ② 3, 4, 8, 9, 7 ③ 3, 8..

01 다음의 그래프에서 가능한 신장 트리를 모두 나열하라. 02 아래의 네트워크에 대하여 Kruskal의 MST 알고리즘을 이용해서 최소비용 신장 트리가 구성되는 과정을 보여라. 03 앞의 네트워크에 대하여 Prim의 MST알고리즘을 이용해서 최소비용 신장 트리가 구성되는 과정을 보여라(A번 정점으로 시작할 것). 04 Prim의 함수에서 distance[]와 selected[]의 값을 출력하는 문장을 삽입하여 출력하여 보고 이들의 의미를 설명하라. 05 다음의 방향그래프에서 정점 0에서 다른 모든 정점까지의 최단 경로의 길이를 구하여라. 본문에서와 같이 다음의 표에 각 단계에서의 distance 배열의 값과 선택된 정점들을 나타내어라 단계 선택된 정점 found 배열 distance배열 1 2 ... ..

01 인접 행렬 adj_mat[][]에서 어떤 정점 v의 진출 차수를 알고 싶으면 어떻게 하면 되는가? (1) 인접 행렬의 v번째 행의 값들을 전부 더한다. (2) 인접 행렬의 v번째 열의 값들을 전부 더한다. (3) 인접 행렬의 v번째 행의 값들을 전부 더해서 2로 나눈다. (4) 인접 행렬의 v번째 열의 값들을 전부 더해서 2로 나눈다. 02 인접 행렬이 {0,1,0,0},{1,0,0,0}{0,1,0,0},{0,1,0,0} 이라면 여기에 대응되는 인접 리스트를 그려라. 03 정점의 개수를 n, 간선의 개수를 e라고 할 때, 인접 행렬에서 특정 정점의 차수를 계산하는 연산의 시간 복잡도는? (a) O(log₂n) (b) O(n) (c) O(n+e) (d) O(e) 04 정점의 개수를 n, 간선의 개수가..

01 히프트리에서 노드가 삭제되는 위치는 어디인가? ① 루트 ② 마지막 노드 ③ 가장 최근에 삽입된 노드 ④ 가장 먼저 삽입된 노드 02 히프를 배열로 표현할 수 있는 이유는 무엇인가? ① 완전 이진 트리이기 때문에 ② 어느 정도 정렬되어 있기 때문에 ③ 이진 트리이기 때문에 ④ 히프 조건을 만족하기 때문에 03 히프 연산 중에서 하나의 노드가 삽입되거나 삭제되는 시간은 무엇에 비례하는가? ① 노드의 개수 ② 트리의 높이 ③ 항상 일정하다. ④ 예측 불가능하다. 04 다음 중 히프 정렬이 특히 유용하게 사용될 수 있는 경우는? ① 데이터 100개 중에서 오름차순으로 20개만 뽑고자 할 때 ② 비교적 데이터의 개수가 적을 때 ③ 정렬의 대상이 되는 레코드의 크기가 클 때 ④ 데이터가 역순으로 정렬되어 있을..

01 다음 트리에 대한 중위 순회 결과는? 02 다음 트리를 전위 순회로 운행할 경우 다섯 번째로 탐색되는 것은? 03 다음 그림과 같은 이진트리를 후위 순회(postorder traversal)한 결과는? 04 다음 트리에서 단말 노드 수는? 05 다음 그림에서 트리의 차수는? 06 Y=A*B*C/D 를 후위 표기 수식으로 표기하면? 07 이진 트리에서 높이가 5일 때, 이 트리는 최대 몇 개의 노드를 가질 수 있는가? 08 NULL 포인터를 트리의 순회에 이용하는 트리를 무엇이라 하는가? (1)완전 이진 트리(complete binary tree) (2)포화 이진 트리(full binary tree) (3)스레드 이진 트리(threaded binary tree) (4)경사 트리(skewed tree)..

01 다음은 연결 리스트를 이용하여 스택을 표현한 것이다. 이에 대한 설명으로 옳지 않은 것은? (단, push는 스택에 자료를 삽입하는 연산이고, pop은 스택에서 자료를 삭제하는 연산이다) ①스택에 가장 최근에 입력된 자료는 top이 지시한다. ②스택에 입력된 자료 중 d가 가장 오래된 자료이다. ③(ㄴ)에서 자료 c를 가져오려면 pop연산이 2회 필요하다. ④(ㄱ)에서 자료의 입력된 순서는 d, c, b이다. 02 삽입과 삭제작업이 자주 발생할 때 실행시간이 가장 많이 소요되는 자료구조는? (1)배열로 구현된 리스트 (2)단순 연결 리스트 (3)원형 연결 리스트 (4) 이중 연결 리스트 03 원형 연결 리스트에서 특정한 값을 탐색하는 함수 search()를 작성하고 테스트하라. search()는 다..