The searching algorithm of ordered array is faster than regular array, but the insertion time is slower than regular array.

True

False

In a weighted graph, the minimum spanning tree (MST) tries to minimize the number of edges connecting all the vertices.

True

False

Greedy algorithm always yields the optimal solution.

True

False

The last node in a heap is always on the bottom row.

True

False

The depth-first search algorithm can be based on a queue; the breadth-first search algorithm can be based on a stack.

True

False

In many situations the array is the first kind of structure you should consider when storing and manipulating data, especially the amount of data is reasonably small.

True

False

Backtracking algorithms are based on breadth-first recursive search.

True

False

Stack is one of general-purpose data structures.

True

False

A topological sort can be carried out only on a DAG, a directed acyclic (no cycles) graph.

True

False

The minimum spanning tree of an undirected graph G exists if and only if G is connected.

True

False

The directed graph: V={V0,V1, V2,V3,V4,V5,V6}. There are the following twelve edges, with edge costs listed as the third item in the triplet: E={ (V0,V2,4), (V1,V0,2), (V1,V3,3), (V3,V0,1), (V3,V2,2), (V3,V5,8), (V3,V6,4), (V4,V1,10), (V4,V3,2), (V4,V6,7), (V5,V2,2), (V6,V5,1)}.
If the above graph were undirected, then what would be the cost of its minimum spanning tree?

A. / 9
B. / 10
C. / 11
D. / 12

Which of the following algorithm solves the unweighted single source shortest path problem?

A. / breadth first search
B. / depth first search
C. / Kruskal’s algorithm
D. / Prim’s algorithm

Which of the following algorithm is NOT using divide-and-conquer?

A. / Merge sort
B. / Heap sort
C. / Quick sort
D. / Binary search

Using divide-and-conquer technique if we know X, what is the minimal number of multiplications we need to compute X^40 ? (Hint: X^N=X^(N/2)* X^(N/2) is one multiplication, ^ is used for the exponential computation)

A. / 5
B. / 6
C. / 7
D. / 8

The directed graph: V={V0,V1, V2,V3,V4,V5,V6}. There are the following twelve edges, with edge costs listed as the third item in the triplet: E={ (V0,V2,4), (V1,V0,2), (V1,V3,3), (V3,V0,1), (V3,V2,2), (V3,V5,8), (V3,V6,4), (V4,V1,10), (V4,V3,2), (V4,V6,7), (V5,V2,2), (V6,V5,1)}.
The shortest weighted path from V4 to V5 has weight

A. / 2
B. / 4
C. / 7
D. / 8

Dijkstra’s algorithm finds the shortest path

A. / from one specified vertex to all other vertices
B. / from one specified vertex to another specified vertex
C. / from all vertices to all other vertices that can be reach along one edge
D. / from all vertices to all other vertices that can be reach along multiple edges.

i is the event number, s(i) is the start time for event i, f(i) is the finish time.
The Maximum-size mutually compatible set size is

A.

3

B.

4

C.

5

D.

6

6, 8, 4, 3, and 1 are inserted into a data structure in that order. An item is deleted using only a basic data structure operation. If the deleted item is 1, the data structure CANNOT be a

A. / Hash Table
B. / stack
C. / queue
D. / search tree

i is the event number, s(i) is the start time for event i, f(i) is the finish time.
Which set is NOT a Maximum-size mutually compatible set?

A. / {1, 2, 4, 7}
B. / {1, 2, 4, 8}
C. / {1, 2, 6, 8}
D. / {1, 2, 6, 9}

The directed graph: V={V0,V1, V2,V3,V4,V5,V6}. There are the following twelve edges, with edge costs listed as the third item in the triplet: E={ (V0,V2,4), (V1,V0,2), (V1,V3,3), (V3,V0,1), (V3,V2,2), (V3,V5,8), (V3,V6,4), (V4,V1,10), (V4,V3,2), (V4,V6,7), (V5,V2,2), (V6,V5,1)}.
If the start vertex is V4, then using the depth-first-search, which is the last vertex to be marked (visited)?

A. / V2
B. / V3
C. / V5
D. / V6

Suppose we are implementing double hashing with a hash function Hash(X)=X mod 10. If an element with key 94 is inserted and the position already occupied, then the next cell (the index number) that will be tried by with second hash function h2(x)=7-(x mod 7) is

A. / 5
B. / 6
C. / 8
D. / 9

If an undirected graph has an adjacency list as following: {{A: B->C->D}, {B: A->D}, {C: A}, {D: A->B}}, what is NOT correct for the following statements?

A. / The graph is connected
B. / The graph is acyclic (no cycles).
C. / Nodes A, C are adjacent
D. / There is a path from node B to node C

i is the event number, s(i) is the start time for event i, f(i) is the finish time.
Which set is the result of Greedy-Activity-Selector algorithm?

A.

{1, 2, 4, 7}

B.

{1, 2, 4, 8}

C.

{1, 2, 6, 8}

D.

{1, 2, 6, 9}

For making change problem, you have a set of coins in {100, 25, 10, 5, 1}, which is the first one you select for the amount of 65 using Greedy algorithm?

A. / 100
B. / 25
C. / 10
D. / 1

If constructing a binary search tree using the inserting sequence {4, 1, 8, 9, 6, 3, 2, 7}, which element will be the new root after the remove() operation?

A. / 3
B. / 6
C. / 7
D. / 8

When the amount of storage data is big, and we need the searching and insertion must be very fast, which kind of data structure we should consider?

A. / Array
B. / Linked list
C. / Hash Table
D. / Binary Search Tree

If constructing a binary search tree using the inserting sequence {4, 1, 8, 9, 6, 3, 2, 7}, where 7 goes?

A. / Right subtree of 2.
B. / Left subtree of 9
C. / Right subtree of 6
D. / Left subtree of 8

Sample space S={1,2,3,4,5,6}. A is the event “the dice number is 3” and B is the event “the dice produces an odd number”, so Pr[B]=0.5, Pr[A|B]

A. / 1/6
B. / 1/3
C. / 1/2
D. / 1

Which data structure has the worst case for searching O(log N), insertion O(log N), and deletion O(log N)?

A. / Array
B. / Linked List
C. / Binary Tree
D. / Balanced Tree

Which is NOT a feature of Dynamic Programming?

A. / Dynamic programming is used to avoid calculating the same thing twice
B. / Dynamic programming solves problem bottom-up
C. / Dynamic programming doesn’t really refer to “computer programming”
D. / Dynamic programming is one method of divide-and-conquer, solve problem by combining the solutions to subproblems.

Which of the following sequence is a max-heap?

A. / {23, 17, 10, 7, 9, 4, 6}
B. / {23, 7, 10, 17, 9, 4, 6}
C. / {23, 17, 6, 7, 9, 10, 6}
D. / {23, 10, 7, 17, 9, 4, 6}

The directed graph: V={V0,V1, V2,V3,V4,V5,V6}. There are the following twelve edges, with edge costs listed as the third item in the triplet: E={ (V0,V2,4), (V1,V0,2), (V1,V3,3), (V3,V0,1), (V3,V2,2), (V3,V5,8), (V3,V6,4), (V4,V1,10), (V4,V3,2), (V4,V6,7), (V5,V2,2), (V6,V5,1)}.
If the start vertex is V4, then using the standard weighted shortest path algorithm (Dijkstra), which is the last vertex to be declared known?

A. / V0
B. / V1
C. / V2
D. / V4