問題一覧
1
다음 설명 중 검색(탐색) 알고리즘과 관련된 사항이다. 틀린 것을 고르시오.
이진 검색(탐색) 알고리즘은 정렬되지 않은 리스트에서 사용 가능한 효율적인 탐색 알고리즘이다.
2
다음 코드는 선형 탐색을 위한 프로그램이다. 출력 결과는? [다음 코드] a = [1, 2, 3, 4, 5] search = 6 # 찾고자 하는 값 k=0 while k<len(a): if a[k] == search: print("ok") break else: k= k+1
아무것도 출력되지 않음
3
다음중 검색(탐색) 알고리즘이 아닌것은?
버블 탐색
4
이진 탐색 트리(BST, Binary Search Tree)에 대한 설명으로 맞는 것은?
트리의 구조에 따라 선형 탐색과 동일한 속도를 낼수도 있다.
5
배열에 다음과 같이 정렬된 값이 있다고 가정한다. 이 때 이진 검색으로 36를 찾을 경우 몇번만에 찾을 수있나? [5][11][19][22][36][59][61]
3번
6
선택정렬(selection sort) 알고리즘을 사용하여 리스트에 저장된 항목을 오름차순 정렬로 출력하기 위해 밑줄 친 곳에 들어갈 올바른 코드를 쓰시오. arr=[40,70,60,30,10,50] for i in range(len(arr)-1): small_idx=i for j in range(i+1, len(arr)): if arr[small_idx] > arr[j]: _________________ arr[i], arr[small_idx]=arr[small_idx], arr[i] print(arr)
small_idx=j
7
시간 복잡도 관점으로 봤을 때 선택정렬, 버블정렬, 삽입정렬 알고리즘 중 가장 빠른 알고리즘은 무엇인가?
세 알고리즘 모두 같다
8
배열 A[1… n]이 임의의 정렬 알고리즘의 입력으로 들어온다. 이때 배열이 이미 정렬되어 있는 상태이면 다음 중 어떤 정렬 알고리즘이 가장 효율적이겠는가?
삽입 정렬 알고리즘
9
다음 그림은 배열에 저장된 자료가 순서대로 삽입정렬(insertion sort)이 이루어지는 과정이다. 그림 다음 4단계 후에 배치될 배열을 순서대로 올바로 기입한 것은?
12 17 42 55 73 43 5 27
10
다음의 설명에 해당하는 용어를 한글로 적으시오. <다음> n개의 숫자가 입력으로 주어졌을 때 사용자가 지정한 기준에 맞게 순서대로 나열하는 방법(순서를 찾은 방법) <답안 작성시 유의사항> 1.영어 및 영어식 한글로 작성하지 말것 2.한글 2자로만 입력할 것 (뒤에 "방법", "문제", "알고리즘"을 적지 말것)
정렬
11
downHeap(다운힙)에 대한 설명으로 잘못된 것을 고르시오.
삽입 연산에 해당하는 작업을 수행한다.
12
다음은 중 힙(heap) 정렬과 관련된 내용이다. 이 중 올바르게 설명하고 있는 내용을 모두 고르시오. 주의: 1. 중복체크 가능 3. 두개 이상의 답이 있을 경우 모두 답을 체크해야 정답으로 인정됩니다. 3. 1개 이상은 반드시 올바른 답이 있습니다.
힙(heap)이란 더미의 뜻을 가진 완전이진트리를 말한다., 힙정렬(heap sort)의 정렬 시간 복잡도는 항상 O(n log n)이다
13
다음 코드는 힙(heap) 정렬에서 업힙(upheap) 연산을 구현한 코드이다. 밑줄 친 부분에 들어가야 할 코드를 올바르게 적은 것은? <코드> heap=[0, 99, 77, 42, 66, 55, 22, 15, 16, 33] v=150 # 새로 삽입할 수 n=len(heap) # 새로 입력한 값의 index heap.append(v) while n!=1 and heap[n]>heap[n//2]: heap[n],heap[n//2]=heap[n//2],heap[n] ________# n 값 위치를 변경함
n=n//2
14
아래 힙(heap)에서 다운힙(downheap)연산을 수행하였다. 다운힙 연산이 최종 완성된 후의 힙을 정확히 표현한 트리는 어떤것인가?
1
15
다음 입력 데이터에 대해 퀵 정렬을 위해 1차( 1 pass) 로 분할한 결과는? 단, 피벗은 7이다. (오름차순정렬) <입력 데이터> [ 7, 6, 8, 2, 10]
[ 2, 6, 7, 8, 10 ]
16
병합정렬(merge sort)에 대한 설명 중 올바르게 설명한 것은?
분할 정보(Divide and Conquer)방법을 이용한 정렬 방법이다.
17
다음은 프림(Prim) 알고리즘을 만드는 과제 이다. 다음 선택되는 간선은 무엇인가? (주황색 노드: MST에 포함된 노드)
(b)
18
다음 그래프를 보고 최소신장트리(MST)를 만드려고 한다. 잘못 설명한 것은 무엇인가?
프림 알고리즘(Prim Algorithm)과 다익스트라(Dijkstra algorithm)은 대표적인 최소신장트리를 만드는 알고리즘이다.
19
아래 그래프를 파이썬의 연결리스트 방법으로 표현하고자 한다. 알맞게 표현한것은?
G={"A":["B","C"],"B":["A"],"C":["A"]}
20
아래의 그래프를 수학적 표기법으로 정확하게 표기한 것은?
G=(V,E) V={A,B,C} E={<A,B>,<A,C>,<C,A>}
21
다음 그래프를 파이썬의 연결리스트로 표현한 문제가 있다. 그 문제의 답과 같이 G를 그래프로 표현했다고 가정하고 실제 두 값을 입력받아 서로 연결되어 있는지 파이썬으로 프로그래밍 하였다. 밑줄 친 빈 칸에 들어 갈 코드를 정확하게 적은 것은? vn1=input("첫번째노드(Vertex)값:") vn2=input("두번째노드(Vertex)값:") if (1) : if (2) : print(f"{vn1}과 {vn2}는 연결됨") else: print(f"{vn1}과 {vn2}는 연결되지 않음") else: print(f"{vn1}은 그래프에 없음")
(1) vn1 in G (2) vn2 in G[vn1]
22
다음 보기는 그래프에 대한 설명이다. 각각의 설명에서 잘못 된 것을 고르시오.
그래프의 차수(degree)는 그래프의 모든 간선(edge)의 개수이다.
23
다음 트리를 보고 잘못된 것을 고르시오.
E의 형제 노드는 D F G H 이다.
24
다음 아래의 이진트르(Binary Tree)의 순회 방법 중 전위 순회(pre order)를 한다면 올바를 방문 순서는?
A B D E G H C F
25
다음 중 이진트리(Binary Tree)에 대하여 잘못 설명한 것은?
이진트리의 차수(degree)는 0부터 3까지 나온다.
26
다음 중 트리(Tree)에 대하여 잘못 설명한 것은?
순환 구조를 가지고 있다.
27
아래의 그래프를 깊이 우선 탐색(순회)를 할 경우 정확한 것은? 출발은 A에서 시작하고 각 노드의 자료구조는 인접 리스트로 작성되어 있으며 다음과 같다. <다음> A: [ C , B ] B: [ A , C , F , G ] C: [ A , B , F , E , D ] D: [ E , C ] E: [ F , D ] F: [ B , C , E ] G: [ B ]
A C B F E D G
28
다음 중 컴퓨터 알고리즘 특징에 대한 설명으로 옳은 것은 무엇인가?
유한 시간 내에 종료한다.
29
빅오 알고리즘 표기에서 가장 속도가 빠른 것은?
O(1)
30
아래와 같은 파이썬 코드가 있을 경우 시간 복잡도를 정확히 구한 것은? <아래 코드> n=int(input("정수:")) a=0 for i in range(n): for j in range(1,n*2): a=a+i+j print(a)
O(n2)
31
다음 그래프에서 너비우선탐색(BFS)을 하는 코드를 파이썬으로 작성하려고 한다. 빈칸에 알맞은 코드를 넣으시오. <코드> G={"A":["B","C","D"],"B":["A"],"C":["A","D","E"],"D":["A","C","F"],"E":["C","F"],"F":["D","E"]} def BFS(node): queue=[] print(f"[{node:^3}]",end="") visited.append(node) queue.append(node) while True: if len(queue)==0: break node=queue.pop(0) for n in : if n not in visited: print(f"[{n:^3}]",end="") visited.append(n) queue.append(n) visited=[] print("BFS:",end="") BFS("A") print()
G[node]