# 550+ Data Structures (DS) Solved MCQs

Chapters

Chapter: Linear Data Structures - List
1.

## Which of these best describes an array?

A. A data structure that shows a hierarchical behaviour
B. Container of objects of similar types
C. Arrays are immutable once initialised
D. Array is not a data structure
Answer» B. Container of objects of similar types
2.

## How do you initialize an array in C?

A. int arr[3] = (1,2,3);
B. int arr(3) = {1,2,3};
C. int arr[3] = {1,2,3};
D. int arr(3) = (1,2,3);
Answer» C. int arr[3] = {1,2,3};
3.

## How do you instantiate an array in Java?

A. int arr[] = new int(3);
B. int arr[];
C. int arr[] = new int[3];
D. int arr() = new int(3);
Answer» C. int arr[] = new int[3];
4.

A. int[] arr;
B. int arr[[]];
C. int[][]arr;
D. int[[]] arr;
5.

## When does the ArrayIndexOutOfBoundsException occur?

A. Compile-time
B. Run-time
C. Not an error
D. Not an exception at all
6.

## Which of the following concepts make extensive use of arrays?

A. Binary trees
B. Scheduling of processes
C. Caching
D. Spatial locality
7.

## What are the advantages of arrays?

A. Objects of mixed data types can be stored
B. Elements in an array cannot be sorted
C. Index of first element of an array is 1
D. Easier to store elements of same data type
Answer» D. Easier to store elements of same data type
8.

## What are the disadvantages of arrays?

A. Data structure like queue or stack cannot be implemented
B. There are chances of wastage of memory space if elements inserted in an array are lesser than the allocated size
C. Index value of an array can be negative
D. Elements are sequentially accessed
Answer» B. There are chances of wastage of memory space if elements inserted in an array are lesser than the allocated size
9.

A. 15
B. 19
C. 11
D. 60
10.

A. 0
B. -1
C. 2
D. 1
11.

## Elements in an array are accessed

A. randomly
B. sequentially
C. exponentially
D. logarithmically
12.

## Which of the following is not a disadvantage to the usage of array?

A. Fixed size
B. There are chances of wastage of memory space if elements inserted in an array are lesser than the allocated size
C. Insertion based on position
D. Accessing elements at specified positions
Answer» D. Accessing elements at specified positions
13.

## What is the time complexity of inserting at the end in dynamic arrays?

A. O(1)
B. O(n)
C. O(logn)
D. Either O(1) or O(n)
Answer» D. Either O(1) or O(n)
14.

A. O(1)
B. O(n)
C. O(logn)
D. O(n2)
15.

## 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(logn)
16.

## Which of these is not an application of linked list?

A. To implement file systems
B. For separate chaining in hash-tables
C. To implement non-binary trees
D. Random Access of elements
Answer» D. Random Access of elements
17.

## Which of the following is false about a doubly linked list?

A. We can navigate in both the directions
B. It requires more space than a singly linked list
C. The insertion and deletion of a node take a bit longer
D. Implementing a doubly linked list is easier than singly linked list
18.

A. O(nlogn)
B. O(logn)
C. O(n)
D. O(1)
19.

## What differentiates a circular linked list from a normal linked list?

A. You cannot have the ‘next’ pointer point to null in a circular linked list
B. It is faster to traverse the circular linked list
C. You may or may not have the ‘next’ pointer point to null in a circular linked list
Answer» C. You may or may not have the ‘next’ pointer point to null in a circular linked list
20.

A. O(n)
B. O(nlogn)
C. O(1)
D. O(n2)
21.

## Which of the following application makes use of a circular linked list?

A. Undo operation in a text editor
B. Recursive function calls
C. Allocating CPU to resources
D. Implement Hash Tables
Answer» C. Allocating CPU to resources
22.

## Which of the following is false about a circular linked list?

A. Every node has a successor
B. Time complexity of inserting a new node at the head of the list is O(1)
C. Time complexity for deleting the last node is O(n)
D. We can traverse the whole circular linked list by starting from any point
Answer» B. Time complexity of inserting a new node at the head of the list is O(1)
23.

