Data structures using JAVA final exam
Q1. In a linked list implementation of a stack, only a fixed number of elements can be pushed onto the stack.
a. true
b. false
Q2. In a linked representation, memory for the stack elements is allocated dynamically.
a. true
b. false
Q3. Which of the following must be imported in a program in order to use the Java stack class?
a. java.util
b. stack.util
c. java.stackclass
d. java.classStack
Q4. An array is a random access data structure; a stack is not.
a. true
b. false
Q5. StackClass s = new StackClass(50);
int x, y, z;
s.push(new IntElement(3));
s.push(new IntElement(7));
x = s.pop();
s.push(new IntElement(5));
y = s.pop();
z = s.pop();
Given the sequence of operations above, what is the value of x?
a. 0
b. 3
c. 5
d. 7
Q6. A stack is also called a LIFO data structure.
a. true
b. false
Q7. In a linked list implementation of a stack you must keep track of the address of the top element of the stack.
a. true
b. false
Q8. The operation pop returns the top element of the stack.
a. true
b. false
Q9. The method deleteQueue does which of the following?
a. uses one queue to delete another
b. removes the back element from the queue
c. removes the front element from the queue
d. removes all elements from the queue leaving an empty queue
Q10. Queue can be derived from the class ____.
a. LinkedListClass
b. stack
c. list
d. array
Q11. The method front returns the first element in the queue.
a. true
b. false
Q12. In a queue object, the constructor initializes queueFront and queueRear to indicate that the queue is empty.
a. true
b. false
Q13. FIFO is similar to the way customers in line at a bank are serviced.
a. true
b. false
Q14. In queuing systems, queues of objects are waiting to be served by various ____.
a. operations
b. lists
c. customers
d. servers
Q15. A queue is a set of elements of the same type in which the elements are added at one end and deleted from the other end.
a. true
b. false
Q16. Each iteration of the main loop in the simulation program represents one minute.
a. true
b. false
Q17. In general, if L is a sorted list of size n, to determine whether an element is in L, the binary search makes at most 2 * log2n + 2 key (item) comparisons.
a. true
b. false
Q18. ____ uses a random number generator to find the next available slot.
a. Linear probing
b. Random probing
c. Quadratic probing
d. Chaining
Q19. Data stored in a hash table can be stored in ____.
a. an array only
b. a linked list only
c. a stack only
d. both an array and a linked list
Q20. If the hash function causes a cluster at a particular home position it is known as ____.
a. rehashing
b. primary clustering
c. aggregation
d. secondary clustering
Q21. On average, the number of comparisons made by a sequential search is equal to one-third the size of the list.
a. true
b. false
Q22. One of the disadvantages of chaining is that if the item size is small, a considerable amount of space is wasted.
a. true
b. false
Q23. One requirement of linear search is that the item must be in the array.
a. true
b. false
Q24. In linear search, you search an array starting from the middle component.
a. true
b. false
Q25. If we want to design a search algorithm that is of an order less than log2n, then it ____ be comparison based.
a. must
b. could
c. cannot
d. should
Q26. The worst case for the number of comparisons in quick sort is O(n2).
a. true
b. false
Q27. Suppose that Lis a list of nelements, where n> 0. Let A(n) denote the number of key comparisons in the average case of merge sort. Which of the following is true?
a. A(n) = O(n log2n)
b. A(n) = O(n log n)
c. A(n) = O(n2 log n)
d. A(n) = O(n2 log2n)
Q28. Selection sort always starts with the middle element of the list.
a. true
b. false
Q29. In quick sort the list is partitioned into three sublists, and the three sublists are then sorted and combined into one list in such a way so that the combined list is sorted.
a. true
b. false
Q30. Empirically, heap sort usually takes twice as long as quick sort.
a. true
b. false
Q31. The functions implementing sorting algorithms are included as private members of the related class.
a. true
b. false
Q32. Tracing the execution of a comparison-based algorithm can be done by using a graph called a comparison tree.
a. true
b. false
Q33. Insertion sort tries to reduce the number of key comparisons relative to which of the following?
a. heap sort
b. merge sort
c. selection sort
d. quick sort
Q34. Merge sort uses a pivot just like quick sort.
a. true
b. false
Q35. In an preorder traversal, the binary tree is traversed as follows: 1) Traverse the left subtree, 2) Visit the node, and 3) Traverse the right subtree.
a. true
b. false
Q36. In a binary search tree, the key in the ____ node is larger than every key in the left subtree and smaller than every key in the right subtree.
a. child
b. root
c. right
d. head
Q37. The ____ of a binary tree is the number of nodes on the longest path from the root to a leaf.
a. level
b. height
c. width
d. depth
Q38. A double rotation at a node is a right rotation followed by a left rotation.
a. true
b. false
Q39. There are ____ cases to consider when deleting a node from a binary search tree.
a. two
b. three
c. four
d. five
Q40. In an AVL tree: 1) the height of the left and right subtrees of the root differ by at most 2, and 2) the left and right subtrees of the root are AVL trees.
a. true
b. false
Q41. In a perfectly balanced binary tree ____.
a. the left and right subtrees of the root are binary trees
b. the left and right subtrees of the root have the same depth
c. the left and right subtrees of the root have the same width
d. the left and right subtrees of the root are perfectly balanced binary trees
Q42. Any node in a binary tree can be called a leaf node.
a. true
b. false
Q43. In a breadth first traversal all the nodes at any level, i, are visited before visiting the nodes at level i+ 1.
a. true
b. false
Q44. An edge incident on a single vertex is called a ____.
a. loop
b. map
c. parallel
d. component
Q45. The two most common graph traversal algorithms are the height first traversal and breadth first traversal.
a. true
b. false
Q46. The ____-first traversal of a graph is similar to traversing a binary tree level by level.
a. height
b. depth
c. breadth
d. width
Q47. Graphs can be used to model chemical compounds.
a. true
b. false
Q48. In an undirected graph G = (V, E), the elements of E are ordered pairs.
a. true
b. false
Q49. The second step in a depth first traversal starting at a given node v is to ____.
a. mark the node as visited
b. visit the node
c. go to the vertex u adjacent to v
d. delete the node
Q50. A ____ tree of G is a spanning tree with the minimum weight.
a. minimal spanning
b. short
c. binary
d. binary search