[데이터 구조] 퀴즈 정답 및 해설 | 1~13차시

[ 2차시 ]

정답: 구현

 

 

 

 

정답: 4번 설계

해설: 설계 단계의 핵심 단어는 '알고리즘'이다.

 

 

 

정답: 2번 구현 레벨

해설: Abstract(추상화)는 구현과 거리가 멀다

 

 

 

정담: 2번 ADL 변환기

 

 

정답: 3번

해설: 특정 Programming 언어로 작성되어 있지 않다. 이건 목적이다.

 

 

 

정답: 2번

해설: x<1도 결과상 문제는 없지만, 이렇게 표현하게 되면 마지막에 1을 두 번 곱하게 됨

...*3*2*1*1은 팩토리얼 정의에 맞지 않기 때문에 x<=1이 맞다.

 

 

정답: 4번 수행 속도

해설: 시스템 스택에 activation record가 쌓임 = 오버 헤드

 

 

정답: 3

해설: 순환함수는 계속 시스템 스택에 activation record가 쌓인다. (오버 헤드)

 

 

---

정답: 4번

해설: 프로그램의 모든 문장에 항상 step count 카운팅 문장을 넣는 것은 번거롭고 어렵다.

 

 

정답: 1번

해설: program code의 단계수를 하나하나 세는 방법은 step count에 가깝다.

 

 

 

 

정답: 1번

 

 

 

 

정답: 1번

해설: O(n^1+2)가 아니라 가장 최악의 경우인 O(n^2)이 맞다.

 

 

 

 

 

 

정답: 1번

해설: Time & Space 측정법에서 Time Complexity를 측정하는 방법인 Run time 추정법은 machine dependent하다. machine independent한 방법은 step count 방법이다.

 

 

 

 

정답: 4

 

 

 

 

---

[ 5차시 ]

정답: 2번

해설: move가 아닌 retrieve이다.

 

 

정답: 2번

해설: 100 + 9*40 + 14 = 474

 

 

 

정답: 4번

해설: 먼저 소진되는 것들을 먼저 곱함

 

 

 

 

 

정답: 4번

 

 

 

정답: 4번

 

 

 

 

 

---

[ 6차시 ]

 

정답: 4번

해설: 정렬이 필요하지는 않다. 단, 다항식을 선형 리스트로 표현할 경우에는 차수 내림차순으로 표현해야 하기 때문에 정렬이 필요함.

 

 

 

 

정답: 4번

해설: 계수가 아니라 지수를 비교하여 연산한다.

 

 

 

정답: 1번

 

 

 

 

 

정답: 1번

해설: 추가적인 자료구조(=배열)을 사용하여 운영 정보(starting_pos, row_terms)를 넣어 사용한다.

 

 

---

정답: 4번

해설: 

 

 

 

 

 

정답: 4번

 

 

 

정답: 4번

해설: depth까지 있어야 함. (row, col, depth, value)가 맞다.

 

 

---

 

정답: 2번

 

 

 

 

정답: 4번

 

 

 

정답: 2번

해설: 배열은 원소를 임의의 위치에 삽입하는 비용이 더 크다. 더 힘들다.

 

 

 

 

 

정답: 2번

해설: p 노드가 가진 data 값이 x일때 포인터 p 반환

 

---

 

 

정답: 3번

해설: 수행 중 미리 할당(자유 공간 리스트는 while문을 이용하여 미리 많이 할당해둔다.)

 

 

 

정답: 2번

해설: 이중 연결 리스트는 양 방향으로 움직이기 때문에 link 포인터가 2개이다. (rlink, llink).

연결리스트도 연속된 메모리 공간에 저장될 수도 있다.

 

 

 

정답: 2번

해설: 2번은 근거가 없는 내용이다.

 

 

 

정답: 2번

해설: ptr이 null일때 insert하지 않고 바로 return하는 부분에서 delete하는 기능인 것을 확인할 수 있다.

 

 

 

 

정답: 2번

 

 

 

 

 

 

 

 

정답: 2번

해설: 헤더 노드에는 통계정보를 포함한 다양한 정보를 포함할 수 있다.

 

 

 

 

정답: 1번

 

 

 

 

정답: 2번

해설: loop가 없기 때문이다. 스텝 k는 상수라서 O(1)로 취급한다. n은 loop가 들어올때 다룬다.

 

 

정답: 1번

해설: delete(queue)와 dequeue(queue)의 차이점에 주목해야한다. delete는 정말 삭제만 하지만. dequeue는 삭제하는 원소를 반환까지 한다. 따라서 해당 함수는 front item을 return 하므로 정답은 1번 dequeue이다.

 

 

정답: 4번

해설: 순차 큐와 원형 큐 모두 front == rear일 때 Empty Queue이다.

 

정답: 2번

해설: front % M == (rear+1) % M 일때 원형 큐는 포화 상태이다.

 

 

정답: 2번

해설: front와 rear가 존재하지 않는 것이 아니라, front와 rear가 NULL인 것이다.

 

 

정답: 3번

해설: 큐가 비어있다면 함수가 종료되고, 비어있지 않다면 노드를 삭제 후 반환하기 때문이다.