Homework answers / question archive / Consider the following binary search tree: Which of the following sequences correctly represents breadth-first traversal of this tree? a

Consider the following binary search tree: Which of the following sequences correctly represents breadth-first traversal of this tree? a

Computer Science

Share With

Consider the following binary search tree: Which of the following sequences correctly represents breadth-first traversal of this tree? a. J, E, M, C, G, P, A, H, N b. J, E, C, A, G, H, M, P, N c. A, C, H, G, E, N, P, M, J d. A, C, E, G, H, J, M, N, P N a. b C. d. 75) Which of the following is NOT a property of a red-black tree? All paths from root to null have the name number of nodes. The root is black. All child nodes of a red node must be black. All nodes must be red or black. 76) Which of the following statements about generic programming is NOT correct? a. Type parameters can be instantiated with wrapper class types. b. Type parameters can be instantiated with class types. C. Type parameters can be instantiated with primitive data types. d. Type parameters can be instantiated with interface types. 77) Consider the following code snippet: public class Box 4 private E data; public Box () {...} } Which of the following is a valid Box object instantiation? a. Box box = new Box(); b. Box box = new Box(); C. Box box = new Box; d. Box box = new Box(); 78) Which of the following necessitates the type erasure process? | The Java virtual machine does not work with generic types || To maintain backward compatibility to older versions of Java III Generics do not work with primitives a. ll only b. I and III only c. I and II only d. I only 69) Consider the following tree diagram: Which arithmetic expression is represented by this tree? (2 + 3) + (5 * 4)*6*(-1) b. [(2 + 3) + (5 * 4)]* (6 - 1) 2 + 3 + 5* 4 - 6-1 d. (2 + 3) * (5 * 4) * (6-1) a C. 70) Which of the following statements about balanced trees is NOT correct? a. For a given height, a balanced tree can hold more nodes than an unbalanced tree. b. In a balanced binary tree, each subtree has approximately the same number of nodes. In a balanced tree, all paths from the root to the leaves have approximately the same length. d. The efficiency of algorithms for balanced trees is better expressed using the size of the tree than the height of the tree. 71) Consider the following tree diagrams show right. Which of these trees is balanced? a. Il and Ill only b. I only C. I and II only d. I and III only II III 72) Assuming that the variablet is instantiated to an empty BinarySearch Tree, select a statement to complete the following code segment, so that the resulting binary search tree has a height of 4. t.add("a"); t.add("day"); t.add("in"); t.add("life"); a. t.add("your"); b. t.add("the"); C. t.add("his"); d. t.add("my"); M 73) Consider the following binary search tree: Which of the following sequences correctly represents a preorder traversal of this tree? a. J, E, M, C, G, P, A, H, N b. J, E, C, A, G, H, M, P, N c. A, C, H, G, E, N, P, M, J d. A, C, E, G, H, J, M, N, P A Η IN a 63) Consider the following tree diagram: Which of the following statements is NOT correct? N His a descendant of M b. N is a descendant of C c Lis a descendant of C (? d. N is a descendant of R 64) What is the height of the tree diagram in problem #63? 7 b. 3 C. 6 d. 4 65) Given the Node class (partially shown below), select an expression to complete the isleaf method, which is designed to return true if the node is a leaf, false otherwise. class Node public Object data; public List children, ... public boolean is Leaf) return } a. children.size() == 0 b. data == null C. children.get(0) == null d. root == null 66) Which of the following is NOT an example of a binary tree? a. A decision tree where each interior node contains a question, and the two subtrees correspond to a yes or no answer. b. An expression tree that shows the order of evaluation in an arithmetic expression. C. The family tree of a person, which includes all descendants of a person. d. A Huffman tree where the left and right turns on the paths to the leaves describe binary encodings. 67) Consider the following Huffman encoding tree: The letter H will be encoded as 0 a. 010 b. 001 C. 011 d. 000 0 68) The phrase OK will encode as O K a. 0110 b. 0010 C. 0111 1 d. 1001 H U a. 57) Suppose we maintain a linked list of length n in sorted order. What would be the big-Oh notation for printing out those elements that occur exactly once in the list? O(1) b. O(n) C. O(n log n) d. O(n2) 58) Insert the missing code in the following code fragment. This fragment is intended to add a new node to the head of a linked list: public class LinkedList public void addFirst (Object element) Node newNode = new Node(); newNode.data = element; } a. first = new Node; newNode.next = first; b. newNode.next = first; first = new Node; c. first = newNode.next; new Node.next = first; d. first = newNode.next; newNode = first; 59) Which of the following operations is least efficient in a LinkedList? a. Adding an element in a position that has already been located b. Linear traversal step Removing an element when the element's position has already been located C. d. Random access of an element a. 60) Which of the following statements about trees is NOT correct? The root of the tree does not have a parent. b. A tree is composed of nodes. C. A node can have multiple parents. d. A node can have multiple child nodes. 61) Consider the following tree diagram: H Which of the following nodes are siblings? a. HandM b. Dand B C. D and U d. Land T ?????? M 2) Conder the tree diagram from problem #61. Which of the following nodes are root nodes? a. R b. P C. C d. Rand P 74) Consider the following binary search tree: Which of the following sequences correctly represents breadth-first traversal of this tree? a. J, E, M, C, G, P, A, H, N b. J, E, C, A, G, H, M, P, N c. A, C, H, G, E, N, P, M, J d. A, C, E, G, H, J, M, N, P N a. b C. d. 75) Which of the following is NOT a property of a red-black tree? All paths from root to null have the name number of nodes. The root is black. All child nodes of a red node must be black. All nodes must be red or black. 76) Which of the following statements about generic programming is NOT correct? a. Type parameters can be instantiated with wrapper class types. b. Type parameters can be instantiated with class types. C. Type parameters can be instantiated with primitive data types. d. Type parameters can be instantiated with interface types. 77) Consider the following code snippet: public class Box 4 private E data; public Box () {...} } Which of the following is a valid Box object instantiation? a. Box box = new Box(); b. Box box = new Box(); C. Box box = new Box; d. Box box = new Box(); 78) Which of the following necessitates the type erasure process? | The Java virtual machine does not work with generic types || To maintain backward compatibility to older versions of Java III Generics do not work with primitives a. ll only b. I and III only c. I and II only d. I only 69) Consider the following tree diagram: Which arithmetic expression is represented by this tree? (2 + 3) + (5 * 4)*6*(-1) b. [(2 + 3) + (5 * 4)]* (6 - 1) 2 + 3 + 5* 4 - 6-1 d. (2 + 3) * (5 * 4) * (6-1) a C. 70) Which of the following statements about balanced trees is NOT correct? a. For a given height, a balanced tree can hold more nodes than an unbalanced tree. b. In a balanced binary tree, each subtree has approximately the same number of nodes. In a balanced tree, all paths from the root to the leaves have approximately the same length. d. The efficiency of algorithms for balanced trees is better expressed using the size of the tree than the height of the tree. 71) Consider the following tree diagrams show right. Which of these trees is balanced? a. Il and Ill only b. I only C. I and II only d. I and III only II III 72) Assuming that the variablet is instantiated to an empty BinarySearch Tree, select a statement to complete the following code segment, so that the resulting binary search tree has a height of 4. t.add("a"); t.add("day"); t.add("in"); t.add("life"); a. t.add("your"); b. t.add("the"); C. t.add("his"); d. t.add("my"); M 73) Consider the following binary search tree: Which of the following sequences correctly represents a preorder traversal of this tree? a. J, E, M, C, G, P, A, H, N b. J, E, C, A, G, H, M, P, N c. A, C, H, G, E, N, P, M, J d. A, C, E, G, H, J, M, N, P A Η IN a 63) Consider the following tree diagram: Which of the following statements is NOT correct? N His a descendant of M b. N is a descendant of C c Lis a descendant of C (? d. N is a descendant of R 64) What is the height of the tree diagram in problem #63? 7 b. 3 C. 6 d. 4 65) Given the Node class (partially shown below), select an expression to complete the isleaf method, which is designed to return true if the node is a leaf, false otherwise. class Node public Object data; public List children, ... public boolean is Leaf) return } a. children.size() == 0 b. data == null C. children.get(0) == null d. root == null 66) Which of the following is NOT an example of a binary tree? a. A decision tree where each interior node contains a question, and the two subtrees correspond to a yes or no answer. b. An expression tree that shows the order of evaluation in an arithmetic expression. C. The family tree of a person, which includes all descendants of a person. d. A Huffman tree where the left and right turns on the paths to the leaves describe binary encodings. 67) Consider the following Huffman encoding tree: The letter H will be encoded as 0 a. 010 b. 001 C. 011 d. 000 0 68) The phrase OK will encode as O K a. 0110 b. 0010 C. 0111 1 d. 1001 H U a. 57) Suppose we maintain a linked list of length n in sorted order. What would be the big-Oh notation for printing out those elements that occur exactly once in the list? O(1) b. O(n) C. O(n log n) d. O(n2) 58) Insert the missing code in the following code fragment. This fragment is intended to add a new node to the head of a linked list: public class LinkedList public void addFirst (Object element) Node newNode = new Node(); newNode.data = element; } a. first = new Node; newNode.next = first; b. newNode.next = first; first = new Node; c. first = newNode.next; new Node.next = first; d. first = newNode.next; newNode = first; 59) Which of the following operations is least efficient in a LinkedList? a. Adding an element in a position that has already been located b. Linear traversal step Removing an element when the element's position has already been located C. d. Random access of an element a. 60) Which of the following statements about trees is NOT correct? The root of the tree does not have a parent. b. A tree is composed of nodes. C. A node can have multiple parents. d. A node can have multiple child nodes. 61) Consider the following tree diagram: H Which of the following nodes are siblings? a. HandM b. Dand B C. D and U d. Land T ?????? M 2) Conder the tree diagram from problem #61. Which of the following nodes are root nodes? a. R b. P C. C d. Rand P 50) Consider the following code snippet: LinkedList myllist - new Linkedlist : myLList.add("Mary"); myLList.add("John"); myLList.add("Sue"); ListIterator iterator - myllist.listIterator; iterator.next(); Iterator.next(); iterator.add("Robert"); iterator.previous(); iterator. previous(); iterator.remove(); System.out.println(myLList); What will be printed when this code is executed? a. [Mary, John, Robert, Sue] b. (John, Robert, Sue] C. (Mary, Robert, Sue] d. (Mary, John, Sue] 51) Which of the following statements about sets is correct? a. Attempting to remove an element that is not in the set generates an exception. b. You can add an element to a specific position within a set. C. A set is a collection of unique elements organized for efficiency. d. A set allows duplicate values. 52) Which of the following statements about the TreeSet class is NOT correct? Elements are stored in nodes. b. Elements are arranged in linear fashion. To use a TreeSet, it must be possible to compare the elements. d. Elements are stored in sorted order. a. C. 53) Assume that you have declared a stack named myStack to hold String elements. Which of the following statements will correctly remove an element from myStack? myStack.delete(); b. myStack.pop(); c. myStack.remove(); d. myStack.get(); a. 54) Elements in a hash table are said to a. be equivalent b. compress when they have the same hash code value. C. collide d. buffer well a. 55) Which of the following statements about hash tables is correct? The hash code is used to determine where to store each element. b. Elements in the hash table are sorted in hash code order. C. A hash table allows duplicate elements. d. No two elements of a hash table can have the same hash code. B) In the textbook implementation, the Node class is a private inner class of the LinkedList class. Wh of the following statements regarding this implementation is NOT correct? a. The methods of the LinkedList class can access the public features of the Node class. b. The methods of the Node class can access the public features of the LinkedList class. c. The methods of the Node class can be directly accessed by other classes. d. The Node class's instance variables that represent the node element and its next node refere are declared as public. 44) Consider the following code snippet: LinkedList words - new Linkedlist> 0 : words. addLast ("abc"); words. addLast ("def"); words.addLast ("ghi"); System.out.print (words. remove Last()); System.out.print (words.removeFirst()); System.out.print (words. removeLast()); What will this code print when it is executed? a. abcdefghi b. defghiabc c. ghiabcdef d. abcghidef 45) What can a generic class be parameterized for? methods b. iterators a. c. types d. properties 46) Which method is NOT part of the ListIterator interface? hasPrevious b. hasMore a. c. add d. hasNext 47) Select an appropriate expression to complete the method below. The number of times that the string stored in name appears in theList. should return the public static int count (LinkedList theList, String name) int number = 0; Iterator iter = theList.iterator(); while 1 if (iter.next().equals (name)) 1 number++; } return number; a. theList.next()!= null b. iter.hasNext() C. theList.hasNext() d. iter.next()!= null 48) When using the add method of the ListIterator to add an element to a linked list, which of the following statements is correct? a. The new element is inserted before the iterator position, and a subsequent call to next would be unaffected. b. The new element is inserted after the iterator position, and a subsequent call to next would return the new element. C. The new element is inserted after the iterator position, and a subsequent call to previous would be unaffected. d. The new element is inserted before the iterator position, and a subsequent call to next would return the new element. need to access values using a key, and the keys must be sorted. Which collection type should use? Queue b. TreeMap c. HashMap d. ArrayList 36) The partial linear search method below is designed to search an array of String objects. Select the expression that would be needed to complete the method. publie static int search (String[] a, string item) for(int 1-0, 1 ca.length; i++) 11 return i return -1; a. ali] == item b. a[i].compare To(item) c. a[i].equals(item) d. a[i].indexOf(item) 37) The sort method of the Arrays class sorts arrays containing objects of classes that implement the interface. a. Ordered b. Sortable c. Array d. Comparable 38) The ArrayList class implements the Stack b. Queue interface. a d. Set c. List 39) A list is a collection that a. does not allow elements to be inserted in any position. b. only allows items to be added at one end and removed at the other end. C. manages associations between keys and values. d. should be used when you need to remember the order of elements in the collection. 40) A collection without an intrinsic order is called a Stack b. Queue a. c. List d. Set 41) A collection that allows speedy insertion and removal of already-located elements in the middle of i called a a. linked list b. stack C. set d. queue 42) What is included in a linked list node? | a reference to its neighboring nodes II an array reference III a data element 3. Il only b. I and III only c. I only d. II and Ill only hich nodes need to be updated when we insert a new node to become the fourth node fro eginning of a doubly-linked list? a. The current third and fourth nodes. b. The current fourth and fifth nodes. c. The current first node. d. The current third node. 26) In big-Oh notation, when we consider the order of the number of visits an algorithm makes, what do we ignore? 1 power of two terms II the coefficients of the terms III all lower order terms II and III only b. ll only c. a. c. I and Il only d. I only 27) In Big Oh notation, selection sort is a n2 algorithm. If you increase the size of a dataset fivefold, how much longer does it take to sort it with the selection sort algorithm? a. Approximately 100 times longer b. Approximately 5 times longer c. Approximately 20 times longer d. Approximately 25 times longer 28) Which sort algorithm starts by cutting the array in half and then recursively sorts each half? insertion sort merge sort b. quicksort d. selection sort 29) How many times can an array with 4,096 elements be cut into two equal pieces? 10 b. 8 c. 16 d. 12 30) Merge sort has a O(n log2(n)) complexity. If a computer can sort 1,024 elements in an amount of time x. approximately how long will it take the computer to sort 1,024 times that many, or 1,048,576 elements? 8,192x 2048x b. 1,024x d. 1,048,576x a. C a. steps. d. O(nl) 31) In the worst case, a linear search locates a value in an array of length n in a. Ollog n2) b. O(n) c. O(log n) b. n 32) If an element is present in an array of length n, how many element visits, on average, are necessary to find it using a linear search? a. n/2 c. 21 d. n2 33) Binary search is an algorithm. a. Odlog n) b. O(n) c. O(n log n) d. O(nl) 34) Given an ordered array with 31 elements, how many elements must be visited in the worst case of binary search? 16 b. 8 c. 5 d. 4 a. Can you search the following array using binary search? int[] A = {6, 5, 4, 2, 0, 1, -1, -17}; a. No, negative numbers are not allowed because they indicate that a value is not prese b. Yes. Binary search can be applied to any array. C. No. Binary search can be applied to a sorted array only. d. Yes, but the algorithm runs slower because the array is in descending order. 21) in each iteration, selection sort places which element in the correct location? The smallest in the array. c. A random element. b. The largest element in the array. d. The smallest element not yet placed in prioriterations 22) Consider the sort method for selection sort shown below: public static void sort (int) a) for (int 1 - 0) 1a. length - 11 1++) int min Pos - minimum Position is swap (min Pos, 1) a. C. d. Suppose we modify the loop control to read int 1 - 1:1 c a.length - 1, 1++. What would be the The sort would still work correctly. b. The sort would not consider the first array element. An exception would occur The sort would not consider the last array element. 23) The performance of an algorithm is most closely related to what? The type of elements b. The total number of elements The total number of element visits d. The number of lines of code in the method a. C. 24) Consider the swap method shown below from the Selection Sorter class. If we modified it as shown the swap2 method shown below, what would be the effect on the sort method? private static void swap (int[] a, int i, int j) int temp = a[i]; a[i] = a[j]; a[j] = temp; } private static void swap2 (int[] a, int i, int j) { a[i] = a[j]; a[j] = a[i]; } a. Some array elements would be overwritten. b. It would sort the array in reverse order. C. It would still be correct but run a little faster. d. There would be no effect. -5) Consider an array with n elements. If we visit each element n times, how many total a. n" c. 21 d. n? b. n 16) What is required to make a recursive method successful? ! special cases that handle the simplest computations directly Il a recursive call to simplify the computation III a mutual recursion a. I, II, and III b. ll only C. d. I only I and II only 17) Consider the getArea method from the textbook shown below. public int getArea() if (width = 0 if (i == 0) { return j; } else ( return add(i - 1, j + 1); } Identify the terminating condition in this recursive method. a. there is no terminating condition b. i == 0 C. return i d. return add(i-1, j + 1) 20) What type of algorithm places elements in order? b. deletion b. searching c. sorting d. insertio Which of the following is the most important consideration when designing a class? Each class should represent no more than three specific concepts. Each class should represent a single concept or object from the problem domain. b C d. Each class should represent multiple concepts only if they are closely related 10) A class (classOne) is considered to have a dependency on another class (classTwo) under which of the following conditions? Each class uses objects of the other. b The public interfaces of both classes are cohesive C Classtwo uses objects of classone. d. Classone uses objects of ClassTwo. 11) A UML class diagram would be most useful in visually illustrating which of the following? a. The cohesiveness of a class's interface. b. The amount of complexity of a class's interface. c. Dependencies between classes. d. Relationships between classes and their interfaces. 12) Which statement correctly describes the class relationship shown in this diagram at the right? a. Cash Register class depends on Coin class b. Coin class depends on Cash Register class Cash Register class aggregates Coin class. Coin Coin class inherits from Cash Register class. 13) Consider the following code snippet: CashRegister C. d public class Motorcycle private Tired tires; a. } This code is best described as an example of Inheritance. b. Aggregation. c. Polymorphism. d. Association 14) Which statement correctly describes the class relationship shown in this diagram? a. Quiz class depends on Question class b. Question class aggregates Quiz class c. Quiz class aggregates Question class. Quiz d. Question class inherits from Quiz class. Ques 15) Consider the following code snippet: public class Motorcycle extends Vehicle private Tire[] tires; } This code is best described as an example of a. Inheritance and multiplicities. c. Inheritance and aggregation b. Aggregation and dependency. d. Inheritance and interface. 1) a. 2) A(n) COMS 104 Introduction to Programming Final Exam Spring 2021 Name: Samuel Abebe Write the letter of the correct choice in front of each numbered question. are generated when the user presses a key, clicks a button, or selects a menu item. Listeners c. Interfaces. b. Events. d. Errors. has an instance method addActionListener() for specifying which object is responsible for implementing the action associated with the object. JFrame C. JButton b. JSlider d. JLabel 3) To draw an ellipse, you must include which of the following import statements? import java.awt.Graphics; import javax.swing.JPanel; b. import javax.awt; d. import java.awt.Ellipse; 4) When added to the code below, which statement will set the color of the next item drawn to green? a a. c. public class Italian Flag Component extends JComponent { public void paint Component (Graphics g) g.drawRect (100, 100, 30, 60); } a. g.setColor(GREEN); b. B)g.setColor(0, 255, 0); C. g.setColor(Color.GREEN); d. g.setColor("GREEN"); 5) Which of the following most likely indicates that you have chosen a good name for your class? a. The name consists of a single word. b. You can tell by the name what an object of the class is supposed to represent. c. You can easily determine by the name how many concepts the class represents. d. The name describes what task the class will perform. 6) Alan is used to create objects with the same behavior. a. aggregation C. dependency b. association d. class 7) After you have identified a set of classes eede for a program, you should now a. Define the behavior of each class. b. Look for nouns that describe the tasks. C. Begin writing the code for the classes. d. Establish the relationships between the classes. A CRC card describes a. A class, its responsibilities, and its collaborating classes. b. A class, its methods, and its constructors. c. A class, its relationships, and its collaborating classes. d. A class, its requirements, and its concurrent classes.