1번 문항
아래 코드의 잘못된 부분을 모두 수정하여 제출하시오.
new_node 정의 부분만 제출하며 struct 정의 부분은 변경하지 못합니다.
#include <stdlib.h>
typedef struct node_t {
int val;
struct node_t *next;
} node_t;
node_t* new_node(int val) {
node_t *p;
p = malloc(1);
p.val = val;
return p;
};
1번 답안
node_t* new_node(int val) {
// 기본적인 malloc 요구조건: 메모리 크기, pointer casting, pointer type
node_t *p = (node_t *) malloc(sizeof(node_t));
if (p) { // malloc이 NULL을 return할 경우의 대비
p->val = val;
p->next = 0; // memory가 initialize 되지 않았을 경우의 대비. 이게 싫으면 malloc을 calloc으로...
}
return p;
};2번 문항
다음 세 함수 f1, f2, f3 각각에 대해서 문제가 있는지, 문제가 있다면 어떤 문제가 있는지 설명하시오.
int* f1(void) {
int x = 10;
return (&x);
}
int* f2(void) {
int *px;
*px = 10;
return px;
}
int* f3(void) {
int *px;
px = (int *) malloc(sizeof(int));
*px = 10;
return px;
}2번 답안
f1: 지역변수 x의 주소를 return함
f2: uninitialized pointer
- px의 값이 임의의 값이므로 임의의 주소에 10을 넣으려고 함. Segmentation Fault
f3: memory leak 가능성 있음 - malloc으로 할당된 메모리가 free되지 않음.
- f3를 부른 함수에서 free를 해 주지 않으면 memory leak 발생
3번 문항
Red-black tree의 search(=find), insert, delete의 time complexity는 얼마인가?
Big-O notation, 즉 O(...)의 형태로 답하시오.
3번 답안
Search(find): O(log n)
Insert: O(log n)
Delete: O(log n)
4번 문항
4-1.다음 프로그램을 compile 하고 실행하면 어떤 결과가 나오는가?
#include<stdio.h>
int main() {
char s[] = "Fine";
*s = 'N';
printf("%s\n", s);
return 0;
}4-2.왜 위의 답처럼 결과가 나오는지 설명하시오.
4번 답안
4-1. 프로그램 결과
프로그램을 실행하면 "Nine" 출력
4-2. 결과에 대한 설명
배열 s의 첫 번째 요소를 'N'으로 변경했기 때문에 "Fine"이 "Nine"로 변경되어 출력
5번 문항
다음 프로그램에서 string "abc", "def", "ghi"는 각각 어느 메모리 영역으로 할당되는가?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
char *s1 = "abc";
char s2[] = "def";
char *s3 = (char *) malloc(4);
strncpy(s3, "ghi", 4);
printf("%s %s %s\n", s1, s2, s3);
free(s3);
return 0;
}5번 답안
abc - data
def - stack
ghi - heap
참고
cc -S 로 assembly code로 바꿔 보면 확실히 알 수 있음.
'abc' 만 .rodata에 있고, 'def'는 stack 영역에 복사,
'ghi'는 malloc의 return 값인 %rax의 indirect address로 복사됨.
extra credit
A.
Python의 set은 unordered set의 구현체라고 부르고, Red-black tree 같은 data structure는 ordered set의 구현체라고 부릅니다.
ordered set, unordered set 구현체 각각의 장단점은 무엇인지 설명하십시오.
time complexity 관점으로도 비교하십시오.
unordered set:
- well distributed hash function 사용
- 전체 원소를 모두 나열 및 정렬하지 않고는 이전/다음 순서의 원소 찾는 것이 불가능
- search 시 있다/없다만 효율적으로 판단할 수 있다.
- 가장 가까운 원소는 찾는 것은 O(H) - H: hash slot의 갯수
- search, insert, delete: 거의 O(1)
ordered set:
- balanced tree 사용.
- 순서가 주어졌을 때 이전/다음 원소를 O(log n)에 찾을 수 있음.
- 해당 집합에 없는 값이라도 search시 가장 가까운 값을 O(log n)에 찾을 수 있음
- search, insert,delete, next, previous: O(log n)
B.
rbtree-lab의 node 정의는 노드 색을 위해서 int type을 사용하므로 64 bit를 사용합니다.
Red-black tree의 색은 red 아니면 black이므로 1 bit 만으로 표현할 수 있습니다.
어떻게 하면 63-bit의 낭비를 줄일 수 있을까요?
간단하게 답하십시오. (실제로 공간을 줄여서 사용합니다.)
Linux kernel의 rbtree 참조
rb_parent_color에는 부모노드의 주소값이 long으로 형변환되어 저장된다.
주소는 4 혹은 8의 배수로 증가하기 때문에 하위 2~3비트는 사용되지 않는다.
rb_node에서는 이 사용하지 않는 비트를 색 지정으로 사용하여 추가 변수 필요없이 메모리 공간을 절약한다.
그래서 rb_parent_color 멤버 변수를 통해 부모노드 주소와 __본인노드 색 두가지를 동시에 가질 수 있다.
C.
search tree는 순서대로 저장되어 있는 것이 특징이다.
특정 node의 pointer가 주어졌을 경우 다음 node의 pointer를 반환하는 다음 함수를 구현하라
node_t *node_next(const node_t *p); // 만약 p가 마지막 노드면 NULL을 반환
// Sentinel node를 사용하지 않은 경우
node_t *node_next(const node_t *p) {
if (p == NULL) {
return NULL;
}
// 우측 자식 tree가 있다면 그 tree의 맨 왼쪽 node
if (p->right != NULL) {
node_t *q = p->right;
while (q->left != NULL) {
q = q->left;
}
return q;
}
// 우측 자식 tree가 없고 p가 부모의 왼쪽 자식이면 부모 노드가 다음 노드
// 오른쪽 자식이면 그 위에서 찾음. root까지 가면 NULL
node_t *parent = p->parent;
while(parent != NULL && p == parent->right) {
p = parent;
parent = p->parent;
}
return parent;
}
}