Data Structures & Algorithms
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 tree
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
Ans: D
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
Ans: B
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
Ans: A
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
Ans: C
5. Which of the following statements is true?
- An abstract data type can be conveniently searched for an item by key.
- An abstract data type can be conveniently traversed.
- An abstract data type is an interface within a program that simplifies problems.
- An abstract data type is a database for direct user-accessible data.
Ans: C
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
Ans: C
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
Ans: C
8. Which of the following statements is true regarding a queue?
- It may be implemented either by an array or a linked list.
- It may be implemented by a heap because first in first out.
- It may be implemented by a linked list because insertions and deletions may be from the same end.
- It may be implemented by an array without providing for wrap-around.
Ans: A
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
Ans: A
10. Which of the following is true regarding the efficiency of the shell sort?
- It is slower than O (n2).
- It is faster than O (n*log2 n).
- It is not as efficient as the insertion sort.
- It has not been established theoretically, i.e. as a single function of n.
Ans: D
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
- d. quick sort
Ans: A
12. Which of the following sorts does not operate in O(n*log2 n) time?
- a. Quick sort
- b. Merge sort
- c. Heap sort
- d. Hash sort
Ans: D
13. Which of the following sorts is not efficient in use of storage because it requires an extra array?
a. quick sort
b. merge sort
c. heap sort
d. insertion sort
Ans: - B
14. Which of the following sorts may deteriorate to ‘O (n2)’ time if the data is partitioned into a sub array of 1 element and a sub array of n-1 elements?
a. Insertion sort
b. Merge sort
c. Heap sort
d. Quick sort
Ans: - D
15. Which of the following sorts is efficient in time but requires a considerable amount of extra storage space?
- shell sort
- merge sort
- heap sort
- quick sort
Ans: - 2
16. If the rightmost element is selected as the pivot in the quick sort
- 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.
Ans: - A
(Left) 44 _ _ _ _ ..._ _ _ _ 86 _ _ _ _ --- _ _ _ _ 29 (right)
17. Applying the median-of-three method to the above array in the quick sort, which of the following would be selected as the pivot value to partition the array?
- a. 44
- b. 86
- c. 29
- d. 53
Ans: - A
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 quick sort with 70 as the pivot and show the position of each item in the array immediately after that partition.
Ans:- 50 30 20 60 10 40 70 110 80 100 90 120
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)
Ans:- O(2n), O(n2), O(n*log2 n), O(n), O(log2 n), O(1)
20. Starting with h = 1, generate the gap sequence for the shell sort using the recursive
Expression: h = 3*h + 1, for an array of 1000 elements.
Ans: - 1 4 13 40 121 364
21. 12 13 11 16 14 15 18 19 17 20
0 1 2 3 4 5 6 7 8 9
The shell sort 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.
Ans:- YES, 12<14<17 13<15<20 11<18 16<19
22. 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
Ans:- True
23. A rooted tree is a directed graph in which each node is referenced by at most ___ node(s).
Ans: - 1
24. A binary tree is a tree in which each node references at most _____ node(s).
Ans: - 2
25. A binary search tree is a binary tree in which the data in the left sub tree of a node is greater than the data in the node and the data in the right sub tree is greater than the data in the node. T/F
Ans:- False
26. A binary expression tree is a binary tree in which the data in the left sub tree of a node is greater than the data in the node and the data in the right sub tree is greater than the data in the node. T/F
Ans:- False
27. What is the minimum height of a binary tree with 31 nodes?
Ans:- 4
28. If a binary search tree containing 31 nodes is balanced, what is the maximum number of comparisons needed to find any key value?
Ans:- 5
Refer to this binary tree for questions 29 - 31
20
30 10
5 15 25 35
8 1 12 18
29. A preorder traversal of this tree is 20 30 5 8 1 15 12 18 10 25 35.
30 An inorder traversal of this tree is 8 5 1 30 12 15 18 20 25 10 35.
31. A post order traversal of this tree is 8 1 5 12 18 15 30 25 35 10 20.
Refer to this binary tree for questions 32 - 35
25
15 35
10 20 30 40
32. Redraw the tree after the value 18 is inserted.
Ans:
25
15 35
10 20 30 40
18
33. Redraw the tree after the value 18 is inserted and 25 is removed.
Ans:
20 30
15 35 OR 15 35
10 18 30 40 10 20 40
18
34. 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
35. 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 36-37
+
/ *
- c d e
a b
36. 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
37. 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))
38. 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 sub tree < root < right sub tree.
d. All nodes have exactly 0 or 2 children.
Ans: C
39. 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
Ans: B
40. 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.
Ans: D
41. 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.
Ans: A
42. 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.
Ans: A
43. 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 quick sort.
Ans: D
44. 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.
45. 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.
Ans: C
46. 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.
Ans: B
No comments:
Post a Comment