방통대 2017-1 이산수학 기말시험 기출문제 정답 및 해설 다운로드

36. 다음 중 이산수학에서 다루는 대상으로 적절한 것은? 

1) 2차 방정식

2) 이진 트리

3) 미분방정식

4) 삼각 함수 

 

정답: 2

해설: 정답은 2번, 이진 트리이다. 이산수학은 연속적이지 않은 구조를 다루는 수학의 한 분야로, 이진 트리는 그래프 이론의 일부로 이산 구조의 예이다. 1번의 2차 방정식과 3번의 미분방정식, 4번의 삼각 함수는 모두 연속수학에서 다루어지므로 이산수학의 대상이 아니다. 이진 트리는 노드와 간선으로 이루어져 있어 각 노드가 최대 두 개의 자식을 가지는 특징을 지닌다.

 

 

 

37. 다음 중 명제인 것은?

1) 2x-6 = 0 

2) 석이는 공부를 잘 한다.

3) 수학 공부를 더 많이 하세요.

4) 영이는 소담이보다 나이가 많다. 

 

정답: 4

해설: 정답 4번인 '영이는 소담이보다 나이가 많다'는 참이거나 거짓이 확실히 판단 가능한 명제이다. 반면, 1번 '2x-6 = 0'은 등식이지만 변수 x의 값을 알 수 없기 때문에 명제가 아니다. 2번 '석이는 공부를 잘 한다'는 주관적 평가가 포함되어 있어 객관적 참거짓을 판단할 수 없고, 3번 '수학 공부를 더 많이 하세요'는 명령문으로 명제가 아니다. 따라서 명제의 정의를 만족하는 것은 4번뿐이다.

 

 

 

38. 다음 중 모순명제인 것은? 

 

1) p ∨ (~q)

2) p → (p ∨q)

3) (p∧q)∧(~p)

4) p∧q → q ∨ p

 

정답: 3

해설: 정답 3번인 (p∧q)∧(~p)은 모순명제이다. 이 명제는 p와 q가 모두 참인 상황과 p가 거짓인 상황을 동시에 요구하므로, 이 두 조건은 동시에 만족될 수 없어 모순이 발생한다. 다른 선지들을 살펴보면, 1번 p ∨ (~q)는 p가 참이거나 q가 거짓일 때 참이 되는 조건명제이고, 2번 p → (p ∨ q)는 p가 참이면 p 또는 q 중 하나는 반드시 참이 되어 참인 함의명제이며, 4번 p∧q → q ∨ p는 p와 q가 모두 참이면 q 또는 p 중 하나가 참이므로 역시 참인 함의명제이다. 따라서 이들 중 유일하게 내부 조건이 서로 충돌하여 항상 거짓이 되는 3번이 모순명제인 것이다.

 

 

 

39. 명제함수 P(x, y) = x+2y=5 일때, 옳은 것은?

1) P(1,2) = T

2) P(2,1) = T

3) P(-1, 3) = F

4) P(3,1) = F 

 

 

정답: 1

해설: 정답은 1번 P(1, 2) = T이다. 명제함수 P(x, y) = x + 2y = 5의 정의에 따라 x = 1, y = 2를 대입하면 1 + 4 = 5가 되어 참이다. 반면, 2번 선지 P(2, 1)을 계산하면 2 + 2 = 4로 5와 같지 않아 거짓이다. 3번 선지 P(-1, 3)는 -1 + 6 = 5이므로 사실 참이고, 오류가 있다. 4번 선지 P(3, 1)는 3 + 2 = 5가 되어 참이므로 이 역시 오류가 있는 설명이다. 따라서 정답은 1번만이 유일하게 조건을 만족한다.

 

 

 

40. 명제함수 P(x)가 x>0이고 x의 정의구역 D = {1,2,3}일 때, ∀𝑥𝑃(𝑥)와 ∃𝑥𝑃(𝑥)의 진리값을 순서대로 적은 것은? 

1) F, F

2) F, T

3) T, F

4) T, T

 

정답: 4

