|
MCQ of CS 502 Fundamentals of Algorithms, fit for final term, mid term and quiz
CS502 Question # 1 of 10 ( Start time: 11:08:19 PM ) Total Marks: 1
Suppose that a graph G = (V,E) is implemented using adjacency lists. What is the complexity of a breadth-first traversal of G?
Select correct option:
O(|V |^2)
O(|V | |E|)
O(|V |^2|E|)
O(|V | + |E|)
CS502 vu.ysapak Question # 2 of 10 ( Start time: 11:09:26 PM ) Total Marks: 1
What is generally true of Adjacency List and Adjacency Matrix representations of graphs?
Select correct option:
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)
Lists require more space than matrices but are faster to find the weight of an edge (v1, v2)
CS502 vu.ysapak Question # 3 of 10 ( Start time: 11:10:06 PM ) Total Marks: 1
What general property of the list indicates that the graph has an isolated vertex?
Select correct option:
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.
CS502 vu.ysapak Question # 4 of 10 ( Start time: 11:11:15 PM ) Total Marks: 1
A dense undirected graph is:
Select correct option:
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
CS502 vu.ysapak Question # 5 of 10 ( Start time: 11:11:59 PM ) Total Marks: 1
In digraph G=(V,E) ;G has cycle if and only if
Select correct option:
The DFS forest has forward edge.
The DFS forest has back edge
The DFS forest has both back and forward edge
BFS forest has forward edge
www.vu.ysapak.net
CS502 vu.ysapak Question # 6 of 10 ( Start time: 11:12:44 PM ) Total Marks: 1
Back edge is:
Select correct option:
(u, v) where v is an ancestor of u in the tree.
(u,v) where u is an ancesstor of v in the tree.
(u, v) where v is an predcessor of u in the tree.
None of above
CS502 vu.ysapak Question # 7 of 10 ( Start time: 11:13:50 PM ) Total Marks: 1
Using ASCII standard the string “abacdaacacwe” will be encoded with __________ bits
Select correct option:
64
128
96
120
CS502 vu.ysapak Question # 8 of 10 ( Start time: 11:14:41 PM ) Total Marks: 1
Cross edge is :
Select correct option:
(u, v) where u and v are not ancestor of one another
(u, v) where u is ancesstor of v and v is not descendent of u.
(u, v) where u and v are not ancestor or descendent of one another
(u, v) where u and v are either ancestor or descendent of one another.
CS502 vu.ysapak Question # 9 of 10 ( Start time: 11:15:22 PM ) Total Marks: 1
Which statement is true?
Select correct option:
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
10 If you find yourself in maze the better traversel approach will bE
www.vu.ysapak.net
CS502 vu.ysapak Question # 1 of 10 ( Start time: 11:22:01 PM ) Total Marks: 1
A dense undirected graph is:
Select correct option:
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
CS502 vu.ysapak Question # 2 of 10 ( Start time: 11:22:21 PM ) Total vu.ysapak Marks: 1
Using ASCII standard the string “abacdaacacwe” will be encoded with __________ bits
Select correct option:
64
128
96
120
CS502 vu.ysapak Question # 3 of 10 ( Start time: 11:22:38 PM ) Total Marks: 1
Which is true statement.
Select correct option:
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.
CS502 vu.ysapak Question # 4 of 10 ( Start time: 11:22:56 PM ) Total Marks: 1
Forward edge is:
Select correct option:
(u, v) where u is a proper descendent of v in the tree.
(u, v) where v is a proper descendent of u in the tree.
(u, v) where v is a proper ancesstor of u in the tree.
(u, v) where u is a proper ancesstor of v in the tree.
CS502 vu.ysapak Question # 5 of 10 ( Start time: 11:23:41 PM ) Total Marks: 1
Back edge is:
Select correct option:
(u, v) where v is an ancestor of u in the tree.
(u,v) where u is an ancesstor of v in the tree.
(u, v) where v is an predcessor of u in the tree.
None of above
CS502 vu.ysapak Question # 6 of 10 ( Start time: 11:24:16 PM ) Total Marks: 1
Suppose that a graph G = (V,E) is implemented using adjacency lists. What is the complexity of a breadth-first traversal of G?
Select correct option:
O(|V |^2)
O(|V | |E|)
O(|V |^2|E|)
O(|V | + |E|)
CS502 vu.ysapak Question # 7 of 10 ( Start time: 11:24:35 PM ) Total Marks: 1
Cross edge is :
Select correct option:
(u, v) where u and v are not ancestor of one another
(u, v) where u is ancesstor of v and v is not descendent of u.
(u, v) where u and v are not ancestor or descendent of one another
(u, v) where u and v are either ancestor or descendent of one another.
www.vu.ysapak.net
CS502 vu.ysapak Question # 8 of 10 ( Start time: 11:25:11 PM ) Total Marks: 1 vu zs
In digraph G=(V,E) ;G has cycle if and only if
Select correct option:
The DFS forest has forward edge.
The DFS forest has back edge
The DFS forest has both back and forward edge
BFS forest has forward edge
CS502 vu.ysapak Question # 9 of 10 ( Start time: 11:25:31 PM ) Total Marks: 1
What is generally true of Adjacency List and Adjacency Matrix representations of graphs?
Select correct option:
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)
Lists require more space than matrices but are faster to find the weight of an edge (v1, v2)
CS502 vu.ysapak Question # 10 of 10 ( Start time: 11:25:52 PM ) Total Marks: 1
What general property of the list indicates that the graph has an isolated vertex?
Select correct option:
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. http://ping.fm/d8ARv
CS502 Question # 1 of 10 ( Start time: 11:08:19 PM ) Total Marks: 1
Suppose that a graph G = (V,E) is implemented using adjacency lists. What is the complexity of a breadth-first traversal of G?
Select correct option:
O(|V |^2)
O(|V | |E|)
O(|V |^2|E|)
O(|V | + |E|)
CS502 vu.ysapak Question # 2 of 10 ( Start time: 11:09:26 PM ) Total Marks: 1
What is generally true of Adjacency List and Adjacency Matrix representations of graphs?
Select correct option:
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)
Lists require more space than matrices but are faster to find the weight of an edge (v1, v2)
CS502 vu.ysapak Question # 3 of 10 ( Start time: 11:10:06 PM ) Total Marks: 1
What general property of the list indicates that the graph has an isolated vertex?
Select correct option:
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.
CS502 vu.ysapak Question # 4 of 10 ( Start time: 11:11:15 PM ) Total Marks: 1
A dense undirected graph is:
Select correct option:
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
CS502 vu.ysapak Question # 5 of 10 ( Start time: 11:11:59 PM ) Total Marks: 1
In digraph G=(V,E) ;G has cycle if and only if
Select correct option:
The DFS forest has forward edge.
The DFS forest has back edge
The DFS forest has both back and forward edge
BFS forest has forward edge
www.vu.ysapak.net
CS502 vu.ysapak Question # 6 of 10 ( Start time: 11:12:44 PM ) Total Marks: 1
Back edge is:
Select correct option:
(u, v) where v is an ancestor of u in the tree.
(u,v) where u is an ancesstor of v in the tree.
(u, v) where v is an predcessor of u in the tree.
None of above
CS502 vu.ysapak Question # 7 of 10 ( Start time: 11:13:50 PM ) Total Marks: 1
Using ASCII standard the string “abacdaacacwe” will be encoded with __________ bits
Select correct option:
64
128
96
120
CS502 vu.ysapak Question # 8 of 10 ( Start time: 11:14:41 PM ) Total Marks: 1
Cross edge is :
Select correct option:
(u, v) where u and v are not ancestor of one another
(u, v) where u is ancesstor of v and v is not descendent of u.
(u, v) where u and v are not ancestor or descendent of one another
(u, v) where u and v are either ancestor or descendent of one another.
CS502 vu.ysapak Question # 9 of 10 ( Start time: 11:15:22 PM ) Total Marks: 1
Which statement is true?
Select correct option:
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
10 If you find yourself in maze the better traversel approach will bE
www.vu.ysapak.net
CS502 vu.ysapak Question # 1 of 10 ( Start time: 11:22:01 PM ) Total Marks: 1
A dense undirected graph is:
Select correct option:
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
CS502 vu.ysapak Question # 2 of 10 ( Start time: 11:22:21 PM ) Total vu.ysapak Marks: 1
Using ASCII standard the string “abacdaacacwe” will be encoded with __________ bits
Select correct option:
64
128
96
120
CS502 vu.ysapak Question # 3 of 10 ( Start time: 11:22:38 PM ) Total Marks: 1
Which is true statement.
Select correct option:
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.
CS502 vu.ysapak Question # 4 of 10 ( Start time: 11:22:56 PM ) Total Marks: 1
Forward edge is:
Select correct option:
(u, v) where u is a proper descendent of v in the tree.
(u, v) where v is a proper descendent of u in the tree.
(u, v) where v is a proper ancesstor of u in the tree.
(u, v) where u is a proper ancesstor of v in the tree.
CS502 vu.ysapak Question # 5 of 10 ( Start time: 11:23:41 PM ) Total Marks: 1
Back edge is:
Select correct option:
(u, v) where v is an ancestor of u in the tree.
(u,v) where u is an ancesstor of v in the tree.
(u, v) where v is an predcessor of u in the tree.
None of above
CS502 vu.ysapak Question # 6 of 10 ( Start time: 11:24:16 PM ) Total Marks: 1
Suppose that a graph G = (V,E) is implemented using adjacency lists. What is the complexity of a breadth-first traversal of G?
Select correct option:
O(|V |^2)
O(|V | |E|)
O(|V |^2|E|)
O(|V | + |E|)
CS502 vu.ysapak Question # 7 of 10 ( Start time: 11:24:35 PM ) Total Marks: 1
Cross edge is :
Select correct option:
(u, v) where u and v are not ancestor of one another
(u, v) where u is ancesstor of v and v is not descendent of u.
(u, v) where u and v are not ancestor or descendent of one another
(u, v) where u and v are either ancestor or descendent of one another.
www.vu.ysapak.net
CS502 vu.ysapak Question # 8 of 10 ( Start time: 11:25:11 PM ) Total Marks: 1 vu zs
In digraph G=(V,E) ;G has cycle if and only if
Select correct option:
The DFS forest has forward edge.
The DFS forest has back edge
The DFS forest has both back and forward edge
BFS forest has forward edge
CS502 vu.ysapak Question # 9 of 10 ( Start time: 11:25:31 PM ) Total Marks: 1
What is generally true of Adjacency List and Adjacency Matrix representations of graphs?
Select correct option:
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)
Lists require more space than matrices but are faster to find the weight of an edge (v1, v2)
CS502 vu.ysapak Question # 10 of 10 ( Start time: 11:25:52 PM ) Total Marks: 1
What general property of the list indicates that the graph has an isolated vertex?
Select correct option:
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. http://ping.fm/d8ARv