Thursday, 24 August 2017

Data Structures and Algorithms Multiple Choice Questions - Set 8

71.       A tree in which, for every node, the difference between the height of its left subtree and right subtree is not more than one is
(A) AVL Tree
(B) Complete Binary Tree
(C) B – Tree
(D) B+ Tree
Answer: A
72.       The data structure needed to convert a recursion to an iterative procedure is ............
(A) Queue
(B) Graph
(C) Stack
(D) Tree
Answer: C
73.       Which of the following uses FIFO method?
(A) Queue
(B) Stack
(C) Hash Table
(D) Binary Search Tree
Answer: A
74.       A binary tree stored using linked representation can be converted to its mirror image by traversing it in ...............
(A) In-order
(B) Pre-order
(C) Post-order
(D) Any order
Answer: B
75.       Minimum number of spanning tree in a connected graph is .............
(A) n
(B) nn - 1
(C) 1
(D) 0
Answer: C
76.       Which of the following algorithm cannot be designed without recursion?
(A) Tower of Hanoi
(B) Fibonacci Series
(C) Tree Traversal
(D) None of the above
Answer: D
77.       The prefix form of an infix expression A+B-C*D is
(A) +AB-*CD
(B) -+A B C * D
(C) -+A B * C D
(D) - + *ABCD
Answer: C
78.       Binary search tree is an example of complete binary tree with special attributes:
(A) BST does not care about complete binary tree properties.
(B) BST takes care of complete binary tree properties.
(C) It depends upon the input.
(D) None of the above.
Answer: A
79.       For a binary search algorithm to work, it is necessary that the array must be ............
(A) sorted
(B) unsorted
(C) in a heap
(D) popped out of stack
Answer: A
80.    A random access file is organized most like a(n):
(A) Array
(B) Object
(C) Class
(D) Pointer
Answer: A

Wednesday, 23 August 2017

Data Structures and Algorithms Multiple Choice Questions - Set 7

61.       To write fixed-length records, use file open mode:
(A) ios::app
(B) ios::ate
(C) ios::trunc
(D) ios::binary
Answer: D
62.       A complete Binary Tree with 15 nodes contains ................. edges
(A) 15
(B) 30
(C) 14
(D) 16
Answer: C
63.       If there is no base criteria in a recursive program, the program will ................
(A) not be executed
(B) execute until all conditions match
(C) execute infinitely
(D) obtain progressive approach
Answer: C
64.       The minimum number of comparisons required to find the largest number from 4 different numbers are
(A) 4
(B) 3
(C) 5
(D) 6
Answer: B
65.       Visiting root node after visiting left and right sub-trees is called .............
(A) In-order Traversal
(B) Pre-order Traversal
(C) Post-order Traversal
(D) None of these
Answer: C
66.       Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest?
(A) union only
(B) intersection, membership
(C) membership, cardinality
(D) union, intersection
Answer: D
67.       An infix expression can be converted to a postfix expression using a .................
(A) Stack
(B) Queue
(C) Dequeue
(D) None of these
Answer: A
68.       A data structure in which an element is added and removed only from one end, is known as
(A) Queue
(B) Stack
(C) In-built structure
(D) None of the above
Answer: B
69.       A complete binary tree with the property that the value of each node is at least as large as the values of its children is known as ..............
(A) Binary Search Tree
(B) AVL Tree
(C) Heap
(D) Threaded Binary Tree.
Answer: C
70.    A sorting algorithm is stable if
(A) its time complexity is constant irrespective of the nature of input.
(B) preserves the original order of records with equal keys.
(C) its space complexity is constant irrespective of the nature of input.
(D) it sorts any volume of data in a constant time.
Answer: B

Tuesday, 22 August 2017

Data Structures and Algorithms Multiple Choice Questions - Set 6

51.       A graph with n vertices will definitely have a parallel edge or self loop if the total number of edges are
(A) more than n
(B) more than n+1
(C) more than (n+1)/2
(D) more than n(n-1)/2
Answer: D
52.       In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is ............
(A) log2 n
(B) n/2
(C) log2 n-1
(D) n
Answer: D
53.       Index of arrays in C programming language starts from.............
(A) 0
(B) 1
(C) either 0 or 1
(D) undefined
Answer: A
54.       Out of the following, the slowest sorting procedure is
(A) Quick Sort
(B) Heap Sort
(C) Shell Sort
(D) Bubble Sort
Answer: D
55.       The minimum number of edges required to create a cyclic graph of n vertices is .............
(A) n
(B) n - 1
(C) n + 1
(D) 2n
Answer: A
56.       In .............., it is possible to traverse a tree without using stacks either implicitly or explicitly.
(A) Threaded binary trees
(B) AVL Tree
(C) B+ tree
(D) Heap
Answer: C
57.       The order of a B-Tree with 2, 3, 4 or 5 children in every internal node is
(A) 2
(B) 3
(C) 4
(D) 5
Answer: C
58.       Prefix notation is also known as ...............
(A) Reverse Polish Notation
(B) Reverse Notation
(C) Polish Reverse Notation
(D) Polish Notation
Answer: D
59.       The number of nodes that have no successors in a complete binary tree of depth 4 is
(A) 0
(B) 8
(C) 16
(D) 4
Answer: B
60.    One can make an exact replica of a Binary Search Tree by traversing it in ...............
(A) In-order
(B) Pre-order
(C) Post-order
(D) Any order
Answer: B