해설: 명제함수 P(x)가 x>0을 만족하고 정의구역 D={1,2,3}인 경우, D 내의 모든 원소는 조건 x>0을 충족한다. 따라서 ∀𝑥𝑃(𝑥), 즉 모든 x에 대해 P(x)가 참이라는 명제는 참이다. 동시에 ∃𝑥𝑃(𝑥), 즉 적어도 하나의 x에 대해 P(x)가 참이라는 명제 또한 참이다. 이에 따라 정답은 4) T, T이다. 이해를 돕기 위해, ∀𝑥𝑃(𝑥)는 정의구역의 모든 원소가 조건을 만족함을 의미하고, ∃𝑥𝑃(𝑥)는 최소 한 원소가 조건을 만족함을 나타낸다.

 

 

 

41. 다음 중 특정한 공리들을 가정하고, 그 가정하에 제안된 명제가 참인 것을 입증하는 작업을 뜻하는 용어는?

1) 탐색

2) 증명

3) 정의

4) 정리 

 

정답: 2

해설: 증명은 특정한 공리들을 가정하고 그 가정하에 제안된 명제가 참인 것을 입증하는 작업이다. 탐색은 정보나 자료를 찾기 위한 활동이며, 정의는 어떤 개념이나 용어의 의미를 명확하게 규정하는 것이고, 정리는 이미 증명된 명제로서 수학적 진리를 표현한다. 따라서 이 경우 올바른 용어는 증명이다.

 

 

 

42. 집합 A = { a, b, c}의 분할(partition)이 되는 것은? 

1) { {a, b, c} } 

2) { Ø, {a}, {b}, {c} } 

3) { Ø, {a,b}, {b,c} } 

4) { {a,b}, {b,c}, {c,a} } 

 

정답: 1

해설: 집합 A = { a, b, c }의 올바른 분할은 집합 A의 모든 원소가 정확히 하나의 부분 집합에만 속하며, 그 부분 집합들의 합집합이 원래의 집합 A와 같아야 한다. 1번 선지 { {a, b, c} }는 A의 모든 원소를 포함하고 있으며, 중복 없이 하나의 부분 집합으로만 이루어져 있어 A를 정확히 재구성한다. 반면, 2번 선지는 공집합을 포함하고 있어 부적절하다. 3번과 4번 선지는 각각 원소가 중복되어 여러 부분 집합에 속하는 문제가 있다. 따라서 정답은 1번이다.

 

 

 

 

 

43. 전체집합 U = {a, b, c, d, e, f, g}이고 A = {a, c, e, g}, B = {b, d, f}, C = {a, b, c}라고 할 때, 다음 중 옳지 않은 것은?

(4점)

1) A ∪ B = U
2) A ∩ B = Ø
3) A^c = C
4) A ⊕ B = U

 

 

정답: 3

해설: 정답 3번인 A^c = C는 옳지 않다. A^c는 집합 A에 속하지 않는 전체집합 U의 원소들을 나타내므로, A^c = {b, d, f}이다. 그러나 C = {a, b, c}로, A^c와 C는 서로 다른 집합이다. 선지 1번 A ∪ B = U는 A와 B의 모든 원소가 U를 구성하므로 맞다. 선지 2번 A ∩ B = Ø는 A와 B에 공통 원소가 없으므로 맞다. 선지 4번 A ⊕ B = U는 A와 B의 대칭차가 U와 같으므로 맞다. 따라서 3번이 정답이다.

 

 

 

44. U가 전체집합이고 A ⊆ B ⊆ U일 때 다음 중 옳지 않은 것은? (3점)

1) A ∪ B = B
2) A ∩ B^c = Ø
3) A^c ⊆ B^c
4) A - B = Ø

정답: 3

해설: 전체집합 U에서 A와 B가 A ⊆ B를 만족한다고 가정할 때, 옳지 않은 명제는 3번이다. 1번 명제 A ∪ B = B는 A가 B에 포함되므로 B와 같다. 2번 명제 A ∩ B^c = Ø는 A와 B의 여집합의 교집합이 공집합임을 의미하며, 이는 A가 B에 완전히 포함되어 있기 때문이다. 4번 명제 A - B = Ø 역시 A가 B에 포함되므로 A에서 B를 뺀 차집합은 공집합이 된다. 하지만 3번 명제 A^c ⊆ B^c는 A의 여집합이 B의 여집합에 포함되는 것을 의미하는데, A ⊆ B라면 오히려 B^c ⊆ A^c가 성립한다. 따라서 3번은 잘못된 명제이다.

 

 

 

 

 

