더여니의 갓생 일기

1. 스레드 이진 트리에서 노드 s의 왼쪽 자식으로 새로운 노드 l을 삽입하는 C++ 함수를 작성하라. s의 왼쪽 서브트리는 l의 왼쪽 서브트리가 된다. void ThreadTree :: Insertleft(ThreadedNode *s, ThreadedNode *r) { r->leftChild = s->leftChild; r->leftThread = s->leftThread; r->rightChild = s; r->rightThread = true; s->leftChild = r; s->leftThread = false; if(!r->leftThread) { ThreadedNode *temp = InorderSucc(r); temp->leftChild = r; } } 2. 스레드 이진 트리에 대한 C++..

1. 체인에 있는 노드의 수를 계산하는 C++ 함수 length를 작성하라. 이 함수의 시간 복잡도는 얼마인가? int length() { ChainNode* ptr; if (isEmpty()) { return 0; } int length = 1; for (ptr = head->link; ptr != head; ptr = ptr->link) length++; return length; } * 시간 복잡도 : O(n) 원소의 개수만큼 반복 * 노드가 공백인 경우는 길이 0 반환. 아닌 경우는 1부터 시작하여 ptr을 head노드가 가르키는 노드부터 시작하여 head가 아닐때까지 반복 시킴. 2. x를 체인에 있는 임의의 노드를 지시하는 포인터라고 하자. 체인으로부터 이것을 삭제하는 C++ 함수를 작성하라...

다음 연습문제들은 모두 4.2.4.절의 정의들을 기반으로 하고 있다. 모든 함수들은 클래스 Chain의 멤버 함수로 구현되는데, 그래서 이들은 ChainNode의 데이타 멤버들에 접근할 수 있다고 가정한다. 1. 체인에 있는 노드의 수를 계산하는 C++ 함수 length를 작성하라. 이 함수의 시간 복잡도는 얼마인가? * 시간 복잡도 : O(n) * 참고 : https://jaimemin.tistory.com/159 2. x를 체인에 있는 임의의 노드를 지시하는 포인터라고 하자. 체인으로부터 이것을 삭제하는 C++ 함수를 작성하라. 만일 x == first라고 하면, first는 체인에서 새로 첫 번째가 된 노드를 가리키도록 반드시 재설정 되어야 한다. 이 함수의 시간 복잡도는 얼마인가? * 시간 복잡도..

4. 다음의 쌍 각각에 대하여 IS-A 관계로 연결되는지 여부를 말하고 그 이유를 밝혀라, (a) 직사각형과 사다리꼴 둘 중의 하나를 어느 것의 서브 타입이라고 할 수 없음 (b) 직사각형과 원 둘 중의 하나를 어느 것의 서브 타입이라고 할 수 없음 (c) 사자와 호랑이 둘 중의 하나를 어느 것의 서브 타입이라고 할 수 없음 (d) 스택과 순서 리스트 스택이 정렬되어 있으면 순서 리스트라고 할 수 있으므로 IS-A 관계 (e) 큐와 순서 리스트 큐가 정렬되어 있으면 순서 리스트라고 할 수 있으므로 IS-A 관계

1. 이 절에서 사용된 표현에서 임의의 원소 A[i][j]를 찾아 그 값을 변경하는 데 소요되는 시간은 얼마나 되는가? - 일반적인 방법 : O(cols*rows) - 빠른 전치 행렬 : O(cols+terms) 3. 희소 행렬을 읽고 출력하는 C++ 함수를 작성하라. 이것은 를 다중화해서 구현되어야 한다. 입출력 형식을 설계해야 하지만 내부 표현은 이 절에서 사용된 0이 아닌 원소들의 1차원 배열을 사용하여야 한다. 이 함수들의 연산 시간을 분석하라. *SparseMatrix 코드의 일부분 발췌 * 전체 코드는 첨부파일에 4. RowSize와 RowStart를 저장하기 위해 두 개의 배열을 사용하지 않고 단지 하나의 배열만을 사용하도록 FastTranspose 함수를 다시 작성하라. //변경 전 // ..