7급 국가직 알고리즘 2024년 기출문제

정점이 6개인 무방향 완전 그래프의 간선의 개수는?

큐에 다음 함수를 적용한 결과로 (가) ∼ (다)에 들어갈 내용을 바르게 연결한 것은?

enqueue(e): 큐의 제 위치에 객체 e를 삽입한다.

dequeue(): 큐의 제 위치에서 객체를 삭제한다. 빈 큐일 경우에는 “error”를 출력한다.

연산순서	함수	출력	큐 저장공간
1	dequeue()	“error”	()
2	enqueue(1)		(1)
3	enqueue(2)		(1, 2)
4	enqueue(5)		(1, 2, 5)
5	dequeue()		(가)
6	enqueue(7)		(나)
7	dequeue()		(다)

(가) (나) (다)

다음 최대 힙에 대한 설명으로 옳지 않은 것은?

그리디 알고리즘으로 최적의 해가 보장되지 않는 것은?

다음 C 코드에서 사용한 재귀 알고리즘의 시간 복잡도는? (단, n은 배열의 크기이다)

int S(int A[ ], int n){
   if( n <= 0 )  return 0;
   else return A[n-1] + S(A, n/2);
}

1부터 n까지 합을 구하는 다음 파이썬 프로그램의 빈칸에 들어갈 내용은? (단, n은 n≥1인 정수이다)

def sum(n):
    ret = 0
    for :
        ret += i
    return ret

연산 이론상의 문제 유형에 대한 설명으로 옳지 않은 것은?

다음 fib() 함수는 피보나치 수열을 계산하는 C 코드이다. fib(17)을 실행할 때 fib(8)과 fib(10)이 각각 호출되는 횟수를 바르게 연결한 것은?

int fib(int n){
	if(n==1 || n==2) return 1;
	else return (fib(n-1) + fib(n-2));
}

fib(8) fib(10)

다음 이진 검색 트리에서 노드 이동 또는 포인터 변경의 횟수를 최소화하면서 노드를 삭제하는 과정의 설명으로 옳지 않은 것은?

레드－블랙 트리로 옳은 것은? (단, 외부 노드(leaf)는 표시하지 않고, 블랙 노드는 검정색으로, 레드 노드는 흰색으로 나타낸 것이다)

해시 테이블에 대한 설명으로 옳지 않은 것은?

프림(Prim) 알고리즘을 적용하여 다음 그래프의 정점 A에서 시작하는 최소 신장 트리를 구할 때, 마지막으로 선택되는 정점은?

다음 그래프에 다익스트라 알고리즘을 적용하여 구한 정점 a에서 정점 f까지 최단 경로의 거리는?

다음 파이썬 프로그램의 실행 결과는?

def test(n):
    if(n<0):
        return 0
    return n+test(n-2)

print(test(5))

다음 그래프에 크루스칼(Kruskal) 알고리즘을 적용하여 최소 신장 트리를 만들 때, 마지막으로 최소 신장 트리에 포함되는 간선은? (단, (i, j)는 정점 i와 정점 j를 잇는 간선이다)

주어진 동전의 집합에 대하여 가장 적은 개수의 동전으로 거스름돈을 만드는 문제를 그리디 알고리즘을 이용해서 해결할 수 있는 경우는? (단, 거스름돈은 10의 배수이다)

다음 그림의 허프만 트리를 이용하여 인코딩한 일부 데이터의 코드를 문자열로 디코딩한 것은? (단, 노드의 왼쪽 자식 연결 간선에는 0, 오른쪽 자식 연결 간선에는 1이 부여된다)

알파벳 순으로 정렬된 다음 배열에 대하여 이진 탐색으로 원소 P를 찾으려고 할 때, 비교해야 할 원소의 개수는?

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
C	E	G	H	J	L	M	N	P	Q	S	T	V	W	Z

그림과 같은 상태의 크기 13인 해시 테이블에 이중(double) 해싱 방법으로 원소 14를 삽입하고 이어서 원소 20을 삽입할 때, 원소 20의 저장 주소는? (단, 해시 함수 h(k,i) = (h₁(k) + iㆍh₂(k)) mod 13, 충돌 횟수 i = 0, 1, 2, ... 이고, h₁(k) = k mod 13, h₂(k) = 1 + (k mod 11)이다)

다음 AVL 트리에 대해 노드 4, 5, 6을 차례대로 삽입한 결과는? (단, 리밸런싱을 위한 회전 횟수는 최소로 한다)

다음 파이썬 프로그램의 실행 결과는?

a=[29,88,60,26,40,74,43,22,61,40]
def partition():
    i = -1
    n = len(a)
    for j in range(0, n-2):
        if a[j] <= a[n-1]:
            i += 1
            b = a[i]
            a[i] = a[j]
            a[j] = b
    b = a[i+1]
    a[i+1] = a[n-1]
    a[n-1] = b

partition()
print(a)

점근적 표기의 정의로 옳지 않은 것은?

배열 A를 오름차순으로 정렬하기 위해 5, 3, 1의 간격을 사용하여 셸(Shell) 정렬을 수행할 때, 간격 3에 대한 처리까지 수행을 완료한 후의 배열 A의 상태로 옳은 것은?

i	0	1	2	3	4	5	6	7	8	9	10
A[i]	9	18	26	21	4	17	13	2	6	24	8

다음 C 코드에 해당하는 문자열 탐색 방법은? (단, s1은 입력 문자열, s2는 s1에서 찾고자 하는 패턴 문자열이고, n1은 s1의 길이, n2는 s2의 길이를 나타낸다)

int match(char *s1, char *s2) {
	int pt = 0, p = 0;
	while(pt != n1 && p != n2) {
		if (s1[pt] == s2[p]) {
			pt++;
			p++;
		} else {
			pt = pt - p + 1;
			p = 0;
		}
	}
	if (p == n2) return pt-p;
	else return -1;	
}

다음은 텍스트에서 패턴과 일치하는 문자열을 찾기 위한 KMP(Knuth Morris Pratt) 알고리즘에서의 전처리 과정을 구현한 파이썬 프로그램이다. 패턴이 abcbabca인 경우, 아래 표의 (가) ∼ (라)에 들어갈 숫자를 바르게 연결한 것은?

def preprocess(pn: str):
    pt = 1
    k = 0
    pi = [0] * (len(pn) + 1)
    pi[pt-1] = -1
    pi[pt] = 0
    while pt != len(pn):
        if pn[pt] == pn[k]:
            k += 1
            pt += 1
            pi[pt] = k
        elif k == 0:
            pt += 1
            pi[pt] = k
        else:
            k = pi[k]
    print(pi)
pattern = 'abcbabca'
preprocess(pattern)

i	0	1	2	3	4	5	6	7	8
pn[i]	a	b	c	b	a	b	c	a
pi[i]	-1	0	0	0	0	(가)	(나)	(다)	(라)

(가) (나) (다) (라)