## This contains data structures and algorithm mcq questions for preparing SPPU exam 2020, for placements exams, companies exam and other.

**This is part 3 of data structures in c mcq questions and answers for sppu exam 2020**

**Click to read part 1**

**Click to read part 2**

1. In...........3 for any node n, every descendant node's value in

the left sub tree of n is less than the value of n and every

descendant node’s value in the right sub tree is greater than the

value n.

(a) Binary tree

(b) Binary search tree

(c) AVL tree

(d) Binary heap tree

(e) None of these

**Answer:(b) Binary search tree**

2. In the best case of BST, the time is on the order of ..........., but

in the worst case it requires linear time.

(a) logon

(b) n

(c) log2(n+1)

(d) n+1

(e) None of these

**Answer:(a) logon**

3. eteteteee Of binary search tree starts by visiting the

current node, then its left child and then its right child.

(a) Preorder traversal

(b) In-order traversal

(c) Linear traversal

(d) Post-order traversal

(e) None of these

**Answer:(a) Preorder traversal **

4. State True or False for internal sorting algorithms.

(i) Internal sorting are applied when the entire collection if data

to be sorted is small enough that the sorting can take place within

main memory.

(ii) The time required to read or write is considered to be

significant in evaluating the performance of internal sorting.

(a) i-True, ii-True

(b) i-True, ii-False

(c) i-False, ii-True

(d) i-False, 1i-False

(e) None of these

**Answer:(b) i-True, ii-False**

5. The height of a tree is the length of the longest root-to-leaf

path in it. The maximum and minimum number of nodes in a

binary tree of height 5 is.

(a) 63 and 6, respectively

(b) 64 and 5, respectively

(c) 32 and 6, respectively

(d) 31 and 5, respectively

**Answer:(a) 63 and 6, respectively**

6. Ina binary tree, the number of internal nodes of degree 1 is 5,

and the number of internal nodes of degree 2 is 10. The number

of leaf nodes in the binary tree is

(a) 10

(b) 11

(c) 12

(d) 15

(e) None of these

**Answer:(b) 11**

7. Breadth First Search (BFS) is started on a binary tree

beginning from the root vertex. There is a vertex t at a distance

four from the root. If t is the n-th vertex in this BFS traversal, then

the maximum possible value of nis

(a) 15

(b) 16

(c) 31

(d) 32

(e) None of these

**Answer:(c) 31 **

8. The maximum number of binary trees that can be formed with

three unlabeled nodes is:

(a) 1

(b) 5

(c) 4

(d) 3

(e) None of these

**Answer:(b) 5**

9, When does top value of the stack changes?

(a) Before deletion

(b) While checking underflow

(c) At the time of deletion

(d) After deletion

(e) None of these

**Answer:(d) After deletion **

10. ....... IS Known as a greedy algorithm, because it chooses

at each step the cheapest edge to add to sub graph S.

(a) Kruskal’s algorithm

(b) Prim’s algorithm

(c) Dijkstra algorithm

(d) Bellman ford algorithm

(e) None of these

**Answer:(b) Prim’s algorithm**

11. The result of prim’s algorithm is a total time bound

Of ..........

(a) O(log n)

(b) O(m + nlog n)

(c) O(mn)

(d) O(m log n)

(e) None of these

**Answer:(a) O(log n) **

12. Which function plays an important role in returning the

address of memory block allocated to locate / store a node

especially while declaring ' top ' in the linked representation of

the Stack?

(a) galloc ()

(b) falloc ()

(c) malloc ()

(d) calloc ()

(e) None of these

**Answer:(c) malloc () **

13.Which of the following statements is/are TRUE for an

undirected graph?

(i) Number of odd degree vertices is even

(ii) Sum of degrees of all vertices is even

(a) Only I

(b) Only ii

(c)Both i and ii

(d) Neitheri nor ii

(e)None of these

**Answer:(c)Both i and ii **

14. The Average case occurs in linear search algorithm

(a) When item is somewhere in the middle of the array

(b) When item is not the array at all

(c) When item is the last element in the array

(d) Item is the last element in the array or item is not there at all

(e) None of these

**Answer:(c) When item is the last element in the array**

15.Which of the following is not the required condition for binary

search algorithm?

(a) The list must be sorted

(b) There should be the direct access to the middle element in

any sub list

(c) There must be mechanism to delete and/or insert elements in

list.

(d) Both (b) and (a)

(e) None of these

**Answer:(c) There must be mechanism to delete and/or insert elements in list**

16. For a linear search in an array of n elements the time

complexity for best, worst and average case are wu. ,

and ....... respectively.

(a) O(n), O(1), and O(n/2)

(b) O(1), O(n) and O(n/2)

(c) O(1),0(n) and O(n)

(d) O(1), O(n) and (n-1/2)

(e) None of these

**Answer:(c) O(1),0(n) and O(n)**

17. Which of the following sorting methods will be the best if

number of swapping done, is the only measure of efficiently?

(a) Bubble sort

(b) Selection sort

(c) Insertion sort

(d) Quick sort

(e) None of these

**Answer:(b) Selection sort**

18. The maximum number of comparisons needed to sort 7 items

using radix sort is (assume each item is 4 digit decimal number)

(a) 280

(b) 40

(c) 47

(d) 38

(e) None of these

**Answer:(a) 280 **

19. Which of the following statements are correct?

I. If each tree node contains a father field, then it's not necessary to

use either stack or threads

II. Traversal using father pointers is more time efficient than

traversal of a threaded tree

III.A in-threaded binary tree is defined as binary tree that is both

left-in threaded and right-in threaded.

(a) I and III

(b) I and III

(c) land II (d) None of these

(e) Both (a) and (b)

**Answer:(b) I and III**

20. If each node in a tree has value greater the every value in its

left sub tree and has value less than every value in its right sub

tree, the tree is called

(a) Complete tree

(b) Full binary tree

(c) Binary search tree

(d) AVL tree

(e) None of these

**Answer:(c) Binary search tree **