다음은 연결리스트 스택의 삭제 알고리즘이다. ㉠ ~ ㉢에 들어갈 문장으… | [7급 국가직 자료구조론] 15년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 15년 1회차
다음은 연결리스트 스택의 삭제 알고리즘이다. ㉠ ~ ㉢에 들어갈 문장으로 옳게 짝지어진 것은? (단, 스택이 비었을 때 top은 NULL이고, top은 스택의 최상위 노드를 가리키는 포인터이다. 또한 스택이 빈 상태에서 맨 처음 삽입되는 노드의 next는 NULL이다)typedef struct node{
int key;
struct node *next;
} NODE; // 스택의 노드 구조
NODE *top = NULL; // 스택의 최상위 노드를 가리키는 포인터
int pop(void) {
NODE *temp;
int ret;
if ( ( ㉠ ) ) {
printf("\n Stack underflow.");
return -1;
}
ret = top→key;
( ㉡ ) ;
( ㉢ ) ;
free(temp);
return ret;
}
㉠ ㉡ ㉢
1
top→next == NULL temp = top→next top = top→next
2
top→next == NULL temp = top top→next = temp→next
3
top == NULL temp = top top = top→next
4
top == NULL temp = top→next top→next = temp→next
해설
㉠ top == NULL, ㉡ temp = top, ㉢ top = top→next 조합이 옳다.
스택이 비면 top이 NULL이므로 top == NULL로 공백을 검사한다. 이후 삭제할 최상위 노드를 temp에 보관하고 top을 다음 노드로 옮긴 뒤 temp를 해제한다.
- top→next == NULL, temp = top→next, top = top→next: 노드가 하나일 때 언더플로로 오판하고, 최상위가 아닌 둘째 노드를 해제한다.
- top→next == NULL, temp = top, top→next = temp→next: top이 바뀌지 않아 해제된 노드를 계속 가리킨다.
- top == NULL, temp = top→next, top→next = temp→next: 최상위 노드가 아닌 둘째 노드를 삭제하게 된다.
오류나 개정된 내용이 보이면 알려주세요