중간고사 (자료 구조)

Transcription

1 Data Structures 215 중간고사 문제에서명시적으로기술하지않은부분은교재의내용에근거함 다음용어에대하여간단하게설명하시오 ( 각 3 점 *1=3 점 ) 1 abstract data type 6 Circular linked list 2 recursion 3 time complexity 4 space complexity 5 Single linked lists 7 Double linked list 8 stacks 9 queues 1 postfix 1 자료구조와이를조작하는연산집합의묶어놓은타입 2 자기와동일한함수를호출 3 연산횟수 ( 또는연산에소요되는시간의길이 ) 4 연산에필요한메모리공간의크기 5 동일한정보를가진노드들을포인터로연결한데이터구조또는배열 (array) 에서중간데이터삽입 / 삭제시발생하는과도한 move 연산발생을제거하기위해만든노드들의연결구조 6 List 구조에서맨마지막노드가맨처음노드를가리키는구조 7 List 구조에서각노드가이전및이후노드를가리키는포인트를가지고있는구조, 즉각노드가이전노드를가리키는 left link pointer, 이후노드를가리키는 right link pointer 를유지하고있음 8 Last-in First-Out 특징을가지는자료구조 9 First-in First-Out 특징을가지는자료구조 1 연산자가관련된 2 개의피연산자뒤에나오는수식표현 2 다음빈칸에알맞은단어또는숫자를쓰시오. ( 각 3 점 *9=27 점 ) 1 하나의함수가호출할수있는 recursive call 의개수는 (stack 또는 stack memory) 이허용하는한도에의해결정된다. ( 주의 : 자료구조명칭이들어감 ) 2 float a[1] 으로선언된배열의시작주소를 1 번지라고할때, 배열의 1 번째 cell 의주소는 [14] 번지이다. ( 주의 : sizeof(float) => 4 를출력 ) 3 int a[5] =1,2,3,4,5; int *p=a; *p=5; p=p+3; *p=1; 문장이수행되면, 배열변수에포함된모든 cell 의내용은어떻게변경되나? 5,2,3,1,5,

2 4 int i=1; int *pi=&i; 의문장이수행된이후, 포인터변수를이용하여변수 i 의값을 2 으 로변경하는문장은 [ *pi=2 ] 이다. 5 int a[1]; 과동일하게 동적으로 정수 1 개를저장할수있는메모리를할당하는문장은 [int *p=(int*)malloc(sizeof(int)*1); ] 이다. (Hint: malloc() 함수를활용 ) 6 struct A int fa; int fb; a; struct A *p=&a; 라고할때, 변수 p 를이용하여멤버변수 fa 에 1 을할당하는문장은 [(*p).fa = 1; ] 이다. 7 단순연결리스트의노드에대한구조체를정의한 C 코드는 typdef struct ListNode element data; struct ListNode *link; ListNode; 이다. 단순연결리스트의노드들을노 드포인터 p 로탐색하고자한다. p 가현재가리키는노드에서다음노드로가기위한 C 코 드는 [p = p->link; ] 이다. 8 미로 (maze) 게임을구현하기위해서필요한자료구조는 [Stack, 스택 ] 이다. 9 은행창구에서고객들이들고나가는상황을시뮬레이션하기위해필요한자료구조는 [Queue, 큐 ] 이다. 3 다음 2 개의 C 언어코드에서시간복잡도를 BigOh 표기법으로각각작성하고그근거 를제시하시오. (1 점 ) ( 주의 : 좌측에있는 sub() 함수의시간복잡도는 O(n) 으로가정 ) for (i=1; i < n; i *= 2) sub(); // sub() 함수의시간복잡도 =O(n) void foo(int n) int i, j, k, r; for(i=; i<n; ++i) for (j=; j<n; ++j) for(r=; r<1; ++r) ++k; 좌측 : O(n*log 2n) => 반복문안에서 i 가 2 배증가하면서 n 까지증가함. k 번반복 한다고할때, i 값은 2 k 가되고, 그값이 n 과같다고한다면 k = log 2n 우측 : 대입 (i=): 1 회 + 비교 (i<n): (n+1) 회 + 덧셈 (++i): n 회 + 대입 (j=): n 회 + 비교 (j<n): n*(n+1) 회 + 덧셈 (++j): n*n 회 + 대입 (r=): n*n 회 + 비교 (r<1): n*n*11 회 + 대입 (++r): n*n*1 회 + 덧셈 (++k): n*n*1 = > O(n 2 )

3 4 다음함수를 recursive(1) 로호출하였을때, 화면에출력되는내용과최종적인함수의 반환값을구하시오. (1 점 ) int recursive(int n) printf( %d,, n); if (n<1) return -1; else return ( recursive(n-2) + 1 ); 화면출력 : 1, 8, 6, 4, 2, 반환값 : 4 5 다음을계산하는 recursive function 을작성하시오. (Note: 함수명은 sum ) (1 점 ) n int sum(int n) if( n==1 ) return 1; else return (n + sum(n-1));

4 6 다음은단순연결리스트 (single linked list) 를위한데이터구조를보여주는 C 코드이다. 빈칸을완성하시오. (1 점 ) // phead: 리스트의헤드포인터의포인터 // p : 선행노드 // new_node : 삽입될노드 void insert_node(listnode **phead, ListNode *p, ListNode *new_node) if( *phead == NULL ) // 공백리스트인경우 new_node->link = NULL; *phead = new_node; else if( p == NULL ) // p 가 NULL 이면첫번째노드로삽입 [new_node->link = *phead;] *phead = new_node; else // p 다음에삽입 [new_node->link = p->link; ] p->link = new_node;

