cmsc230 Computer Science II: Data Structures & Algorithms

Review for Final Exam 12/02

1. Which of the following arrangements of general-purpose data structures is from slowest to fastest for the purpose of finding objects according to a key value :

  1. sorted arrays, sorted linked lists, hash tables, binary search trees
  2. sorted arrays, binary search trees, sorted linked lists, hash tables
  3. hash tables, binary search trees, sorted arrays, sorted linked lists
  4. sorted linked lists, sorted arrays, binary search trees, hash tables

2. Which of the following arrangements of general-purpose data structures is from slowest to fastest for the purpose of storing objects by key value (not necessarily in order):

  1. unsorted arrays, sorted linked lists, hash tables, binary search trees
  2. sorted arrays, binary search trees, linked lists, hash tables
  3. hash tables, binary search trees, sorted arrays, sorted linked lists

d. linked lists, binary search trees, hash tables, unsorted arrays

3. Which of the following arrangements of general-purpose data structures is from slowest to fastest for the purpose of storing objects by key value (in order):

a. unordered arrays, unordered linked lists, binary search trees

b. sorted arrays, binary search trees, linked lists, heaps

c. hash tables, sorted arrays, sorted linked lists

d. sorted arrays, sorted linked lists, binary search trees

4. Which of the following arrangements of general-purpose data structures is from slowest to fastest for the purpose of deleting objects by key value :

a. unsorted arrays, sorted linked lists, hash tables, binary search trees

b. sorted arrays, binary search trees, linked lists, hash tables

c. hash tables, binary search trees, sorted arrays, sorted linked lists

d. unsorted arrays, linked lists, binary search trees, hash tables

5. In an abstract data type, access is often limited to certain items. Which of the following is not such an abstract data type?

  1. binary search tree
  2. priority queue
  3. queue
  4. stack

6. Which of the following is not a basic data structure that could be used to implement an abstract data type?

a. arrayb. linked listc. hash table d. heap

7. Which of the following statements is true?

  1. An abstract data type can be conveniently searched for an item by key value.
  2. An abstract data type can be conveniently traversed.
  3. An abstract data type is an interface within a program that simplifies problems.
  4. An abstract data type is a database for direct user-accessible data.

8. Which of the following data structures implement a priority queue where deletion of

the item with highest priority must be as fast as possible?

a. any arrayb. ordered linked listc. heapd. binary search tree

9. Which of the following methods of implementing a priority queue is best when both insertion and deletion need to be reasonably fast?

a. ordered arrayb. ordered linked listc. heapd. binary search tree

10. The abstract data type stack can be implemented by which of the following data

structures:

a. binary search tree b. array c. binary expression tree d. heap

11. If the amount of data to be stored in a stack cannot be predicted, the best data structure to implement the stack is:

a. hash tableb. binary search treec. linked list d. array

12. Which of the following statements is true regarding a queue?

  1. It may be implemented either by an array or a linked list.
  2. It may be implemented by a heap because first in is first out.
  3. It may be implemented by a linked list because insertions and deletions may be from the same end.
  4. It may be implemented by an array without providing for wrap-around.

13. Which of the following sort algorithms is not an O(n2) sort?

a. shell sortb. insertion sortc. selection sortd. bubble sort

14. Which of the following sort algorithms is not an O(n*log2(n)) sort?

a. heap sort b. shell sortc. quick sortd. merge sort

15. Which of the following is true regarding the efficiency of the shell sort ?

  1. It is slower than O(n2).
  2. It is faster than O(n*log2 n).
  3. It is not as efficient as the insertion sort.
  4. It has not been established theoretically, i.e. as a single function of n.

16. The ______sort is good for almost-sorted files, operating in O(n) time if not too many items are out of place even though its complexity is O(n2) time when data is stored randomly.

a. insertionb. bubblec. selectionquicksort

17. Which of the following sorts does not operate in O(n2) time?

a. selection sortb. bubble sort c. heap sortd. insertion sort

18. Which of the following sorts is not efficient in use of storage because it requires an extra array?

a. quick sortb. merge sortc. heap sortd. insertion sort

19. Which of the following sorts may deteriorate to O(n2) time if the data is partitioned into a subarray of 1 element and a subarray of n-1 elements?

a. insertion sortb. mergesort c. heapsort d. quicksort

