CS234 Data Types and Structures Spring 2015 Example Questions for the Final Exam

Document Content and Description Below

CS234 Data Types and Structures Spring 2015 Example Questions for the Final Exam Q1) Multiple Choice Questions 1) Which of the following growth-rate functions indicate a problem whose time requir ... ement is independent of the size of the problem? a) O(n) b) O(log2n) c) O(2n ) d) O(1) 2) What feature of heaps allows them to be efficiently implemented using an array/Python list? a) Heaps are binary search trees. b) Heaps are complete binary trees. c) Heaps are full binary trees. d) Heaps contain only integer data. 3) Tree algorithms typically run in time O(d) . What is d? a) The depth of the tree. b) The number of divisions at each level. c) The number of entries in each node. d) The number of nodes in the tree. e) The total number of entries in all the nodes of the tree. 4) In the context of hashing, what is meant by a collision? a) The hash function returns a value index greater than the table size. b) The insertion algorithm cannot find an empty slot in the table. c) Two equal objects hash to the same slot. d) Two unequal objects hash to the same slot. 5) Which of the following data structures allow us to find any element in O(1) expected runtime? a) Stack c) Queue b) Hash Table d ) Linked List 6) An algorithm that calls itself directly or indirectly is known as a) Sub algorithm c) Recursion b) Polish notation d) Traversal algorithm 7) The in order traversal of tree will yield a sorted listing of elements of tree in a) Binary trees c) Binary search trees b) Heaps d) None of above 8) In a Min binary Heap a) Values in a node is greater than every value in left sub tree and smaller than right sub tree b) Values in a node is smaller than both values in its children c) Both of above conditions applies d) Are not in both choice a and b 9) the basic idea behind Huffman coding is to: a) Compress data by using fewer bits to encode fewer frequently occurring characters b) Compress data by using fewer bits to encode more frequently occurring characters c) Expand data by using fewer bits to encode more frequently occurring characters d) Compress data by using more bits to encode more frequently occurring characters 10) If a graph is a tree( a graph with no cycle), BFS performs: a) Inorder tree traversal b) Preorder tree traversal c) Postorder tree traversal d) Level order tree traversal 11) What value does function mystery return when called with a value of 4? def fib(x): if x == 0 or x ==1: return 1 else: return fib(x-1)+ fib(x-2) a) 0 b) 1 c) 3 d) 5 12) How many elements in a 2D array declared as D[2][4]? a) 4 b) 6 c) 10 d) 8 13) An algorithm that requires __________ operations to complete its task on n data elements is said to have a linear runtime. a) n3 + 9 b) 3 n2 + 3 n + 2 c) 2 n + 1 d) 6 14) At most, how many comparisons are required to search a sorted vector of 1023 elements using the binary search algorithm? a) 10 b) 15 c) 20 d) 30 15) In general, linked lists allow: a) Insertions and removals anywhere. b) Insertions and removals only at one end. c) Insertions at the back and removals from the front. d) None of the above. 16) Which data structure represents a waiting line and limits insertions to be made at the back of the data structure and limits removals to be made from the front? a) Stack. b) Queue. c) Binary tree. d) Linked list. 17) Which of the following is a difference between vectors and arrays? a) Access to any element using the [] operator. b) Stored in contiguous blocks of memory. c) The ability to change size dynamically. d) Efficient direct access to any element. 18) Which of the following algorithms can be used to most efficiently determine the presence of a cycle in a given graph? a) Depth First Search b) Breadth First Search c) Prim's Minimum Spanning Tree Algorithm d) Kruskal' Minimum Spanning Tree Algorithm 19) Traversal of a graph is different from tree because a) There can be a loop in graph so we must maintain a visited flag for every vertex b) DFS of a graph uses stack, but inorrder traversal of a tree is recursive [Show More]

Last updated: 3 years ago

Preview 1 out of 15 pages