EECE 330 Questions Midterm Sample, Fall 2011

Data Structures and Algorithms Student Name: Student ID: 1. Given the same data size and same pointer size, which of the following is not true? a) Binary trees cost more overhead than all linked lists b) Binary trees cost less overhead than all linked lists c) Binary trees cost the same overhead as all linked lists d) All of the above 2. A complete binary tree is one in which: a) Every internal node has two non-empty children. b) All of the levels, except possibly the bottom level, are filled. 3. If we visit the node first, then its left child followed by its right child, then we are performing: a) Preorder traversal. b) Inorder traversal. c) Postorder traversal. 4. When every node of a full binary tree stores a 16-byte data field and two 4-byte child pointers, the overhead fraction is approximately: a) one quarter. b) one third. c) one half. d) two thirds. e) three quarters. f) none of the above. 5. The following function displays the values in the tree nodes in void sorder(BinNode<Elem>* subroot) { if (subroot->left() != NULL) sorder(subroot->left() ); if (subroot->right() != NULL) sorder(subroot->right()); cout<<"value in node: "<<subroot->val()<<endl; return; } a) preorder fashion b) postorder fashion c) inorder fashion d) some other order 6. Given the array implementation of stacks, what is the third line displayed by the code: AStack<int> s1(10); for (int i=0; i<4;i++) s1.push(i); while(s1.pop(i)) cout<<i<<endl; a- 0 b-1 c-2 d-3 7. The function push in the linked list implementation of stacks is modified and implemented as follows: bool push(const Elem& item) { if(top==NULL) top = new Link<Elem>(item, top); else top->next = new Link<Elem>(item, top->next); size++; return true; } All other functions or code remain unchanged. What is the second line displayed by the code: LStack<int> s1(10); for (int i=0; i<4;i++) s1.push(i); while(s1.pop(i)) cout<<i<<endl; a-0 b-1 c-2 d-3 8. In which order the tree below is traversed by the code: template<Elem> void order (BinNode<Elem>* root) { if (root==NULL) return; cout<<root->val<<endl; order(root->right); order(root->left); } a- ABCFGIKLMN b- AKNLMBCGIF c- FCGIBALMKN d- NKMLABIGCF