## Consider a small circular linked list. How to detect the presence of cycles in this list effectively?

A. Keep one node as head and traverse another temp node till the end to check if its ‘next points to head
B. Have fast and slow pointers with the fast pointer advancing two nodes at a time and slow pointer advancing by one node at a time
C. Cannot determine, you have to pre-define if the list contains cycles
D. Circular linked list itself represents a cycle. So no new cycles cannot be generated
Answer» B. Have fast and slow pointers with the fast pointer advancing two nodes at a time and slow pointer advancing by one node at a time
24.

## A linear collection of data elements where the linear node is given by means of pointer is called?

B. Node list
C. Primitive list
D. Unordered list
25.

## In linked list each node contain minimum of two fields. One field is data field to store the data second field is?

A. Pointer to character
B. Pointer to integer
C. Pointer to node
D. Node
26.

A. O(1)
B. O(n)
C. θ(n)
D. θ(1)
27.

A. O(1)
B. O(n)
C. O(n2)
D. O(n3)
28.

A. O(1)
B. O(n)
C. O(n2)
D. O(n4)
29.

A. O(1)
B. O(n)
C. O(n2)
D. O(n3)
30.

## The concatenation of two list can performed in O(1) time. Which of the following variation of linked list can be used?

D. Array implementation of list
31.

## Which of the following c code is used to create new node?

A. ptr = (NODE*)malloc(sizeof(NODE));
B. ptr = (NODE*)malloc(NODE);
C. ptr = (NODE*)malloc(sizeof(NODE*));
D. ptr = (NODE)malloc(sizeof(NODE));
Chapter: Linear Data Structures -Stacks and Queues
32.

A. Create
B. Push
C. Evaluation
D. Pop
33.

A. Create
B. Push
C. Evaluation
D. Pop
34.

## In a stack, if a user tries to remove an element from empty stack it is called

A. Underflow
B. Empty collection
C. Overflow
D. Garbage Collection
35.

A. Overflow
B. Crash
C. Underflow
D. User flow
36.

## Entries in a stack are “ordered”. What is the meaning of this statement?

A. A collection of stacks is sortable
B. Stack entries may be compared with the ‘<‘ operation
C. The entries are stored in a linked list
D. There is a Sequential entry that is one by one
Answer» D. There is a Sequential entry that is one by one
37.

## Which of the following is not the application of stack?

A. A parentheses balancing program
B. Tracking of local variables at run time
C. Compiler Syntax Analyzer
D. Data Transfer between two asynchronous process
Answer» D. Data Transfer between two asynchronous process
38.

A. 1
B. 2
C. none
D. none
39.

A. 1
B. 40
C. 74
D. -18
40.

## The postfix form of the expression (A+ B)*(C*D- E)*F / G is?

