6주차 퀴즈 복습
1번 문제
다음 소스 코드를 완성하여 55와 22가 각 줄에 순서대로 출력되게 만드세요.
#include <stdio.h>
int main()
{
int numArr[5] = {11, 22, 33, 44, 55};
int *numPtrA;
void *ptr;
numPtrA = &numArr[2];
ptr = numArr;
printf("%d\n", /** 변수는numPtrA만을 사용하세요. **/);
printf("%d\n", /** 변수는 ptr만을 사용하세요. **/);
return 0;
}→ numPtrA 만을 사용할 수 있으므로, numPtrA는 2번 인덱스인 33이고, 우리가 원하는 결과인 55를 꺼내기 위해서는 인덱스에 +2를 하여야합니다.
그러므로 첫 번째 printf 답은 *(numPtrA + 2) 입니다.
→ ptr함수만 쓸수 있으므로, 위에서 ptr = numArr 라고 정의했고 void로 선언했으니 자료형을 같이 선언해서 22를 불러와야 합니다. 이것을 저희는 캐스팅이라고 합니다. 고로 int로 캐스팅하여 22의 값을 불러와야합니다.
그러면 두 번째 printf 답은 ((int )ptr + 1) 또는 (++(int )ptr) 입니다.
2번 문제
아래 코드의 실행 결과를 적어 보시오.
#include <stdio.h>
int main()
{
char *str[2];
str[0] = "hello!";
str[1] = "jungler";
printf("1. %s\n", str[0] + 1);
printf("2. %s\n", (str + 1)[0] + 2);
return 0;
}→ 첫 번째 printf의 경우 str[0] 으로 ‘h’를 가르키고, 그 인덱스에 +1을 하였으니 ‘e’를 가르키게 됩니다. 해당문자 이후의 문자들을 출력하므로 답은 ello! 입니다.
→ 두 번째 printf는 (str+1)을 통해 포인터로 str[0], str[1] 중 str[1]을 가르킵니다. 그 이후 글자에서 +2를 지정했으니 n 부터 출력하게 됩니다. 그러므로 답은 ngler 입니다.
3번 문제
다음과 같은 순서로 데이터를 탐색 구조에 삽입할 때, 이진 탐색 트리, AVL 트리, 레드블랙 트리의 결과 트리를 그리시오.
(7, 5, 11, 10, 2, 3, 6, 8, 15, 13 / 단, 블랙노드는 숫자(B), 레드노드는 숫자(R)로 표시한다.)
→ 위에서 부터 차례대로 이진 탐색 트리, AVL 트리, 레드블랙트리 입니다.
작성하는 방법은 개념 포스팅을 참조하자.
4번 문제
위 레드 블랙 트리의 결과에서 10을 삭제했을 때의 결과 트리를 그리시오. 두 개의 자식 노드를 가진 노드를 삭제할 경우 삭제할 노드보다 작은 노드 중 가장 가까운 노드와 위치를 바꾼다고 가정하세요.
→ 레드 블랙 트리의 삽입 삭제 이론에 따라 노드를 삭제하고 재조정하는 과정을 거칩니다.
대략적으로 설명하자면, 문제 조건에 따라 10과 8을 스위칭하고 10을 삭제 합니다. 15와 13이 색을 교환하고 left rotation을 수행하며 13의 자식 11은 8의 자식으로 옮겨지게 됩니다.
5번 문제
n개의 원소가 삽입돼 있는 이진 탐색 트리, AVL 트리, 레드 블랙 트리에 새로운 원소를 삽입할 때, 최악의 경우의 시간 복잡도를 빅오(Big-Oh) 표기법으로 표현하시오.
→ 이진 탐색 트리는 최악의 경우 선형 리스트 형식이 되어 O(N)이고 AVL과 RB tree는 이진 균형 트리로써 항상 O(logN)의 시간 복잡도를 가집니다.
6번 문제
x86-64 OS에서 아래 c코드를 실행할 때 ???로 되어 있는 부분의 값을 적어보시오. (1점)
#include <stdio.h>
void main()
{
char arr_char[5];
int arr_int[5];
int64_t arr_int64[5];
printf("char base : %p, %p\n", arr_char, &arr_char[2]);
printf("int base : %p, %p\n", arr_int, &arr_int[0]);
printf("int64 :%p, %p\n", arr_int64, &arr_int64[3]);
}(printf에서 %p는 포인터 변수가 가리키는 객체의 메모리 주소를 16진수 형태로 출력하게 해주는 format specifier 입니다.)
→ [출력]
char base : 0x8004000fd3, ??? → 0x8004000fd5
int base : 0x8004000fbc, ??? → 0x8004000fbc
Int64 : 0x8004000f90, ??? → 0x8004000fa8
주어진 자료형에 따라 계산합니다.
- char은 1바이트 이므로 &arr_char[2]는 메모리 주소상 +2이므로 fd5
- int형은 애초에 0이라서 그대로 나오면 됩니다. fbc
- int 64 는 하나에 8바이트이므로 &arr_int64[3] 는 8x3=24바이트 임을 알 수 있습니다.
그러므로 16진수 표기법에 따라 fa8 입니다.
난이도는 좀 어려웠던 마지막 문제 빼고는 포인터의 개념과 각각의 트리 개념을 잘 알고 있으면 어렵지 않게 풀 수 있었던 퀴즈인 것 같습니다.
