새발블로그

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()는 다..

01 다음 중 NULL 포인터 (NULL pointer)가 존재하지 않는 구조는 어느 것인가? (1) 단순 연결 리스트 (2) 원형 연결 리스트 (3) 이중 연결 리스트 (4) 헤더 노드를 가지는 단순 연결 리스트 02 리스트의 n번째 요소를 가장 빠르게 찾을 수 있는 구현 방법은 무엇인가? (1) 배열 (2) 단순 연결 리스트 (3) 원형 연결 리스트 (4) 이중 연결 리스트 03 단순 연결 리스트에서 포인터 last가 마지막 노드를 가리킨다고 할 때 다음 수식 중 참인 것은? (1) last==NULL (2)last->data==NULL (3)last->link==NULL (4)last->link->link==NULL 04 단순 연결 리스트의 노드들을 포인터 p로 방문하고자 한다. 현재 p가 가리키는..

01 문자 A, B, C, D, E를 큐에 넣었다가 다시 꺼내어 출력하면 어떻게 되는가? (a)A, B, C, D, E (b)E, D, C, B, A (c)A, B, C, E, D (d)B, A, C, D, E 02 원형큐에서 front가 3이고 rear가 5라고 하면 현재 원형큐에 저장된 요소들의 개수는?(단, MAX_QUEUE_SIZE는 8이다.) (a)1 (b)2 (c)3 (d)4 03 10, 20, 30, 40, 50 을 큐에 넣었다고 가정하고 3개의 항목을 삭제하였다. 남아 있는 항목은? 04 다음 중 원형큐에서 공백상태에 해당하는 조건은? (a)front==0 && rear==0 (b)front==(MAX_QUEUE_SIZE-1)&&rear==(MAX_QUEUE_SIZE-1) (c)front=..

01 스택에서 삽입작업이 발생하면 top의 값은 어떻게 변경되는가? (1) top=0 (2) top=1 (3) top=top-1 (4) top=top+1 02 문자 A, B, C, D, E 를 스택에 넣었다가 다시 꺼내어 출력하면 어떻게 되는가? (1) A, B, C, D, E (2) E, D, C, B, A (3) A, B, C, E, D (4) B, A, C, D, E 03 10, 20, 30, 40, 50 을 스택에 넣었다가 3개의 항목을 삭제하였다. 남아있는 항목은? 04 배열로 구현된 스택에서 top가 3이면 현재 스택에 저장된 요소들의 개수는? (1) 1 (2) 2 (3) 3 (4) 4 05 다음 중 배열로 구현된 스택에서 공백상태에 해당하는 조건은? 또 포화상태에 해당되는 조건은? (1) t..