CSE214 COMPUTER SCIENCE II FINAL EXAM

CSE214 COMPUTER SCIENCE II
 FINAL EXAM
USE THE FOLLOWING INFORMATION TO ANSWER PROBLEMS 1.1-1.4:
Consider the following four operations on a data structure containing n data values.
A. Finding the maximum value in a singly linked list of n IntNode nodes. O(n)
B. Finding the maximum value in an array of n int values by sorting it first using insertion
sort.O(n^2)
C. Finding the maximum value in a full binary search tree of n BTNode nodes.O(log n)
D. Finding the maximum value in a standard heap of n data values. O(1)
1.1 The worst-case order of complexity is O(1) for which of these operations?
(a) A (b) B (c) C (d) D (e) none of these answers
1.2 The worst-case order of complexity is O(log n) for which of these operations?
(a) A (b) B (c) C (d) D (e) none of these answers
1.3 The worst-case order of complexity is O(n) for which of these operations?
(a) A (b) B (c) C (d) D (e) none of these answers
1.4 The worst-case order of complexity is O(n log n) for which of these operations?
(a) A (b) B (c) C (d) D (e) none of these answers
1.5 Which of the following postfix expressions evaluates to 35 (assuming integer division)?
(a) 5 4 3 2 1 + * - / (b) 5 4 3 2 1 * - / +
(c) 5 4 3 2 1 - / + * (d) 5 4 3 2 1 / + * -
(e) none of these answers
1.6 Consider a binary tree as a directed graph, where every non-leaf node has an edge to each of its
children. Assuming that left child is visited before right child, the depth-first traversal of this graph started
at root, is equivalent to which of the following binary tree traversal?
(a) preorder (b) postorder (c) inorder (d) none of these answers
1.7 What is the maximum number of edges in an undirected graph with n vertices without any multiple
edges? Remember self-cycles (self-loops) must be counted.
(a) n (b) n2
 (c) n2 – n (d) (n2 + n)/2 (e) (n2 – n)/2
1.8 What is the maximum number of edges in a simple directed graph with n vertices? Directed = n^2
(a) n (b) n2
 (c) n2 – n (d) (n2 + n)/2 (e) (n2 – n)/2
1.9 What is the order of complexity for the most efficient algorithm to make a heap, i.e. to convert an array
into a heap?