e02 : Midterm Exam-II

num ready? description exam date
e02 true Midterm Exam-II Thu 11/14 05:00PM

Instructions for the exam

Review problems

Solutions available HERE

1) Find the Big-O running time of the entire snippet of code below.

for(int i=N; i>1; i-=2) {
	for(int j = 1; j<N; j*=2) {
		cout<<i<<j<<endl;
	}
}
for(int i=N; i>1; i=i/2) {
	for(int j = 1; j<N; j+=5) {
		cout<<i<<j<<endl;
	}
}

2) Complete the following table, where you are asked to find the Big O running times for the remove, find, insert, find min, and find max operations on each data structure. Provide the tightest bound.

Data structure Remove Find Insert Find Min Find Max
Balanced BST          
BST (not necessarily balanced)          
Singly linked list in ascending order (stored head and tail)          
Unsorted singly linked list (stores head and tail)     *at tail    
Sorted array in ascending order          
Unsorted array          

3) Insert the following values into a binary search tree (in the order given), and draw the result 5, 2, 3, 21, 120, 15, 1

4) Write a member function of a BST that, given an integer value as input, returns an std::vector of all values in a BST that are larger than the given value, or an empty vector if the node with the input value doesn’t exist. You may use any functions from lab04 in your solutions.

5) Is this a valid binary search tree? Explain briefly.

If the tree is valid, trace the preorder, postorder, and inorder traversals of this binary tree. If not, trace the traversals of the tree without the problematic node.

Reference material

You are expected to know the material from the following lectures, labs and homeworks:

Answers to homeworks

Study guide

Past exams