20. Which of the following sorts is efficient in time but requires a considerable amount of extra storage space?

a. shell sortb. merge sort c. list insertion sort d. quick sort

21. If the rightmost element is selected as the pivot in the quicksort

a. when the data is truly random, that value is a good choice.

b. when the data is sorted, that value is a good choice.

c. when the data is in reverse order, that value is a good choice.

d. that value is never a good choice.

(left) 44 _ _ _ _ ---_ _ _ _ 86 _ _ _ _ --- _ _ _ _ 29 (right)

22. Applying the median-of-three method to the above array in the quicksort, which of the following would be selected as the pivot to partition the array.

a. 44b. 86c. 29d. 53

23. 90 100 20 60 80 110 120 40 10 30 50 70

0 1 2 3 4 5 6 7 8 9 10 11

Apply one partition to the above array in the quicksort with 70 as the pivot and

show the position of each item in the array immediately after that partition.

24. Arrange the following functions, often used to represent complexity of algorithms

in order from slowest to fastest.

O(1), O(n), O(n*log2 n), O(log2 n), O(n2), O(2n)

25. public void mergeSort() // called by main()

{ // provides workspace

double[] workSpace = new double[nElems];

recMergeSort(workSpace, 0, nElems-1);

}

//------

private void recMergeSort(double[] workSpace, int lowerBound,

int upperBound)

{

if(lowerBound == upperBound) // if range is 1,

return; // no use sorting

else

{

int mid = (lowerBound+upperBound) / 2;

recMergeSort(workSpace, lowerBound, mid);

recMergeSort(workSpace, mid+1, upperBound);

merge(workSpace, lowerBound, mid+1, upperBound);

} // end else

} // end recMergeSort()

Apply the above sort to this array: 64 21 33 70 12 85 44 3 97 24 51 40

0 1 2 3 4 5 6 7 8 9 10 11

Show each subarray as it is ordered. (Hint: 10 subarrays of lengths 2,3 and 6 are sorted and merged.)

26. Starting with h = 1, generate the gap sequence for the shellsort using the recursive

expression: h = 3*h + 1, for an array of 1000 elements.

27. 12 13 11 16 14 15 18 19 17 20

0 1 2 3 4 5 6 7 8 9

The shellsort has been applied to the above array but is not completed!

Has the array been "4-sorted"? If yes, prove your answer by exhaustion.

If no, prove your answer by counterexample.

28. Which of the following recursive algorithms run in O(2n) time?

a. Arithmetic Series b. Factorials c.Towers of Hanoi d.Reverse Name

29. In computer science a graph is a data structure where vertices (nodes) represent objects which in turn represent real world data, and edges represent references to objects: how objects are related.

a. never true

b. true only when the graph is a tree

c. true only when the graph is directed

d. always true


Refer to this graph for nos.

30. Draw the adjacency matrix that could be used to store this graph.

31. What is the degree of vertex 'a' ?

32. Does an Eulerian path exist for this graph? If yes, show one. If no, explain why.

33. Show a depth-first search of this graph starting at vertex b.

34. Show a breadth-first search of this graph starting at vertex b.

35. A rooted tree is a directed graph in which each node is referenced by at

most ___ node(s).

36. A binary tree is a tree in which each node references at most _____ node(s).

37. A binary search tree is a binary tree in which the data in the left subtree of a node is

greater than the data in the node and the data in the right subtree is greater than the

data in the node. T/F

38. A binary expression tree is a binary tree in which the data in the left subtree of a

node is greater than the data in the node and the data in the right subtree is greater

than the data in the node. T/F

39. What is the minimum height of a binary tree with 31 nodes?

40. If a binary search tree containing 31 nodes is balanced, what is the maximum number of comparisons needed to find any key value?

Refer to this binary tree for questions 41-43

20

30 10

5 15 25 35

8 1 12 18

41. A preorder traversal of this tree is ______.

42 An inorder traversal of this tree is ______.

43. A postorder traversal of this tree is ______.

Refer to this binary tree for questions

25

1535

10 20 30 40

44. Redraw the tree after the value 18 is inserted.

45. Redraw the tree after the value 18 is inserted and 25 is removed.

46. Which of the following is the result of a postorder traversal of the original tree?

a. 10 15 20 30 35 40 25b. 10 20 15 30 40 35 25

