Data Structures and Algorithms | Set 37

Que – 1. For 8 keys and 6 slots in a hashing table with uniform hashing and chaining, what is the expected number of items that hash to a particular location. 
(A) 2.33 
(B) 0.75 
(C) 1.33 
(D) 2 

Solution: 
Probability that key1 ends up in slot 1 = 1/6 
Probability that key2 ends up in slot 1 = 1/6 
Probability that key3 ends up in slot x = 1/6 
Probability that key4 ends up in slot x = 1/6 
Probability that key5 ends up in slot x = 1/6 
Probability that key6 ends up in slot x = 1/6 
Expected number of items that hash to a particular location = 8/6 
Option (C) is correct. 

Que – 2. For n keys and m slots in a hashing table, which of the following is the expected number of empty location. 
(A) n((m-1)/m)^n 
(B) m((m-1)/m)^n 
(C) n((n-1)/m)^n 
(D) n((n-1)/n)^m 

Solution: 
Expected number of items that hash to a particular location = n/m 
Probability that slot 1 is empty after n keys are inserted = ((m-1)/m)^n 
Probability that slot 2 is empty after n keys are inserted = ((m-1)/m)^n 
Probability that slot 3 is empty after n keys are inserted = ((m-1)/m)^n 
So for m slots expected number of empty locations = m((m-1)/m)^n 
Option (B) is correct. 

Que – 3. What is the number of binary search trees with 20 nodes with elements 1, 2, 3,…..20 such that the root of tree is 12 and the root of left subtree is 7? 
(A) 2634240 
(B) 1243561 
(C) 350016 
(D) 2642640 

Solution: 
Number of nodes in left subtree = 11 {1, 2, 3, 4….11} 
Number of nodes in the right subtree = 8 {13, 14, ….20} 
Since for the left subtree root is 7 
Number of elements in the left part of left subtree = 6 {1, 2, 3..6} 
Number of elements in the right part of left subtree = 4 {8, 9, 10, 11} 
We know number of Binary Search trees with n nodes = (C(2n,n)/n+1) 
Number of BST with 6 nodes = (C(12,6)/7) = 132 
Number of BST with 4 nodes = (C(8,4)/5) = 14 
Number of BST with 8 nodes = (C(16,8)/9) =1430 
Total number of BST = 2642640 
Option (D) is correct. 

Que – 4. For a graph with E edges and V vertices what is the time complexity of Dijkstra algorithm using array as data structure for storing non-finalized vertices. Graph is undirected and represented as adjacency list? 
(A) O(VE) 
(B) O(ElogV) 
(C) O(V^2 ) 
(D) O(E^2log V) 

Solution: 
Given data structure used is array so initialization of all nodes in array (setting infinity to all nodes which are not reachable), this operation takes O(V) 
At each step we have to delete minimum from the array. For one such operation it takes O(V), using selection sort first pass. We have V such steps. So total complexity due to deletion of minimum element at each step = V*O(V) = O(V^2) 
After a minimum is selected at each step we have to check its adjacent and perform decrease key to the neighbors of selected node. It takes total O(2E) to check adjacents for all steps. Also the decrease key of all the steps is E. O(1) = O(E) . Since the array is unsorted we don’t have to sort the array at each step. 
Total complexity = O(V) + O(V^2) + O(2E) + O(E) = O(V^2) 
Note: For a simple graph V^2 is always >= E 
Option (C) is correct. 

Que – 5. What is the output of the following program? 
 

int a = 5;
main()
{
   extern int a;
   extern int a;
   printf(a);
}

(A) Compile time error. 
(B) Run time error. 
(C) 0 
(D) 5 

Solution: 
Above program does not cause any compile time error since extern does not allocate any memory. So within a function declaration of same variable as extern does not cause any error as long as the variable is declared globally. Output is 5. 
Option (D) is correct. 

A

Aastha Mishra

Improve