45. 행렬 \( A \)와 \( B \)가 아래와 같을 때, 다음 중 행렬 연산이 잘못된 것은? (4점)

\[ A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}, \quad B = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \]

1) \( A + B = \begin{pmatrix} 2 & 3 \\ 3 & 5 \end{pmatrix} \)
2) \( AB = \begin{pmatrix} 1 & 2 \\ 0 & 4 \end{pmatrix} \)
3) \( 2A = \begin{pmatrix} 2 & 4 \\ 6 & 8 \end{pmatrix} \)
4) \( B^2 = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix} \)

정답: 2

해설: 정답은 2번이다. 행렬 \( A \)와 \( B \)의 곱 \( AB \)는 각 원소의 곱과 덧셈으로 이루어진 결과를 나타낸다. 실제 계산을 통해 \( AB \)는 \( \begin{pmatrix} 1 & 3 \\ 3 & 7 \end{pmatrix} \)가 되어야 한다. 따라서 2번 선지에서 제시된 \( \begin{pmatrix} 1 & 2 \\ 0 & 4 \end{pmatrix} \)는 잘못된 값이다. 1번, 3번, 4번은 각각의 연산 규칙에 따라 올바르게 계산된 결과이다.

 

 

 

46. 다음 행렬 \( A \)를 나타내는 용어로서 적절한 것은? (4점)

\[ A = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix} \]

1) 부울행렬
2) 대각행렬
3) 삼각행렬
4) 행사다리꼴 행렬

정답: 1

해설: 해설: 행렬 \( A \)는 각 원소가 0 또는 1로 이루어진 행렬로, 부울행렬이라 할 수 있다. 대각행렬은 주대각선을 제외한 나머지 성분이 모두 0이지만 \( A \)는 이 조건에 맞지 않다. 삼각행렬은 대각선 이하 또는 이상의 성분이 모두 0이어야 하지만 \( A \)는 그렇지 않다. 행사다리꼴 행렬은 행을 기준으로 모든 0이 아닌 행이 0 행 위에 위치해야 하고, 각 0이 아닌 행의 첫 번째 0이 아닌 수는 그 이전 행의 첫 번째 0이 아닌 수보다 오른쪽에 위치해야 하는데 \( A \)는 이 기준에도 부합하지 않는다. 따라서 \( A \)는 부울행렬에 가장 적합하다.

 

 

 

* (47~48) 다음 행렬들에 대한 문제에 답하세요.

\[ A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \quad B = \begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix}, \quad C = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}, \quad D = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} \]

 

 

 

 

 

47. A ∩ B, 즉 A와 B의 교차(meet)를 구하면? (3점)
① A
② B
③ C
④ D

 

정답: 4

해설: 해설: 문제 47번에서 A ∩ B, 즉 A와 B의 교차를 구하는 문제다. A ∩ B는 행렬 A와 B에서 동일한 위치의 요소들이 모두 1일 때 해당 위치에 1을 가지는 새로운 행렬을 의미한다. A와 B 행렬을 비교해 보면, 두 행렬에서 동시에 1이 위치하는 요소는 없다. 따라서 A ∩ B의 결과는 모든 요소가 0인 행렬이 되어야 한다. 이는 주어진 선택지 중 D 행렬과 일치한다. 

 

 

 

 

48. A ⊙ B, 즉 A와 B의 부울곱을 구하면? (3점)
① A
② B
③ C
④ D

 

정답: 2

해설: 부울 곱 연산은 원소 cj에 대해 곱집합 후 전부 합집합하는 연산이므로 B이다. 

 

 

 

※ (49~51) 다음을 잘 읽어 A = {1, 2, 3}에서의 관계 R을 발휘 그림으로 나타낸 것이다. 표현에 답하시오.

 

 

 

49. 관계 R을 수식의 집합으로 나타낸 것은? (3점)
① R = {(1, 2), (2, 3), (3, 1)}
② R = {(1, 3), (3, 2), (2, 1)}
③ R = {(1, 1), (1, 3), (2, 1), (2, 2), (3, 2), (3, 3)}
④ R = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 1), (3, 3)}

 