A. AB+ CD*E – FG /**
B. AB + CD* E – F **G /
C. AB + CD* E – *F *G /
D. AB + CDE * – * F *G /
Answer» C. AB + CD* E – *F *G /
41.

A. Stack
B. Queue
C. Array
D. Tree
42.

B. Stack
C. Queue
D. Tree
43.

A. Heap
B. Binary Tree
C. Array
D. Stack
44.

A. *AB/CD+
B. AB*CD/+
C. A*BC+/D
D. ABCD+/*
45.

A. Branch
B. Tree
C. Queue
D. Stack
46.

A. -/*^ACBDE
B. -ABCD*^DE
C. -A/B*C^DE
D. -A/BC*^DE
47.

A. X
B. X+S
C. S
D. none
48.

## The prefix form of an infix expression (p + q) – (r * t) is?

A. + pq – *rt
B. – +pqr * t
C. – +pq * rt
D. – + * pqrt
Answer» C. – +pq * rt
49.

A. Queue
B. Stack
C. Array
D. List
50.

## When an operand is read, which of the following is done?

A. It is placed on to the output
B. It is placed in operator stack
C. It is ignored
D. Operator stack is emptied
Answer» A. It is placed on to the output
51.

## What should be done when a left parenthesis ‘(‘ is encountered?

A. It is ignored
B. It is placed in the output
C. It is placed in the operator stack
D. The contents of the operator stack is emptied
Answer» C. It is placed in the operator stack
52.

A. (a+b)*(c+d)
B. ab+c*
C. +ab
D. abc+*
53.

A. O(N log N)
B. O(N)
C. O(N2)
D. O(M log N)
54.

## Which of the following statement is incorrect with respect to infix to postfix conversion algorithm?

A. operand is always placed in the output
B. operator is placed in the stack when the stack operator has lower precedence
C. parenthesis are included in the output
D. higher and equal priority operators follow the same condition
Answer» C. parenthesis are included in the output
55.

## In infix to postfix conversion algorithm, the operators are associated from?

A. right to left
B. left to right
C. centre to left
D. centre to right
56.

A. Queue
B. Stack
C. Tree
57.

A. Stack
B. Array
C. Queue
D. Tree
58.

## A queue follows

A. FIFO (First In First Out) principle
B. LIFO (Last In First Out) principle
C. Ordered array
D. Linear tree
Answer» A. FIFO (First In First Out) principle
59.

## Circular Queue is also known as

A. Ring Buffer
B. Square Buffer
C. Rectangle Buffer
D. Curve Buffer
60.

A. ABCD
B. DCBA
C. DCAB
D. ABDC
61.

## A data structure in which elements can be inserted or deleted at/from both the ends but not in the middle is?

A. Queue
B. Circular queue
C. Dequeue
D. Priority queue
62.

## A normal queue, if implemented using an array of size MAX_SIZE, gets full when

A. Rear = MAX_SIZE – 1
B. Front = (rear + 1)mod MAX_SIZE
C. Front = rear + 1
D. Rear = front
Answer» A. Rear = MAX_SIZE – 1
63.

## Queues serve major role in

A. Simulation of recursion
B. Simulation of arbitrary linked list
C. Simulation of limited resource allocation
D. Simulation of heap sort
Answer» C. Simulation of limited resource allocation
64.

## Which of the following is not the type of queue?

A. Ordinary queue
B. Single ended queue
C. Circular queue
D. Priority queue
65.

A. Array
B. List
C. Heap
D. Tree
66.

## Which of the following is not an application of priority queue?

A. Huffman codes
B. Interrupt handling in operating system
C. Undo operation in text editors
D. Bayesian spam filter
Answer» C. Undo operation in text editors
67.

A. O(nlogn)
B. O(logn)
C. O(n)
D. O(n2)
68.

## What is not a disadvantage of priority scheduling in operating systems?

A. A low priority process might have to wait indefinitely for the CPU
B. If the system crashes, the low priority systems may be lost permanently
C. Interrupt handling
D. Indefinite blocking
69.

## Which of the following is not an advantage of priority queue?

A. Easy to implement
B. Processes with different priority can be efficiently handled
C. Applications with differing requirements
D. Easy to delete elements in any case
Answer» D. Easy to delete elements in any case
70.

A. O(nlogn)
B. O(logn)
C. O(n)
D. O(n2)
71.

## What is a dequeue?

A. A queue with insert/delete defined for both front and rear ends of the queue
B. A queue implemented with a doubly linked list
C. A queue implemented with both singly and doubly linked lists
D. A queue with insert/delete defined for front side of the queue
Answer» A. A queue with insert/delete defined for both front and rear ends of the queue
72.

## What are the applications of dequeue?

A. A-Steal job scheduling algorithm
B. Can be used as both stack and queue
C. To find the maximum of all sub arrays of size k
D. To avoid collision in hash tables
Answer» D. To avoid collision in hash tables
73.

## Which of the following properties is associated with a queue?

A. First In Last Out
B. First In First Out
C. Last In First Out
D. Last In Last Out
Answer» B. First In First Out
74.

## In a circular queue, how do you increment the rear end of the queue?

A. rear++
B. (rear+1) % CAPACITY
C. (rear % CAPACITY)+1
D. rear–
75.

## What is the term for inserting into a full queue known as?

A. overflow
B. underflow
C. null pointer exception
D. program won’t be compiled
76.

A. O(logn)
B. O(nlogn)
C. O(n)
D. O(1)
77.

## What is the need for a circular queue?

A. effective usage of memory
B. easier computations
C. to delete elements based on priority
D. implement LIFO principle in queues
Answer» A. effective usage of memory
78.

## What is the space complexity of a linear queue having n elements?

A. O(n)
B. O(nlogn)
C. O(logn)
D. O(1)
Chapter: Non Linear Data Structures - Trees
79.

A. 0
B. 1
C. 2
D. 3
80.

## The following given tree is an example for?

A. Binary tree
B. Binary search tree
C. Fibonacci tree
D. none
81.

A. 1
B. 2
C. 3
D. 4
82.

## What is the traversal strategy used in the binary tree?

A. depth-first traversal
C. random traversal
D. Priority traversal
83.

A. 1
B. 2
C. 3
D. 4
84.

## What operation does the following diagram depict?

A. inserting a leaf node
B. inserting an internal node
C. deleting a node with 0 or 1 child
D. none
Answer» C. deleting a node with 0 or 1 child
85.

A. n+O(n)
B. 2n+O(n)
C. n/2
D. n
86.

A. O(N)
B. O(√N)
C. O(N2)
D. O(log N)
87.

A. 1
B. 4
C. 2
D. 3
88.

A. 2i+1
B. 2i+2
C. 2i
D. 4i
89.

A. (i+1)/2
B. (i-1)/2
C. i/2
D. 2i/2
90.

## Which of the following properties are obeyed by all three tree – traversals?

A. Left subtrees are visited before right subtrees
B. Right subtrees are visited before left subtrees
C. Root node is visited before left subtree
D. Root node is visited before right subtree
Answer» A. Left subtrees are visited before right subtrees
91.

## For the tree below, write the pre-order traversal.

A. 2, 7, 2, 6, 5, 11, 5, 9, 4
B. 2, 7, 5, 2, 6, 9, 5, 11, 4
C. 2, 5, 11, 6, 7, 4, 9, 5, 2
D. none
Answer» A. 2, 7, 2, 6, 5, 11, 5, 9, 4
92.

## For the tree below, write the post-order traversal.

A. 2, 7, 2, 6, 5, 11, 5, 9, 4
B. 2, 7, 5, 2, 6, 9, 5, 11, 4
C. 2, 5, 11, 6, 7, 4, 9, 5, 2
D. none
Answer» C. 2, 5, 11, 6, 7, 4, 9, 5, 2
93.

A. O(1)
B. O(n)
C. O(logn)
D. O(nlogn)
94.

A. O(1)
B. O(nlogd)
C. O(logd)
D. O(d)
95.

## To obtain a prefix expression, which of the tree traversals is used?

A. Level-order traversal
B. Pre-order traversal
C. Post-order traversal
D. In-order traversal
96.

## Consider the following data. The pre order traversal of a binary tree is A, B, E, C, D. The in order traversal of the same binary tree is B, E, A, D, C. The level order sequence for the binary tree is

A. A, C, D, B, E
B. A, B, C, D, E
C. A, B, C, E, D
D. D, B, E, A, C
Answer» B. A, B, C, D, E
97.

A. 15
B. 3
C. 5
D. 8
98.

## The post-order traversal of a binary tree is O P Q R S T. Then possible pre-order traversal will be

A. T Q R S O P
B. T O Q R P S
C. T Q O P S R
D. T Q O S P R
Answer» C. T Q O P S R
99.

## A binary search tree contains values 7, 8, 13, 26, 35, 40, 70, 75. Which one of the following is a valid post-order sequence of the tree provided the pre-order sequence as 35, 13, 7, 8, 26, 70, 40 and 75?

A. 7, 8, 26, 13, 75, 40, 70, 35
B. 26, 13, 7, 8, 70, 75, 40, 35
C. 7, 8, 13, 26, 35, 40, 70, 75
D. 8, 7, 26, 13, 40, 75, 70, 35
Answer» D. 8, 7, 26, 13, 40, 75, 70, 35
100.

## Which of the following pair’s traversals on a binary tree can build the tree uniquely?

A. post-order and pre-order
B. post-order and in-order
C. post-order and level order
D. level order and preorder