c. 10 15 20 25 30 35 40 d. 40 35 30 25 20 15 10

47. Which of the following is the result of a preorder traversal of the original tree?

a. 25 10 15 20 30 35 40b. 25 15 10 20 35 30 40

c. 10 15 20 25 30 35 40 d. 40 35 30 25 20 15 10

Refer to this binary expression tree for questions

+

/*

- c d e

a b

48. Choose the algebraic expression stored in the above tree.

a. * + / - a b c d eb. - a b / c + * d e

c. + / a b - c * d ed. + / - a b c * d e

49. Choose the algebraic expression stored in the above tree.

a. ((a - b / c) + d * e)b. (((a - b) / (c + d) ) + d * e)

c. ((a - b / c) + (d * e))d. (((a - b) / c) + (d * e))

50. Draw a binary expression tree that stores the expression: (((a - b) / c) + (d * e))

51. Which of the following is not true about a binary expression tree?

a. All the internal nodes are operators.

b. All operands are leaves.

c. All data is stored following the rule: left subtree < root < right subtree.

d. All nodes have exactly 0 or 2 children.

52. The minimum height of a binary search tree containing n nodes is:

a. n - 1b. (int) log2 nc. nd. no. levels + 1

53. Which of the following statements concerning binary search trees is always true?

a. The search time is O(log2 n).

b. They are always balanced.

c. The delete time is O(log2 n).

d. The insert time depends on how well balanced they are.

54. Which of the following statements concerning heaps is not true?

a. A heap can be stored in a binary search tree.

b. A heap can be stored in an array.

c. A heap can be used to implement a priority queue.

d. A heap can be used to sort data.

55. Which of the following statements concerning heaps is not true?

a. Traversing a heap in order provides access to the data in numeric or

alphabetical order

b. Removing the item at the top provides immediate access to the key value

with highest (or lowest) priority.

c. Inserting an item is always done at the end of the array, but requires

trickleup() to maintain the heap rule.

d. A heap may be stored in an array.

56. A heapsort -

a. is impossible because the data is not in order, except that the highest is first.

b. requires a second array, making it space inefficient.

c. has O(n2) complexity.

d. is almost as efficient as the quicksort.

57. The following array contains a heap:80 60 70 40 30 20 50 10

0 1 2 3 4 5 6 7

Draw the same heap as a binary tree.

58. Which of the following is not true concerning hash tables?

a. An advantage of using hash tables is constant search time.

b. A disadvantage of hash tables implemented as arrays is the need to know

the amount of data in advance.

c. An advantage of hash tables is that data can be accessed in order.

d. The load factor of a hash table should never be more than 1/2 to 2/3 when

open addressing is used.

59. Which of the following is not true concerning hash tables?

a. A hash table has two dimensions as in a matrix.

b. A hash function is used to increase the size of the key value

c. A hash table is an array in which the location of an item is determined by

its key value.

d. Using a hash table avoids collisions.

60. Draw a diagram of a doubly linked list of objects that have 1 integer field and

two self - referential fields. Write a definition of the class of which each object is an

instance.. Write code that inserts a new first node in the list.

NOTE: the exam will consist of 3 parts:

part 1: 25 objective questions (@ 3 pts each = 75 pts).

part 2: 1 question requiring the top-down design of a program showing

use of appropriate classes and appropriate no. of classes for good

programming style and requiring justification of your choice of

data structures and algorithms. (10 pts.)

part 3: 1 question that will require writing code that solves a problem or

performs a task. (10 pts)

Total: 95pts.

Sample part 2: Design a program that accepts a string of characters such as an algebraic expression, checks whether the expression is parenthetically correct, and outputs an appropriate message. Ex. [(a + b / (c - d)] is not correct

Ex. [(a + b) / (c - d)] is correct

Sample part 2: Design a program that maintains records of participants in a tennis tournament, outputs the leading player at any given time and displays all records in order at the end of the tournament.

Sample part 2: Design a program for a credit card company that keeps records of and allows access to all its cardholders. Among important functions are identifying invalid ID's, inserting new members, closing accounts.

Sample part 3: Write a recursive method that returns the number of nodes in a linked list.

Sample part 3: Write a method that returns the number of nodes with values less than the

root node in a binary search tree.

Sample part 3: Write a method that returns the number of cells in a square matrix that

contain zero.