Below is the IntList class we discussed in week 2. We are in the middle of...

Transcribed Image Text:

Below is the IntList class we discussed in week 2. We are in the middle of implementing a new recursive method called contains that should return true if the list contains the given number and false if it does not. What code should replace the comment/* recursive case */ so that the contains method works correctly? public class IntList { private class IntNode { } } private IntNode first; private int data; private IntNode next; public IntList() { first = null; } public IntNode(int data, IntNode next) { this.data data; this.next next; } public void insertAtFront (int data) { first = new IntNode (data, first); 8 } /** * Determins if the list contains target. 8 @param target the number to search for @return true if the list contains tgarget and false otherwise. public boolean contains (int target) { return containsH(first, target); private boolean containsH(IntNode n, int target) { if (n == null) /* base case */ else { boolean temp containsH(n.next, target); /* recursive case */ else { boolean temp = containsH(n.next, target); /* recursive case */ return temp && (n.data == target); return temp || (n.data == target); if (temp == true) else } return (n.data == target); return false; if (temp == false) return containsH(first, target); else return true; True False Question 15 (5 points) The SequentialsearchST class allows null as a possible key. What is the order of growth of the worst case running time of the delete operation for the book's BinarySearchST with n keys, when the key being deleted is present in the symbol table? O logarithmic O constant O quadratic Olinear O(lgn) O(1) O(n) O(n) What is the order of growth of the worst case running time of the delete operation for the book's BinarySearchST with n keys, when the key being deleted is not present in the symbol table? O quadratic O logarithmic O linear O constant O(n) O(lgn) O(n) O(1) What happens when the following function is called with a valid Map object? public static void fun (Map dict) { dict.put("hello", null); } if (dict.containsKey("hello")) stdout.println("dict else stdout.println("dict does NOT contain hello"); it depends on what is already stored in dict dict does NOT contain hello is printed to the screen an exception is thrown dict contains hello is printed to the screen contains hello"); Question 18 (5 points) What is the order of growth of the worst case running time of the get operation for the book's BinarySearchST with n keys, when the key being searched for is not in the symbol table? O linear O logarithmic O quadratic constant O(n) O(lgn) O(n.) O(1) Below is the IntList class we discussed in week 2. We are in the middle of implementing a new recursive method called contains that should return true if the list contains the given number and false if it does not. What code should replace the comment/* recursive case */ so that the contains method works correctly? public class IntList { private class IntNode { } } private IntNode first; private int data; private IntNode next; public IntList() { first = null; } public IntNode(int data, IntNode next) { this.data data; this.next next; } public void insertAtFront (int data) { first = new IntNode (data, first); 8 } /** * Determins if the list contains target. 8 @param target the number to search for @return true if the list contains tgarget and false otherwise. public boolean contains (int target) { return containsH(first, target); private boolean containsH(IntNode n, int target) { if (n == null) /* base case */ else { boolean temp containsH(n.next, target); /* recursive case */ else { boolean temp = containsH(n.next, target); /* recursive case */ return temp && (n.data == target); return temp || (n.data == target); if (temp == true) else } return (n.data == target); return false; if (temp == false) return containsH(first, target); else return true; True False Question 15 (5 points) The SequentialsearchST class allows null as a possible key. What is the order of growth of the worst case running time of the delete operation for the book's BinarySearchST with n keys, when the key being deleted is present in the symbol table? O logarithmic O constant O quadratic Olinear O(lgn) O(1) O(n) O(n) What is the order of growth of the worst case running time of the delete operation for the book's BinarySearchST with n keys, when the key being deleted is not present in the symbol table? O quadratic O logarithmic O linear O constant O(n) O(lgn) O(n) O(1) What happens when the following function is called with a valid Map object? public static void fun (Map dict) { dict.put("hello", null); } if (dict.containsKey("hello")) stdout.println("dict else stdout.println("dict does NOT contain hello"); it depends on what is already stored in dict dict does NOT contain hello is printed to the screen an exception is thrown dict contains hello is printed to the screen contains hello"); Question 18 (5 points) What is the order of growth of the worst case running time of the get operation for the book's BinarySearchST with n keys, when the key being searched for is not in the symbol table? O linear O logarithmic O quadratic constant O(n) O(lgn) O(n.) O(1)

Answer rating: 100% (QA)

Step 1 To implement the recursive case of the contains method we need to check if the current node contains the target or if it is in the rest of the list If the current node contains the target we re... View the full answer