Midterm Exam with Solution - Data Structures and File Management | CS 2604, Exams of Computer Science

Download Midterm Exam with Solution - Data Structures and File Management | CS 2604 and more Exams Computer Science in PDF only on Docsity! CS 2604 Data Structures Midterm Spring 2004 1 V IR G IN IA PO LYTECHNIC INSTITU TE A N D STATE UNIV ER SI T Y UT PROSI M Instructions: • Print your name in the space provided below. • This examination is closed book and closed notes, aside from the permitted one-page formula sheet. No calculators or other computing devices may be used. • Answer each question in the space provided. If you need to continue an answer onto the back of a page, clearly indicate that and label the continuation with the question number. • If you want partial credit, justify your answers, even when justification is not explicitly required. • There are 9 questions, priced as marked. The maximum score is 100. • When you have completed the test, sign the pledge at the bottom of this page and turn in the test. • Note that either failing to return this test, or discussing its content with a student who has not taken it is a violation of the Honor Code. Do not start the test until instructed to do so! Name Solution printed Pledge: On my honor, I have neither given nor received unauthorized aid on this examination. signed CS 2604 Data Structures Midterm Spring 2004 2 1. [12 points] Circle TRUE or FALSE according to whether the statement is true or false: a) 1000 – 7n + 2n2 is Θ( n ) TRUE FALSE b) 27n + 2 log n is Θ( n ) TRUE FALSE c) 2n2 + 3 n log n is Θ( n log n ) TRUE FALSE d) ∑ ∑ = =       + n i i j j 1 1 34 is Θ( n2 ) TRUE FALSE 2. [12 points] Assuming that each assignment, arithmetic operation, comparison, and array index costs one unit of time, analyze the complexity of the following code fragment that transposes an n×n matrix, and give an exact count complexity function T(n): for (int Row = 0; Row < n; Row++) { // 1 before, 2 each pass, 1 after for (int Col = 0; Col < Row; Col++) { // 1 before, 2 each pass, 1 after int tmp = Mtx[Row][Col]; // 3 (2 for indexing, 1 assign) Mtx[Row][Col] = Mtx[Col][Row]; // 5 (4 for indexing, 1 assign) Mtx[Col][Row] = tmp; // 3 (2 for indexing, 1 assign) } } Applying the analysis logic from the notes, we write summations for the two loops. Let R and C be the Row and Col counters, respectively. Then we get: ( ) 2 1 1 1 1 0 1 0 1 0 1 0 2 13 2 212 2 )1(1342 1342 1342 1342 1113121)( nn nnn R nT n R n R R C n R R C n R R C ++= + ++= ++= =      ++= =      ++= +      ++++= ∑ ∑ ∑ ∑ ∑ ∑ ∑ = = = − = − = − = − = CS 2604 Data Structures Midterm Spring 2004 5 For the next three questions, consider the partial BST and binary node template interfaces given below: template <typename T> class BinNodeT { public: Data T Element; BinNodeT<T>* Left; BinNodeT<T>* Right; BinNodeT(); BinNodeT(const T& E, BinNodeT<T>* L, BinNodeT<T>* R); ~BinNodeT(); }; template <typename T> class BST { private: BinNodeT<T> *Root; . . . public: BST(); . . . bool Insert(const T& Elem); T* Find(const T& D); bool Delete(const T& D); ~BST(); }; 7. [12 points] Write a BST member function deleteMax() which conforms to the interface and description below. // The function deletes the maximum value from the BST, as efficiently as possible. // The function may not call any other member functions of the BST template, and // must not use recursion. // // You may assume that the BST does not contain any duplicate values. // template <typename T> void BST<T>::deleteMax( ) { if ( Root == NULL ) return; // handle empty tree BinNodeT<T>* Parent = Root; // will move this to parent of right-most node if ( Root->Right == NULL ) { // root node is right-most Root = Root->Left; // reset Root to left subtree delete Parent; // deallocate old root node return; // done } while ( Parent->Right->Right != NULL ) // walk to parent of right-most node Parent = Parent->Right; BinNodeT<T>* toKill = Parent->Right; // save pointer to right-most node Parent->Right = Parent->Right->Left; // reset parent's child pointer delete toKill; // deallocate right-most node return; } Note: the key is that the maximum value will always be in the right-most node in the BST. So, we need to find the parent of that node, and perform a simple deletion case (since the right-most node has at most one subtree). There are two special cases: an empty tree, and one in which the root node has no right subtree. CS 2604 Data Structures Midterm Spring 2004 6 8. [12 points] Write a BST member function which conforms to the description and interface given below. You may write one or more recursive helper functions if you like. // The function deletes all the leaves from the BST and returns a vector containing // the values that were in the leaves. // template <typename T> vector<T> BST<T>::pickLeaves( ) { vector<T> Trimmings; // vector to hold contents of leaves if ( Root != NULL ) // nothing to do if tree is empty Picker(Root, Trimmings); // trim off the leaves and get their contents return Trimmings; // return leaf contents } template <typename T> void Picker(BinNodeT<T>*& sRoot, vector<T>& Trimmings) { if ( sRoot == NULL ) return; // empty subtree, nothing to do if ( sRoot->Left == NULL && sRoot->Right == NULL ) { // we're at a leaf! Trimmings.push_back(sRoot->Element); // save contents delete sRoot; // deallocate leaf node sRoot = NULL; // fix pointer in parent return; // we're done here } Picker(sRoot->Left, Trimmings); // process left subtree Picker(sRoot->Right, Trimmings); // process right subtree } Notes: The node pointer is passed to the helper function by reference so the helper can properly update the pointer (which is a child pointer in the parent ) when a leaf is removed. The test for an empty tree in the first function is, strictly speaking, unnecessary since the helper function does its own NULL test. But, putting the test in the first function will eliminate the overhead of a function call if the initial tree is empty. CS 2604 Data Structures Midterm Spring 2004 7 9. [10 points] Recall the homework problem about devising a test to determine whether a given binary tree has the BST property. Consider the following proposed solution, which would be passed a pointer to the root of the binary tree: template <typename T> bool isBST( BinNodeT<T>* Root ) { if ( Root == NULL ) return true; if ( (Root->Left != NULL) && (Root->Element <= Root->Left->Element) ) return false; if ( (Root->Right != NULL) && (Root->Element > Root->Right->Element) ) return false; return ( isBST(Root->Left) && isBST(Root->Right) ); } Is the solution is correct? If not, give an example of a binary tree for which it would return the incorrect result. Note there are two cases for possible logical errors: the function may say that a BST is not a BST, or it may say that a non-BST is a BST. You must consider both possibilities. The given function essentially performs a pre-order traversal, comparing the value in each node to the values in its children (if it has children). The traversal logic is correct. The comparisons are correct, as far as they go. Some of you convinced yourselves the element comparisons in the second and third if conditions were incorrect --- they are not. But… the given function performs ONLY a local test at each node. That is not enough. The given function will return true if given the root pointer of the following binary tree, even though it is not a BST: Many other examples exist. However, the given function will deal correctly with any true BST it's given. 50 75 40 80