Questions and answers - MCQ with explanation on Computer Science subjects like System Architecture, Introduction to Management, Math For Computer Science, DBMS, C Programming, System Analysis and Design, Data Structure and Algorithm Analysis, OOP and Java, Client Server Application Development, Data Communication and Computer Networks, OS, MIS, Software Engineering, AI, Web Technology and many other subjects also make available Q & A for exam, interview, competitive exam and entrance test.

Showing posts with label Solved Paper. Show all posts

Data Structure and Algorithm Analysis Set 1

Data Structure and Algorithm Analysis

Questions 1 to 10

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) O(n log n)
(b) O(n³)
(c) O(n²)
(d) O(log n)
(e) O(n⁴).

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]

(e) [9, 2, 0, 0, 0, 7, 0, 0, 0, 0, 6, 4, 0, 0].

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]

(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].

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.

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.

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.

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.

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(n²).

The worst case time complexity of the nondeterministic dynamic knapsack algorithm is

(a) O(n log n)
(b) O( log n)
(c) O(n²)
(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.

Set 1 Set 2 Set 3 Set 4 Set 5 Set 6 Set 7 Set 8 Set 9 Set 10 Set 11 Set 12 Set 13 Set 14 Set 15 Set 16 Set 17 Set 18 Set 19 Set 20 Set 21 Set 22 Set 23 Set 24 Set 25 Set 26

Set 27 Set 28 Set 29 Set 30

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 j_s, such that j < x and position( 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) ].

Data Structure and Algorithm Analysis

Questions 11 to 20

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.

Answers

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.

<< Prev Set 1 Set 2 Set 3 Set 4 Set 5 Set 6 Set 7 Set 8 Set 9 Set 10 Set 11 Set 12 Set 13 Set 14 Set 15 Set 16 Set 17 Set 18 Set 19 Set 20 Set 21 Set 22 Set 23 Set 24 Set 25 Set 26 Set 27 Set 28 Set 29 Set 30 Next >>

Data Structure and Algorithm Analysis

Questions 21 to 30

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(n²), O(n log n) (b) O(n²), O(n²) (c) O(n log n), O(n²) (d) O(n log n), O(n log n) (e) O(n log n), O(n² 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) N² 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.

Answers

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 2⁵ – 1. (2^level – 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 i^th smallest element with the i^th 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.

Subscribe to: Posts ( Atom )

All the content available on this blog is for informational purposes only. The content in this blog is fetched through online and offline research. If any of the information available on this blog violates or infringes any of your copyright protection, leave a comment or contact us by using the above form. Appropriate action will be taken as soon as possible. This blog makes no representations as to accuracy, completeness, correctness or validity of any information on this site and will not be liable for any errors, or delays in this information. The information contained in this blog is subject to change without notice. You can use contents in this blog only for personal use. Reproduction and republishing of any contents from here to any other websites or blogs is strictly prohibited.

Pages

Data Structure and Algorithm Analysis Set 1

Data Structure and Algorithm Analysis

Questions 1 to 10

Set 1 Set 2 Set 3 Set 4 Set 5 Set 6 Set 7 Set 8 Set 9 Set 10 Set 11 Set 12 Set 13 Set 14 Set 15 Set 16 Set 17 Set 18 Set 19 Set 20 Set 21 Set 22 Set 23 Set 24 Set 25 Set 26

Set 27 Set 28 Set 29 Set 30

Answers

Data Structure and Algorithm Analysis Set 2

Data Structure and Algorithm Analysis

Questions 11 to 20

Answers

Data Structure and Algorithm Analysis Set 3

Data Structure and Algorithm Analysis

Questions 21 to 30

Answers