자료구조론-가정답(2021-05-10 / 243.4KB / 348회)
자료구조론 가 책형 1 쪽 자료구조론 문 1. 다음 C 언어 함수를 사용하여 function(9)를 수행했을 때, 반환 되는 값은? int function(int n) { if (n 1; j /= 2) sum += 1; } ① O(n) ② O(n2) ③ O(nlogn) ④ O(logn) 문 14. 다음은 원형 연결 리스트(circular linked list)의 길이를 구하는 C 언어 프로그램이다. ㉠ ~ ㉢에 들어갈 내용으로 옳게 짝지은 것은? typedef struct node { int key; struct node *link; } list_node; int length(list_node *ptr) { list_node *temp; int count = 0; if ( ㉠ ) { temp = ptr; do { count++; ㉡ ; } while ( ㉢ ); } return count; } ㉠ ㉡ ㉢ ① ptr != NULL temp = temp→link temp != ptr ② ptr == NULL temp = temp→link temp == ptr ③ ptr != NULL ptr = temp→link temp != ptr ④ ptr == NULL ptr = temp→link temp == ptr 문 15. 이중 연결 리스트(doubly linked list)의 노드를 나타내는 구조체 node에 이전 노드를 가리키는 포인터 llink와 다음 노드를 가리키는 포인터 rlink가 있다고 하자. 포인터 new_node가 가리키는 노드를 포인터 p가 가리키는 노드의 왼쪽에 삽입할 때, 문장의 수행 순서를 바르게 나열한 것은? ㄱ. p→llink→rlink = p→rlink; ㄴ. p→rlink→llink = p→llink; ㄷ. p→llink→rlink = new_node; ㄹ. new_node→rlink = p; ㅁ. p = new_node; ㅂ. new_node→llink = p→llink; ㅅ. p→llink = new_node; ① ㄱ → ㄴ ② ㅂ → ㅅ → ㄷ → ㄹ ③ ㄷ → ㅂ → ㄹ → ㅁ ④ ㄷ → ㄹ → ㅂ → ㅅ 문 16. 다음은 C 언어를 사용하여 원형 큐(circular queue)의 삽입(enqueue)과 삭제(dequeue) 연산을 구현한 것이다. int Q[8] = {0}; int front = 0; int rear = 0; void enqueue(int item) { rear = (rear + 1) % 8; if (front == rear) { printf("Queue is full.\n"); return; } Q[rear] = item; } int dequeue() { int item; if (front == rear) { printf("Queue is empty.\n"); exit(1); } else { front = (front + 1) % 8; item = Q[front]; Q[front] = 0; return item; } } front와 rear의 값이 0인 공백 큐에 6개의 값 1, 3, 2, 4, 8, 6을 차례대로 삽입하고, 여기에서 2개의 값을 삭제한 다음, 다시 3개의 값 5, 7, 9를 차례대로 삽입할 때, 배열 Q의 최종 모습은? Q[0] Q[1] Q[2] Q[3] Q[4] Q[5] Q[6] Q[7] ① 0 7 9 2 4 8 6 5 ② 2 4 8 6 5 7 9 0 ③ 7 9 0 2 4 8 6 5 ④ 9 0 2 4 8 6 5 7 자료구조론 가 책형 4 쪽 문 17. 다음 C 프로그램의 출력 값으로 옳은 것은? (단, int 데이터 타입은 4 바이트로 표현되며, 배열 a의 시작 주소는 2293520이다) int main() { int a[3][4] = {{10, 15, 20, 25}, {30, 35, 40, 45}, {50, 55, 60, 65}}; printf("a+1 = %d, ", a+1); printf("*(*a+2) = %d, ", *(*a+2)); printf("*(*(a+1)+2) = %d\n", *(*(a+1)+2)); return 0; } ① a+1 = 2293521, *(*a+2) = 50, *(*(a+1)+2) = 55 ② a+1 = 2293536, *(*a+2) = 20, *(*(a+1)+2) = 40 ③ a+1 = 2293521, *(*a+2) = 20, *(*(a+1)+2) = 40 ④ a+1 = 2293536, *(*a+2) = 50, *(*(a+1)+2) = 55 문 18. 다음 인접행렬이 표현하는 그래프의 부분 그래프 중에서 간선 (edge)이 최소한 1개 이상인 연결 그래프의 개수는? [0] [1] [2] [3] [0] 0 1 1 1 [1] 1 0 1 0 [2] 1 1 0 0 [3] 1 0 0 0 ① 12 ② 13 ③ 14 ④ 15 문 19. 기수 정렬(radix sort)을 수행하여 다음 원소들을 오름차순으로 정렬하고자 한다. 각 단계별 정렬 순서로 나타날 수 없는 것은? (단, 정수 는 ≤ ≤ 범위에 있고 각 자리수를 나타내는 3개의 서브키( , , )로 구성되어 있다고 생각한다. 여기서 는 일의 자리 수, 는 십의 자리 수, 는 백의 자리 수를 의미하고, ≤ ≤ 이다) 129, 308, 506, 92, 3, 841, 33 ① 3, 506, 308, 129, 33, 841, 92 ② 92, 3, 33, 129, 308, 506, 841 ③ 841, 92, 3, 33, 506, 308, 129 ④ 3, 33, 92, 129, 308, 506, 841 문 20. 행렬 가 이면 0 값을 가질 때, 이러한 행렬을 삼중대각행렬(tridiagonal matrix)이라고 하며, 다음은 × 삼중 대각행렬의 예를 보여준다. (단, ≤ ≤ , ≤ ≤ ) 행렬 × 의 0이 아닌 원소 를 열 우선(column major) 순서로 배열 A에 저장한다고 할 때, 0이 아닌 원소 가 배열 A에 저장되는 위치를 계산하는 수식으로 옳은 것은? (단, 배열 A의 시작주소는 이고, 행렬 의 0인 원소는 배열에 저장하지 않는다) ① · ② · ③ · ④ ·