Quantitative Methods Answers

60. Consider the following possible data structures for a set of n distinct integers.
I. A min-heap
II. An array of length n sorted in increasing order
III. A balanced binary search tree
For which of these data structures is the number of steps needed to find and remove the 7th largest element
O n (log ) in the worst case?
(A) I only (B) II only (C) I and II (D) I and III (E) II and III

Which of the following problems can be solved by a standard greedy algorithm?
I. Finding a minimum spanning tree in an undirected graph with positive-integer edge weights
II. Finding a maximum clique in an undirected graph
III. Finding a maximum flow from a source node to a sink node in a directed graph with positive-integer edge
capacities
(A) I only (B) II only (C) III only (D) I and II only (E) I, II, and III

Consider the following grammar.
S → ( S )
S → x
Which of the following statements is (are) true?
I. The grammar is ambiguous.
II. The grammar is suitable for top-down parsing.
III. The grammar is suitable for bottom-up parsing.
(A) I only (B) II only (C) III only (D) II and III only (E) I, II, and III

Mergesort works by splitting a list of n numbers in half, sorting each half recursively, and merging
the two halves. Which of the following data structures will allow mergesort to work in O n n ( ) log time?
I. A singly linked list
II. A doubly linked list
III. An array
(A) None (B) III only (C) I and II only (D) II and III only (E) I, II, and III

A k-ary tree is a tree in which every node has at most k children. In a k-ary tree with n nodes and height h,which of the following is an upper bound for the maximum number of leaves as a function of h, k,and n ?
(A) logk n
(B) logk h
(C)n/(logk n)
(D) h^k
(E)k^h

4. Which of the following is the name of the data structure in a compiler that is responsible for managing
information about variables and their attributes?
(A) Abstract Syntax Tree (AST)
(B) Attribute Grammar
(C) Symbol Table
(D) Semantic Stack
(E) Parse Table

Which of the following algorithms has running time Q(n2) in the worst case but Q( n log n)on average? (A) Bubblesort (B) Mergesort (C) Heapsort (D) Quicksort (E) Tournament sort

Both's algorithm for integer multiplication gives worst performance when the multiplier pattern is

A)101010 ..... 1010

B)100000 ..... 0001

C)111111 ..... 1111

D)011111 ...... 1110

What is the number of vertices in an undirected connected graph with 27 edges, 6 vertices of degree 2, 3 vertices of degree 4 and remaining of degree 3?

A)10

B)11

C)18

D)19