정답: 4

 

 

 

 

50. 관계 R에 대한 설명으로 옳은 것은? (2점)
① 반사적이 아니다.
② 대칭적이다.
③ 추이적이다.
④ 동치 관계다.

 

정답: 1,2,3,4

 

 

 

 

51. 관계 R을 부울행렬로 나타낸 것은? (2점)
① M_R = 
    { 1 1 0
      0 1 1
      1 0 1 }
② M_R = 
    { 1 1 1
      0 1 1
      0 0 1 }
③ M_R = 
    { 1 1 0
      1 0 1
      0 1 1 }
④ M_R = 
    { 1 0 1
      0 1 0
      1 0 1 }

 

정답: 1

 

 

 

 

52. A = {1, 2, 3}, B = {a, b, c, d}일 때, 다음 관계를 중 A에서 B로의 단사함수인 것은? (2점)
① R = {(1,a), (2,b), (3,a)}
② R = {(1,b), (2,c), (3,a)}
③ R = {(1,b), (2,c), (3,a), (3,b)}
④ R = {(1,a), (1,b), (2,c), (2,a), (3,b), (3,c)}

 

정답: 2

해설: 정답 2번은 A에서 B로의 단사함수이다. 단사함수는 모든 원소가 유일한 이미지를 가지는 함수를 말한다. 2번 선지에서는 {(1,b), (2,c), (3,a)}로 각 A의 원소가 B의 서로 다른 원소와 대응한다. 다른 선지에서는 중복되는 대응이 있거나 동일 원소가 여러 이미지를 갖는 경우가 있어 단사함수가 아니다. 예를 들어, 1번은 1과 3이 같은 'a'에 매핑되고, 3번은 3이 'a'와 'b'에 중복 매핑되며, 4번은 각 원소가 여러 이미지를 갖는다. 따라서 2번만이 A에서 B로의 단사함수 조건을 만족한다.

 

 

 

53. 30 mod 5와 관계가 같은 것은? (3점)

① ⌈ 7.1⌉  mod 3
②  ⌊10.5⌋  mod 4
③ 3! mod 4
④ (6! / 5!) mod 6

 

정답: 4

해설: 정답은 4번이다. 30 mod 5의 결과는 0이며, 이는 30이 5로 나누어 떨어지기 때문이다. 4번 선지인 (6! / 5!) mod 6을 분석하면, 6!은 720, 5!은 120이고, 6!/5!은 720/120 = 6이다. 6 mod 6 역시 0으로, 6이 6으로 나누어 떨어진다. 다른 선지들을 살펴보면, ①은 8 mod 3으로 결과는 2이고, ②는 10 mod 4로 결과는 2이며, ③은 6 mod 4로 결과는 2이다. 이들은 모두 0이 아니므로, 4번이 유일하게 30 mod 5와 관계가 같다.

 

 

 

54. 부울함수 \( F= AB +  ABC+ AB\overline{C} \) 를 간소화한 결과는? (2점)
① \( F = AB + AC \)

② \( F= AB +  A\overline{C} \)
③ \( F = AB \)
④ \( F = AC \)

 

정답: 3

해설: 우선 \( ABC \)와 \( AB\overline{C} \)는 \( AB \)라는 공통 항을 가지고 있으며, 이를 통해 \( AB \)만 남게 된다. \( AB \)항은 \( AB \)를 포함하므로 다시 작성할 필요가 없다. 따라서 최종적으로 \( F = AB \)가 된다. 

 

 

 

* (55~56) 다음 그래프 G에 대해 물음에 답하시오 

 

 

 

55. G와 관계된 서술 중 부적절한 것은?

1) G는 단순그래프이다.

2) G의 꼭지점의 집합은 {v1, v2, v3, v4} 이다.

3) G의 차수는 10이다.

4) v1의 차수는 2이고 v2의 차수는 4이다. 

 

정답: 1

해설:  단순그래프는 루프가 없어야 한다.  

 

 

 

56. 그래프 \( G \)를 인접행렬로 표현한 것은? (3점)
① 
    0 1 0 1
    1 0 2 1
    0 2 0 0
    1 1 0 0
