Solved MCQ Questions On Data Structure Set-2

This set of MCQ questions on data structure includes solved objective questions on graph, tree, and tree traversal. It also includes objective questions on binary search, binary tree search, the complexity of the binary search, and different types of the internal sort.

1. A directed graph is ………………. if there is a path from each vertex to every other vertex in the digraph.
A) Weakly connected
B) Strongly Connected
C) Tightly Connected
D) Linearly Connected

2. In the …………….. traversal we process all of a vertex’s descendants before we move to an adjacent vertex.
A) Depth First
B) Breadth First
C) With First
D) Depth Limited

3. State True of False.
i) Network is a graph that has weights or costs associated with it.
ii) An undirected graph which contains no cycles is called a forest.
iii) A graph is said to be complete if there is no edge between every pair of vertices.
A) True, False, True
B) True, True, False
C) True, True, True
D) False, True, True

4. Match the following.
a) Completeness i) How long does it take to find a solution
b) Time Complexity ii) How much memory need to perform the search.
c) Space Complexity iii) Is the strategy guaranteed to find the solution when there in one.
A) a-iii, b-ii, c-i
B) a-i, b-ii, c-iii
C) a-iii, b-i, c-ii
D) a-i, b-iii, c-ii

5. The number of comparisons done by sequential search is ………………
A) (N/2)+1
B) (N+1)/2
C) (N-1)/2
D) (N+2)/2

6. In ……………, search start at the beginning of the list and check every element in the list.
A) Linear search
B) Binary search
C) Hash Search
D) Binary Tree search

7. State True or False.
i) Binary search is used for searching in a sorted array.
ii) The time complexity of binary search is O(logn).
A) True, False
B) False, True
C) False, False
D) True, True

8. Which of the following is not the internal sort?
A) Insertion Sort
B) Bubble Sort
C) Merge Sort
D) Heap Sort

9. State True or False.
i) An undirected graph which contains no cycles is called forest.
ii) A graph is said to be complete if there is an edge between every pair of vertices.
A) True, True
B) False, True
C) False, False
D) True, False

10. A graph is said to be ……………… if the vertices can be split into two sets V1 and V2 such there are no edges between two vertices of V1 or two vertices of V2.
A) Partite
B) Bipartite
C) Rooted
D) Bisects

11. In a queue, the initial values of front pointer f rare pointer r should be …….. and ……….. respectively.
A) 0 and 1
B) 0 and -1
C) -1 and 0
D) 1 and 0

12. In a circular queue the value of r will be ..
A) r=r+1
B) r=(r+1)% [QUEUE_SIZE – 1]
C) r=(r+1)% QUEUE_SIZE
D) r=(r-1)% QUEUE_SIZE

13. Which of the following statement is true?
i) Using singly linked lists and circular list, it is not possible to traverse the list backwards.
ii) To find the predecessor, it is required to traverse the list from the first node in case of singly linked list.
A) i-only
B) ii-only
C) Both i and ii
D) None of both

14. The advantage of …………….. is that they solve the problem if sequential storage representation. But disadvantage in that is they are sequential lists.
A) Lists
B) Linked Lists
C) Trees
D) Queues

15. What will be the value of top, if there is a size of stack STACK_SIZE is 5
A) 5
B) 6
C) 4
D) None

16. ………… is not the operation that can be performed on queue.
A) Insertion
B) Deletion
C) Retrieval
D) Traversal

17. There is an extra element at the head of the list called a ……….
A) Antinel
B) Sentinel
C) List header
D) List head

18. A graph is a collection of nodes, called ………. And line segments called arcs or ……….. that connect pair of nodes.
A) vertices, edges
B) edges, vertices
C) vertices, paths
D) graph node, edges

19. A ……….. is a graph that has weights of costs associated with its edges.
A) Network
B) Weighted graph
C) Both A and B
D) None A and B

20. In general, the binary search method needs no more than ……………. comparisons.
A) [log2n]-1
B) [logn]+1
C) [log2n]
D) [log2n]+1

Answers:

1. B) Strongly Connected
2. A) Depth First
3. B) True, True, False
4. C) a-iii, b-i, c-ii
5. B) (N+1)/2
6. A) Linear search
7. D) True, True
8. C) Merge Sort
9. A) True, True10. B) Bipartite
11. B) 0 and -1
12. C) r=(r+1)% QUEUE_SIZE
13. C) Both i and ii
14. B) Linked Lists
15. C) 4
16. D) Traversal
17. B) Sentinel
18. A) vertices, edges
19. C) Both A and B
20. D) [log2n]+1