Scribd
Upload
97 views

Samsung QP Data Struct Solution

SELINDIA, NOIDA Test: Data Structure: SOLUTION Duration: 1 Hr Max. Marks: 50 NOTE: All questions are compulsory. Please attempt questions inorder only.

Uploaded by

Piyush Goyal
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
97 views

Samsung QP Data Struct Solution

SELINDIA, NOIDA Test: Data Structure: SOLUTION Duration: 1 Hr Max. Marks: 50 NOTE: All questions are compulsory. Please attempt questions inorder only.

Uploaded by

Piyush Goyal
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

SEL- INDIA, NOIDA

Test: Data Structure: SOLUTION


Duration: 1 Hr Max. Marks: 50 NOTE: All questions are compulsory. Please attempt questions inorder only. Question 1 To delete the ith node in a min heap, you can exchange the last node with the ith node, and then do the minheapify on the ith node, and then shrink the heap size to be one less the original size. (True/False) Explain. False, the last node may be smaller than the ith nodes parent. min-heapify would not fix that. Question 2 Draw a binary search tree whose Preorder and Inorder traversal are as follows: Preorder Traversal: 1 2 4 8 9 10 11 5 3 6 7 Inorder Traversal: 8 4 10 9 11 2 5 1 6 3 7 [2]

[4]

[4] Question 3 Write the Recurrence equation for Merge Sort algorithm. Show your work to derive the equivalent Big-Oh notation from the recurrence. T(1) = a if n = 1 T(n) = 2T(n/2) + bn if n > 1 Repeatedly substitute the value of n by n/2 , n/4 ans so on. Finally we will have an expression in which we can put T(1). Solving that we get T(n) = 2i T(n/2i) + ibn Now, if we let i = log2 n, we end up with: n*T(1) + bn log2 n = an + bn log2 n = O(n log n) (because 2log2n = n). (NOTE: Solution of recurrence using mater theorem has also been marked correct)

Question 4 [4] Write pseudocode for a recursive, divide-and-conquer algorithm MAX(A,p,r) that returns the maximum element of the integer array A[p..r]. The initial call to the algorithm is MAX(A,1,n), where n = length(A). No global variables are allowed.

(NOTE: Other solutions have also been marked correct if found logically right)

[4] Question 5 Write a function that simulates the departure of vehicles queued at a Toll Booth. Assume vehicles are assigned an integer sequence number as soon as they reach the toll station. x = q.items[0]; for(i=0; i<q.rear; i++) q.items[i] = q.items[i+1]; q.rear -- ; (All elements have to be moved to front as happens at a Toll Plaza. Server at Front remains fixed) Question 6 [4] Write a recursive algorithm for a function named PreToPost that converts a prefix expression to its equivalent postfix expression. PreToPost( ){ read character c; if (c is operator) { PretoPost(); PretoPost(); } print c; }

Question 7 Show the rotations required to insert value 4 in the following AVL tree:

[4]

Question 8 Write a function Reverse to reverse a linked list iteratively in template given below: void Reverse(struct node** headRef) { struct node* tmp = NULL; struct node* current = *headRef; struct node* next; while (current!= NULL) { next = current link; current link = tmp; tmp = current ; current = next; } *headRef = tmp; }

[6]

Question 9 [6] Consider a hash table of size m = 12 that uses collision-resolution by open addressing and the quadratic probing hash function h(k, i) = ((k mod m) + i + i2) mod m. Show the hash table resulting from inserting the keys 10, 22, 34 and 16, in this order. The hash function for this hash table does not generate a valid probe sequence. Explain why and give a key that cannot be inserted into the table you produced in part (a) above.

Question 10 Consider the following B-tree of minimum degree 2.

[6]

(i) (ii)

Show the two B-trees resulting from the insertion of key B and then key C into the B-tree above. Show the two B-trees resulting from the deletion of key A and then key D from the original Btree above.

[6] Question 11 Write the pseudocode for finding the Minimum Spanning Tree using Prims Algorithm. Apply the same for the following undirected graph starting from the bottom most vertex. Draw the graph at each step.

You might also like