Data Structures using Java
9. To traverse a linked list, first set current = first; Next, set up a loop, using the following test: while(current.link != NULL) a. true b. false 10. In a linear representation of a stack, which of the following values points to the top item in the stack? a. stackTop b. stackTop - 1 c. 0 d. -1 11. The method front returns the first element in the queue. a. true b. false 12. In a queuing system, the time it takes to serve a customer is referred to as the waiting time. a. true b. false 13. A queue is a last in first out data structure. a. true b. false 14. The addQueue method properly inserts an element to the queue and increments the variable count by one. a. true b. false 15. In a queuing system, the term server refers to the object that provides the service. a. true b. false 16. A technique in which one system models the behavior of another system is called simulation. a. true b. false 17. 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 18. In queuing systems, queues of objects are waiting to be served by various ____. a. operations b. lists c. customers d. servers
19. Refer to the figure below. Which of the following members in the UML diagram adds an element to the front of the queue?
|
QueueClass |
|
-maxQueueSize: int -count: int -queueFront: int -queueRear: int -list: DataElement[] |
|
+Queueclass() +QueueClass(int) +QueueClass(Queueclass) +inializeQueue(): void +isemptyQueue(): boolean +isFullQueue(): boolean +front() throws QueueUnderfolwException: DataElement +back() throws QueueUnderfolwException: DataElement +addQueue(DateElement) throws QueueOverflowException: void +deleteQueue() throws QueueUnderflowException: void +copyQueue(QueueClass): void |
a. front b. addQueue c. back d. Elements aren't added to the front of queues 20. Queue can be derived from the class ____. a. LinkedListClass b. stack c. list d. array 21. In chaining, the average number of comparisons for an unsuccessful search is equal to the load factor. a. true b. false 22. In open addressing, data is stored in which of the following? a. linked list b. hash table c. stack d. queue 23. One way to solve secondary clustering is with double hashing. a. true b. false 24. The sequential search algorithm is the optimal worst-case algorithm for solving search problems by the comparison method. a. true b. false 25. In the binary search algorithm, two key comparisons are made through every iteration of the loop. a. true b. false 26. To search through a list you need to know the length of the list. a. true b. false 27. ____ uses a random number generator to find the next available slot. a. Linear probing b. Random probing c. Quadratic probing d. Chaining 28. 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 29. Binary search can be performed on both sorted and unsorted lists. a. true b. false 30. What is the maximum number of key comparisons made when searching a list L of length n for an item using binary search? a. log n b. 2 * log2n + 2 c. 2 d. n 31. Selection sort always starts with the middle element of the list. a. true b. false 32. Suppose that L is a list of n elements, where n > 0. Let W(n) denote the number of key comparisons in the worse case of merge sort. Which of the following is true? a. W(n) = O(n log n) b. W(n) = O(n log2n) c. W(n) = O(n2 log2n) d. W(n) = O(log n) 33. In quick sort, the average case for the number of swaps is O(n log2n). a. true b. false 34. Heap sort, for array-based lists, is of the order ____ even in the worst case. a. O(log n) b. O(n log n) c. O(log2n) d. O(n log2n)
35. A selection sort can be implemented by selecting the largest element in the (unsorted portion of the) list and moving it to the ____ of the list. a. pivot b. top c. middle d. bottom 36. The selection sort algorithm repeatedly moves the smallest element from the unsorted list to the beginning of the unsorted list. a. true b. false 37. In quick sort, the list is partitioned into two sublists by selecting a(n) ____, and the two sublists are then sorted and combined into one list in such a way so that the combined list is sorted. a. marker b. pivot c. midpoint d. average 38. A heap is a list in which each element contains a key, such that the key in the element at position k in the list is at least as large as the key in the element at position 2k + 1 (if it exists), and 2k + 2 (if it exists). a. true b. false 39. Merge sort divides the list into ____ sublists of nearly equal size. a. two b. three c. four d. five 40. It can be shown that the average number of key comparisons for insertion sort is ____. a. O(n) b. O(n2) c. O(n log n) d. O(n2 log n) 41. The height of a binary tree is the number of nodes on the longest path from the root to a leaf. a. true b. false 42. If a binary tree x has two subtrees, left and right, which of the following must be true about left and right? a. left and right are binary trees b. left and right are lists c. left and right are linked lists d. left and right are queues 43. In a binary search tree, the average number of nodes visited in a search of T is approximately ____. a. O(n log n) b. O(n log2n) c. O(n2 log2n) d. O(log2n)
44. In a diagram of a binary tree, each node of the binary tree is represented as a circle and the circle is labeled by the node. a. true b. false