Data Structures and Algorithms Design (SSZG519) Quiz 3
MTech Software Systems- BITS-PILANI-WILP - 2016
1. Dijkstra's algorithm is a
Select one:
a. Brute force algorithm
b. Greedy algorithm
c. Divide and Conquer algorithm
d. Dynamic Programming algorithm
e. None of the above
Ans: b. Greedy algorithm
2. Consider the experiment of tossing a coin until a head appears. The number of elements in the sample space is
Select one:
a. 0
b. None of the above
c. 1
d. 4
e. 2
Ans: e. 2
3. Prim's algorithm is a
Select one:
a. None of the above
b. Dynamic Programming algorithm
c. Greedy algorithm
d. Brute force algorithm
e. Divide and Conquer algorithm
Ans: c. Greedy algorithm
4. Merge sort is
Select one:
a. None of the above
b. Greedy algorithm
c. Divide and Conquer algorithm
d. Dynamic programming algorithm .
e. Brute force algorithm.
Ans: c. Divide and Conquer algorithm
5. Consider the interval scheduling problem. The triple (i,s,f) denotes the task i with starting time s and finishing time f. Each of the tasks has to use a resource but no two tasks can be accommodated simultaneously. We have to accommodate maximum number of tasks. Consider the following instance of the problem. {(1,2,4), (2,1,3),(3,4,6), (4,5,6)}. Which of the following is true?
Select one:
a. None of the above
b. Tasks 1 and 2 are in conflict
c. Tasks 2 and 3 are in conflict
d. Tasks 1 and 4 are in conflict
e. Tasks 2 and 4 are in conflict
Ans: b. Tasks 1 and 2 are in conflict
6. If a graph G with n vertices and m edges is represented using Adjacency list, then running time of Prim's algorithm is
Select one:
a. O(m2)
b. O(nlogn)
c. O(mlogn)
d. O(n2)
e. None of the above
Ans: c. O(mlogn)
7. Let G be a simple undirected graph with n vertices. Then number of edges in G is
Select one:
a. None of the above
b. at least n(n-1)/2
c. at most n
d. at least n
e. at most n(n-1)/2
Ans: e. at most n(n-1)/2
8. Let A be an adjacency matrix of an undirected graph in G. Then sum of all entries in the matrix is equal to
Select one:
a. Number of vertices in G
b. Twice the number of edges in G
c. Twice the number of vertices in G
d. Number of edges in G
e. None of the above
Ans: b. Twice the number of edges in G
9. Average case running time for quick sort is
Select one:
a. O(n2)O(n2)
b. O(nlogn)
c. O(nloglogn)
d. None of the above
e. O(n)
Ans: b. O(nlogn)
10. Running time of Depth First Search algorithm on a graph with n vertices and m edges is
Select one:
a. O(mn)
b. O(m)
c. O(m+n)
d. None of the above
e. O(n)
Ans: c. O(m+n)
11. Consider the interval scheduling problem. The triple (i,s,f) denotes the task i with starting time s and finishing time f. Each of the tasks has to use a resource but no two tasks can be accommodated simultaneously. We have to accommodate maximum number of tasks. Consider the following instance of the problem. {(1,2,4), (2,1,3),(3,4,10), (4,5,6), (5,7,10)}. Suppose we use a greedy strategy: Choose a task with the minimum starting time. The solution, number of tasks, given by greedy algorithm is
Select one:
a. 3
b. 1
c. None of the above
d. 2
e. 4
Ans: d. 2
12. Let T be a tree with m edges. Then the number of vertices in T is
Select one:
a. exactly m-1
b. exactly m
c. None of the above
d. exactly m+1
e. at most m
Ans: a. exactly m-1
13. Worst case running time for merge sort is
Select one:
a. O(nloglogn)
b. O(nlogn)
c. None of the above
d. O(n)
e. O(n2)
Ans: b. O(nlogn)
14. Total number of comparisons needed for merge(L1,L2) where L1 is 2,4,6,8 and L2 is 10, 12, 13,15, 17
Select one:
a. 4
b. 9
c. 5
d. None of the above
e. 8
Ans: e. 8
15. Consider the instance of coin changing problem. We have infinite supply of each of 1,2,5,25 valued coins and we want to make change for 70 cents using minimum number of coins. The optimum solution is
Select one:
a. 6
b. 14
c. 1
d. 70
e. None of the above
Ans:
16. Consider the following statement about DFS.
i) At the end of DFS algorithm, each edge will be labelled as either discovery edge or back edge
ii) Discovery edges will form a spanning tree of the graph.
Select one:
a. ii only
b. i only
c. None of them is true
d. None of the above
e. Both of them are true
Ans:
17. Which of the following statements is correct.
i) Any comparison based algorithm must perform Ω(nlogn) comparisons to sort n elements in the worst case
ii. Any comparison based algorithm must perform Ω(nlogn) comparisons to sort n elements in the best case
Select one:
a. None of the above
b. only i is true
c. none of them is true
d. both of them are true
e. only ii is true
Ans:
18. Suppose the input to Quick sort is 1,2,...17. What would be the best pivot element during the first invocation?
Select one:
a. None of the above
b. 8
c. 17
d. 1
e. 9
Ans:
19. The running time of quick sort depends heavily on the selection of:
Select one:
a. Arrangement of elements in the array
b. None of the above
c. Size of elements
d. Pivot element
e. Number of inputs
Ans: d. Pivot element
20. Suppose an undirected graph, which has n vertices and d maximum degree, is represented using adjacency list. The running time to find the degree of a given vertex is
Select one:
a. O(logn)
b. O(d)
c. O(1)
d. O(n)
e. None of the above
Ans:
21. The space complexity to represent a graph with n vertices and m edges using adjacency matrix is
Select one:
a. None of the above
b. O(nlogn)
c. O(n^2)
d. O(n)
e. O(n+m)
Ans: c. O(n^2)
22. Consider the problem of sorting a sequence in ascending order. If the input is already in ascending order, which of the following sorting procedure is most efficient.
Select one:
a. None of the above
b. Merge sort
c. Quick sort
d. Heap sort
e. Insertion sort
Ans: e. Insertion sort
23. Suppose a directed graph is represented using adjacency list. The running time to calculate indegree of a vertex is
Select one:
a. O(d)
b. None of the above
c. O(n)
d. O(m+n)
e. O(logn)
Ans:
24. Consider the instance of coin changing problem. We have infinite supply of each of 1, 10, 25 valued coins and we want to make change for 30 cents using minimum number of coins. The optimum solution is
Select one:
a. None of the above
b. 6
c. 3
d. 30
e. 1
Ans: c. 3
25. Consider the interval scheduling problem. The triple (i,s,f) denotes the task i with starting time s and finishing time f. Each of the tasks has to use a resource but no two tasks can be accommodated simultaneously. We have to accommodate maximum number of tasks. {(1,2,4), (2,1,3),(3,4,10), (4,5,6), (5,7,10)}. Suppose we use a greedy strategy: Choose the task with smallest interval (difference in starting time and finishing time). The solution, number of tasks, given by greedy algorithm is
Select one:
a. None of the above
b. 1
c. 3
d. 2
e. 4
Ans: b. 1
26. Consider the experiment of tossing a coin until k heads appears. Then expected number of tosses is
Select one:
a. None of the above
b. k
c. 2
d. 2k
e. 1
Ans:
27. Consider the interval scheduling problem. The triple (i,s,f) denotes the task i with starting time s and finishing time f. Each of the tasks has to use a resource but no two tasks can be accommodated simultaneously. We have to accommodate maximum number of tasks. Consider the following instance of the problem. {(1,2,4), (2,1,3),(3,4,6), (4,5,6)}. Which of the following taskset is optimal?
Select one:
a. {1,4}
b. {1}
c. {1,2,3,4}
d. {1,2}
e. None of the above
Ans:
28. Consider the instance of coin changing problem. We have infinite supply of each of 1, 10, 25 valued coins and we want to make change for 30 cents using minimum number of coins. Suppose we use the greedy strategy: Choose a largest coin less than or equal to the remaining sum. The solution given by greedy algorithm is
Select one:
a. 3
b. 6
c. 30
d. None of the above
e. 1
Ans: b. 6
29. If a graph G with n vertices and m edges is represented using Adjacency matrix, then running time of Prim's algorithm is
Select one:
a. $O(m^2)$
b. O(mlogn)
c. $O(n^2)$
d. None of the above
Ans: b. O(mlogn)
30. Worst case running time for quick sort is
Select one:
a. O(nloglogn)
b. O(n^2)
c. O(n)
d. None of the above
e. O(nlogn)
Ans: b. O(n^2)
No comments:
Post a Comment