## 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 notsorted, 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. TRUEWhen using "binary search" to search an array, the array must always be sorted in increasing order. FALSEWhen using "binary search" to search an array, and the arrays is notsorted, then:

he program will crash FALSEyou will never find the value you are looking for even if it does exist in the array FALSEsometimes the search will be successful, but sometimes it will fail even if the value does exist in the array TRUESuppose 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 FALSEthe binary search always finds the last occurance of a value FALSEsometimes it finds the first, sometimes the last, and sometimes a value in between. TRUEA binary tree of height 3

must contain a minimum of 4 nodes TRUEcould contain 12 nodes TRUEcould contain 20 nodes FALSEThe 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. FALSEA tree is an example of a list. FALSEA list is an example of a tree. FALSEA tree is a hierarchical data structure. TRUEWhen 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. FALSESuppose 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.

FALSEWe discussed a "post-order" traversion function in class. As we have discussed this class, it used

single recursion FALSEdouble recursion TRUEA recursive function is a function that calls itself TRUEIf a recursive function does not have a base case it is likely to result in an infinite loop TRUEIf a recursive function does have a base case, it will never result in a recursive loop FALSEA double-recursive function is a function that calls itself again, but doubles the input argument when calling itself. FALSE