Data Structure MCQ SET-4

1. Which of the following points is/are true about linked list data structure when it is compared with array ?

(A) Arrays have better cache locality that can make them better in terms of performance.
(B) It is easy to insert and delete elements in linked list.
(C) The size of array has to be pre-decided, linked lists can change their size any time.
(D) All of the above

2. In the worst case, a binary search tree will take how much time to search an element ?

(A) O(n)
(B) O(log n)
(C) O(n² )
(D) O(n log n)

3. What is the space complexity for deleting a linked list?

(A) O(1)
(B) O(n)
(C) Either O(1) or O(n)
(D) O(log n)

4. The situation when in a linked list START-NULL is

(A) Underflow
(B) Overflow
(C) Housefull
(D) Saturated

5. What would be the asymoptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list ?

(A) O(1)
(B) O(n)
(C) O(n)
(D) O(1)

6. What kind of linked list is best to answer question like
*What is the item at position n*?

(A) Singly linked list
(B) Doubly linked list
(C) Circular linked list
(D) Array implementation of linked list

7. A variation of linked list is cirular linked list, in which the last node in the list points to first node of the list. One problem with this type of list is

(A) It waste memory space since the pointer head already points to the first node and thus the list node does not need to point to the first node
(B) It is not possible to add a node at the end of the list
(C) It is difficult to traverse the list as pointer of the last node is now not NULL
(D) All of the above

8. Each node in a linked list must contain at least

(A) Three fields
(B) Two fields
(C) Four fields
(D) Five fields

9. A linear list in which the last node points to the first node is

(A) Singly linked list
(B) Circular linked list
(C) Doubly linked list
(D) None of the above

10. In a linked list, insertion can be done as

(A) beginning
(B) end
(C) middle
(D) All of the above

11. What is the worst case run-time complexity of binary search algorithm?

(A) O(n² )
(B) O(n^{log n} )
(C) O(n³ )
(D) O(n)

12. push() and pop() functions are found in

(A) queues
(B) list
(C) stacks
(D) trees

13. Binary search tree has average case run-time complexity of O(log n). What could be the worst case ?

(A) O(n)
(B) O(n² )
(C) O(n³)
(D) None of the above

14. What will be the running-time of Dijkstra’s single-source shortest path algorithm, if the graph G(V,E) is stored in the form of adjacency list and binary heap is used?

(A) O(|V|²)
(B) O(|V|log|V|)
(C) O(|E|+|V|log|V|)
(D) None of the above

15. Tower of Hanoi is a classic example of

(A) Divide and conquer
(B) Recursive approach
(C)(B) but not (A)
(D) Both (A) and (B)

16. If locality is a concern, you can use ______ to traverse the graph.

(A) Breadth-first search
(B) Depth-first search
(C) Either BFS or DFS
(D) None of the above

17. Which data structure is used for balancing of symbols?

(A) Queue
(B) Stack
(C) Tree
(D) Graph

18. Which data structure is most efficient to find the top 10 largest items out of 1 million items stored in file?

(A) Min heap
(B) Max heap
(C) Binary search tree
(D) AVL tree

19. A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set :

(A) A heap can be used but not a balanced binary search tree
(B) A balanced binary search tree can be used but not a heap
(C) Both balanced binary search tree and heap can be used
(D) Neither balanced binary search tree nor heap can be used

20. The most appropriate matching for the following pairs is
X. Depth-first search 1. Heap
Y. Breadth-first 2.Queue
Z. Sorting 3.Stack

(A) X-1, Y-2, Z-3
(B) X-3, Y-1, Z-2
(C) X-3, Y-2, Z-1
(D) X-2, Y-3, Z-1