【컴퓨터과학개론】종합 정리 기출문제 - 3

안녕하세요 【키보드 워리어】

 

⌨🗡🧑

블로그 방문자 여러분, 안경닦이입니다.

 

컴퓨터과학개론 기출문제 정리하는 시간을 가져보겠습니다.

 

---

 

기출문제 - 3

 

 

[09] 그래프에 대한 설명으로 틀린 것은 무엇인가?

 

보기 (1) 두 정점이 간선으로 직접 연결되어 있으면 두 정점은 인접되었다고 한다.

     (2) 두 정점이 간섭으로 직접 연결되어 있으면 해당 간선은 두 정점에 부수해 있다고 한다.

     (3) 경로(path)는 간선으로 연결된 정점들의 순차적 나열을 의미한다.        

     (4) 무방향 그래프(undirected graph)는 두 정점을 연결하는 간선이 방향성을 가지는 간선으로 연결된 그래프이다.

 

 

[정답]: 3번

 

 

※ 두 정점을 연결하는 간선이 방향성을 가진다면 방향 그래프가 되며 간선이 방향성이 없다면 무방향 그래프가 된다.

 

 

 

 

 

[10] 아래 그래프를 1부터 시작하는 너비 우선 탐색으로 옳은 것은 무엇인가?

보기

(1)   1, 3, 2, 6, 5, 7, 4

(2)   1, 2, 4, 3, 6, 5, 7

(3)   1, 2, 3, 4, 5, 6, 7

(4)   1, 2, 4, 5, 7, 6, 3

 

[정답]: 3번

너비 우선 탐색은 다음과 같은 방법으로 수행합니다. 너비 우선 탐색은 방문하지 않은 인접한 정점 중에서 가장 오래된 것부터 먼저 방문합니다.

 

1)     우선 시작 정점을 결정하며, 설명을 위해 시작 정점 1을 방문합니다.

2)     정점 1과 인접했지만 방문하지 않은 정점 2와 3에 대해서 하나씩 차례로 방문을 시작하는데 이때 순서는 프로그래머가 결정할 수 있습니다.

3)     정점 2와 정점 3의 방문을 완료하면, 다시 정점 2와 정점 3에서 인접했지만 방문하지 않은 정점(정점 4, 5, 6)을 차례로 방문합니다.

4)     정점 5와 정점 6에 인접했지만 방문하지 않은 정점 7을 방문해요. 더 이상의 방문할 정점이 없기 때문에 탐색을 종료합니다.

 

이와 같은 순서로는 너비 우선 탐색으로는 1, 2, 3, 4, 5, 6, 7의 방문 순서를 얻게 되므로 정답은 3번이 됩니다.

 

 

 

[11] 디스크 헤드의 위치에서 가장 짧은 트랙 탐색 거리(또는 탐색 시간)를 가진 디스크 접근 요청을 먼저 처리하는 디스크 스케줄링 방식은?

 

보기

     (1) FCFS(First – Come First Served) 스케줄링 기법

     (2) SSTF(Shortest Seek Time First) 스케줄링 기법

     (3) SCAN 스케줄링 기법

     (4) SLTF(Shortest Latency Time First) 스케줄링 기법

 

 

[정답]: 2번

 

1) FCFS(First – Come First Served) 스케줄링 기법

       -먼저 도착한 디스크 요청이 가장 먼저 서비스를 받는 방법이다. 부하가 커질수록 장치를 포화시키기가 쉽고 응답 시간이 길어지는 단점이 있습니다.

 

(2) SSTF(Shortest Seek Time First) 스케줄링 기법

      -현재 디스크 헤드의 위치에서 가장 짧은 트랙 탐색 거리를 가진 디스크 접근 요청을 먼저 처리하는 방식으로 FCFS에 비해 평균 응답 시간도 짧지만, 가장 중요한 단점은 중간 범위의 트랙에 비해 가장 안쪽 또는 바깥쪽 트랙이 서비스를 받지 못하는 경우가 발생할 확률이 높습니다.

 

(3) SCAN 스케줄링 기법

     - 한쪽 방향에서 가장 짧은 탐색 거리의 디스크 접근 요청을 먼저 서비스합니다.

     - 해당 방향의 마지막 실린더를 만나거나 기다리는 요구가 더 이상 없을 때에는 방향을

       바꾸어 서비스를 계속합니다.

 

(4) SLTF(Shortest Latency Time First) 스케줄링 기법

      - 모든 요구를 검사한 후 가장 짧은 회전 지연을 갖는 요구들에게 우선적으로 서비스하는 기법입니다.

 

※ 참조 강의 10강 31:20초 디스크 스케줄링 편, 교재 197p 5.4.2. 디스크 스케줄링 참고

 

 

 

[12] 가상 기억장치 기법에서 기변적인 크기의 영역으로 나누고 관리하는 단위를 무엇이라 부르는가?

 

보기 (1) 세그먼트 (2) 페이지 (3) 파티션 (4) 프레임

 

[정답]: 1번

 

세그먼트 - 프로그램 코드나 데이터를 일정하지 않은 서로 다른 크기로 분할하여 주기억장치에 접근하는 것은 세그먼트 기법입니다. 그 외로 페이징 기법은 코드나 데이터를 페이지라고 불리는 동일한 크기의 블록으로 쪼개어 주기억 장치에 적재하여 접근하는 기법입니다. (주기억 장치도 페이지 크기와 같은 크기로 분할함)

 

 

※ 참조 교재 185p 5.2.2 가상 기억장치

 

 

[13] 아래의 그림은 단일 연결 리스트에서 새로운 노드(Y)를 삽입하기 전의 그림이다. 새로운 노드 (Y)를 X노드 다음에 위치하도록 삽입하는 과정의 순서가 올바른 것은 무엇인가?

 

 

• 가.   선행 노드 X의 후행 노드 링크 필드가 Y의 저장 주소를 가리키게 한다.
• 나.   삽입할 노드 Y의 후행 노드 링크 필드가 후행 노드 저장 주소를 가리키게 한다.
• 다.   삽입할 노드 Y에 대한 컴퓨터 메모리를 할당받고, 삽입할 내용을 저장한다.

보기

(1) 가 → 나 → 다

(2) 가 → 다 → 나

(3) 다 → 가 → 나

(4) 다 → 나 → 가

 

[정답]: 4번

 

연결 리스트는 단일, 이중 연결 리스트로 나누어지는데 이 문제에서는 단일 연결 리스트에서 노드의 삽입, 검색, 삭제 연산중 삽입을 위한 문제만 언급되었습니다.

    단계 1: 새로운 노드 할당

    단계 2: 새 노드의 링크 필드 조정

    단계 3: 선행 노드의 링크 필드 조정

위와 같은 순서로 이어집니다.

따라서 답은 4번입니다.

 

※ 참조 교재 56~57p 자료구조 단일 연결 리스트에서의 노드 삽입 참고, 강의 3강 자료구조(1) 53:00 리스트 참고