② 
    1 1 1 0
    1 2 1 1
    0 1 2 0
    1 1 1 1
③ 
    0 2 0 1
    2 0 2 1
    0 2 0 0
    1 1 0 0
④ 
    0 1 1 0
    1 0 1 0
    1 1 0 2
    0 0 2 0

 

정답: 1

 

 

 

 

57. 다음 서술 중 부적절한 것은?

1) 사이클이 없는 연결그래프를 트리라고 한다.

2) n개의 꼭지점을 가지는 연결그래프가 n-1개의 변을 가진다면 해당 그래프는 트리이다.

3) 높이가 k인 완전 이진트리의 최대 노드 수는 2^k+1 -1이다.

4) 최소 신장트리를 구하는 방법으로 힙 정렬 알고리즘과 쉘 정렬 알고리즘이 있다. 

 

정답: 4

해설: 정답은 4번이다. 최소 신장트리를 구하는 과정에서 사용되는 알고리즘은 크루스칼 알고리즘과 프림 알고리즘이 대표적이다. 이 두 알고리즘은 그래프 내에서 최소 비용의 트리를 찾아내는 데 초점을 맞춘다. 반면, 힙 정렬과 쉘 정렬은 정렬 알고리즘으로, 데이터의 순서를 재배열하는 데 사용되며, 그래프의 최소 신장트리를 구하는 용도로는 사용되지 않는다. 따라서 4번 선지는 부적절하다. 다른 선지들은 트리와 관련된 정의나 특성을 올바르게 서술하고 있다. 1번은 사이클이 없는 연결 그래프의 정의를, 2번은 트리의 변의 수와 꼭지점의 관계를, 3번은 완전 이진 트리의 노드 수를 정확히 기술하고 있다.

 

 

 

58. 다음은 4개의 수(3, 4, 5, 7)가 키로 입력되었을 때 생성된 이진 탐색 트리이다. 키로 사용된 4개의 수는 어떤 순서로 입력 되었는가? 

 

 

 

1) 4, 3, 5, 7

2) 7, 5, 3, 4

3) 5, 3, 7, 4

4) 4, 3, 7, 5 

 

정답: 3

해설: 이진 탐색 트리(Binary Search Tree, BST)는 특정 규칙을 따라 구성된 자료구조로서, 각 노드의 왼쪽 하위 트리에는 노드보다 작은 모든 값이 있으며, 오른쪽 하위 트리에는 노드보다 큰 모든 값이 위치한다. 주어진 수 5, 3, 7, 4를 이 순서대로 입력하여 이진 탐색 트리를 생성하면 다음과 같이 트리가 구성된다:

- 1. 5를 루트 노드로 설정한다.
- 2. 3은 5보다 작으므로 5의 왼쪽 자식 노드가 된다.
- 3. 7은 5보다 크므로 5의 오른쪽 자식 노드가 된다.
- 4. 4는 5보다 작으므로 5의 왼쪽 트리에 들어가고, 3보다 크므로 3의 오른쪽 자식 노드가 된다.

따라서 위의 그림과 같은 이진 탐색 트리가 된다. 

    5
   / \
  3   7
   \
    4

 

59. 다음과 같은 컴퓨터 네트워크가 있다고 하였을 때, A에서 B까지 최단 거리로 가는 방법은 몇 가지인가? 

 

 

 

 

 

1) 12

2) 20

3) 24

4) 35 

 

정답: 4

해설: 오른쪽으로 하나의 변을 이동하는 것을 r, 위로 하나의 변을 이동하는 것을 u라고 하면 A에서 B로 최단 길이로 가기 위해서는 4개의 r과 3개의 u를 거쳐야 한다. 따라서 총 7개의 변을 지나 A에서 B로 가는 방법은 7!/4! x 3!으로 35이다. 

 

 

 

60. 다음 상태 전이도는 결정적 유한 오토마타를 표현하고 있다. 입력 문자열 00011에 대응하는 출력 문자열을 구한 것은? 

 

 

1) ababa

2) abbba

3) aaabb

4) bbbaa

 

 

 

정답: 2

 

 

 

 

 

 

 

 

 

---