New version page

UT CS 307 - Study Notes

Documents in this Course
Midterm 2

Midterm 2

15 pages

Midterm 1

Midterm 1

15 pages

Syllabus

Syllabus

24 pages

s

s

8 pages

Midterm 1

Midterm 1

14 pages

Midterm 2

Midterm 2

14 pages

Recursion

Recursion

14 pages

Midterm 1

Midterm 1

16 pages

Load more
Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

CS 307 – Final – Fall 2010 1 Points off 1 2 3A 3B 4 5 Total off Net Score CS 307 – Final – Fall 2010 Name__________________________________________ UTEID login name _______________________________ Instructions: 1. Please turn off your cell phones and all other electronic devices. 2. There are 5 questions on this test. 3. You have 3 hours to complete the test. 4. You may not use a calculator on the test. 5. You may add helper methods if you wish when answering coding questions. 6. When answering coding questions assume the preconditions of the methods are met. 1. (1.5 point each, 30 points total) Short answer. Place you answers on the attached answer sheet. For questions that ask "what is the output": • If the code contains a syntax error or other compile error, answer “Compiler error”. • If the code would result in a runtime error or exception answer “Runtime error”. • If the code results in an infinite loop answer “Infinite loop”. On questions that ask for the order (Big O) of a method or algorithm, recall that when asked for Big O your answer should be the most restrictive, correct Big O function. For example Selection Sort has is order O(N2), but per the formal definition of Big O it is correct to say Selection Sort is O(N3), O(N4), O(2N), and O(N!). Give the most restrictive, correct function. (Closest without going under.) A. The following values are inserted one at a time in the order shown into an initially empty binary search tree using the traditional, naïve algorithm. Draw the resulting tree. 97 35 -59 93 2 95 B. What is the height of the resulting tree from part A? (Recall the height of a tree is the number of links from root to deepest leaf.)CS 307 – Final – Fall 2010 2 Consider the following binary tree. 50 is the root of the tree. 50 / \ -7 70 / \ \ -50 25 90 \ 91 C. What is the result of a pre-order traversal of the binary tree shown above? D. What is the result of a in-order traversal of the binary tree shown above? E. What is the result of a post-order traversal of the binary tree shown above? F. Is the tree shown above a binary search tree? G. Assume the tree shown above has all nodes colored black. (There are no red nodes in the tree.) Is the tree shown above a Red-Black tree? If not which Red-Black tree rule is violated? H. What is the result of the following postfix expression? 5 2 + 100 200 * + I. 2000 distinct (no repeats) integers that are in random order are inserted one at a time into a binary search tree using the traditional, naïve algorithm presented in class. What is the expected height of the resulting tree? Give the actual number as you did on the experiments in assignment 11, NOT the order (Big O) of the height. J. On the answer sheet, fill in the nodes of the given binary tree with integer values between 1 and 10 so that the tree is a binary search tree.CS 307 – Final – Fall 2010 3 K. Consider the following methods: public int myst(int[] data, int x) { return mystHelp(data, x, 0); } public int mystHelp(int[] data, int x, int y) { if(y == data.length) return 0; else if(data[y] == x) return 1 + mystHelp(data, x + 1, y + 1); else return mystHelp(data, x, y + 1); } What is output by the following code? int[] vals = {4, -5, 5, 5, 4, 4, 6, 5, 3}; System.out.print( myst(vals, 4) ); L. What is the best case order (Big O) of the following method? N = list.size(). public int alo(ArrayList<String> list, int tgt) { int result = 0; final int LIMIT = list.size(); for(int i = 0; i < LIMIT; i++) if(list.get(i) != null && list.get(i).length() > tgt) result++; return result; } M. What is the best case order (Big O) of the following method? N = list.size(). list is a LinkedList from the Java standard library. public int llo(LinkedList<Integer> list) { int result = 0; while(list.size() > 0) { result += list.get(0); list.remove(0); } return result; }CS 307 – Final – Fall 2010 4 N. What is the average case order (Big O) of the following method? The BST class uses the traditional, naïve algorithms for insertion and deletion of values. N = tree.size() = vals.length public int bst1(BST<Integer> tree, int[] vals) { int result = 0; for(int i = 0; i < vals.length; i++) if(tree.contains(vals[i])) result++; return result; } O. What is the worst case order (Big O) of the following method? The BST class uses the Red-Black tee algorithms for insertion and deletion of values. N = tree.size() = vals.length public int bst2(BST<Integer> tree, int[] vals) { int result = 0; for(int i = 0; i < vals.length; i++) if(tree.contains(vals[i])) result++; return result; } P. What is output by the following code? Queue<Integer> q = new Queue<Integer>(); q.enqueue(3); q.enqueue(1); q.enqueue(2); for(int i = 0; i < 5; i++) { int x = q.dequeue(); q.enqueue(x); q.enqueue(x); } int total = 0; while(!q.isEmpty()) total += q.dequeue(); System.out.print(total);CS 307 – Final – Fall 2010 5 Q. What is output by the following code? Stack<Character> st = new Stack<Character>(); String name = "wirth"; int other = name.length() - 1; for(int i = 0; i < name.length(); i++){ st.push(name.charAt(0)); st.push(name.charAt(other)); other--; } while(!st.isEmpty()) System.out.print(st.pop()); R. Consider the following method: public void removeMany(Collection<Integer> col, int[] data) { for(int i = 0; i < data.length; i++) col.remove(data[i]); } Recall the remove method from the Collection interface: boolean remove(Object o) Removes a single instance of the specified element from this collection, if it is present. The Collection named col contains N elements and the int array data contains N elements. Assume none of the elements in data are present in col. Given the following timing data for method removeMany what type of Collection is being passed? Choose from LinkedList, TreeSet, and HashSet. N Time 100,000 1 second 200,000 4 seconds 400,000 16 seconds 800,000 64 secondsCS 307 – Final – Fall 2010 6 S. Given this method: public void


View Full Document
Download Study Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Study Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Study Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?