CS 1112  Exam 2 Sample Questions

Please answer, in your own words, the following questions:

	What is Binary Search ?
	What is Recursion ?
	What is a Binary Search Tree ?

Please look at the following code and circle any errors you see. Then disregard all lines containing errors and write down, for each "cout" statement, the value that would be printed.

SOME CODE GOES HERE

Please answer the following TRUE/FALSE questions:

	When using "binary search" to search an array, the array must be sorted.
	When using "binary search" to search an array, the array must always be sorted in increasing order.
	When using "binary search" to search an array, and the arrays is not sorted, then: the program will crash you will never find the value you are looking for even if it does exist in the array sometimes the search will be successful, but sometimes it will fail even if the value does exist in the array
	Suppose A is an array containing numbers in increasing order, but some numbers occur more than once. When using a binary search for a value, the binary search always finds the first occurance of a value the binary search always finds the last occurance of a value sometimes it finds the first, sometimes the last, and sometimes a value in between.
	A binary tree of height 3 must contain a minimum of 4 nodes could contain 12 nodes could contain 20 nodes
	The difference between a binary tree and a binary search tree is that a binary search tree has two children per node whereas a binary tree can have none, one, or two children per node.
	A tree is an example of a list.
	A list is an example of a tree.
	A tree is a hierarchical data structure.
	When you insert the values 40, 30, 60, 40, and 50 into a binary search tree, and then search for, say, 40, the search will find the second occurance of 40, not the first.
	Suppose you insert the values 40, 30, 60, 50, and 10 into a binary search tree, and then use the following function: void someOrder(Node *p) { if (p != 0) { someOrder(p->right); cout << p->data << endl; someOrder(p->left); } } then the output of calling someOrder(root) would be: 10, 30, 40, 50, , then 60.
	We discussed a "post-order" traversion function in class. As we have discussed this class, it used single recursion double recursion
	A recursive function is a function that calls itself
	If a recursive function does not have a base case it is likely to result in an infinite loop
	If a recursive function does have a base case, it will never result in a recursive loop
	A double-recursive function is a function that calls itself again, but doubles the input argument when calling itself.

Click here for answers to true/false questions

  

 
Which of the following two trees is a binary search tree ?

A tree could be represented either as a picture, or by listing the nodes in a specific order.

a) List the nodes in the tree below as they would appear if the tree below is traversed in post-order.

b) If the nodes below are listed from a tree traversed in pre-order, reconstruct the picture of the tree:

Level 0: Node data: 50

Level 1 Node data: 25

Level 2: Node data: 10

Level 1: Node data: 75

Level 2: Node data: 60

Level 2: Node data: 90

Level 3: Node data: 80

 Consider the binary tree on the left. List each of the following:
 

all nodes that are leafs all pairs of nodes that are siblings all ancestors of the node with value 60 all descendents of the node with value 25 the height of the tree the size of the tree

  

Draw the binary search tree after each operation. Each insertion and deletion operates on the original tree, and the new tree should again be a binary search tree.

a) Insert 65 b) Insert 35

c) Delete 70 d) Delete 60

d) Delete 50

For a binary search tree, write C++ code that accomplishes the following:

a) A function that finds the left-most node of a tree starting at the input node pointer p.

void leftMost(Node *p);

On input, p is a pointer to a node of a tree, on output p points to the left-most node of the subtree.

b) A function that traverses the tree in inOrder and prints out the values of all nodes in the tree.

void inOrder(Node *p);

Recall that a Node and a Binary Search tree are defined as follows:

typedef int Element;
class Node
{
public double data;
public Node *left, *right;
public Node(void);
public Node(Element);
};

class BinSTree

{

private: Node *root;

}
 

 

Explain, in your own words, how a binary search works on a sorted array [1..N] of integers. Why is this search method preferred over a regular search ? What, if any are the requirements to use this type of search

Write the code for a recursive binary search function on an array that is sorted in decreasing order, i.e. starting with the largest value,

 Consider the following functions defined recursively:

void Mystery1(int N)
{
   if (N == 1)
      cout << N << endl;
   else
   {
      cout << N << endl;
      Mystery1(N-1);
     Mystery1(N-1);
   }
}
 

void Mystery2(int N)
{
   if (N == 1)
      cout << N << endl;
   else
   {
      Mystery2(N-1);
      cout << N << endl;
      Mystery2(N-1);
   }
}

void Mystery3(int N)
{
   if (N == 1)
      cout << N << endl;
   else
   {
      Mystery3(N-1);
      Mystery3(N-1);
      cout << N << endl;
   }
}

double F1(double x, int n)
{
   if (n == 0)
      return 0;
   else
      return x + F1(x, n-1);
}

double F2(int n)
{
   if (n < 2)
      return 0;
   else
      return 1 + F2(n/2);
}

	What is the output for Mystery1(4), Mystery2(4), and Mystery3(4) ?
	The functions F1 and F2 can be described in much simpler terms. What, therefore, do these functions "really" do ?
	How often does the function Mystery1(4) call itself ? How often does the function Mystery(10) call itself ? How often does the function Mystery1(64) call itself, approximately ?

Answers to True/False Questions

	When using "binary search" to search an array, the array must be sorted. TRUE
	When using "binary search" to search an array, the array must always be sorted in increasing order. FALSE
	When using "binary search" to search an array, and the arrays is not sorted, then: he program will crash FALSE you will never find the value you are looking for even if it does exist in the array FALSE sometimes the search will be successful, but sometimes it will fail even if the value does exist in the array TRUE
	Suppose A is an array containing numbers in increasing order, but some numbers occur more than once. When using a binary search for a value, the binary search always finds the first occurance of a value FALSE the binary search always finds the last occurance of a value FALSE sometimes it finds the first, sometimes the last, and sometimes a value in between. TRUE
	A binary tree of height 3 must contain a minimum of 4 nodes TRUE could contain 12 nodes TRUE could contain 20 nodes FALSE
	The difference between a binary tree and a binary search tree is that a binary search tree has two children per node whereas a binary tree can have none, one, or two children per node. FALSE
	A tree is an example of a list. FALSE
	A list is an example of a tree. FALSE
	A tree is a hierarchical data structure. TRUE
	When you insert the values 40, 30, 60, 40, and 50 into a binary search tree, and then search for, say, 40, the search will find the second occurance of 40, not the first. FALSE
	Suppose you insert the values 40, 30, 60, 50, and 10 into a binary search tree, and then use the following function: void someOrder(Node *p) { if (p != 0) { someOrder(p->right); cout << p->data << endl; someOrder(p->left); } } then the output of calling someOrder(root) would be: 10, 30, 40, 50, then 60. FALSE
	We discussed a "post-order" traversion function in class. As we have discussed this class, it used single recursion FALSE double recursion TRUE
	A recursive function is a function that calls itself TRUE
	If a recursive function does not have a base case it is likely to result in an infinite loop TRUE
	If a recursive function does have a base case, it will never result in a recursive loop FALSE
	A double-recursive function is a function that calls itself again, but doubles the input argument when calling itself. FALSE