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