Unformatted text preview:

COMP 410 updated Fall 2015 Sample problems for Midterm Exam 1 1 a Given an array A of integers sorted into ascending order design an efficient algorithm for finding is there is any array subscript i where A i i What is the worst case run time of your algorithm in Big Oh notation Answer Here we have numbers that can be negative and positive and they are sorted We binary search on the array looking for A i i we can use the fact that they are sorted to decide which half to throw away each test This approach works if we allow duplicates or if all elements are unique values O log N for N elements in the array b Do the same for an array A of non negative integers sorted in ascending order What is the worst case run time of your algorithm in Big Oh notation Answer We have two situations First assume there are no duplicates We now have sorted unique integers and the smallest possible element is 0 So we check to see if A 0 0 If so then there is some A i i at least 0 possibly more but we did not need to find them all we just need to answer is there some i If A 0 is not 0 then there can be no other A i i O 1 worst case complexity Second situation if there are duplicates allowed Here we have 0 as the lowest possible element but we can also have sequences of the same element in places in the array Now checking simply for A 0 0 is not enough for example if all elements in the array are 7 then A 0 is not 0 but A 7 is 7 So we are back to doing binary search to find the answer O log N wirst case 2 a Show the result of inserting these integers in this order into an initially empty AVL tree 2 1 4 5 9 3 6 7 Make sure to show the tree after each insertion I can give partial credit is you give good detail You might consider showing the patterns we used to define the various insertion situations that are possible b Show the tree after doing delete 4 on the result from a c Show the tree after doing delete 9 on the result from b Answer Can t easily draw it here You can use one of the animations to check your work 3 The height of a tree that is only one node no children is zero Given this work these problems BST is Binary Search Tree a In a BST with N nodes the maximum height is what in terms of N Answer N 1 b In a BST of N nodes the minimum height is what Answer floor log N c In an AVL tree of 12 nodes the maximum height is what Answer 4 here is one example 12 nodes height 4 meets AVL conditions 19 7 31 3 11 17 43 2 14 34 55 77 d In an AVL tree of 12 nodes the minimum height is what Answer 3 This is the same as the height of a complete binary tree with 12 nodes 4 Consider this algorithm Take a complete binary tree T We dont know anything about it except that it meets the requirements to be a complete binary tree Start at the root Select at random one of the children and go to that child count that path as length 1 Select at random one of the children of this child Go to that child and increase the path length to 2 Continue to select random children and counting the path length until you hit a leaf node with no children This means that if you come to a node with one child you will take the path to that child Lets say when we are done the path length we found is K Using this number K give bounds on the number of nodes in this tree Answer TBD 5 We have a tree with the following properties a It is a binary tree b For each node R all values in the subtree rooted at R s left child are smaller than the value of R all values stored in the subtree rooted at R s right subchild are greater than R s value This tree is a circle one Binary Search Tree AVL Tree Left Right Topo Tree Binary Heap Splay Tree not something we have studied Answer BST AVL SPlay all work here 6 We have a tree with the following properties a It is a binary tree b For any two paths P1 and P2 that go from root to a leaf the AbsoluteValue length P1 length p2 is either 0 or 1 This tree is a circle one Binary Search Tree AVL Tree Left Right Topo Tree Binary Heap Splay Tree not something we have studied Answer binary heap but we are not doing binary heaps on this exam a binary heap is structurally a complete binary tree which has the specified property None of the other structures given will always have the property BTW there is no such thing as a left right topo tree not that I know or anyway 7 a Take an initially empty BST and show the tree after doing these insertions in this order 2 1 4 5 9 3 6 7 Show your work show the intermediate trees so I can give partial credit in case your final tree is incorrect b Show the tree you get when you do delete 4 starting with the result of a c Show the tree you get when you do delete 9 starting with the result of b Answer Can t easily draw it here You can use one of the animations to check your work 8 Take the axioms defining the STACK that we studied in class Let s add some new behavior to get a new type we will call SWAPSTACK We want to keep the operations we have push pop top size empty but we want to add this operation swap SWAPSTACK SWAPSTACK It will take a stack and swap the top two elements This means that if 12 is on top the initial stack and 6 is the second element then the resulting stack will have 6 on top and 12 as the second element Be careful to consider what swap does if you call it on a stack that does not contain at least two elements Answer None of the axioms for a normal stack will change The swap operation is not canonical so all we need to do is add axioms for how swap does on new and how it does on push one way swap new new swap push new e push new e swap push push S e f push push S f e another way swap new new swap push S e if empty S then push S e else push push pop S e top S 9 Describe a data structure that …


View Full Document

UNC-Chapel Hill COMP 410 - Midterm Exam 1

Documents in this Course
Load more
Download Midterm Exam 1
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 Midterm Exam 1 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 Midterm Exam 1 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?