5 7 다음은 6 번문항의단순연결리스트에대한추상데이터타입 ListType 과관련함수 get_node_at( ) 를보여준다. get_node_at( ) 함수는리스트안에서입력인자 pos 위치에있는노드의주소값을반환한다. 빈칸내용을완성하시오. (Hint: 반복문을사용함 ) (1 점 ) => 8 다음은 double linked list 의데이터구조및이를통해구현한 double linked list 의 예를보여준다. 이 list 의적정한위치에새로운노드를삽입하는함수를완성하시오. (1 점 ) // 노드 new_node 를노드 before 의오른쪽에삽입한다. void dinsert_node(dlistnode *before, DlistNode *new_node) new_node->llink = before; new_node->rlink = before->rlink; [before->rlink->llink = new_node;] [before->rlink = new_node;]

6 9 다음은 stack 의 push 연산과 pop 연산을구현한코드이다. (15 점 ) 1 빈칸의코드를완성하시오. (5 점 ) 2 pop () 함수의시간복잡도를 BigOh 표기법으로작성하고, 그이유를설명하시오. (5 점 ) 시간복잡도는 O(1) 이다. 이는 pop() 함수가 stack 에저장되어있는데이 터개수에상관없이일정하게항상 top 에있는노드의데이터를반환하기 때문이다. 3 stack 에포함된모든노드를출력하는함수 stack_output( ) 를작성하시오. (5 점 ) int stack_output(linkedstacktype *s) StackNode *temp=s->top; while(temp!= NULL ) printf( %d\n, temp->item); temp = temp->link;

7 1 Palindrome 은앞에서나뒤에서나그철자가같은단어또는구를의미한다. 예를들어, reviver 는 palindrome 이다. 어떤단어나구가 palindrome 인지아닌지를 stack 을이용해서검사할수가있다. 7 번문제에서정의된 stack 을사용하여 palindrome 이면 1 를, 아니면 을 return 하는 C 함수를작성하시오. (Hint: 함수명은 palindrome 으로함. 문자열의길이를반환하는함수는 strlen() 임 ) (15 점 ) void main() char s[5]; int len, i; char ch; printf("enter the String\n"); scanf("%s", s); len = strlen(s); for (i = ; i<len/2;i++) // len 이홀수, 짝수상관없이절반을 push push(s[i]); if( len%2!= ) i++; // len 이홀수인경우, 정가운데문자 skip 하기위함 for ( ; i < len; i++) ch = pop(); if (ch == s[i]) continue; else printf("%s is not a palindrome\n", s); break; if (i == len) printf("%s is a palindrome\n", s);

8 11 Stack 을이용하여 infix 로표현된수식을계산하기위한프로그램은 2 단계과정을거쳐작업을수행한다. 교재내용에준거하여아래물음에답하시오. (4 점 *3=12 점 ) 1 Infix 로표현된수식 1*2/(3-1)+4*5 이 1 단계과정을거쳐 postfix 로변환된형태는? => 1 2 * / 4 5 * + 2 위에주어진수식 1*2/(3-1)+4*5 에서, 프로그램이 1 단계과정에서두번째 1 까지읽었을때, stack 의내용을쓰시오. => / ( - ( 맨오른쪽이 top) 3 (1) 항의문제에서제시한 postfix 형태의수식을계산하는 2 단계과정에서, 프로그램이두번째 * 연산자까지읽어서이를처리하였을때 stack 의내용을쓰시오. => 2 ( 맨오른쪽이 top) 12 아래와같은다항식을효과적으로저장하기위한자료구조를제시하시오. ( 아래문항에 답하면됨 ) (15 점 ) 1x 5 +6x+3 1 위와같은다항식을효과적으로저장하기위한 linked list 형태의자료구조를 C 언어문법에맞게작성하시오. ( 주의 : 하나의노드를정의하기위한자료구조타입 과 list 전체에대한메타데이터를저장하는자료구조타입을제시해야함 ) (1 점 ) 2 두개의다항식이주어졌을때, 이를더하는함수 poly_add() 의알고리즘을개략적 으로기술하시오. (5 점 ) 교재참조

9 13 행렬 (matrix) 를 2 차원배열을이용하여표현하는경우, 대부분의항들이 인희소행 렬 (sparse matrix) 의경우 ( 아래그림의 B 행렬 ) 메모리공간낭비가많아진다. 2 A B 이를해결하기위한자료구조를제시하고설명하시오. ( 주의 : 제시하는자료구조를 C 언어의구조체문법에맞게표현하고, 주요부분을설명해야함 ) (1 점 ) typedef struct int row; => 행번호 int col; => 열번호 int value; => 해당행, 열에해당하는값 element; typedef struct SparseMatrix element data[max_terms]; int rows; => 행의개수 int cols; => 열의개수 int terms; => 항의개수 SparseMatrix; => 행렬에존재하는 < 행, 열, 값 > 들을저장하는배열 2 위에서제시한자료구조를가지고행렬데이터를표현할때, 덧셈연산을수행하는함수의알고리즘을작성하시오. ( 주의 : 해당알고리즘의핵심적인내용을우리말로기술하기바람 ) (5 점 ) 교재참조