{\rtf1\ansi\ansicpg950\deff0\deflang1033\deflangfe3076{\fonttbl{\f0\fmodern\fprq6\fcharset134 SimSun;}} {\colortbl ;\red255\green0\blue0;} \viewkind4\uc1\pard\lang3076\f0\fs20 1. \par Consider the following recursive definition of a function search that performs search in a binary tree.\par \par bool search(Type a, Tree T) \{\par if (empty(T)) \{\par return false;\par \}\par else\par if(a == data(T)) \{\par return true;\par \}\par else \{\par bool bl = search(a, left(L));\par bool br = search(a, right(L));\par return bl || br;\par \}\par \}\par \par Which of the following describes a problem with the function when executed?\par \par (a) It might terminate prematurely.\par (b) It might take quadratic time unnecessarily.\par (c) It might fail to terminate.\par \cf1 (d) It might take linear time unnecessarily. \par \cf0\par \par 2. \par A node in a tree that does not have any children is called \par \par \cf1 (a) a leaf\par \cf0 (b) an empty node\par (c) an internal node\par (d) a root \par \par \par 3. \par A full node in a binary tree has how many children? \par \par (a) 0\par \cf1 (b) 2\par \cf0 (c) 1 or 2\par (d) 1 \par \par \par 4. \par In the standard array implementation of a binary tree the nodes are stored in an array. What is the convention for the array position of the parent of the node in position p of the array? \par \par \par (a) 2 * p\par (b) 2 * p + 1\par (c) p - 1\par \cf1 (d) p/2 \par \cf0\par \par 5. \par A tree can be implemented as a graph whose vertices are the nodes of the tree and where an edge (u,v) indicates that u is the parent of v. Which of the following indicates all the nodes of such an implementation that are reachable by a depth first search starting at the root? \par \par \cf1 (a) All nodes in the tree\par \cf0 (b) Only the nodes in the left subtree of the root\par (c) Only the leaves of the tree\par (d) Only the interior nodes of the tree \par \par \par 6. \par Which of the following traversals of a binary search tree will produce a sorted list if a visit to a node prints what is stored there? \par \par (a) Preorder\par \cf1 (b) Inorder\par \cf0 (c) Level-by-level\par (d) Postorder \par \par \par 7. \par Searching for an element in a binary search tree takes O(s) steps where s is \par \par (a) the size of the tree\par \cf1 (b) the depth of the tree\par \cf0 (c) the number of leaves of the tree\par (d) 1 (the search takes constant time) \par \par \par 8. \par During a failed search for an element in a completely balanced binary search tree of size 1,000,000, approximately how many nodes of the tree is visited? \par \par (a) 10,000\par \cf1 (b) 20\par \cf0 (c) 200\par (d) 1000 \par \par \par 9. \par Suppose S is a binary search tree and x is not an element of S. Consider the following code fragment.\par \par S.insert( x );\par S.remove( x );\par \par If T is the tree that results from executing the fragment, what is the relationship between S and T?\par \par (a) S and T differ in exactly one leaf.\par \cf1 (b) S and T are the same.\par \cf0 (c) S is a proper subtree of T.\par (d) S and T differ in exactly the root. \par \par \par 10. \par If numbers 1,2,...,n are inserted into a binary search tree, in order, then the result for large n is a \par \par \cf1 (a) totally unbalanced tree\par \cf0 (b) mildly unbalanced tree\par (c) completely balanced tree\par (d) tree where all nodes are full \par \par \par \lang1033 1\lang3076 1. \par A node in a tree that does not have a predecessor is called \par \par \cf1 (a) a root\par \cf0 (b) an internal node\par (c) a leaf\par (d) a parent node \par \par \par \lang1033 12\lang3076 . \par Consider the following pseudo-code, which indicates part of a standard binary tree algorithm.\par \par print( node )\par \{\par print data;\par if( there is a left child ) print( left child );\par if( there is a right child ) print( right child );\par \}\par \par Which of the following is the standard name for this algorithm?\par \par (a) Postorder traversal\par (b) Inorder traversal\par \cf1 (c) Preorder traversal\par \cf0 (d) Binary search \par \par \par 1\lang1033 3\lang3076 . \par If numbers 1,2,...,n are inserted into a binary search tree in random order, then the result for large n is a \par \par (a) completely balanced tree\par \cf1 (b) reasonably balanced tree\par \cf0 (c) tree where all nodes are full\par (d) totally unbalanced tree \par \par \par \lang1033 14\lang3076 . \par Which of the following is true about the total number of nodes in a binary tree with depth 2? \par \par (a) There is no bound on the number of nodes.\par \cf1 (b) It is at most 7.\par \cf0 (c) It is at most 2.\par (d) It is at most 4. \par \par \par \lang1033 15\lang3076 . \par In the standard array implementation of a binary tree, the nodes are stored in an array. What is the convention for the array position of the left child of the node in position p of the array? \par \par (a) p + 1\par \cf1 (b) 2 * p\par \cf0 (c) p/2\par (d) 2 * p + 1 \par \par \par \lang1033 16\lang3076 . \par Suppose S is a binary search tree and x is not an element of S. Consider the following code fragment.\par \par S.insert( x );\par S.remove( x );\par \par If T is the tree that results from executing the fragment, what is the relationship between S and T?\par \par \cf1 (a) S and T are the same.\par \cf0 (b) S and T differ in exactly the root.\par (c) S is a proper subtree of T.\par (d) S and T differ in exactly one leaf. \par \par \par \lang1033 17\lang3076 . \par Which of the following is true about the depth of a tree with exactly 3 nodes? \par \par (a) It is at most 1.\par (b) There is no bound on the depth.\par (c) It is at most 3.\par \cf1 (d) It is at most 2. \par \cf0\par \par \lang1033 18\lang3076 . \par Which of the following is true about the total number of nodes in a tree with depth 2? \par \par (a) It is at most 3.\par \cf1 (b) There is no bound on the number of nodes.\par \cf0 (c) It is at most 2.\par (d) It is at most 1. \par \par \par 1\lang1033 9\lang3076 . \par Which of the following sequences cannot represent values visited during a binary search? \par \par (a) 30, 50, 40, 45, 42\par (b) 10, 20, 30, 40, 50\par (c) 50, 40, 30, 20, 10\par \cf1 (d) 10, 20, 30, 15, 18 \par \cf0\par \par \lang1033 20\lang3076 . \par Which of the following is true about the total number of nodes in a binary tree with depth 2? \par \par (a) It is at least 4.\par \cf1 (b) It is at least 3.\par \cf0 (c) It is at least 2.\par (d) It is at least 7. \par \par \par \lang1033 21\lang3076 . \par Suppose S is a binary search tree and x is not an element of S. Consider the following code fragment.\par \par S.remove( x );\par S.insert( x );\par \par If T is the tree that results from executing the fragment, what is the relationship between S and T?\par \par (a) S is a proper subtree of T.\par (b) S and T differ in exactly the root.\par (c) S and T are the same.\par \cf1 (d) S and T differ but how depends on S. \cf0\par }