|
CS502 Principals of Algorithm, Solved-Unsolved MCQ's for Final, Mid and Quizes
1: What is the time complexity to extract a vertex from the priority queue in Prim’s algorithm?
• log (v)
• v.v
• e.e
• log(e)
2: Which statement is true?
• If a dynamic-programming problem satisfies the optimal-substructure property, then a locally optimal solution is globally optimal.
• If a greedy choice property satisfies the optimal-substructure property, then a locally optimal solution is globally optimal.
• both of above
• none of above
3: Kruskal's algorithm (choose best non-cycle edge) is better than Prim's (choose best tree edge) when the graph has relatively few edges.
• True
• False
4: You have an adjacency list for G, what is the time complexity to compute Graph transpose G^T ?
• V+e
• v.e
• v
• e
5: What general property of the list indicates that the graph has an isolated vertex?
• There is Null pointer at the end of list.
• The Isolated vertex is not handled in list.
• Only one value is entered in the list.
• There is at least one null list.
6: Which is true statement.
• Breadth first search is shortest path algorithm that works on un-weighted graphs.
• Depth first search is shortest path algorithm that works on un-weighted graphs.
• Both of above are true.
• None of above are true.
7: A dense undirected graph is:
• A graph in which E = O(V^2)
• A graph in which E = O(V)
• A graph in which E = O(log V)
• All items above may be used to characterize a dense undirected graph.
8: What is generally true of Adjacency List and Adjacency Matrix representations of graphs?
• Lists require less space than matrices but take longer to find the weight of an edge (v1,v2)
• Lists require less space than matrices and they are faster to find the weight of an edge (v1, v2)
• Lists require more space than matrices and they take longer to find the weight of an edge (v1, v2).
9: Suppose that a graph G = (V,E) is implemented using adjacency lists. What is the complexity of a breadth-first traversal of G?
• O(|V |^2)
• O(|V | |E|)
• O(|V |^2|E|)
• O(|V | + |E|)
10: The relationship between number of back edges and number of cycles in DFS is,
• Both are equal
• Back edges are half of cycles
• Back edges are one quarter of cycles
• There is no relationship between no. of edges and cycles
11: Using ASCII standard the string “abacdaacacwe” will be encoded with __________ bits
• 64
• 128
• 96
• 120
12: What is the time complexity to extract a vertex from the priority queue in Prim’s algorithm?
• log (V)
• v.v
• e.e
• log
13: the analysis of selection algorithm shows the total running time is indeed------------in n.
• arithmetic
• geometric
• linear
• orthogonal
14: back edge is
(1) In Prim’s algorithm, the additional information maintained by the algorithm is the length of the shortest edge from vertex v to points already in the tree.
A) TRUE
B) FALSE
C) UNKNOWN
(2) Although it requires more complicated data structures, Prim's algorithm for a
minimum spanning tree is better than Kruskal's when the graph has a large number of
vertices.
A) TRUE.
B) FALSE
C: UNKNOWN
(3) If a problem is NP-complete, it must also be in NP.
A) TRUE.
B) FALSE
C) UNKNOWN
(4) What is the worst-case runtime complexity of the following C function
int function(int n){
int i, j, k;
k = n;
for(i=-100; i<10*log(n);i++){
k = k/2;
} for(j=i; j> n; j--){
k=j/2;
}r
return k;
}
What order is the execution of this code
a) O(log n)
b) O(n)
c) O(n log n)
d) O(n2)
e) O(n2 log n)
(4) Which statement is true
(I) The running time of Bellman-Ford algorithm is T (VE)
(II) Both Dijkstra’s algorithm and Bellman-Ford are based on performing repeated relaxations
(III) The 0-1 knapsack problem is hard to solve
• Only I
• Only III
• Both I and III
• All of these
5) Which of the following arrays represent descending (max) heaps?
I. [10,7,7,2,4,6]
II. [10,7,6,2,4,7]
III. [10,6,7,2,4,6]
IV. [6,6,7,2,4,10]
• Only II
• Only IV
• Both II and IV
• Both I and III
6. Which of the following statement(s) is/are correct?
(a) O(n log n + n2) = O(n2).
(b) O(n log n + n2) = O(n2 log 2n)
(c) O(c n2) = O(n2) where c is a constant.
(d) O(c n2) = O(c) where c is a constant.
(e) O(c) = O(1) where c is a constant.
• Only (a) & (e)
• Both (c) and (e)
7. Which of the shortest path algorithms would be most appropriate for finding paths in the graph with negative edge weights and cycles?
I.Dijkstra’s Algorithm
II. Bellman-Ford Algorithm
III. Floyd Warshall Algorithm
• Only II
• Only III
• Both II & III
8. Which of the following orders is not a possible order in which Depth First Search can visit the vertices of the directed graph shown below?
• ABCEFD
• ACEBFD
• ADFEBC
• ADFBCE
• ABFECD
9. Suppose we have two problems A and B .Problem A is polynomial-time reducible and problem B is NP-complete. If we reduce problem A into B then problem A becomes NP-complete
• Yes
• No
10. How can the number of strongly connected components of a graph change if a new edge is added?
• The number of strongly connected components can be increased.
• The number of strongly connected components can be reduced.
• No change will occur.
• None of these.
11. The recurrence relation of Tower of Hanoi is given below
? 1 if n =1
T n =?
-133( )
2 (T n- +1) 1if n>1
In order to move a tower of 6 rings from one peg to another, how many moves are
required?
• 15
• 7
• 63
• 32
12. Edge (u, v) is a forward edge if
• u is a proper descendant of v in the tree
• v is a proper descendant of u in the tree
• None of these
13. Is 22n= O?
2n -26? ?
• Yes it is possible
• No it is not possible
• None of these
14. If, in a DFS forest of digraph G = (V, E), f = f[v] for an edge (u, v) ? E then the edge is called
• Back edge
• Forward edge
• Cross Edge
• Tree Edge
• None of these
15. How can the number of strongly connected components of a graph change if a new edge is added?
• The number of strongly connected components can be increased.
• The number of strongly connected components can be reduced.
• No change will occur.
• None of these. http://ping.fm/w54D6
1: What is the time complexity to extract a vertex from the priority queue in Prim’s algorithm?
• log (v)
• v.v
• e.e
• log(e)
2: Which statement is true?
• If a dynamic-programming problem satisfies the optimal-substructure property, then a locally optimal solution is globally optimal.
• If a greedy choice property satisfies the optimal-substructure property, then a locally optimal solution is globally optimal.
• both of above
• none of above
3: Kruskal's algorithm (choose best non-cycle edge) is better than Prim's (choose best tree edge) when the graph has relatively few edges.
• True
• False
4: You have an adjacency list for G, what is the time complexity to compute Graph transpose G^T ?
• V+e
• v.e
• v
• e
5: What general property of the list indicates that the graph has an isolated vertex?
• There is Null pointer at the end of list.
• The Isolated vertex is not handled in list.
• Only one value is entered in the list.
• There is at least one null list.
6: Which is true statement.
• Breadth first search is shortest path algorithm that works on un-weighted graphs.
• Depth first search is shortest path algorithm that works on un-weighted graphs.
• Both of above are true.
• None of above are true.
7: A dense undirected graph is:
• A graph in which E = O(V^2)
• A graph in which E = O(V)
• A graph in which E = O(log V)
• All items above may be used to characterize a dense undirected graph.
8: What is generally true of Adjacency List and Adjacency Matrix representations of graphs?
• Lists require less space than matrices but take longer to find the weight of an edge (v1,v2)
• Lists require less space than matrices and they are faster to find the weight of an edge (v1, v2)
• Lists require more space than matrices and they take longer to find the weight of an edge (v1, v2).
9: Suppose that a graph G = (V,E) is implemented using adjacency lists. What is the complexity of a breadth-first traversal of G?
• O(|V |^2)
• O(|V | |E|)
• O(|V |^2|E|)
• O(|V | + |E|)
10: The relationship between number of back edges and number of cycles in DFS is,
• Both are equal
• Back edges are half of cycles
• Back edges are one quarter of cycles
• There is no relationship between no. of edges and cycles
11: Using ASCII standard the string “abacdaacacwe” will be encoded with __________ bits
• 64
• 128
• 96
• 120
12: What is the time complexity to extract a vertex from the priority queue in Prim’s algorithm?
• log (V)
• v.v
• e.e
• log
13: the analysis of selection algorithm shows the total running time is indeed------------in n.
• arithmetic
• geometric
• linear
• orthogonal
14: back edge is
(1) In Prim’s algorithm, the additional information maintained by the algorithm is the length of the shortest edge from vertex v to points already in the tree.
A) TRUE
B) FALSE
C) UNKNOWN
(2) Although it requires more complicated data structures, Prim's algorithm for a
minimum spanning tree is better than Kruskal's when the graph has a large number of
vertices.
A) TRUE.
B) FALSE
C: UNKNOWN
(3) If a problem is NP-complete, it must also be in NP.
A) TRUE.
B) FALSE
C) UNKNOWN
(4) What is the worst-case runtime complexity of the following C function
int function(int n){
int i, j, k;
k = n;
for(i=-100; i<10*log(n);i++){
k = k/2;
} for(j=i; j> n; j--){
k=j/2;
}r
return k;
}
What order is the execution of this code
a) O(log n)
b) O(n)
c) O(n log n)
d) O(n2)
e) O(n2 log n)
(4) Which statement is true
(I) The running time of Bellman-Ford algorithm is T (VE)
(II) Both Dijkstra’s algorithm and Bellman-Ford are based on performing repeated relaxations
(III) The 0-1 knapsack problem is hard to solve
• Only I
• Only III
• Both I and III
• All of these
5) Which of the following arrays represent descending (max) heaps?
I. [10,7,7,2,4,6]
II. [10,7,6,2,4,7]
III. [10,6,7,2,4,6]
IV. [6,6,7,2,4,10]
• Only II
• Only IV
• Both II and IV
• Both I and III
6. Which of the following statement(s) is/are correct?
(a) O(n log n + n2) = O(n2).
(b) O(n log n + n2) = O(n2 log 2n)
(c) O(c n2) = O(n2) where c is a constant.
(d) O(c n2) = O(c) where c is a constant.
(e) O(c) = O(1) where c is a constant.
• Only (a) & (e)
• Both (c) and (e)
7. Which of the shortest path algorithms would be most appropriate for finding paths in the graph with negative edge weights and cycles?
I.Dijkstra’s Algorithm
II. Bellman-Ford Algorithm
III. Floyd Warshall Algorithm
• Only II
• Only III
• Both II & III
8. Which of the following orders is not a possible order in which Depth First Search can visit the vertices of the directed graph shown below?
• ABCEFD
• ACEBFD
• ADFEBC
• ADFBCE
• ABFECD
9. Suppose we have two problems A and B .Problem A is polynomial-time reducible and problem B is NP-complete. If we reduce problem A into B then problem A becomes NP-complete
• Yes
• No
10. How can the number of strongly connected components of a graph change if a new edge is added?
• The number of strongly connected components can be increased.
• The number of strongly connected components can be reduced.
• No change will occur.
• None of these.
11. The recurrence relation of Tower of Hanoi is given below
? 1 if n =1
T n =?
-133( )
2 (T n- +1) 1if n>1
In order to move a tower of 6 rings from one peg to another, how many moves are
required?
• 15
• 7
• 63
• 32
12. Edge (u, v) is a forward edge if
• u is a proper descendant of v in the tree
• v is a proper descendant of u in the tree
• None of these
13. Is 22n= O?
2n -26? ?
• Yes it is possible
• No it is not possible
• None of these
14. If, in a DFS forest of digraph G = (V, E), f = f[v] for an edge (u, v) ? E then the edge is called
• Back edge
• Forward edge
• Cross Edge
• Tree Edge
• None of these
15. How can the number of strongly connected components of a graph change if a new edge is added?
• The number of strongly connected components can be increased.
• The number of strongly connected components can be reduced.
• No change will occur.
• None of these. http://ping.fm/w54D6