1CS 61BL Midterm 2 ReviewData StructuresColleen Lewis, Kaushik Iyer, Jonathan Kotker, David Zeng, George WangBased on problems by Jonathan Shewchuk, Mike Clancy, Leonard Wei, Min XuTopics of Emphasis (not exhaustive)• Linked Lists – 2 implementations• Big-O Notation• Amoeba Family Trees and Trees• Binary Trees and Tree Iterators• Search• BSTs and TreeMaps• Hash Tables• Everything in MT1• Upto Monday’s QuizOption A: TrueOption B: FalseOption C: 42Option D: ????????????????????Option A: TrueOption B: FalseOption C: 42Option D: ???????????????Option A: TrueOption B: FalseOption C: 42Option D: ????????????????????Option A: TrueOption B: FalseOption C: 42Option D: ???????????????2What is the Big-O run time of this piece of code?public static void main (String [] a) {int i = 5;f (i);System.out.println("i=" + i);}void f (int i) {i = i * i;}Option A: O(1)Option B: O(n) where n is a.length()Option C: O(log(n)) where n is 5Option D: O(f)What is the Big-O run time of this piece of code?public static void main (String [] a) {int i = 5;f (i);System.out.println("i=" + i);}void static f (int i) {i = i * i;}Option A: O(1)Option B: O(n) where n is a.length()Option C: O(log(n)) where n is 5Option D: O(f)What is the big-O runtime of this block of code?public static void g (int [] a) {for (int i = 0; i < a.length; i++) {f(a[i]);}}void static f(int s) {for(int i = 0; i < s; i++) {System.out.println(i);}}Option A: O(1)Option B: O(a.length) Option C: O(a.length * max(a[i]))Option D: O(a.length2)Option A: O(1)Option B: O(a.length) Option C: O(a.length * max(a[i]))Option D: O(a.length2)What is the big-O runtime of this block of code?public static void g (int [] a) {for (int i = 0; i < a.length; i++) {f(a[i]);}}void static f(int s) {for(int i = 0; i < s; i++) {System.out.println(i);}}What is the big-O runtime of this block of code?public static void main(String args) {for (int i = 0; i < a.length; i++) {for (int j = 0; j < 10; j++) {System.out.println(i+j);}}}Option A: O(10 * a.length)Option B: O(a.length2 )Option C: O(a.length)Option D: ???What is the big-O runtime of this block of code?public static void main(String args) {for (int i = 0; i < a.length; i++) {for (int j = 0; j < 10; j++) {System.out.println(i+j);}}}Option A: O(10 * a.length)Option B: O(a.length2 )Option C: O(a.length)Option D: ???Correct, but unnecessarily specific3What is the big-O runtime of this block of code?public static void main(String args) {for (int i = 0; i < a.length; i++) {for (int j = 0; j < i; j++) {System.out.println(i+j);}}}Option A: O(i * a.length)Option B: O(a.length2 )Option C: O(a.length)Option D: ???Option A: O(i * a.length)Option B: O(a.length2 )Option C: O(a.length)Option D: ???What is the big-O runtime of this block of code?public static void main(String args) {for (int i = 0; i < a.length; i++) {for (int j = 0; j < i; j++) {System.out.println(i+j);}}}What is the Big-O runtime of f ?public static void f(int[] a) {for (int i = 0; i < a.length; i++) {System.out.println(a[i]);}}Option A: O(a.length2)Option B: O(1)Option C: O(a.length)Option D: O(n)Option A: O(a.length2)Option B: O(1)Option C: O(a.length)Option D: O(n)What is the Big-O runtime of f ?public static void f(int[] a) {for (int i = 0; i < a; i++) {System.out.println(a[i]);}}What is the Big-O runtime of f ?public static void f(LinkedList a) {for (int i = 0; i < a.length(); i++) {System.out.println(a.get(i));}}Option A: O(a.length2)Option B: O(1)Option C: O(a.length)Option D: O(n)Option A: O(a.length2)Option B: O(1)Option C: O(a.length)Option D: O(n)What is the Big-O runtime of f ?public static void f(LinkedList a) {for (int i = 0; i < a.length(); i++) {System.out.println(a.get(i));}}4Data Structures Matter!What is the Big-O runtime of f ?public static void (List a) {for (ListNode point = a.myHead;point != null; point = point.myRest) {System.out.println(point.myFirst);}}Option A: O(a.length2)Option B: O(1)Option C: O(a.length)Option D: O(n)What is the Big-O runtime of f ?public static void (List a) {for (ListNode point = a.myHead;point != null; point = point.myRest) {System.out.println(point.myFirst);}}Option A: O(a.length2)Option B: O(1)Option C: O(a.length)Option D: O(n)Implementation Matters!It’s not all multiple choice ☺• Consider the width of a tree defined as the maximal number of nodes on a path from one node in the tree to another (the width of the empty tree is 0).• Write a BinaryTree method width() that returns the width of a binary tree. • Assume that each tree node contains the height of the tree rooted at the node.• The height of the empty tree is 0.5• Using the AmoebaFamily class you saw in lab:• write a method that finds the closest common ancestor of two Amoebas in this Family given their names.We want to code the following method:Implement the search function in the Amoeba class. Required runtime: O(number of nodes under this node• Implement the closestCommonAncestor in AmoebaFamily. Required runtime: O(depth of f1 + depth of f2)Coding Break!• You have an array of int values sorted in ascending order.• Using the insert method coded in lab for BSTs (adds new values only as leaves), we insert values one by one.• What’s the depth of the BST created?• What would the depth be if the array was sorted in descending order?• How long would it take to find out if the array contained a value?• How long would it take to find out if the BST contained a value?• Write code that would ensure that the BST was maximally balanced by modifying how you insert the values from the sorted array.Binary Search TreesWhat is the running time of looking for an element in a binary search tree?Option A: O(1)Option B: O(log n), n being the number of nodes in the tree.Option C: O(log n), n being the height.Option D: O(log n), n being the element.6Binary Search TreesWhat is the running time of looking for an element in a binary search tree?Option A: O(1)Option B: O(log n), n being the number of nodes in the tree.Option C: O(log n), n being the height.Option D: O(log n), n being the element.Linked Lists with abstract ListNodeOption A: Whatever x.myFirst isOption B: ExceptionOption C: Exception OR whatever x.myFirst isOption D: nullOption A: x.myFirstOption B:
View Full Document
Unlocking...