Data Structures Mid - I, September - 2014

1.You have to sort a list L consisting of a sorted list followed by a few “random” elements. Which of the following sorting methods would be especially suitable for such a task?
  • Bubble sort
  • Selection sort
  • Quick sort
  • Insertion sort
Answer: D
2.A technique for direct search is
  • Binary Search
  • Linear Search
  • Tree Search
  • Hashing
Answer: D
3.The searching technique that takes O(1) time to find a data is
  • Linear Search
  • Binary Search
  • Hashing
  • Tree Search
Answer: C
4.A mathematical-model with a collection of operations defined on that model is called
  • Data Structure
  • Abstract Data Type
  • Primitive Data Type
  • Algorithm
Answer: B
5.The number of interchanges required to sort 5, 1, 6, 2 4 in ascending order using Bubble Sort
  • 6
  • 5
  • 7
  • 8
Answer: B
6.In worst case Quick Sort has order
  • O(n log n)
  • O(n2)
  • O(log n)
  • O(n)
Answer: B
7.A full binary tree with 2n+1 nodes contain
  • n leaf nodes
  • n non-leaf nodes
  • n-1 leaf nodes
  • n-1 non-leaf nodes
Answer: B
8.If a node in a BST has two children, then its inorder predecessor has
  • no left child
  • no right child
  • two children
  • no child
Answer: B
9.A full binary tree with n leaves contains
  • n nodes
  • log n2nodes
  • 2n - 1 nodes
  • n2 nodes
Answer: C
10.The data structure required for Breadth First Traversal on a graph is
  • queue
  • stack
  • array
  • tree
Answer: A
11.In strictly binary tree, the outdegree of every node is _____________
Answer: Either 0 or 2
12.Any node is the path from the root to the node is called ___________
Answer: Ancestor node
13.Nodes that are not root and not leaf are called as _________________ nodes.
Answer: Internal nodes
14.The _________of an algorithm is the amount of computer time it needs to run to compilation.
Answer: Time complexity
15.The space complexity of an algorithm is the amount of _____________it needs to run to compilation.
Answer: spaces
16.__________ refers to the rate at which the storage time grows as a function of the problem size.
Answer: complexities
17.the function f(n) = O(g(n)) if there exist positive constants c and no such that f(n) ≤ c*g(n) for all n, n ≥ no.is called _____________ notation.
Answer: Big O
18.___________ notation the function f(n) = (g(n)) iff there exist positive constants c and no such that f(n) ≥ c*g(n) for all n, n ≥ no.
Answer: Omega
19.If n is the total no of nodes and e is the total no of edges then e = n-1. The tree must be ________binary tree.
Answer: Non-empty
20.The data structure used for recursion is ______________.
Answer: Stack