## MCQs Data Structure|UGC-NET|GATE|Data Structures

11. | Given a binary search trees for a set of n=5 keys with the following probabilities : i 0 1 2 3 4 5 p 0.15 0.10 0.05 0.10 0.20 qi 0.05 0.10 0.05 0.05 0.05 0.10 The expected optimal cost of the search is |

A. | 2.65 |

B. | 2.70 |

C. | 2.75 |

D. | 2.80 |

View/Hide Ans | |

Explanation | |

12. | The worst case time complexity of AVL tree is better in comparison to binary search tree for |

A. | Search and Insert Operations |

B. | Search and Delete Operations |

C. | Insert and Delete Operations |

D. | Search, Insert and Delete Operations |

View/Hide Ans | |

Explanation | |

13. | In which tree, for every node the height of its left subtree and right subtree differ almost by one ? |

A. | Binary search tree |

B. | AVL tree |

C. | Threaded Binary Tree |

D. | Complete Binary Tree |

View/Hide Ans | |

Explanation | |

14. | A hash function f defined as f (key) = key mod 13, with linear probing is used to insert keys 55, 58, 68, 91, 27, 145. What will be the location of 79 ? |

A. | 1 |

B. | 2 |

C. | 3 |

D. | 5 |

View/Hide Ans | |

Explanation | |

15. | Consider the tree given below : Using the property of eccentricity of a vertex, find every vertex that is the centre of the given tree. |

A. | d & h |

B. | c & k |

C. | g, b, c, h, i, m |

D. | c & h |

View/Hide Ans | |

Explanation | |

16. | Given an empty stack, after performing push (1), push (2), Pop, push (3), push (4), Pop, Pop, push(5), Pop, what is the value of the top of the stack ? |

A. | 4 |

B. | 3 |

C. | 2 |

D. | 1 |

View/Hide Ans | |

Explanation | |

17. | Enumeration is a process of |

A. | Declaring a set of numbers |

B. | Sorting a list of strings |

C. | Assigning a legal values possible for a variable |

D. | Sequencing a list of operators |

View/Hide Ans | |

Explanation | |

18. | The time complexities of some standard graph algorithms are given. Match each algorithm with its time complexity ? (n and m are no. of nodes and edges respectively) a. Bellman Fordalgorithm1. O (m log n) b. Kruskals algorithm 2. O (n3) c. Floyd Warshallalgorithm 3. O(mn) d. Topological sorting 4. O(n + m) Codes : a b c d |

A. | 3 1 2 4 |

B. | 2 4 3 1 |

C. | 3 4 1 2 |

D. | 2 1 3 4 |

View/Hide Ans | |

Explanation | |

19. | Let T(n) be the function defined by T(n) = 1 and T(n) = 2T (n/2) + n, which of the following is TRUE ? |

A. | T(n) = O( n) |

B. | T(n) = O(log2n) |

C. | T(n) = O(n) |

D. | T(n) = O(n2) |

View/Hide Ans | |

Explanation | |

20. | Which of the following permutations can be obtained in the output using a stack of size 3 elements assuming that input, sequence is 1, 2, 3, 4, 5 ? |

A. | 3, 2, 1, 5, 4 |

B. | 5, 4, 3, 2, 1 |

C. | 3, 4, 5, 2, 1 |

D. | 3, 4, 5, 1, 2 |

View/Hide Ans | |

Explanation |

Author Does Not claim of any answer these answers are as per expert opinion