독학사2단계_기출문제01

독학사] 독학사 2단계 컴퓨터과학과 자료구조 기출문제

 

1. 평균적 연산시간이 가장좋은 정렬방법은?

  1) 힙정렬        2) 퀵정력렬        3) 머지정렬                4) PADIX 정렬

 

2. 비선형 자료구조는 ?

  1) 큐               2) 스택           3) 데큐           4) 트리

 

3. 프로그램 성능 평가의 기준이 아닌것은 ?

  1) 수행시간              2) 명령어              3) 실행 빈도수             4) 사용공간

 

4. 기억장소에 산재한 미사용중인 공간을 사용가능하도록 만드는 기법은 ?

  1) 재할당 기법            2) 쓰레기 기법         3) 동적 연결         4) 압축

 

5. 일반적으로 속도가 가장 빠르고 순환 알고리즘이 사용되어 스택이 필요한 정렬방법은 ?

  1) 퀵정렬         2) 머지정렬            3) 힙정렬              4) 캐스캐이드

 

6. 정렬방법 중 분류기준이 다른 하나는 ?

  1) 텍정렬           2) 힙정렬                    3) 퀵정렬              4) 캐스캐이드 정렬

 

7. 알고리즘의 표현방법으로 부적합한 것은 ?

  1) 자연어       2) 흐름도          3) C언어           4) 2진어

 

8. 이진트리의 표현방법에서 연속배열을 사용하는 것이 있는데 연속배열을 사용할 때 기억장소의 낭비가 가장 심한 트리는 ?

  1) 와전이진트리                 2) 포화이진트리         3) 경사이진트리            4) 널트리

 

 

 

 

10. 환형연결리스트에서 투핑 즉 처리과정의 반복을 방지하기 위하여 첨가된 노드는 ?

  1) 헨드노드               2) 뉴노드               3) 링크노드           4) 루트노드

 

11. 수식 A-(B+C)-D+E를 후위표기 방법으로 바르게 나타낸 것은 ?

  1) ABC+-C-E+

  2) ABCDE-+-+

  3) ABCDE+-+-

  4) ABC+--D+E

 

12. 메모리 단편화현상을 해결할 수 있는 방법은 ?

  1) 압축            2) 할당            3) 분배            4) 사상

 

14. 배열 SAMPLE(1:10, 1:5)이 행우선순위에 의하여 구현되었다. 이배열의 시작주소가 10번지이고 각 배열원소가 1BYTE의 기억공간을 차지할 때 SAMPLE(7,2)의 주소는 ?

  1) 41           2) 42            3) 71            4) 72

 

15. 다음에 기술한 알고리즘은 무엇인가?

- 출발점에서 나머지 모든 정점에 이르는 거리를 계산한다
- 가장 거리가 짧은 정점을 선택한다
- 다른 정점들에 대하여 먼저 선택된 정점과 비교하여 새로운 거리가 더 짧은 경우 경로를 바꾼다

  1) 최단경로 알고리즘

  2) 최소비용 알고리즘

  3) 위상적 정렬 알고리즘

  4) 경로변경 알고리즘

 

16. 이진 탐색트리에서 노드의 개수가 30개인 경우 탐색할 때의 최대 비교 횟수는 ?

  1) 2          2) 3           3) 4                  4) 5

 

 

 

18. 해싱에 대한 설명이 바르지 않은 것은 ?

  1) KEY를 테이블 색인으로 변환시키는 함수를 해시함수라 한다

  2) 해싱에서 가장 문제가 되는 것은 충돌이며 이를 해결하는 방법은 테이블의 크기를 증가시키는 것 뿐이다

  3) 해싱에서 충돌을 해결하는 방법 중에는 동일한 해시함수 값을 갖는 것들을 디스크로 연결하는 CHAIN 방식이 있다

  4) 해싱에서 테이블의 크기가 소수일 때는 제산방법이 최대의 효과를 발휘한다

 

19. 참조계수에 관한 다음 설명으로 바르지 않은 것은 ?

  1) 참조계수는 접근할 수 없는 노드를 찾기 위한 방법 중의 하나이다

  2) 자료구조가 포인터 사이클을 허용하는 경우 참조계수를 이용하면 효과적이다

  3) 보통 참조계수가 0이면 그 노드는 접근할 수 없는 노드를 판단되어 사용가능 영역으로 반환된다

  4) 어떤 포인트가 한 노드를 지칭하게 되면 그 노드의 참조계수를 하나 증가하켜 준다

 

 

 

 

21. 환형 리스트의 설명이 아닌 것은 ?

  1) 삭제시에 노드수와는 무관하게 일정한 시간이 소요된다

  2) 리스트의 어느 한 노드를 찾을 때 무한 루푸에 빠질 가능성이 있다

  3) 리스트가 빈 상태일 경우 LINK(HEAD)=HEAD, 즉 HEAD의 링크가 자기 자신을 포인트한다

  4) 리스트의 어느 한 노드에서 다른 노드로 접근시 선형 리스트보다 조작이 복잡하다

 

 

 

 

24. 알고리즘 복합도 함수의 배열로 바른 것은 ?

  1) O(1)＜ 0(n) ＜ 0(logn) ＜ 0(nlogn) ＜ 0(n)＜ o(2)

  2) O(1)＜ 0(logn) ＜ 0(n) ＜ 0(nlogn) ＜ 0(n)＜ o(2)

  3) O(1)＜ 0(n) ＜ 0(logn) ＜ 0(nlogn) ＜ o(2)＜ 0(n)

  4) O(1)＜ 0(logn)＜ 0(n) ＜ 0(nlogn) ＜ o(2)＜ 0(n)

 

25. 순환 프로그램의 구현에 필수적인 자료구조는 ?

 (                                                                                        )

 

26. 순서 리스트를 표현하는 가장 보편적인 방법은 ?

 (                                                                                        )

 

27. 그래프의 종류 중 정점의 수가 n일 때 간선수의 수가 n(n-1)/2개로 존재하는 그래프를 무엇이라 하는가?

(                                                                                                                                              )

 

28. 단일변수 또는 다중변수 등의 다항식을 표현하는데 가장 적합한 자료구조는 무엇인가 ?

(                                                                                                                     )

 

29. 중위순회한 산술식이 A/B**C+D+E이고 후위순회한 결과가 ABC**/D+E+인 이진트리를 표현하시오.

(                                                                                                                 )

 

30. 파일정렬은 정보량이 많아서 일반적으로 주기억장치에서 한번에 정렬을 못하기 때문에 외부기억장치를 이용하여 정렬을 수행하는데 이를 외부정렬이라한다. 이에 반하여 주기억장치에서 수행할 수 있을 정도로 정보량이 충분히 적을 때 사용하는 정렬방법을 무엇이라 하는가?

(                                                                                                             )