Cmsc230 Computer Science II: Data Structures & Algorithms



cmsc230 Computer Science II: Data Structures & Algorithms

Review for Final Exam

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:

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

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

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

d. 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):

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

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

a. binary search tree

b. priority queue

c. queue

d. stack

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

a. array b. linked list c. hash table d. heap

5. Which of the following statements is true?

a. An abstract data type can be conveniently searched for an item by key.

b. An abstract data type can be conveniently traversed.

c. An abstract data type is an interface within a program that simplifies problems.

d. An abstract data type is a database for direct user-accessible data.

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

a. ordered array b. ordered linked list c. heap d. binary search tree

7. 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 table b. binary search tree c. linked list d. unordered array

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

a. It may be implemented either by an array or a linked list.

b. It may be implemented by a heap because first in is first out.

c. It may be implemented by a linked list because insertions and deletions may be from the same end.

d. It may be implemented by an array without providing for wrap-around.

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

a. shell sort b. insertion sort c. selection sort d. bubble sort

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

a. It is slower than O(n2).

b. It is faster than O(n*log2 n).

c. It is not as efficient as the insertion sort.

d. It has not been established theoretically, i.e. as a single function of n.

11. The __________________ sort is good for almost-sorted files, operating in O(n) time if not too many items are out of place.

a. insertion b. bubble c. selection quicksort

12. Which of the following sorts does not operate in O(n*log2 n) time?

a. quicksort b. mergesort c. heapsort d. hashsort

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

a. quicksort b. mergesort c. heapsort d. insertion sort

14. 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 sort b. mergesort c. heapsort d. quicksort

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

a. shell sort b. mergesort c. heapsort d. quicksort

16. 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)

17. 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. 44 b. 86 c. 29 d. 53

18. 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.

19. 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)

20. 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.)

21. 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.

22. 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.

23. 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. T/F

Refer to this graph for nos. 24 - 27

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

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

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

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

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

most ___ node(s).

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

30. 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

31. 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

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

33. 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 34 - 36

20

30 10

5 15 25 35

8 1 12 18

34. A preorder traversal of this tree is ______________________________________.

35 An inorder traversal of this tree is ______________________________________.

36. A postorder traversal of this tree is ______________________________________.

Refer to this binary tree for questions 37 - 40

25

15 35

10 20 30 40

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

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

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

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

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

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

a. 25 10 15 20 30 35 40 b. 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 41 -

+

/ *

- c d e

a b

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

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

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

42. 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))

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

44. 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.

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

a. n - 1 b. (int) log2 n c. n d. no. levels + 1

46. 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.

47. 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.

48. 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.

49. 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.

50. 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.

51. 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.

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

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

its key value.

b. Using a hash table avoids collisions.

c. Linear probing, quadratic probing and rehashing are all methods of open

addressing.

d. The size of a table should be prime to facilitate efficient wraparound when

rehashing.

Refer to the following for questions 53 - 55

A simple hashing method for alphabetic keys has each letter of a key replaced by the number that represents where the letter is located in the alphabet disregarding case:

a b c d e f g h i j k l m n o p q r s t u v w x y z

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

and all of the resulting numbers are summed. The hash value is then formed by taking this intermediate result modulo the hash table length: h(word) = sum(lettercode) % tablesize

The length of the table to be used is 17 and the key fields of the objects to be stored in the table are:

BROWN,COLE,DAVIS,FOX,BAKER,ADAMS,GALO,JONES,FARMER,BROCK

53. Create a hash table to store this data using the method of linear probing to resolve collisions.

54. Create a hash table to store this data using the method of separate chaining.

55. Create a hash table to store this data rehashing if collisions occur using: step = 5 - key % 5.

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 justificationof 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 in a binary search tree

with values less than the root.

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

contain zero.

Answers:

1 d 2 b 3 a 4 c 5 c 6 c 7 c 8 a 9 a 10 d 11 a 12 d

13 b 14 d 15 b 16 a 17 a

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

19. 2n n2 n*log n n log n 1

20 see p.234

21. 1 4 13 40 121 364

22 yes: 12 baker --> /

4 --> brown --> davis --> adams --> /

5 --> /

6 --> /

7 --> /

8 --> /

9 --> /

10 --> farmer --> /

11 --> fox --> /

12 --> jones --> /

13 --> /

14 --> /

15 --> brock --> /

16 --> /

55. 0 /

1 cole

2 /

3 baker

4 brown

5 /

6 adams

7 /

8 /

9 davis

10 farmer

11 fox

12 jones

13 /

14 /

15 brock

16 galo

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download