Data Structures and Algorithms Design (SSZG519)
Comprehensive Examination - Make up Question Paper 2016
MTech Software Systems- BITS WILP
Showing posts with label DSA. Show all posts
Showing posts with label DSA. Show all posts
Data Structures and Algorithms Design Mid-Semester Examination - Regular Question Paper 2016 MTech Software Systems- BITS WILP
Data Structures and Algorithms Design (SSZG519)
Mid-Semester Examination - Regular Question Paper 2016
MTech Software Systems- BITS WILP
Data Structures and Algorithms Quiz 3- MTech Software Systems- BITS-PILANI-WILP - 2016
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)
Data Structures and Algorithms Design - Comprehensive Examination - Regular Question Paper 2016 MTech Software Systems- BITS WILP
Data Structures and Algorithms Design (SSZG519)
Comprehensive Examination - Regular Question Paper 2016
MTech Software Systems- BITS WILP
BITS PILANI WILP - M Tec Software Systems - Data Structures and Algorithms Design Mid-Semester Regular Test Question Paper 2016 - 2017
SS ZG519: Data Structures and Algorithms Design
Mid-Semester Test (Regular) -2016 - 2017
MTech Software Systems- WILP(Work Integrated Learning Programmes)
Birla Institute of Technology and Science,
Data Structures and Algorithms Design (SSZG519) Comprehensive Examination - Regular Question Paper 2015-2016 MTech Software Systems- BITS WILP
Data Structures and Algorithms Design (SSZG519)
Comprehensive Examination - Regular Question Paper 2015-2016
MTech Software Systems- BITS WILP
Data Structures and Algorithms Design (SSZG519)- Quiz-2-MTech Software Systems- BITS Pilani-WILP
Data Structures and Algorithms Design (SSZG519)- Quiz- 2
MTech Software Systems- WILP(Work Integrated Learning Programmes)
Birla Institute of Technology and Science, Pilani
1. Consider the following statements.
i) External nodes of heap does not store any keys or elements
ii) Insertion and deletion in heap can be done in O(logn) time
iii) Min can be found in constant time.
Select one:
a. None of the above
b. i, ii are true and iii is false
c. i is true and ii, iii are false
d. All of them are true
e. All of them are false
Ans: d. All of them are true
2. Which of the sorting algorithm has same running time for every input of size n?
Select one:
a. Heap sort
b. Insertion Sort
c. Selection Sort
d. None of the above
Ans: c. Selection Sort
3. What is the best case running time for heap sort?
Select one:
a. O(n log n)
b. O(n)
c. None of the above
d. O(log n)
e. O(n²)
Ans: a. O(n log n)
4. Which of the following has more than O(n) space requirement where n is the number of items stored.
Select one:
a. Direct Address Table
b. Look-up Table
c. None of the above
d. Binary Search Tree
e. Log File
Ans: a. Direct Address Table
5. Which of the following statements are true?
i. In linear probing method, there are only m different probe sequences are possible.
ii. In quadratic probing method, there are m^2 different probe sequences are possible
iii. In double hashing, there are only m different probe sequences are possible.
Select one:
a. None of the above
b. All of them are true
c. i is true and ii, iii are false
d. All of them are false
e. i, ii are true and iii is false
Ans: e. i, ii are true and iii is false
6. A binary search tree has n internal nodes. The number of external nodes is at most
Select one:
a. n
b. n+1
c. None of these
d. 2n
e. log n
Ans: d. 2n
7. Let T be a binary search tree built by receiving keys 3, 5, 10, 4, 8, 12, 2, 9. The in-order traversal of T is
Select one:
a. Any random order of 3, 5, 10, 4, 8, 12, 2, 9
b. 2, 3, 4, 5, 8, 9, 10, 12
c. 12, 10, 9, 8, 5, 4, 3, 2
d. None of the above
e. 3, 5, 10, 4, 8, 12, 2, 9
Ans: b. 2, 3, 4, 5, 8, 9, 10, 12
8. The worst case running time to find a maximum element in Binary search tree with n items is
Select one:
a. O(1)
b. O(n2)
c. None of the above
d. O(n)
e. O(logn)
Ans: d. O(n)
9. Which of the following have O(1) running time for insert operation.
Select one:
a. Binary Search Tree, Look-up Table
b. Look-up Table, Hash Table
c. Hash Table, Binary Search Tree
d. Log File, Hash Table
e. None of the above
Ans: d. Log File, Hash Table
10. Keys { 200,205,210,...,600} are stored in a chained hash table.
Let h(k) = k mod 101, alpha be the load factor, and v be the maximum number of keys stored in a single slot. Which of the following is true?
Select one:
a. alpha > 1
b. alpha >v
c. None of the above
d. alpha =v
e. alpha < v
Ans: e. alpha < v
11. Assume the keys are inserted in the following order. 1055, 1492, 1776, 1812, 1918, 1945.
1945 is stored in the slot ________ if linear probing policy is used and h(k) =5*x mod 8 is the auxiliary hash function.
Select one:
a. 0
b. 6
c. None of the above
d. 7
e. 5
Ans: d. 7
12. Keys "63, 73, 43, 98, 110" are stored in a direct address table.
"43" will be stored in the slot ____________
Select one:
a. 43
b. 44
c. None of the above
d. 3
e. 0
Ans: a. 43
13. Let m is the size of the hash table and n is the number of elements in the hash table. Simple uniform hashing is impossible if
Select one:
a. n>m
b. n=2m
c. n<m
d. n=m
e. None of the above
Ans: c. n<m
14. When using linear probing policy, the probability of an empty slot gets filled if it is preceded by i full slots.
Select one:
a. 1/m
b. (i+1)/m
c. None of the above
d. (i+1)/n
e. 1/n
Ans: b. (i+1)/m
15. Keys "63, 73, 43, 98, 110" are stored in a direct address table
What is the minimum size of the table?
Select one:
a. None of the above
b. 111
c. 109
d. 4
e. 5
Ans: b. 111
16. Which of the following input sequence stores the items { 1,2,3,4,5,6,7} in a size-balanced binary search tree (that is for every node v the number of nodes in the left subtree of v is same as the number of nodes in right subtree of v)
Select one:
a. 1,2,3,4,5,6,7
b. None of the above
c. 4,2,1,3,6,5,7
d. 4,3,1,2,7,5,6
e. 7,6,5,4,3,2,1
Ans: c. 4,2,1,3,6,5,7
17. Keys { 200,205,210,...,600} are stored in a chained hash table.
Suppose h(k) = k mod 100 is used, which slot will have maximum number of keys?
Select one:
a. 200
b. None of the above
c. 100
d. 99
e. 0
Ans: e. 0
18. Assume the keys are inserted in the following order. 1055, 1492, 1776, 1812, 1918, 1945.
Find the the total number of key comparisons if linear probing policy is used and h(k) = 5*x mod 8 is the auxiliary hash function.
Select one:
a. 6
b. 9
c. None of the above
d. 7
e. 4
Ans: b. 9
19. Assume the keys are inserted in the following order. 1055, 1492, 1776, 1812, 1918, 1945.
1812 is stored in the slot ___________ if double hashing policy is used with h_1(k) = 5*x mod 8 and h_2(x) = 1+ (k mod 7).
Select one:
a. 7
b. 4
c. 3
d. 1
e. None of the above
Ans: c. 3
20. Suppose a simple uniform hashing function is used with chaining. The expected number of key comparisons in successful search is at most __________
Select one:
a. None of the above
b. alpha
c. 1+ alpha/2 - alpha/(2n)
d. 1
e. 1+alpha
Ans: c. 1+ alpha/2 - alpha/(2n)
Data Structures and Algorithms Design - Mid-Semester - Regular Question Paper 2014-2015 MTEC- Software System - BITS -WILP
Data Structures and Algorithms Design (SSZG519)
Mid-Semester - Regular Question Paper 2014-2015
MTEC- Software System - BITS -WILP
Data Structures and Algorithms Design (SSZG519) Mid-Semester - Makeup Question Paper 2014-2015 MTEC- Software System - BITS -WILP
Data Structures and Algorithms Design (SSZG519)
Mid-Semester - Makeup Question Paper 2014-2015
MTEC- Software System - BITS -WILP
Data Structures and Algorithms Design Quiz-1 -MTech Software Systems- BITS PILANI - WILP
Data Structures and Algorithms Design (SSZG519)- Quiz- 1
MTech Software Systems- WILP(Work Integrated Learning Programmes)
Birla Institute of Technology and Science, Pilani
1. Consider the following stack operations. new(), push(a), push(b), pop(), push (c), pop(), push(5). what is the index of top element in the array implementation?
Select one:
a. 2
b. None of the above
c. -1
d. 1
e. 0
Ans: d. 1
2. Suppose T is a proper binary tree with 11 internal nodes. What is the size of T?
Select one:
a. 21
b. None of the above
c. 22
d. 23
e. 12
Ans: d. 23
3. Which of the following expressions is not sublinear?
Select one:
a. None of the above
b. O(logn)
c.n√n
d. O(log log n)
e. O(n)
Ans: e. O(n)
4. Consider the ArrayFind algorithm.
input : an element x, n, an array A of n integers
Output : The index i such that A[i]=x or -1 if no element in A is equal to x
i ← 0
while i <n do
if x = A[i] then
return i
else
i ←i+1
return -1
The number of primitive operations for the best case is
Select one:
a. n
b. 5
c. 1
d. 3
e. None of the above
Ans: b. 5
5. 1+3+9+27+... + 3n is
Select one:
a. O(2n)
b. O(n3)
c. None of the above
d. O(4n)
Ans: d. O(4n)
6. Consider a binary tree of size n. The minimum size of array in the array implementation is
Select one:
a. n
b. n2
c. None of the aboven
d. n log n
e. 2n
Ans: a. n
7.Consider the ArrayFind algorithm.
input : an element x, n, an array A of n integers
Output : The index i such that A[i]=x or -1 if no element in A is equal to x
i ← 0
while i <n do
if x = A[i] then
return i
else
i ←i+1
return -1
The number of primitive operations for the worst case is
Select one:
a. None of the above
b. 5n+1
c. 5n
d. 5n+3
e. 5n-2
Ans: d. 5n+3
8. Which of these is the correct big-O expression for 1+4+9+...+n²?
Select one:
a. O(n³)
b. O(n²)
c. O(log n)
d. O(n log n)
e. None of the above
Ans: a. O(n³)
9. Stack is empty when t=1
Select one:
a. t=0
b. None of the above
c. t=-1
d. t=1
Ans: c. t=-1
10. Which of the following statements are true. '
i) 2(n+1) is O(2n)
ii) 2(2n) is O(2n)
Select one:
a. ii only
b. None of them is true
c. i only
d. Both of them are true
Ans: c. i only
11. If C =1, what would be the appropriate value of n_0 to show that 2n² +9 is O( n²)?
Select one:
a. None of the above
b. 5
c. 4
d. 10
Ans: a. None of the above
12. Which of the following formulas in big-O notation best represent the expression n²+3nlogn?
Select one:
a. O(n)
b. O(42)
c. O(n³)
d. O(n²)
e. None of the above
Ans: d. O(n²)
13. Algorithm A uses 5nlog n operations and algorithm B uses n\sqrt n operations. Determine the value n_0 such that A is better than B for n >n_0.
Select one:
a. None of the above
b. 2048
c. 1024
d. 4096
e. 512
Ans: d. 4096
14.Which of the following statements are true?
i. If f(n) is O(n3), then f(n) is o(n3)
ii. If f(n) is O(n3), then f(n) is Θ(n3)
iii. If f(n) is o(n3), then f(n) is O(n3)
Select one:
a. i only
b. i and iii only
c. All of them are true
d. None of them is true
e. iii only
Ans: e. iii only
15. log2(n/2) is
Select one:
a. None of the above
b. log n2
c. log2 n-1
d. log2 n -2logn +1
Ans: d. log2 n -2logn +1
16.T(n) = b if n=1
2T(n-1) +b otherwise
Then T(n) is
Select one:
a. O(n2)
b. None of the above
c. O(log n)
d. O(2^n)
e. O(nb)
Ans: d. O(2^n)
17. Consider the following recurrence relation.
T(n) = 5 if n <= 2
T(n-1)+ n otherwise
Closed form solution for T(n) is
Select one:
a. None of the above
b. n(n+1)/2 +7
c. n(n+1)/2 +2
d. n(n+1)/2
e. n(n-1)/2
Ans: c. n(n+1)/2 +2
18. f-r Queue is full in the circular array implementation when n
Select one:
a. r-f=1
b. f-r=1
c. f-r=0
d. None of the above
Ans: d. None of the above
19. Which of the following statements are true?
I) n! Is O(n)
ii) n! Is O(n^n)
iii) n! Is O(2n)
Select one:
a. ii and iii
b. ii only
c. None of the above
d. i only
Ans: b. ii only
20. Algorithm Loop(n)
p ← 1
for i← 1 to n do
p ← p.i
return p
Give a big-Oh characterization for the above algorithm.
Select one:
a. None of the above
b. O(logn)
c. n√n
d. O(n)
e. O(1)
Ans: d. O(n)
Subscribe to:
Comments (Atom)