CS 146 Practice Midterm
Return to classpage.
The practice midterm is below. Here are some facts about the actual
midterm: (a) The midterm will be in class Oct. 24. (b) It is closed
book, closed notes. Nothing will be permitted on your desk except
your pen (pencil) and test. (c) You should bring your student ID.
(d) There will be more than one version of the test. Each version
will be of comparable difficulty. (e) If your cell-phone or beeper
goes off you will be excused from the test at that point and graded
on what you have done till your excusal. (f) The test covers from
chapter 1 to the material on leftist heaps in Chapter 6. (g) To prepare for
this test you should go over the practice midterm below, all homework
problems, and examples discussed in class. Then review your notes
and the readings from the book.
(1) Prove formally that:
(a) N! is in O(2Nlog N)
(b) N2+N is Theta(N2)
(c) sumNi=1 (i+1)3i is O(N3N)
(d) N is Omega(N1/2)
(e) log N is o(N)
(2) Estimate the runtimes of the following code fragments as a function of N:
(a) for( int i = 0; i < N; i++)
for( int j = 0; j < N; j++)
System.out.println("Hello world");
(b) if( 5 > 3) System.out.println("hello");
else
for( int i = 0; i < N; i++)
System.out.println("" + i);
(c) for( int i = 0; i < N; i++)
System.out.println("" + i);
for( int j = 0; j < N; j++)
System.out.println("" + j);
(d) for(int j =0; j*j < N; j++)
System.out.println("" + j);
(e) while (N > 0)
N = N >>> 1;
(3) Suppose you have a singly linked-list A1->A2->...->A> and you are given
a reference to A1 and a reference to some node Am where 1 < m < n.
(a) Give an O(1) algorithm to remove Am+1 from the list
(b) Give an O(1) algorithm to insert a node A' after Am.
(c) Give an O(n) algorithm to find A(m-1)
(d) Give an O(1) algorithm to remove the data associated with Am from the
list.
(e) Give an O(1) algorithm to produce a list with data items
the same as the list:
A1->...->A(m-1)->A'->Am->...->An
where A' is some new node.
(4) Show step by step how radix sort would sort the names
Ana, Art, Bea, Ted in increasing alphabetical order.
(5) Show step by step how to use a stack to evaluate the postfix expression:
4 2 7 * 5 - *
(6) Show step by step how to use a queue to perform a level order traversal
of the tree:
(r)
/ | \
(h) (i) (n)
/ /
(o) (s)
(7) (a) Give the BST that results from performing the inserts 4 2 7 5 6.
(b) What does the BST look like after deleting the (4)?
(c) redo (a) using AVL trees
(d) redo (b) using AVL trees.
(e) Given the tree we got from (a) what would be the result of
a splay tree find operation on a search for 6?
(8) Define the following concepts:
(a) B-tree of order M
(b) primary clustering
(c) rehashing
(d) separate chaining
(e) quadratic probing
(9) (a) Give an O(N) algorithm that given an array of size N makes it into
a heap.
(b) Prove that it is O(N).
(10) Consider the following two leftist heaps:
(3) (4)
/ / \
(9) (5) (6)
Show how the merge algorithm from the book would merge them into
one leftist heap.
|