Section A : Basic Concepts (30 Marks)
1. If all c(i, j )’s and r(i, j)’s are calculated, then OBST algorithm in worst case takes one of the following time.
(a) Ï(n log n) (b) Ï(n3) (c) Ï(n2) (d) Ï(log n) (e) Ï(n4)
2. The following is a weighted binary tree, then what is the weighted array for the TVS problem?
(a) [9, 2, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 4] (b) [9, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 4, 6]
(c) [9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 6, 7, 4] (d) [9, 2, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 6, 4]
(e) [9, 2, 0, 0, 0, 7, 0, 0, 0, 0, 6, 4, 0, 0].
3. What are the entries of the array TREE[ ] for the above weighted binary tree for the TVS problem.
(a) [1, 2, 3, 4, 5, 6, 0, 0]
(b) [1, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 4, 5, 6]
(c) [1, 2, 3, 0, 0, 0, 0, 4, 5, 6]
(d) [1, 2, 3, 0, 0, 0, 0, 0, 4, 5, 6]
(e) [1, 2, 3, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 5, 6].
4. For a 15-puzzle problem let the initial arrangement be the following one, then answer the questions 4 – 7 with the following arrangement.
10 13 15 7
9 1 4 14
12 8 6
11 2 5 3
What is the value of ‘x’ used to find the reachability of the solution?
(a) 1 (b) 0 (c) 8 (d) 10 (e) 13.
5. The values for the position(i), position(j) where i = 14 and j =11, are
(a) 2, 8 (b) 8, 2 (c) 8, 13 (d) 2, 13 (e) 13, 8.
6. The values for less(i), less(j) where i =5, j =7 are
(a) 0, 6 (b) 6, 0 (c) 2, 4 (d) 2, 6 (e) 1, 6.
7. What is the value to find the reachability of the problem with which you can say the solution is
reachable or not?
(a) 71 (b) 72 (c) 73 (d) 69 (e) 68.
8. The upper bound on the time complexity of the nondeterministic sorting algorithm is
(a) O(n) (b) O(n log n) (c) O(1) (d) O( log n) (e) O(n2).
9. The worst case time complexity of the nondeterministic dynamic knapsack algorithm is
(a) O(n log n) (b) O( log n) (c) O(n2) (d) O(n) (e) O(1).
10. For the LCBB solution of knapsack problem with the data (p1–p4) = (10,10,12,18) and (w1–w4) = (2, 4, 6, 9) and m = 18, then the values of u(1) and ĉ(1) respectively are
(a) -38, -44 (b) -44, -38 (c) -44, -32 (d) -32, -44 (e) -32, - 38.
11. If for the above problem, the tree is created following the FIFOBB, then the values for ĉ (5) and u(5) respectively are
(a) -40, -40 (b) -40, -38 (c) -40, -32 (d) -22, -32 (e) -32, - 22.
12. There is a chain of 20 stores; each of the store having 5 departments. Then, which of the following is a correct representation of array size?
(a) 5 * 20 (b) 6 * 21 (c) 20 * 5 (d) 21 * 6 (e) 19 * 4.
13. From the following, select the valid data structure which reflects hierarchical relationship between the elements.
(a) Graph (b) Queue (c) Linked list (d) Stack (e) Tree.
14. Which of the following matrix does have high proportions of zero entries as the elements?
(a) Inverse Matrix (b) Sparse Matrix (c) Determinant Matrix (d) Square Matrix (e) Transpose Matrix.
15. Let there is a queue whose initial values for Front and Rear are 0 and 1 respectively. Later queue found to be having the elements 3, 2, 1, 5. If a new element is inserted in the queue, then which of the following statements is correct?
(a) Front = 0 and Rear = 5
(b) Front = 0 and Rear = 4
(c) Front = 1 and Rear = 4
(d) Front = 1 and Rear = 5
(e) Insertion is not possible as there is no space in the queue.
16. One from the following is also known as Pre-Order traversal. What that one is?
(a) LNR (b) LRN (c) RLN (d) RNL (e) NLR.
17. Which of the following data structure is the best example for the multitasking systems?
(a) Tree (b) Queue (c) Stack (d) Linked List (e) Graph.
18. The initial configuration of the queue is having the elements ‘x, y, z, a’ forming a queue. To get the new configuration ‘a, z, y, x’ one needs a minimum of
(a) 3 additions and 4 deletion (b) 3 deletions and 4 additions (c) 3 deletions and 2 additions (d) 3 deletions and 3 additions (e) 4 deletions and 4 additions.
19. To form the new configuration in the above problem, what best data structure is seems to be used?
(a) Tree (b) Queue (c) Linked List (d) Circular Queue (e) Stack.
20. Recursive algorithms are based on
(a) Divide and conquer approach (b) Top-down approach (c) Bottom-up approach (d) Hierarchical approach (e) Heuristic approach.
21. What do you call the selected keys in the quick sort method?
(a) Outer key (b) Inner Key (c) Partition key (d) Pivot key (e) Recombine key.
22. Primary clustering occurs in
(a) Linear probing (b) Quadratic probing (c) Mid-square method (d) Order probing (e) Chaining.
23. How many nodes do a full binary tree with ‘N’ leaves contain?
(a) 2N nodes (b) N nodes (c) 2N-1 nodes (d) N-1 nodes (e) 2(N-1) nodes.
24. How many nodes does a complete binary tree of level 5 have?
(a) 16 (b) 15 (c) 32 (d) 31 (e) 64.
25. How do you determine the cost of a spanning tree?
(a) By the sum of the costs of the edges of the tree
(b) By the sum of the costs of the edges and vertices of the tree
(c) By the sum of the costs of the vertices of the tree
(d) By the sum of the costs of the edges of the graph
(e) By the sum of the costs of the edges and vertices of the graph.
26. What would be the depth of tree whose level is 9?
(a) 10 (b) 8 (c) 9 (d) 11 (e) 7.
27. A node of a directed graph G having no out-degree and a positive in-degree is called
(a) Source node (b) Sink node (c) Sibling node (d) Null node (e) In-node.
28. The time complexity of the normal quick sort, randomized quick sort algorithms in the worst case is
(a) O(n2), O(n log n) (b) O(n2), O(n2) (c) O(n log n), O(n2) (d) O(n log n), O(n log n)
(e) O(n log n), O(n2 log n).
29. Let there be an array of length ‘N’, and the selection sort algorithm is used to sort it, how many times a swap function is called to complete the execution?
(a) N log N times (b) log N times (c) N2 times (d) N-1 times (e) N times.
30. The Sorting method which is used for external sort is
(a) Bubble sort (b) Quick sort (c) Merge sort (d) Radix sort (e) Selection sort.
Section B : Problems (50 Marks)
1. a. Let there be an array of ‘n’ elements, write an algorithm to find the maximum and minimum in the array following the divide and conquer strategy where the division is made at the middle of the considered part of the list.
b. Write a recursive ‘C’ function to create a singly linked list. (6 + 4 = 10marks)
2.
1. If all c(i, j )’s and r(i, j)’s are calculated, then OBST algorithm in worst case takes one of the following time.
(a) Ï(n log n) (b) Ï(n3) (c) Ï(n2) (d) Ï(log n) (e) Ï(n4)
2. The following is a weighted binary tree, then what is the weighted array for the TVS problem?
(a) [9, 2, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 4] (b) [9, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 4, 6]
(c) [9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 6, 7, 4] (d) [9, 2, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 6, 4]
(e) [9, 2, 0, 0, 0, 7, 0, 0, 0, 0, 6, 4, 0, 0].
3. What are the entries of the array TREE[ ] for the above weighted binary tree for the TVS problem.
(a) [1, 2, 3, 4, 5, 6, 0, 0]
(b) [1, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 4, 5, 6]
(c) [1, 2, 3, 0, 0, 0, 0, 4, 5, 6]
(d) [1, 2, 3, 0, 0, 0, 0, 0, 4, 5, 6]
(e) [1, 2, 3, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 5, 6].
4. For a 15-puzzle problem let the initial arrangement be the following one, then answer the questions 4 – 7 with the following arrangement.
10 13 15 7
9 1 4 14
12 8 6
11 2 5 3
What is the value of ‘x’ used to find the reachability of the solution?
(a) 1 (b) 0 (c) 8 (d) 10 (e) 13.
5. The values for the position(i), position(j) where i = 14 and j =11, are
(a) 2, 8 (b) 8, 2 (c) 8, 13 (d) 2, 13 (e) 13, 8.
6. The values for less(i), less(j) where i =5, j =7 are
(a) 0, 6 (b) 6, 0 (c) 2, 4 (d) 2, 6 (e) 1, 6.
7. What is the value to find the reachability of the problem with which you can say the solution is
reachable or not?
(a) 71 (b) 72 (c) 73 (d) 69 (e) 68.
8. The upper bound on the time complexity of the nondeterministic sorting algorithm is
(a) O(n) (b) O(n log n) (c) O(1) (d) O( log n) (e) O(n2).
9. The worst case time complexity of the nondeterministic dynamic knapsack algorithm is
(a) O(n log n) (b) O( log n) (c) O(n2) (d) O(n) (e) O(1).
10. For the LCBB solution of knapsack problem with the data (p1–p4) = (10,10,12,18) and (w1–w4) = (2, 4, 6, 9) and m = 18, then the values of u(1) and ĉ(1) respectively are
(a) -38, -44 (b) -44, -38 (c) -44, -32 (d) -32, -44 (e) -32, - 38.
11. If for the above problem, the tree is created following the FIFOBB, then the values for ĉ (5) and u(5) respectively are
(a) -40, -40 (b) -40, -38 (c) -40, -32 (d) -22, -32 (e) -32, - 22.
12. There is a chain of 20 stores; each of the store having 5 departments. Then, which of the following is a correct representation of array size?
(a) 5 * 20 (b) 6 * 21 (c) 20 * 5 (d) 21 * 6 (e) 19 * 4.
13. From the following, select the valid data structure which reflects hierarchical relationship between the elements.
(a) Graph (b) Queue (c) Linked list (d) Stack (e) Tree.
14. Which of the following matrix does have high proportions of zero entries as the elements?
(a) Inverse Matrix (b) Sparse Matrix (c) Determinant Matrix (d) Square Matrix (e) Transpose Matrix.
15. Let there is a queue whose initial values for Front and Rear are 0 and 1 respectively. Later queue found to be having the elements 3, 2, 1, 5. If a new element is inserted in the queue, then which of the following statements is correct?
(a) Front = 0 and Rear = 5
(b) Front = 0 and Rear = 4
(c) Front = 1 and Rear = 4
(d) Front = 1 and Rear = 5
(e) Insertion is not possible as there is no space in the queue.
16. One from the following is also known as Pre-Order traversal. What that one is?
(a) LNR (b) LRN (c) RLN (d) RNL (e) NLR.
17. Which of the following data structure is the best example for the multitasking systems?
(a) Tree (b) Queue (c) Stack (d) Linked List (e) Graph.
18. The initial configuration of the queue is having the elements ‘x, y, z, a’ forming a queue. To get the new configuration ‘a, z, y, x’ one needs a minimum of
(a) 3 additions and 4 deletion (b) 3 deletions and 4 additions (c) 3 deletions and 2 additions (d) 3 deletions and 3 additions (e) 4 deletions and 4 additions.
19. To form the new configuration in the above problem, what best data structure is seems to be used?
(a) Tree (b) Queue (c) Linked List (d) Circular Queue (e) Stack.
20. Recursive algorithms are based on
(a) Divide and conquer approach (b) Top-down approach (c) Bottom-up approach (d) Hierarchical approach (e) Heuristic approach.
21. What do you call the selected keys in the quick sort method?
(a) Outer key (b) Inner Key (c) Partition key (d) Pivot key (e) Recombine key.
22. Primary clustering occurs in
(a) Linear probing (b) Quadratic probing (c) Mid-square method (d) Order probing (e) Chaining.
23. How many nodes do a full binary tree with ‘N’ leaves contain?
(a) 2N nodes (b) N nodes (c) 2N-1 nodes (d) N-1 nodes (e) 2(N-1) nodes.
24. How many nodes does a complete binary tree of level 5 have?
(a) 16 (b) 15 (c) 32 (d) 31 (e) 64.
25. How do you determine the cost of a spanning tree?
(a) By the sum of the costs of the edges of the tree
(b) By the sum of the costs of the edges and vertices of the tree
(c) By the sum of the costs of the vertices of the tree
(d) By the sum of the costs of the edges of the graph
(e) By the sum of the costs of the edges and vertices of the graph.
26. What would be the depth of tree whose level is 9?
(a) 10 (b) 8 (c) 9 (d) 11 (e) 7.
27. A node of a directed graph G having no out-degree and a positive in-degree is called
(a) Source node (b) Sink node (c) Sibling node (d) Null node (e) In-node.
28. The time complexity of the normal quick sort, randomized quick sort algorithms in the worst case is
(a) O(n2), O(n log n) (b) O(n2), O(n2) (c) O(n log n), O(n2) (d) O(n log n), O(n log n)
(e) O(n log n), O(n2 log n).
29. Let there be an array of length ‘N’, and the selection sort algorithm is used to sort it, how many times a swap function is called to complete the execution?
(a) N log N times (b) log N times (c) N2 times (d) N-1 times (e) N times.
30. The Sorting method which is used for external sort is
(a) Bubble sort (b) Quick sort (c) Merge sort (d) Radix sort (e) Selection sort.
Section B : Problems (50 Marks)
1. a. Let there be an array of ‘n’ elements, write an algorithm to find the maximum and minimum in the array following the divide and conquer strategy where the division is made at the middle of the considered part of the list.
b. Write a recursive ‘C’ function to create a singly linked list. (6 + 4 = 10marks)
2.
a. There is a graph representing the connections between ‘N’ cities. Mrs. HIA wants to find the cyclic path, which start from a specific city and goes across all the remaining cities exactly once and terminates at the starting city. Write an algorithm to find the solution for such requirement using backtracking approach.
b. Write a ‘C’ program to sort an array of size ‘n’ using the shell sort technique.
b. Write a ‘C’ program to sort an array of size ‘n’ using the shell sort technique.
(5 + 5 = 10marks)
3.
3.
a. Let there be a weighted graph G with ‘N’ nodes and ‘E’ edges. To find the minimum cost spanning tree, write a greedy algorithm, which construct the minimum cost spanning tree by extending the tree with the addition of a new edge every time.
b. Let there be a singly linked list created using a recursive function. Then, write a recursive ‘C’ function to count the number of nodes in a singly linked list. (7 + 3 = 10marks)
4.
b. Let there be a singly linked list created using a recursive function. Then, write a recursive ‘C’ function to count the number of nodes in a singly linked list. (7 + 3 = 10marks)
4.
a. There is a system having only one processor, and there are ‘n’ jobs which are required to be completed before their deadlines to earn a maximum profit. Write a greedy algorithm to find the solution for such problem.
b. Write a ‘C’ function to delete a node from the Binary Search Tree. (5 + 5 = 10marks)
5.
b. Write a ‘C’ function to delete a node from the Binary Search Tree. (5 + 5 = 10marks)
5.
a. Write a ‘C’ function to display a linked list in the reverse order. [Don’t reverse the linked list, just display it]
b. Write a bounding function algorithm to kill a non feasible right child of the state space tree for the backtracking knapsack algorithm. (5 + 5 = 10marks)
Section C : Applied Theory (20 Marks).
6.
b. Write a bounding function algorithm to kill a non feasible right child of the state space tree for the backtracking knapsack algorithm. (5 + 5 = 10marks)
Section C : Applied Theory (20 Marks).
6.
a. What do you mean by hashing? Explain it.
b. Suppose there is a collision, then explain when it happens and also write how the collision can be resolved. (5 + 5 = 10marks)
7. Distinguish array from the linked list along with the tradeoffs, specifying which one is good and advisable; in what circumstances. (10 marks)
Suggested Answers
1. Answer : (b)
Reason: As we have to calculate c(i,j), w(i,j) and r(i,j).
2. Answer : (d)
Reason: If we create a full binary tree then the non existing nodes will have the corresponding edge values to zero.
3. Answer : (e)
Reason: If we create a full binary tree then the non existing nodes will have the corresponding node values to zero.
4. Answer : (a)
Reason: ‘x’ takes the value 0 if it is there in shaded position which starts from second square and goes across every alternative square in the initial arrangement, otherwise it takes one. In
this question it is there in shaded square.
5. Answer : (c)
Reason: position( x ) = the square number with in which value ‘x’ is there.
6. Answer : (e)
Reason: less( x ) is the number of all js, such that j <> position(x).
7. Answer : (b)
Reason: The value to define reachable is “sum of less(i) + x”, where i takes the values from 1 to 15, and ‘x’ is value defined in question(4).
8. Answer : (a)
Reason: In the algorithm there is only one for loop which runs from 1 to n.
9. Answer : (d)
Reason: In the algorithm there is only one for loop which runs from 1 to n.
10. Answer : (d)
Reason: u(1) is the negation of sum of all profits so long as the weights as whole can be taken [ -(10+10+12)]. ĉ(1) is the value of u(1) and the negation of profit of the fraction of the next element taken to fill the knapsack [ u(1) + -( 6/9*18) ].
11. Answer : (a)
Reason: Node 5 is a node generated if first element is taken and the second object is rejected. And just calculate as question(10).
12. Answer : (c)
Reason: Its array [20][5] and hence 20 * 5.
13. Answer : (e)
Reason: Tree, according to the organization of tree a node may have a child and a parent also.
14. Answer : (b)
Reason: As sparse matrix is a matrix where the number of zeros are much than that of non zero elements.
15. Answer : (a)
Reason: As a new element is inserted at a position pointed by Rear, And Rear is incremented after insertion.
16. Answer : (e)
Reason: As in Pre-Order the traverse is as Node( root node), then Left node and Right node.
17. Answer : (b)
Reason: Because a queue is used to hold the jobs which are waiting for their turn to work with the common processor.
18. Answer : (d)
Reason: Because, first we have to delete ‘x’, ‘y’, ‘z’ and then insert ‘z’, ‘y’, ‘x’. And hence three deletions first followed by three additions.
19. Answer : (e)
Reason: As in the above discussion ‘x’ is deleted first but inserted at last. Hence there should be a stack to hold the deleted entries from above queue.
20. Answer : (b)
Reason: As in case of recursions the ARIs are created, and the recursive function is called by other function first, then it calls itself util a condition is met.
21. Answer : (d)
Reason: As in quick sort the division is made at an element which is pivotal element.
22. Answer : (a)
Reason: As there is no chance for the other probing techniques to have primary clustering.
23. Answer : (c)
Reason: According to full binary tree, if there are 2n-1 nodes, then there would be n leaves exactly.
24. Answer : (d)
Reason: This is 25 – 1. (2level – 1)
25. Answer : (a)
Reason: As the other options are wrong, and the cost of a spanning tree is the cost of edges of the tree only.
26. Answer : (c)
Reason: As both the depth and level are same.
27. Answer : (a)
Reason: Because the source vertex is a vertex which contains only leaving edges, but no any incoming edge.
28. Answer : (b)
Reason: Because, there is no difference between normal quick sort and randomized quick sort algorithms for their efficiency, except the picking of a pivotal element.
29. Answer : (d)
Reason: Because, every time we swap the ith smallest element with the ith position. And we do this for i=1 to n-1 times.
30. Answer : (c)
Reason: As Merge sort is the only one from the given sorting techniques which is used for the external sorting.
7. Distinguish array from the linked list along with the tradeoffs, specifying which one is good and advisable; in what circumstances. (10 marks)
Suggested Answers
1. Answer : (b)
Reason: As we have to calculate c(i,j), w(i,j) and r(i,j).
2. Answer : (d)
Reason: If we create a full binary tree then the non existing nodes will have the corresponding edge values to zero.
3. Answer : (e)
Reason: If we create a full binary tree then the non existing nodes will have the corresponding node values to zero.
4. Answer : (a)
Reason: ‘x’ takes the value 0 if it is there in shaded position which starts from second square and goes across every alternative square in the initial arrangement, otherwise it takes one. In
this question it is there in shaded square.
5. Answer : (c)
Reason: position( x ) = the square number with in which value ‘x’ is there.
6. Answer : (e)
Reason: less( x ) is the number of all js, such that j <> position(x).
7. Answer : (b)
Reason: The value to define reachable is “sum of less(i) + x”, where i takes the values from 1 to 15, and ‘x’ is value defined in question(4).
8. Answer : (a)
Reason: In the algorithm there is only one for loop which runs from 1 to n.
9. Answer : (d)
Reason: In the algorithm there is only one for loop which runs from 1 to n.
10. Answer : (d)
Reason: u(1) is the negation of sum of all profits so long as the weights as whole can be taken [ -(10+10+12)]. ĉ(1) is the value of u(1) and the negation of profit of the fraction of the next element taken to fill the knapsack [ u(1) + -( 6/9*18) ].
11. Answer : (a)
Reason: Node 5 is a node generated if first element is taken and the second object is rejected. And just calculate as question(10).
12. Answer : (c)
Reason: Its array [20][5] and hence 20 * 5.
13. Answer : (e)
Reason: Tree, according to the organization of tree a node may have a child and a parent also.
14. Answer : (b)
Reason: As sparse matrix is a matrix where the number of zeros are much than that of non zero elements.
15. Answer : (a)
Reason: As a new element is inserted at a position pointed by Rear, And Rear is incremented after insertion.
16. Answer : (e)
Reason: As in Pre-Order the traverse is as Node( root node), then Left node and Right node.
17. Answer : (b)
Reason: Because a queue is used to hold the jobs which are waiting for their turn to work with the common processor.
18. Answer : (d)
Reason: Because, first we have to delete ‘x’, ‘y’, ‘z’ and then insert ‘z’, ‘y’, ‘x’. And hence three deletions first followed by three additions.
19. Answer : (e)
Reason: As in the above discussion ‘x’ is deleted first but inserted at last. Hence there should be a stack to hold the deleted entries from above queue.
20. Answer : (b)
Reason: As in case of recursions the ARIs are created, and the recursive function is called by other function first, then it calls itself util a condition is met.
21. Answer : (d)
Reason: As in quick sort the division is made at an element which is pivotal element.
22. Answer : (a)
Reason: As there is no chance for the other probing techniques to have primary clustering.
23. Answer : (c)
Reason: According to full binary tree, if there are 2n-1 nodes, then there would be n leaves exactly.
24. Answer : (d)
Reason: This is 25 – 1. (2level – 1)
25. Answer : (a)
Reason: As the other options are wrong, and the cost of a spanning tree is the cost of edges of the tree only.
26. Answer : (c)
Reason: As both the depth and level are same.
27. Answer : (a)
Reason: Because the source vertex is a vertex which contains only leaving edges, but no any incoming edge.
28. Answer : (b)
Reason: Because, there is no difference between normal quick sort and randomized quick sort algorithms for their efficiency, except the picking of a pivotal element.
29. Answer : (d)
Reason: Because, every time we swap the ith smallest element with the ith position. And we do this for i=1 to n-1 times.
30. Answer : (c)
Reason: As Merge sort is the only one from the given sorting techniques which is used for the external sorting.
No comments:
Post a Comment