EECE 330 Problems For Exam, Fall 2011

1. If a node is at position r in the array implementation for a complete binary tree, then its parent is at: a) (r - 1)/2 if r > 0 b) 2r + 1 if (2r + 1) < n c) 2r + 2 if (2r + 2) < n d) r - 1 if r is even e) r + 1 if r is odd. 2. After deleting the node with value 12 from this BST which tree below would result: a) b) c) 4. what will be the bits per letter for the following Huffman coding Letter Freq A 20 M 30 G 1 D 5 a) 1.26 b) 1.69 c) 1.88 d) 1.57 5. for the previous question what will be the encoding of “11011100101” a) AMGMD b) AMAGD c) AMAGA d) AMDGA 2 12 9 6 9 11 15 13 10 2 13 9 6 9 11 15 10 2 11 9 6 9 15 13 10 2 9 9 6 11 15 13 10 Question 1 Suppose that we have numbers between 1 and 1000 in a binary search tree and want to search for the number 363. Which of the following sequences could not be the sequence of nodes examined? a. 2, 252, 401, 398, 330, 344, 397, 363. b. 924, 220, 911, 244, 898, 258, 362, 363. c. 925, 202, 911, 240, 912, 245, 363. d. 2, 399, 387, 219, 266, 382, 381, 278, 363. e. 935, 278, 347, 621, 299, 392, 358, 363. Question 3 What is the maximum number of edges for a graph with n vertices? a. n-1 b. (n-1)/2 c. n(n-1) d. n(n-1)/2 e. n/2 Question 4 In a non-empty full k-ary tree, what is the number of leaves if n is the number of internal nodes? a. kn+1 b. n(k-1) + 1 c. n(k-1) d. n+1 e. nk Question 5 If the costs for the edges of Graph G are distinct, then only ____ MST exist(s) for G. a. one b. no c. two d. three e. none of the above Question 1: What does the following function does? template <class Key, class Elem, class KEComp, class EEComp> BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>:: inserthelp(BinNode<Elem>* subroot, const Elem& val) { BinNode<Elem>* A,*B; A=B=subroot; if (subroot ==NULL) return new BinNodePtr <Elem> (val, NULL, NULL); while(B!=NULL) { A=B; if(EEComp:: lt(val, A->val())) B=A->left(); else B=A->right(); } if (EEComp:: gt(val, A->val()) ) A->setRight(new BinNodePtr<Elem>(val)); else A->setLeft(new BinNodePtr<Elem>(val)); return subroot; } a) It is the nonrecursive version of the insert function b) It is the insert function but it sets the smaller elements to the right part and the larger elements to the left part of the tree c) It is the nonrecursive version of the insert function with duplicates inserted d) It is the insert function but it sets the smaller elements to the right part and the larger elements and the duplicates to the left part of the tree Question 2: 48 70 44 50 22 78 90 100 86 48 70 44 50 22 78 90 100 86 Given the following tree, we traverse in it postorder then we insert the obtained results one after the other in a different binar y tree. Which of these trees is the new tree? a) b) 48 70 44 50 22 78 86 100 90 48 70 44 50 22 78 90 100 86 48 70 44 50 22 78 90 100 86 c) d) Question 3: In order to merge two general trees in the fastest way we have to a) traverse the shortest tree(least number of elements) and insert the results in the other tree b) traverse the longest tree (greatest number of elements) and insert the results in the other tree c) create a new pointer to a general tree and link it to the roots of each tree A B C D E K Q Z W A B C Z Q D E W K D A B C Z Q E W K D A B C Z Q E W K d) a new general tree is created and the contents of the two trees are passed to this new tree Question 4: The binary equivalent tree of this general tree is: A) B) C) d)There is no binary equivalent tree for this general tree Question 5: Which one of the following statements is true about this code? template <class Key, class Elem, class KEComp, class EEComp> class UALdict : public Dictionary<Key,Elem,KEComp,EEComp> { private: AList<Elem>* list; public: bool remove(const Key& K, Elem& e) { for(list->setStart(); list->getValue(e); list->next()) if (KEComp::eq(K, e)) { list->remove(e);// ::AList remove method return true; } return false; } }; a) the value of e used in KEComp is taken from the passed parameter e b) getvalue(e) and remove(e) result in different values c) KEComp compares K with the value of e taken from getValue(e) d) All of the above are false e) All of the above are true 1. Determine which of the following arrays have the heap property. a. 0 1 2 3 4 5 6 7 88 66 44 33 55 77 33 b. 0 1 2 3 4 5 6 7 88 77 55 44 33 22 c. 0 1 2 3 4 5 6 7 88 66 77 22 33 44 55 d. 0 1 2 3 4 5 6 7 88 77 22 33 44 55 66 e. None of the above. 1. What is the content of the max heap which is built from an array of characters initialized to: STRUCTURESDATA (FALL 2005 QUIZ 2) 1- Find the cost of each of the followings operations for a Binary search tree respectively: - To find a node in a Balanced Binary tress (findhelp function) - To insert a node in a Balanced Binary tree (inserthelp function) - Remove a node from a Balanced Binary tree (removehelp function) - Inserting n nodes in random order. - Inserting n nodes in order of decreasing values a) log(n) , n log(n) , n log(n) , n2 , n b) log(n) , log(n) , log(n) , n log(n) , n2 c) log(n) , n log(n) , n2, n log(n) , n d) n log(n) , n log(n) , n2, n log(n) , n e) log(n) , log(n) , log(n2) , n log(n) , n2 2- Having the following max-heap, how would this heap become after inserting 2 new nodes with values 21 and 8, and then removing the node having a value 6. a) 10 5 6 4 2 1 3 21 10 5 8 2 1 3 4 b) c) 21 10 3 8 2 1 4 5 d) e) None of the above. 3- Having the following General tree, what is its sequential representation? 21 10 5 8 2 4 3 1 21 10 8 5 2 1 3 4 a) AC/BD//F/IH/EG// b) AC/BI//DH/E//FG/// c) AC)BI)DH))E))FG))) d) AC)BI))DH)E))FG))) e) None of the above. 4- Having the following Graph, find the adjacency 4 matrix including cycles. 012345 A B C D F I H G E 0 3 4 1 5 2 a) 0 010110 1 001000 2 000010 3 000011 4 010000 5 000010 012345 b) 0 011011 1 000010 2 010000 3 010010 4 001000 5 010000 012345 c) 0 011010 1 010000 2 001000 3 011000 4 000010 5 001000 012345 d) 0 011010 1 001000 2 000010 3 001010 4 010000 5 000010 e) None of the above 1- In what order does the following traverse a binary tree? template<Elem> void order (BinNode<Elem>* root) { if (subroot==NULL) return; order(root->right); order(root->left); cout<<root->val<<endl; } a- left-right-root b- right-left-root c- root-right-left d- right-root-left e- None of the above 2- Given the above traversal, traverse the below tree. a- FIGCBMLNKA b- NMLKIGFCBA c- AKNLMBCGIF d- NKMLAIGCFB e- None of the above 3- If we remove the 1 from the below code, what would we be counting? template<Elem> int count (BinNode<Elem>* root) { if (subroot==NULL) return 0; return 1 + count(subroot->left()) + count(subroot->right()); } a- The number of children on the right and left. b- The number of children on the right. c- The number of children on the left. d- Nothing. e- None of the above. 4- What does the following code do? template<class Key, class Elem, class KEComp, class EEComp> BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>:: do(BinNode<Elem>*root, BinNode<Elem>*& bn) { if(root->right() == NULL) { bn = root; return root->left(); } else { root->setright()(do(root->right(), bn)); return root; } } a- Delete the node with maximum value. b- The code does not represent a set operation. c- Delete the node with average value. d- Insert a node “bn” at a certain location in the binary tree. e- Node of the above. 5- How does the last else-statement of the function “removehelp” below differ from that of the original one (given in class)? Would it be valid? template <class Key, class Elem, class KEComp, class EEComp> BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>:: removehelp(BinNode<Elem>* subroot, const Key& K, BinNode<Elem>*& t) { if (subroot == NULL) return NULL; else if (KEComp::lt(K, subroot->val())) subroot->setLeft(removehelp(subroot->left(), K, t)); else if (KEComp::gt(K, subroot->val())) subroot->setRight(removehelp(subroot->right(), K, t)); else { BinNode<Elem>* temp; t = subroot; if (subroot->left() == NULL) subroot = subroot->right(); else if (subroot->right() == NULL) subroot = subroot->left(); else { subroot->setLeft(deletemin(subroot->left(), temp)); Elem te = subroot->val(); subroot->setVal(temp->val()); temp->setVal(te); t = temp; } } } a- The “removehelp” function replaces the removed node with the minimum value from the left of subroot. It won’t be valid. b- The “removehelp” function replaces the removed node with a value from the left of subroot. It will be valid. c- The “removehelp” function only removes a given node. d- Not different. e- None of the above. 6- If a child of a heap is at position “pos”, what is the position of its parent? a- 2*pos + 2 b- Answer requires heap c- 2*pos + 1 d- (pos-1)/2 e- None of the above. 7- What function is used to avoid rewriting terms in a code (for example when changing from using a linked list based graph implementation to an array- based graph implementation)? a- #include b- #define. c- Inline. d- Typedef. f- None of the above. 8- What is incorrect in the below code for getting v1’s neighbor after v2 for an array-based graph implementation? int next(int v1, int v2) { int i; for(i=v2; i<=numVertex; i++) if (matrix[v1][i] != 0) return i; return i; } a- i = v2 + 1. b- i<numVertex. c- i<numVertex – 1. d- a and b. e- a and c. 9- In what of the below conditions would a siftdown probably be required in a max-heap implementation? I. Removing a node. II. Inserting a node. III. Building a Heap. IV. Removing the maximum. V. Removing the minimum. a- I and IV. b- All except II. c- I, III, and IV. d- All except V. e- III and IV. For questions 1 –3 please refer to the following tree: 1) What would the result of a pre-order traversal of the above tree? a. 60 20 10 40 30 50 70 (The nodes on the left are printed before the nodes in the right subtree) b. 10 20 30 40 50 60 70 c. 10 30 50 40 20 70 60 d. 70 60 50 40 30 20 10 e. None of the above 2) What would the result of an in-order traversal of the above tree? a. 60 20 10 40 30 50 70 b. 10 20 30 40 50 60 70 c. 10 30 50 40 20 70 60 d. 70 60 50 40 30 20 10 e. None of the above 3) What would the result of a post-order traversal of the above tree? a. 60 20 10 40 30 50 70 b. 10 20 30 40 50 60 70 c. 10 30 50 40 20 70 60 d. 70 60 50 40 30 20 10 e. None of the above 4) Consider this binary search tree: 14 / \ 2 16 / \ 1 5 / 4 Suppose we remove the root, replacing it with something from the left subtree. What will be the new root? A. 1 B. 2 C. 4 D. 5 E. 16 1) Consider this binary search tree: 14 / \ 2 16 / \ 1 5 / 4 Suppose we remove the root, replacing it with something from the left subtree. What will be the new root? 5?? 2) What graph traversal algorithm uses a queue to keep track of vertices which need to be processed? 3) A complete binary tree of size 16 has a height of 4) Which of the following statements are true of the tree shown below? It is a binary search tree. Yes?? 1. The tree shown below is a Huffman code tree for the letters F, G, H, I, and J. What is the last character in the string encoded by “011101011101"? A. F B. G C. H D. I E. J 2.Creat a Binary search tree that contains {M,T,J,R,G,D} What will be the tree if we delete M 0 0 0 0 1 1 1 1 F G H I J 3.How many nodes in the following tree at most have one sibling? a) 5 b) 6 c) 7 d) 8 e) 3 4. if we remove the root what will replace the new root from the lower left sub tree? D T R G J J G J T R D T D G J R a) b) c) 2 7 13 6 1 3 7 10 12 Letter Freq Code Bits C 32 1110 4 D 42 101 3 E 120 0 1 K 7 111101 6 L 42 110 3 M 24 11111 5 U 37 100 3 Z 2 111100 6 1 4 2 1 6 5 1 4 a) 4 b) 1 c) 5 d) 2 e) non of the above 1) What will become the code of M if the frequency of L is changed to 12? a) 1111 b) 111 c) 11101 d) 11011 e) 11111 2) What is the equivalent adjacency matrix of the following adjacency list? a) b) c) d) e) none of the above 3) What will become the following array of integers after using build heap for a max-heap? A ={ 2,0,7,9,6,8,1,5,3,4 } a) A = { 9,8,7,6,5,4,3,2,1,0 } b) A = { 4,2,0,1,7,6,3,8,5,9 } c) A = { 9,5,8,3,6,7,1,0,2,4 } d) A = { 9,6,8,5,4,7,1,0,3,2 } e) None of the above 4) What are respectively the inorder; postorder; preorder traversals of the following tree? a) ABCDEFGHILP; PLIHGFEDCBA; ABDGEHLCFIP b) GDBHELACIFP; ABDGEHLCFIP; GDHLEBIPFCA c) GDBHELACIFP; GDHLEBIPFCA; ABDGEHLCFIP d) GDHLEBIPFCA; ABDGEHLCFIP; GDBHELACIFP e) ABDGEHLCFIP; GDHLEBIPFCA; GDBHELACIFP 5) What is the parent pointer implementation of the following tree? a) KEY A B C D E F G H I parent 1 / 1 2 1 2 0 8 / node 0 1 2 3 4 5 6 7 8 b) KEY A B C D E F G H I parent 1 / 1 2 1 2 2 8 / node 0 1 2 3 4 5 6 7 8 c) KEY A B C D E F G H I parent 1 1 1 2 0 2 2 8 8 node 0 1 2 3 4 5 6 7 8 d) KEY A B C D E F G H I parent 1 / 1 2 0 2 2 / 7 node 0 1 2 3 4 5 6 7 8 e) KEY A B C D E F G H I parent 7 / 7 6 8 6 6 0 / node 8 7 6 5 4 3 2 1 0 1) Which of the following rankings orders the algorithms from fastest to slowest? a. O(N), O(log2N), O(NM), O(2N), O(N!) b. O(log2N), O(N), O(NM), O(2N), O(N!) c. O(log2N), O(N), O(2N), O(NM), O(N!) d. O(log2N), O(N), O(N!), O(NM), O(2N), e. O(log2N), O(N), O(NM), O(N!), O(2N) For Questions 2 & 3 please refer to the graph shown below. 2) What would be the result of a breadth first traversal starting with node V1? Whenever there is a choice of path traversals, the node with the lowest number will be traversed first. a. V1 V2 V3 V4 V5 V6 V7 V8 V9 b. V1 V2 V3 V4 V5 V9 V8 V7 V6 c. V1 V2 V6 V3 V7 V4 V8 V5 V9 d. V1 V5 V2 V3 V4 V9 V6 V7 V8 e. V1 V2 V3 V1 V2 V3… 3) What would be the result of a depth first traversal (ignoring backtracking) starting with node V1? Whenever there is a choice of path traversals, the node with the lowest number will be traversed first. a. V1 V2 V3 V4 V5 V6 V7 V8 V9 b. V1 V2 V3 V4 V5 V9 V8 V7 V6 c. V1 V2 V6 V3 V7 V4 V8 V5 V9 d. V1 V5 V2 V3 V4 V9 V6 V7 V8 e. V1 V2 V3 V1 V2 V3… 4) Which of the following statements are true of the tree shown below? a. It is a binary search tree. b. It is a complete tree. c. It is a full tree. d. It is a max heap. e. (a) & (b) 1) Answer by true or false i- In a binary tree the preorder successor of a node is its left son (if the left son exists) ii- In a binary tree the postorder successor of a left son is its brother (A) T F (B) F T (C) F F (D) T T (E) None of the above 2) A complete binary tree contains n nodes. What is the possible value of n? (A) 1023 (B) 1024 (C) 1025 (D) 1026 (E) None of the above 3) Given the following table: Symbol Frequency A 8 B 6 C 12 D 5 E 10 F 3 G 1 What is the code of F? (A) 1000 (B) 0001 (C) 001 (D) 1001 (E) None of the above 4) Suppose that the following letters are entered inorder into an empty binary search tree. JRDGTEMHPAFQ Indicate the address of Q (A) 12 (B) 15 (C) 26 (D) 35 (E) None of the above A B Z F 50 6 4 Find the missing frequency (or weight) knowing that “F” has a 75% reduction in the number of bits of an ASCII letter representation, and that its probability of occurrence in the given set is 25%. Also, for this Huffman coding, the number of bits/letter is 1.5 Samer AZAR Ward Questions and answers : 1-In what order does the following function prints the binary tree? void BST<Key, Elem, KEComp, EEComp>:: printhelp(BinNode<Elem>* subroot, int level) const { if (subroot == NULL) return; for (int i=0; i<level; i++) cout << " "; printhelp(subroot->right(), level+1); cout << subroot->val() << "\n"; printhelp(subroot->left(), level+1); } a) inorder traversal b) preorder traversal c) postorder traversal d) descending order (answer) e) none of the above 2-Given the following information about traversing a general tree propose a correct structure of the tree. Preorder traversal: R A C D E B F Postorder traversal: C D E A F B R (1) (2) (3) (4) a) all of the above b) none of the above c) only (1) (answer) d) (1) and (3) e) (1) and (4) 3-What does the function “unknown” do? void GenTree<Elem>::unknown(GTNode<Elem>* subroot) { if (subroot->isleaf()) cout<<”leaf”; else cout<<”internal:”; cout << subroot->value() << "\n"; for (GTNode<Elem>* temp = subroot->leftmost_child(); temp != NULL; temp = temp->right_sibling()) unknown(subroot); } a) prints all nodes of the tree b) distinguishes between a leaf and internal node c) merges two trees d) none of the above(answer) 4- What is the sequential representation of the below tree? a) RAC)D)E))BF))) b) AB/D//CEG///FH//I// c) A’B’/DC’E’G/F’HI d) All of the above(answer) e) None of the above Quiz 2 questions: Consider the following piece of code: template <class Key, class Elem, class KEComp, class EEComp> void BST<Key, Elem, KEComp, EEComp>::myfunction() { bool popped=false;; int n = nodecount; AStack<BinNode<Elem>*> s(n); BinNode<Elem>* temp = root; for(int i=0; i!= nodecount; ) { if (temp->left() == NULL || popped) { popped = false; cout << temp-> val() << endl ; i++; if (temp-> right() != NULL ) temp = temp -> right() ; else { s.pop(temp) ; popped = true; } } else { s.push (temp); temp = temp -> left(); } } } Question 1: Choose the role of the function: a- Preorder Traversal b- Postorder Traversal c- Inorder Traversal d- Insert e- None of the above Question 2: If we move the statement cout << temp-> val() << endl ; to before s.push (temp); what function do we get? a- Preorder Traversal b- Postorder Traversal c- Inorder Traversal d- Insert e- None of the above Question 3: Given a plain binary tree, examine the tree to determine if it meets the requirement to be a binary search tree. Which trees are BSTs? a.  5 / \ 2   7 b.  5 / \ 6   7 c.   5 / \ 2   7 / 1 d.   5 / \ 2   7 / \ 1   6 a - Tree a , b and d b - Tree b c- Trees b and c d- Trees a and d e- None of the above Question 4: Given the following code: void myfunction(BinNodePtr* node) { if (node==NULL) { return; } else { BinNodePtr* temp; // do the subtrees myfunction(node->left); myfunction (node->right); // swap the pointers in this node temp = node->left; node->left = node->right; node->right = temp; } } What will be its role? a- Inorder traversal b- Mirror tree c- Search node d- Find node e- None of the above Question 5: Given the previous code and the following tree: 4 / \ 2   5 / \ 1   3 What can be the output of the function: a- Function has no role b- The same Tree c- Tree 4 / \ 5   2 / \ 3   1 d- Tree 4 / \ 2   5 / \ 1   3 e- None of the above