Monday, 21 August 2017

Data Structures and Algorithms Multiple Choice Questions - Set 5

41.       A complete graph can have ...............
(A) n2 spanning trees
(B) nn-2 spanning trees
(C) nn+1 spanning trees
(D) nn spanning trees
Answer: B
42.       Access time of a binary search tree may go worse in terms of time complexity upto ..............
(A) Ο(n2)
(B) Ο(n log n)
(C) Ο(n)
(D) Ο(1)
Answer: C
43.       A desirable choice for the partitioning element in quick sort is
(A) First element of the list
(B) Last element of the list
(C) Randomly chosen element of the list
(D) Median of the list
Answer: A
44.       lg (n!) = .................
(A) O(n)
(B) O(lg n)
(C) O(n2)
(D) O(n lg n)
Answer: D
Explanation:
n!=n(n-1)(n-2).......3X2X1
≥(n/2)n/2
log n! ≥ n/2logn/2
≥ n/2(logn-log2)
≥ n/2 (log n-1)
≤ n log n
= O(n log n)
45.       Binary search tree has best case run-time complexity of Ο(log n). What could the worst case?
(A) Ο(n)
(B) Ο(n2)
(C) Ο(n3)
(D) None of these
Answer: A
46.       The total number of elements that can be stored in a string without increasing its current amount of allocated memory is called its:
(A) Size
(B) Length
(C) Capacity
(D) Maximum size
Answer: C
47.       Graph traversal is different from a tree traversal, because:
(A) trees are not connected.
(B) graphs may have loops.
(C) trees have root.
(D) None of these
Answer: C
48.       The result of evaluating the following postfix expression is
5, 7, 9, *, +, 4, 9, 3, /, +, -
(A) 50
(B) 65
(C) 61
(D) 70
Answer: C
49.       Find the odd out:
(A) Prim's Minimal Spanning Tree Algorithm
(B) Kruskal's Minimal Spanning Tree Algorithm
(C) Floyd-Warshall's All pair shortest path Algorithm
(D) Dijkstra's Minimal Spanning Tree Algorithm
Answer: C
Explanation
Floyd-Warshall's All pair shortest path Algorithm uses dynamic programming approach. All other mentioned algorithms use greedy programming approach
50.    Which data structure allows deleting data elements from the front and adding at the back?
(A) Stack
(B) Queue
(C) Binary-search tree
(D) Map
Answer: B

Sunday, 20 August 2017

Data Structures and Algorithms Multiple Choice Questions - Set 4

31.       The pre-order traversal of a binary-search tree is DBACFE. What is the post-order traversal?
(A) ABFCDE
(B) ADBFEC
(C) ABFEDC
(D) ACBEFD
Answer: D
32.       What could be the worst case height of an AVL tree?
(A) 0.97 log n
(B) 2.13 log n
(C) 1.44 log n
(D) n2 log n
Answer: C
33.       Which amongst the following cannot be a balance factor of any node of an AVL tree?
(A) 1
(B) 0
(C) 2
(D) -1
Answer: C
34.       How many distinct binary search trees can be formed which contains the integers 1, 2, 3?
(A) 6
(B) 5
(C) 4
(D) 3
Answer: B
35.       The sort which inserts each elements A(K) into proper position in the previously sorted sub array A(1), ..., A(K–1)
(A) Insertion sort
(B) Radix sort
(C) Merge sort
(D) Bubble sort
Answer: A
36.       Direct or random access of elements is not possible in ...............
(A) Linked list
(B) Array
(C) String
(D) None of these
Answer: A
37.       push() and pop() functions are found in ...............
(A) queues
(B) lists
(C) stacks
(D) trees
Answer: C
38.       Shell sort uses ................
(A) insertion sort
(B) merge sort
(C) selection sort
(D) quick sort
Answer: A
39.       Which of the following algorithm cannot be designed without recursion?
(A) Tower of Hanoi
(B) Fibonacci Series
(C) Tree Traversal
(D) None of the above
Answer: D
Explanation
Every problem which can be solved using recursion can also be solved using iterations.
40.    Level of any node of a tree is
(A) Height of its left subtree minus height of its right subtree
(B) Height of its right subtree minus height of its left subtree
(C) Its distance from the root
(D) None of these
Answer: C