DS ALL MCQs

Linked List
1. A linear collection of data elements where the linear node is given by means of pointer is called?
a) Linked list
b) Node list
c) Primitive list
d) Unordered list
View Answer
Answer: a
Explanation: In Linked list each node has its own data and the address of next node. These nodes are linked
by using pointers. Node list is an object that consists of a list of all nodes in a document with in a particular
selected set of nodes.
2. Consider an implementation of unsorted singly linked list. Suppose it has its representation with a head
pointer only. Given the representation, which of the following operation can be implemented in O(1) time?
i) Insertion at the front of the linked list

ii) Insertion at the end of the linked list
iii) Deletion of the front node of the linked list
iv) Deletion of the last node of the linked list
a) I and II
b) I and III
c) I, II and III
d) I, II and IV
View Answer
Answer: b
Explanation: We know the head node in the given linked list. Insertion and deletion of elements at the front
of the linked list completes in O (1) time whereas for insertion and deletion at the last node requires to
traverse through every node in the linked list. Suppose there are n elements in a linked list, we need to
traverse through each node. Hence time complexity becomes O(n).
3. In linked list each node contains a 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
View Answer
Answer: c
Explanation: Each node in a linked list contains data and a pointer (reference) to the next node. Second field
contains pointer to node.
4. What would be the asymptotic 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) θ(n)
d) θ(1)
View Answer
Answer: c
Explanation: In case of a linked list having n elements, we need to travel through every node of the list to
add the element at the end of the list. Thus asymptotic time complexity is θ(n).
5. What would be the asymptotic time complexity to insert an element at the front of the linked list (head is
known)?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)
View Answer
Answer: a
Explanation: To add an element at the front of the linked list, we will create a new node which holds the data
to be added to the linked list and pointer which points to head position in the linked list. The entire thing
happens within O (1) time. Thus the asymptotic time complexity is O (1).
6. What would be the asymptotic time complexity to find an element in the linked list?
a) O(1)
b) O(n)
c) O(n2)
d) O(n4)
View Answer
Answer: b
Explanation: If the required element is in the last position, we need to traverse the entire linked list. This will
take O (n) time to search the element.
7. What would be the asymptotic time complexity to insert an element at the second position in the linked
list?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)
View Answer
Answer: a
Explanation: A new node is created with the required element. The pointer of the new node points the node
to which the head node of the linked list is also pointing. The head node pointer is changed and it points to
the new node which we created earlier. The entire process completes in O (1) time. Thus the asymptotic time
complexity to insert an element in the second position of the linked list is O (1).
8. The concatenation of two lists can be performed in O(1) time. Which of the following variation of the
linked list can be used?
a) Singly linked list
b) Doubly linked list
c) Circular doubly linked list
d) Array implementation of list
View Answer
Answer: c
Explanation: We can easily concatenate two lists in O (1) time using singly or doubly linked list, provided
that we have a pointer to the last node at least one of the lists. But in case of circular doubly linked lists, we
will break the link in both the lists and hook them together. Thus circular doubly linked list concatenates two
lists in O (1) time.
9. Consider the following definition in c programming language.
struct node
{
int data;
struct node * next;
}
typedef struct node NODE;
NODE *ptr;
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));
View Answer
Answer: a
Explanation: As it represents the right way to create a node.
1. What kind of linked list is best to answer questions like “What is the item at position n?”
c) Circular linked list
d) Array implementation of linked list
View Answer
Answer: d
Explanation: Arrays provide random access to elements by providing the index value within square brackets.
In the linked list, we need to traverse through each element until we reach the nth position. Time taken to
access an element represented in arrays is less than the singly, doubly and circular linked lists. Thus, array
implementation is used to access the item at the position n.
2. Linked lists are not suitable for the implementation of ___________

a) Insertion sort
b) Radix sort
c) Polynomial manipulation
d) Binary search
View Answer
Answer: d
Explanation: It cannot be implemented using linked lists.
3. Linked list is considered as an example of ___________ type of memory allocation.
a) Dynamic
b) Static
c) Compile time
d) Heap
View Answer
Answer: a
Explanation: As memory is allocated at the run time.
4. In Linked List implementation, a node carries information regarding ___________

a) Data
b) Link
c) Data and Link
d) Node
View Answer
Answer: b
Explanation: A linked list is a collection of objects linked together by references from an object to another
object. By convention these objects are names as nodes. Linked list consists of nodes where each node
contains one or more data fields and a reference(link) to the next node.
5. Linked list data structure offers considerable saving in _____________

a) Computational Time
b) Space Utilization
c) Space Utilization and Computational Time
d) Speed Utilization
View Answer
Answer: c
Explanation: Linked lists saves both space and time.
6. Which of the following points is/are not true about Linked List data structure when it is compared with an
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) Random access is not allowed in a typical implementation of Linked Lists
d) Access of elements in linked list takes less time than compared to arrays
View Answer
Answer: d
Explanation: To access an element in a linked list, we need to traverse every element until we reach the
desired element. This will take more time than arrays as arrays provide random access to its elements.
7. What does the following function do for a given Linked List with first node as head?
void fun1(struct node* head)

{
if(head == NULL)
return;
fun1(head->next);
printf("%d ", head->data);
}
a) Prints all nodes of linked lists

b) Prints all nodes of linked list in reverse order
c) Prints alternate nodes of Linked List
d) Prints alternate nodes in reverse order
View Answer
Answer: b
Explanation: fun1() prints the given Linked List in reverse manner.
For Linked List 1->2->3->4->5, fun1() prints 5->4->3->2->1.
8. Which of the following sorting algorithms can be used to sort a random linked list with minimum time
complexity?
a) Insertion Sort
b) Quick Sort
c) Heap Sort
d) Merge Sort
View Answer
Answer: d
Explanation: Both Merge sort and Insertion sort can be used for linked lists. The slow random-access
performance of a linked list makes other algorithms (such as quicksort) perform poorly, and others (such as
heapsort) completely impossible. Since worst case time complexity of Merge Sort is O(nLogn) and Insertion
sort is O(n2), merge sort is preferred.
7. You are given pointers to first and last nodes of a singly linked list, which of the following operations are
dependent on the length of the linked list?
a) Delete the first element
b) Insert a new element as a first element
c) Delete the last element of the list
d) Add a new element at the end of the list
View Answer
Answer: c
Explanation: Deletion of the first element of the list is done in O (1) time by deleting memory and changing
the first pointer.
Insertion of an element as a first element can be done in O (1) time. We will create a node that holds data
and points to the head of the given linked list. The head pointer was changed to a newly created node.
Deletion of the last element requires a pointer to the previous node of last, which can only be obtained by
traversing the list. This requires the length of the linked list.
Adding a new element at the end of the list can be done in O (1) by changing the pointer of the last node to
the newly created node and last is changed to a newly created node.
8. 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
View Answer
Answer: d
Explanation: The worst-case happens if the required element is at last or the element is absent in the list. For
this, we need to compare every element in the linked list. If n elements are there, n comparisons will happen
in the worst case.
5. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given
element is?
a) log 2 n
b) n⁄2
c) log 2 n – 1
d) n
View Answer
Answer: d
Explanation: In the worst case, the element to be searched has to be compared with all elements of the linked
list.
6. Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not
given, can we delete the node X from given linked list?
a) Possible if X is not last node
b) Possible if size of linked list is even
c) Possible if size of linked list is odd
d) Possible if X is not first node
View Answer
Answer: a
Explanation: Following are simple steps.
1. 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
View Answer
Answer: d
Explanation: Array elements can be accessed in two steps. First, multiply the size of the data type with the
specified position, second, add this value to the base address. Both of these operations can be done in
constant time, hence accessing elements at a given index/position is faster.
2. 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)
View Answer
Answer: d
Explanation: Depending on whether the array is full or not, the complexity in dynamic array varies. If you
try to insert into an array that is not full, then the element is simply stored at the end, this takes O(1) time. If
you try to insert into an array which is full, first you will have to allocate an array with double the size of the
current array and then copy all the elements into it and finally insert the new element, this takes O(n) time.
3. What is the time complexity to count the number of elements in the linked list?
a) O(1)
b) O(n)
c) O(logn)
d) O(n2)
View Answer
Answer: b
Explanation: To count the number of elements, you have to traverse through the entire list, hence complexity
is O(n).
6. 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)
View Answer
Answer: a
Explanation: You need a temp variable to keep track of current node, hence the space complexity is O(1).
8. Which of these is not an application of a 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
View Answer
Answer: d
Explanation: To implement file system, for separate chaining in hash-tables and to implement non-binary
trees linked lists are used. Elements are accessed sequentially in linked list. Random access of elements is
not an applications of linked list.
1. 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
View Answer
Answer: d
Explanation: A doubly linked list has two pointers ‘left’ and ‘right’ which enable it to traverse in either
direction. Compared to singly liked list which has only a ‘next’ pointer, doubly linked list requires extra
space to store this extra pointer. Every insertion and deletion requires manipulation of two pointers, hence it
takes a bit longer time. Implementing doubly linked list involves setting both left and right pointers to
correct nodes and takes more time than singly linked list.
3. What is a memory efficient double linked list?

a) Each node has only one pointer to traverse the list back and forth
b) The list has breakpoints for faster traversal
c) An auxiliary singly linked list acts as a helper list to traverse through the doubly linked list
d) A doubly linked list that uses bitwise AND operator for storing addresses
View Answer
Answer: a
Explanation: Memory efficient doubly linked list has only one pointer to traverse the list back and forth. The
implementation is based on pointer difference. It uses bitwise XOR operator to store the front and rear
pointer addresses. Instead of storing actual memory address, every node store the XOR address of previous
and next nodes.
5. How do you calculate the pointer difference in a memory efficient double linked list?
a) head xor tail
b) pointer to previous node xor pointer to next node
c) pointer to previous node – pointer to next node
d) pointer to next node – pointer to previous node
View Answer
Answer: b
Explanation: The pointer difference is calculated by taking XOR of pointer to previous node and pointer to
the next node.
6. What is the worst case time complexity of inserting a node in a doubly linked list?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)
View Answer
Answer: c
Explanation: In the worst case, the position to be inserted maybe at the end of the list, hence you have to
traverse through the entire list to get to the correct position, hence O(n).
1. 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
d) Head node is known in circular linked list
View Answer
Answer: c
Explanation: The ‘next’ pointer points to null only when the list is empty, otherwise it points to the head of
the list. Every node in a circular linked list can be a starting point(head).
4. What is the time complexity of searching for an element in a circular linked list?
a) O(n)
b) O(nlogn)
c) O(1)
d) O(n2)
View Answer
Answer: a
Explanation: In the worst case, you have to traverse through the entire list of n elements.
5. 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
View Answer
Answer: c
Explanation: Generally, round robin fashion is employed to allocate CPU time to resources which makes use
of the circular linked list data structure. Recursive function calls use stack data structure. Undo Operation in
text editor uses doubly linked lists. Hash tables uses singly linked lists.
9. 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
View Answer
Answer: b
Explanation: Time complexity of inserting a new node at the head of the list is O(n) because you have to
traverse through the list to find the tail node.
10. 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
View Answer
Answer: b
Explanation: Advance the pointers in such a way that the fast pointer advances two nodes at a time and slow
pointer advances one node at a time and check to see if at any given instant of time if the fast pointer points
to slow pointer or if the fast pointer’s ‘next’ points to the slow pointer. This is applicable for smaller lists.
1. What is the best case time complexity of deleting a node in a Singly Linked list?
a) O (n)
b) O (n2)
c) O (nlogn)
d) O (1)
View Answer
Answer: d
Explanation: Deletion of the head node in the linked list is taken as the best case. The successor of the head
node is changed to head and deletes the predecessor of the newly assigned head node. This process
completes in O(1) time.
2. Which of the following statements are not correct with respect to Singly Linked List(SLL) and Doubly
Linked List(DLL)?
a) Complexity of Insertion and Deletion at known position is O(n) in SLL and O(1) in DLL
b) SLL uses lesser memory per node than DLL
c) DLL has more searching power than SLL
d) Number of node fields in SLL is more than DLL
View Answer
Answer: d
Explanation: To insert and delete at known positions requires complete traversal of the list in worst case in
SLL, SLL consists of an item and a node field, while DLL has an item and two node fields, hence SLL
occupies lesser memory, DLL can be traversed both ways(left and right), while SLL can traverse in only one
direction, hence more searching power of DLL. Node fields in SLL is 2 (data and address of next node)
whereas in DLL is 3(data, address to next node, address to previous node).
6. What does ‘stack overflow’ refer to?

a) accessing item from an undefined stack
b) adding items to a full stack
c) removing items from an empty stack
d) index out of bounds exception
View Answer
Answer: b
Explanation: Adding items to a full stack is termed as stack underflow.
8. Consider these functions:
push() : push an element into the stack
pop() : pop the top-of-the-stack element
top() : returns the item stored in top-of-the-stack-node
What will be the output after performing these sequence of operations
push(20);
push(4);
top();
pop();
pop();
pop();
push(5);
top();
a) 20
b) 4
c) stack underflow
d) 5
View Answer
Answer: d
Explanation: 20 and 4 which were pushed are popped by the two pop() statements, the recent push() is 5,
hence top() returns 5.
9. Which of the following data structures can be used for parentheses matching?
a) n-ary tree
b) queue
c) priority queue
d) stack
View Answer
Answer: d
Explanation: For every opening brace, push it into the stack, and for every closing brace, pop it off the stack.
Do not take action for any other character. In the end, if the stack is empty, then the input has balanced
parentheses.
10. Minimum number of queues to implement stack is ___________

a) 3
b) 4
c) 1
d) 2
View Answer
Answer: c
Explanation: Use one queue and one counter to count the number of elements in the queue.
1. In linked list implementation of queue, if only front pointer is maintained, which of the following
operation take worst case linear time?
a) Insertion
b) Deletion
c) To empty a queue
d) Both Insertion and To empty a queue
View Answer
Answer: d
Explanation: Since front pointer is used for deletion, so worst time for the other two cases.
2. In linked list implementation of a queue, where does a new element be inserted?

a) At the head of link list
b) At the centre position in the link list
c) At the tail of the link list
d) At any position in the linked list
View Answer
Answer: c
Explanation: Since queue follows FIFO so new element inserted at last.
3. In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will
change during an insertion into a NONEMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) No pointer will be changed
View Answer
Answer: b
Explanation: Since queue follows FIFO so new element inserted at last.
4. In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will
change during an insertion into EMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) No pointer will be changed
View Answer
Answer: c
Explanation: Since its the starting of queue, so both values are changed.
5. In case of insertion into a linked queue, a node borrowed from the __________ list is inserted in the
queue.
a) AVAIL
b) FRONT
c) REAR
d) NULL
View Answer
Answer: a
Explanation: All the nodes are collected in AVAIL list.
advertisement
6. In linked list implementation of a queue, from where is the item deleted?
a) At the head of link list
b) At the centre position in the link list
c) At the tail of the link list
d) Node before the tail
View Answer
Answer: a
Explanation: Since queue follows FIFO so new element deleted from first.
7. In linked list implementation of a queue, the important condition for a queue to be empty is?
a) FRONT is null
b) REAR is null
c) LINK is empty
d) FRONT==REAR-1
View Answer
Answer: a
Explanation: Because front represents the deleted nodes.
8. The essential condition which is checked before insertion in a linked queue is?
a) Underflow
b) Overflow
c) Front value
d) Rear value
View Answer
Answer: b
Explanation: To check whether there is space in the queue or not.
9. The essential condition which is checked before deletion in a linked queue is?
a) Underflow
b) Overflow
c) Front value
d) Rear value
View Answer
Answer: a
Explanation: To check whether there is element in the list or not.
10. Which of the following is true about linked list implementation of queue?
a) In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes
must be removed from end
b) In push operation, if new nodes are inserted at the beginning, then in pop operation, nodes must be
removed from the beginning
c) In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed
from end
d) In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed
from beginning
View Answer
Answer: a
Explanation: It can be done by both the methods.
1. With what data structure can a priority queue be implemented?
a) Array
b) List
c) Heap
d) Tree
View Answer
Answer: d
Explanation: Priority queue can be implemented using an array, a list, a binary search tree or a heap,
although the most efficient one being the heap.
2. 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
View Answer
Answer: c
Explanation: Undo operation is achieved using a stack.
4. What is the time complexity to insert a node based on key in a priority queue?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
View Answer
Answer: c
Explanation: In the worst case, you might have to traverse the entire list.
6. 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
View Answer
Answer: c
Explanation: The lower priority process should wait until the CPU completes the processing higher priority
process. Interrupt handling is an advantage as interrupts should be given more priority than tasks at hand so
that interrupt can be serviced to produce desired results.
7. Which of the following is not an advantage of a 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
View Answer
Answer: d
Explanation: In worst case, the entire queue has to be searched for the element having the highest priority.
This will take more time than usual. So deletion of elements is not an advantage.
8. What is the time complexity to insert a node based on position in a priority queue?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
View Answer
Answer: c
Explanation: In the worst case, you might have to traverse the entire list.
1. 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
View Answer
Answer: a
Explanation: A dequeue or a double ended queue is a queue with insert/delete defined for both front and rear
ends of the queue.
4. 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
View Answer
Answer: d
Explanation: All of the mentioned can be implemented with a dequeue.
7. What is the time complexity of deleting from the rear end of the dequeue implemented with a singly
linked list?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
View Answer
Answer: c
Explanation: Since a singly linked list is used, first you have to traverse till the end, so the complexity is
O(n).
1. A linear list of elements in which deletion can be done from one end (front) and insertion can take place
only at the other end (rear) is known as _____________
a) Queue
b) Stack
c) Tree
d) Linked list
View Answer
Answer: a
Explanation: Linear list of elements in which deletion is done at front side and insertion at rear side is called
Queue. In stack we will delete the last entered element first.
2. The data structure required for Breadth First Traversal on a graph is?
a) Stack
b) Array
c) Queue
d) Tree
View Answer
Answer: c
Explanation: In Breadth First Search Traversal, BFS, starting vertex is first taken and adjacent vertices
which are unvisited are also taken. Again, the first vertex which was added as an unvisited adjacent vertex
list will be considered to add further unvisited vertices of the graph. To get the first unvisited vertex we need
to follows First In First Out principle. Queue uses FIFO principle.
3. A queue follows __________

a) FIFO (First In First Out) principle
b) LIFO (Last In First Out) principle
c) Ordered array
d) Linear tree
View Answer
Answer: a
Explanation: Element first added in queue will be deleted first which is FIFO principle.
4. Circular Queue is also known as ________

a) Ring Buffer
b) Square Buffer
c) Rectangle Buffer
d) Curve Buffer
View Answer
Answer: a
Explanation: Circular Queue is also called as Ring Buffer. Circular Queue is a linear data structure in which
last position is connected back to the first position to make a circle. It forms a ring structure.
5. If the elements “A”, “B”, “C” and “D” are placed in a queue and are deleted one at a time, in what order
will they be removed?
a) ABCD
b) DCBA
c) DCAB
d) ABDC
View Answer
Answer: a
Explanation: Queue follows FIFO approach. i.e. First in First Out Approach. So, the order of removal
elements are ABCD.
6. A data structure in which elements can be inserted or deleted at/from both ends but not in the middle is?
a) Queue
b) Circular queue
c) Dequeue
d) Priority queue
Answer: c
Explanation: In dequeuer, we can insert or delete elements from both the ends. In queue, we will follow first
in first out principle for insertion and deletion of elements. Element with least priority will be deleted in a
priority queue.
7. 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
View Answer
Answer: a
Explanation: When Rear = MAX_SIZE – 1, there will be no space left for the elements to be added in
queue. Thus queue becomes full.
8. 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
View Answer
Answer: c
Explanation: Simulation of recursion uses stack data structure. Simulation of arbitrary linked lists uses
linked lists. Simulation of resource allocation uses queue as first entered data needs to be given first priority
during resource allocation. Simulation of heap sort uses heap data structure.
9. Which of the following is not the type of queue?

a) Ordinary queue
b) Single ended queue
c) Circular queue
d) Priority queue
View Answer
Answer: b
Explanation: Queue always has two ends. So, single ended queue is not the type of queue.
Tree
1. How many children does a binary tree have?
a) 2
b) any number of children
c) 0 or 1 or 2
d) 0 or 1
View Answer
Answer: c
Explanation: Can have atmost 2 nodes.
2. What is/are the disadvantages of implementing tree using normal arrays?

a) difficulty in knowing children nodes of a node
b) difficult in finding the parent of a node
c) have to know the maximum number of nodes possible before creation of trees
d) difficult to implement
View Answer
Answer: c
Explanation: The size of array is fixed in normal arrays. We need to know the number of nodes in the tree
before array declaration. It is the main disadvantage of using arrays to represent binary trees.
3. What must be the ideal size of array if the height of tree is ‘l’?
a) 2l-1
b) l-1
c) l
d) 2l
View Answer
Answer: a
Explanation: Maximum elements in a tree (complete binary tree in worst case) of height ‘L’ is 2L-1. Hence
size of array is taken as 2L-1.
4. What are the children for node ‘w’ of a complete-binary tree in an array representation?
a) 2w and 2w+1
b) 2+w and 2-w
c) w+1/2 and w/2
d) w-1/2 and w+1/2
View Answer
Answer: a
Explanation: The left child is generally taken as 2*w whereas the right child will be taken as 2*w+1 because
root node is present at index 0 in the array and to access every index position in the array.
5. What is the parent for a node ‘w’ of a complete binary tree in an array representation when w is not 0?
a) floor(w-1/2)
b) ceil(w-1/2)
c) w-1/2
d) w/2
View Answer
Answer: a
Explanation: Floor of w-1/2 because we can’t miss a node.
6. If the tree is not a complete binary tree then what changes can be made for easy access of children of a
node in the array?
a) every node stores data saying which of its children exist in the array
b) no need of any changes continue with 2w and 2w+1, if node is at i
c) keep a seperate table telling children of a node
d) use another array parallel to the array with tree
View Answer
Answer: a
Explanation: Array cannot represent arbitrary shaped trees. It can only be used in case of complete trees. If
every node stores data saying that which of its children exists in the array then elements can be accessed
easily.
7. What must be the missing logic in place of missing lines for finding sum of nodes of binary tree in
alternate levels?
//e.g:-consider -complete binary tree:-height-3, [1,2,3,4,5,6,7]-answer must be 23

n=power(2,height)-1; //assume input is height and a[i] contains tree elements
for(i=1;i<=n;)
{
//present level is initialized to 1 and sum is initialized to 0
for(j=1;j<=pow(2,currentlevel-1);j++)
{
sum=sum+a[i];
i=i+1;
}
//missing logic
}
a)
i=i+pow(2,currentlevel);
currentlevel=currentlevel+2;
j=1;
b)
j=0;
c)
i=i-pow(2,currentlevel);
j=1;
d)
j=1;
View Answer
Answer: a
Explanation: The i value must skip through all nodes in the next level and current level must be one+next
level.
8. Consider a situation of writing a binary tree into a file with memory storage efficiency in mind, is array
representation of tree is good?
a) yes because we are overcoming the need of pointers and so space efficiency
b) yes because array values are indexable
c) No it is not efficient in case of sparse trees and remaning cases it is fine
d) No linked list representation of tree is only fine
View Answer
Answer: c
Explanation: In case of sparse trees (where one node per level in worst cases), the array size (2h)-1 where h
is height but only h indexes will be filled and (2h)-1-h nodes will be left unused leading to space wastage.
9. Why is heap implemented using array representations than tree(linked list) representations though both
tree representations and heaps have same complexities?
for binary heap

-insert: O(log n)
-delete min: O(log n)
for a tree
-insert: O(log n)
-delete: O(log n)
Then why go with array representation when both are having same values ?
a) arrays can store trees which are complete and heaps are not complete
b) lists representation takes more memory hence memory efficiency is less and go with arrays and arrays
have better caching
c) lists have better caching
d) In lists insertion and deletion is difficult
View Answer
Answer: b
Explanation: In memory the pointer address for next node may not be adjacent or nearer to each other and
also array have wonderful caching power from os and manipulating pointers is a overhead. Heap data
structure is always a complete binary tree.
10. Can a tree stored in an array using either one of inorder or post order or pre order traversals be again
reformed?
a) Yes just traverse through the array and form the tree
b) No we need one more traversal to form a tree
c) No in case of sparse trees
d) Yes by using both inorder and array elements
View Answer
Answer: b
Explanation: We need any two traversals for tree formation but if some additional stuff or techniques are
used while storing a tree in an array then one traversal can facilitate like also storing null values of a node in
array.
1. Advantages of linked list representation of binary trees over arrays?
a) dynamic size
b) ease of insertion/deletion
c) ease in randomly accessing a node
d) both dynamic size and ease in insertion/deletion
View Answer
Answer: d
Explanation: It has both dynamic size and ease in insertion and deletion as advantages.
2. Disadvantages of linked list representation of binary trees over arrays?

a) Randomly accessing is not possible
b) Extra memory for a pointer is needed with every element in the list
c) Difficulty in deletion
d) Random access is not possible and extra memory with every element
View Answer
Answer: d
Explanation: Random access is not possible with linked lists.
3. Which of the following traversing algorithm is not used to traverse in a tree?

a) Post order
b) Pre order
c) Post order
d) Randomized
View Answer
Answer: d
Explanation: Generally, all nodes in a tree are visited by using preorder, inorder and postorder traversing
algorithms.
4. Level order traversal of a tree is formed with the help of

a) breadth first search
b) depth first search
c) dijkstra’s algorithm
d) prims algorithm
View Answer
Answer: a
Explanation: Level order is similar to bfs.
5. Identify the reason which doesn’t play a key role to use threaded binary trees?
a) The storage required by stack and queue is more
b) The pointers in most of nodes of a binary tree are NULL
c) It is Difficult to find a successor node
d) They occupy less size
View Answer
Answer: d
Explanation: Threaded binary trees are introduced to make the Inorder traversal faster without using any
stack or recursion. Stack and Queue require more space and pointers in the majority of binary trees are null
and difficulties are raised while finding successor nodes. Size constraints are not taken on threaded binary
trees, but they occupy less space than a stack/queue.
Join Sanfoundry@YouTube
6. The following lines talks about deleting a node in a binary tree.(the tree property must not be violated
after deletion)
i) from root search for the node to be deleted
ii)
iii) delete the node at
what must be statement ii) and fill up statement iii)
a) ii)-find random node,replace with node to be deleted. iii)- delete the node
b) ii)-find node to be deleted. iii)- delete the node at found location
c) ii)-find deepest node,replace with node to be deleted. iii)- delete a node
d) ii)-find deepest node,replace with node to be deleted. iii)- delete the deepest node
View Answer
Answer: d
Explanation: We just replace a to be deleted node with last leaf node of a tree. this must not be done in case
of BST or heaps.
7. What may be the psuedo code for finding the size of a tree?
a) find_size(root_node–>left_node) + 1 + find_size(root_node–>right_node)
b) find_size(root_node–>left_node) + find_size(root_node–>right_node)
c) find_size(root_node–>right_node) – 1
d) find_size(root_node–>left_node + 1
View Answer
Answer: a
Explanation: Draw a tree and analyze the expression. we are always taking size of left subtree and right
subtree and adding root value(1) to it and finally printing size.
8. What is missing in this logic of finding a path in the tree for a given sum (i.e checking whether there will
be a path from roots to leaf nodes with given sum)?
checkSum(struct bin-treenode *root , int sum) :

if(root==null)
return sum as 0
else :
leftover_sum=sum-root_node-->value
//missing
a) code for having recursive calls to either only left tree or right trees or to both subtrees depending on their
existence
b) code for having recursive calls to either only left tree or right trees
c) code for having recursive calls to either only left tree
d) code for having recursive calls to either only right trees
View Answer
Answer: a
Explanation: if(left subtree and right subtree) then move to both subtrees
else if only left subtree then move to left subtree carrying leftover_sum parameter
else if only right subtree then move to right subtree carrying leftover_sum parameter.
9. What must be the missing logic below so as to print mirror of a tree as below as an example?
if(rootnode):
mirror(rootnode-->left)
mirror(rootnode-->right)
//missing
end
a) swapping of left and right nodes is missing

b) swapping of left with root nodes is missing
c) swapping of right with root nodes is missing
d) nothing is missing
View Answer
Answer: a
Explanation: Mirror is another tree with left and right children of nodes are interchanged as shown in the
figure.
10. What is the code below trying to print?
void print(tree *root,tree *node)

{
if(root ==null) return 0
if(root-->left==node || root-->right==node) || print(root->left,node)
||printf(root->right,node)
{
print(root->data)
}
}
a) just printing all nodes

b) not a valid logic to do any task
c) printing ancestors of a node passed as argument
d) printing nodes from leaf node to a node passed as argument
View Answer
Answer: c
Explanation: We are checking if left or right node is what the argument sent or else if not the case then move
to left node or right node and print all nodes while searching for the argument node.
1. What is the maximum number of children that a binary tree node can have?
a) 0
b) 1
c) 2
d) 3
View Answer
Answer: c
Explanation: In a binary tree, a node can have atmost 2 nodes (i.e.) 0,1 or 2 left and right child.
2. The following given tree is an example for?
a) Binary tree
b) Binary search tree
c) Fibonacci tree
d) AVL tree
View Answer
Answer: a
Explanation: The given tree is an example for binary tree since has got two children and the left and right
children do not satisfy binary search tree’s property, Fibonacci and AVL tree.
3. A binary tree is a rooted tree but not an ordered tree.

a) true
b) false
View Answer
Answer: b
Explanation: A binary tree is a rooted tree and also an ordered tree (i.e) every node in a binary tree has at
most two children.
4. How many common operations are performed in a binary tree?

a) 1
b) 2
c) 3
d) 4
View Answer
Answer: c
Explanation: Three common operations are performed in a binary tree- they are insertion, deletion and
traversal.
5. What is the traversal strategy used in the binary tree?
a) depth-first traversal
b) breadth-first traversal
c) random traversal
d) Priority traversal
View Answer
Answer: b
Explanation: Breadth first traversal, also known as level order traversal is the traversal strategy used in a
binary tree. It involves visiting all the nodes at a given level.
6. How many types of insertion are performed in a binary tree?

a) 1
b) 2
c) 3
d) 4
View Answer
Answer: b
Explanation: Two kinds of insertion operation is performed in a binary tree- inserting a leaf node and
inserting an internal node.
7. 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) deleting a node with 2 children
View Answer
Answer: c
Explanation: The above diagram is a depiction of deleting a node with 0 or 1 child since the node D which
has 1 child is deleted.
8. General ordered tree can be encoded into binary trees.

a) true
b) false
View Answer
Answer: a
Explanation: General ordered tree can be mapped into binary tree by representing them in a left-child-right-
sibling way.
9. How many bits would a succinct binary tree occupy?
a) n+O(n)
b) 2n+O(n)
c) n/2
d) n
View Answer
Answer: b
Explanation: A succinct binary tree occupies close to minimum possible space established by lower bounds.
A succinct binary tree would occupy 2n+O(n) bits.
10. The average depth of a binary tree is given as?

a) O(N)
b) O(√N)
c) O(N2)
d) O(log N)
View Answer
Answer: d
Explanation: The average depth of a binary tree is given as O(√N). In case of a binary search tree, it is O(log
N).
11. How many orders of traversal are applicable to a binary tree (In General)?
a) 1
b) 4
c) 2
d) 3
View Answer
Answer: d
Explanation: The three orders of traversal that can be applied to a binary tree are in-order, pre-order and post
order traversal.
12. If binary trees are represented in arrays, what formula can be used to locate a left child, if the node has
an index i?
a) 2i+1
b) 2i+2
c) 2i
d) 4i
View Answer
Answer: a
Explanation: If binary trees are represented in arrays, left children are located at indices 2i+1 and right
children at 2i+2.
13. Using what formula can a parent node be located in an array?

a) (i+1)/2
b) (i-1)/2
c) i/2
d) 2i/2
View Answer
Answer: b
Explanation: If a binary tree is represented in an array, parent nodes are found at indices (i-1)/2.
14. 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
View Answer
Answer: a
Explanation: In preorder, inorder and postorder traversal the left subtrees are visited before the right
subtrees. In Inorder traversal, the Left subtree is visited first then the Root node then the Right subtree. In
postorder traversal, the Left subtree is visited first, then Right subtree and then the Root node is visited.
15. Construct a binary tree using the following data.

The preorder traversal of a binary tree is 1, 2, 5, 3, 4. The inorder traversal of the same binary tree is 2, 5, 1,
4, 3.
a)
b)
c)
d)
View Answer
Answer: d
Explanation: Here,
Preorder Traversal is 1, 2, 5, 3, 4
Inorder Traversal is 2, 5, 1, 4, 3
Root node of binary tree is the first node in Preorder traversal.
The rough sketch of tree is:
Second node in preorder traversal is 2. This makes 5 as right child to node 2. The fourth node in preorder
traversal is 3. This makes 4 as right child to node 3. Thus the final tree is:
1. 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) 2, 7, 5, 6, 11, 2, 5, 4, 9
View Answer
Answer: a
Explanation: Pre order traversal follows NLR(Node-Left-Right).
2. 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) 2, 7, 5, 6, 11, 2, 5, 4, 9
View Answer
Answer: c
Explanation: Post order traversal follows LRN(Left-Right-Node).
3. Select the code snippet which performs pre-order traversal.
a)
public void preorder(Tree root)

{
System.out.println(root.data);
preorder(root.left);
preorder(root.right);
}
b)

{
}
c)
{
}
d)

{
}
View Answer
Answer: a
Explanation: Pre-order traversal follows NLR(Node-Left-Right).
4. Select the code snippet which performs post-order traversal.
a)
public void postorder(Tree root)
{
postorder(root.left);
postorder(root.right);
}
b)

{
}
c)

{
}
d)

{
}
View Answer
Answer: b
Explanation: Post order traversal follows NLR(Left-Right-Node).
5. Select the code snippet that performs pre-order traversal iteratively.
a)
public void preOrder(Tree root)
{
if (root == null) return;
Stack<Tree> stk = new Stack<Tree>();
st.add(root);
while (!stk.empty())
{
Tree node = stk.pop();
System.out.print(node.data + " ");
if (node.left != null) stk.push(node.left);
if (node.right != null) stk.push(node.right);
}
}
b)

{
{
}
}
c)

{
st.add(root);
{
}
}
d)
{
st.add(root);
{
if (node.right != null) stk.push(node.left);
if (node.left != null) stk.push(node.right);
}
}
View Answer
Answer: c
Explanation: Add the root to the stack first, then continously check for the right and left children of the top-
of-the-stack.
6. Select the code snippet that performs post-order traversal iteratively.
a)
{
if (root == null)
return;
Tree node = root;
while (!stk.isEmpty() || node != null)
{
while (node != null)
{
if (node.right != null)
stk.add(node.left);
stk.add(node);
node = node.right;
}
node = stk.pop();
if (node.right != null && !stk.isEmpty() && node.right == stk.peek())
{
Trees nodeRight = stk.pop();
stk.push(node);
node = nodeRight;
} else
{
node = null;
}
}
}
b)

{
if (root == null)
return;
Tree node = root;
{
{
stk.add(node.right);
stk.add(node);
node = node.left;
}
node = stk.pop();
if (node.right != null && !stk.isEmpty() && node.right == stk.peek())
{
stk.push(node);
node = nodeRight;
} else
{
node = null;
}
}
}
c)

{
if (root == null)
return;
Tree node = root;
{
{
stk.add(node.right);
stk.add(node);
node = node.left;
}
node = stk.pop();
{
stk.push(node);
node = nodeRight;
} else
{
node = null;
}
}
}
d)

{
if (root == null)
return;
Tree node = root;
{
{
stk.add(node.left);
stk.add(node);
node = node.left;
}
node = stk.pop();
{
stk.push(node);
node = nodeLeft;
} else
{
node = null;
}
}
}
View Answer
Answer: b
Explanation: The left and right children are added first to the stack, followed by the node, which is then
popped. Post-order follows LRN policy.
7. What is the time complexity of pre-order traversal in the iterative fashion?
a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)
View Answer
Answer: b
Explanation: Since you have to go through all the nodes, the complexity becomes O(n).
8. What is the space complexity of the post-order traversal in the recursive fashion? (d is the tree depth and n
is the number of nodes)
a) O(1)
b) O(nlogd)
c) O(logd)
d) O(d)
View Answer
Answer: d
Explanation: In the worst case we have d stack frames in the recursive call, hence the complexity is O(d).
9. 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
View Answer
Answer: b
Explanation: As the name itself suggests, pre-order traversal can be used.
10. 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
View Answer
Answer: b
Explanation: The inorder sequence is B, E, A, D, C and Preorder sequence is A, B, E, C, D. The tree
constructed with the inorder and preorder sequence is

The levelorder traversal (BFS traversal) is A, B, C, E, D.
11. Consider the following data and specify which one is Preorder Traversal Sequence, Inorder and
Postorder sequences.
S1: N, M, P, O, Q
S2: N, P, Q, O, M
S3: M, N, O, P, Q
a) S1 is preorder, S2 is inorder and S3 is postorder
b) S1 is inorder, S2 is preorder and S3 is postorder
c) S1 is inorder, S2 is postorder and S3 is preorder
d) S1 is postorder, S2 is inorder and S3 is preorder
View Answer
Answer: c
Explanation: Preorder traversal starts from the root node and postorder and inorder starts from the left child
node of the left subtree. The first node of S3 is different and for S1 and S2 it’s the same. Thus, S3 is
preorder traversal and the root node is M. Postorder traversal visits the root node at last. S2 has the root
node(M) at last that implies S2 is postorder traversal. S1 is inorder traversal as S2 is postorder traversal and
S3 is preorder traversal. Therefore, S1 is inorder traversal, S2 is postorder traversal and S3 is preorder
traversal
1. In postorder traversal of binary tree right subtree is traversed before visiting root.
a) True
b) False
View Answer
Answer: a
Explanation: Post-order method of traversing involves – i) Traverse left subtree in post-order, ii) Traverse
right subtree in post-order, iii) visit the root.
2. What is the possible number of binary trees that can be created with 3 nodes, giving the sequence N, M, L
when traversed in post-order.
a) 15
b) 3
c) 5
d) 8
View Answer
Answer: c
Explanation: 5 binary trees are possible and they are,
3. 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
View Answer
Answer: c
Explanation: The last, second last nodes visited in post-order traversal are root and it’s right child
respectively. Option T Q R S O P can’t be a pre-order traversal, because nodes O, P are visited after the
nodes Q, R, S. Option T O Q R P S, can’t be valid, because the pre-order sequence given in option T O Q R
P S and given post-order traversal creates a tree with node T as root and node O as left subtree. Option T Q
O P S R is valid. Option T Q O S P R is not valid as node P is visited after visiting node S.
4. 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
View Answer
Answer: d
Explanation: The binary tree contains values 7, 8, 13, 26, 35, 40, 70, 75. The given pre-order sequence is 35,
13, 7, 8, 26, 70, 40 and 75. So, the binary search tree formed is
Thus post-order sequence for the tree is 8, 7, 26, 13, 40, 75, 70 and 35.
5. 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
View Answer
Answer: b
Explanation: A binary tree can uniquely be created by post-order and in-order traversals.
advertisement
6. A full binary tree can be generated using ______
a) post-order and pre-order traversal
b) pre-order traversal
c) post-order traversal
d) in-order traversal
View Answer
Answer: a
Explanation: Every node in a full binary tree has either 0 or 2 children. A binary tree can be generated by
two traversals if one of them is in-order. But, we can generate a full binary tree using post-order and pre-
order traversals.
7. The maximum number of nodes in a tree for which post-order and pre-order traversals may be equal is
______
a) 3
b) 1
c) 2
d) any number
View Answer
Answer: b
Explanation: The tree with only one node has post-order and pre-order traversals equal.
8. The steps for finding post-order traversal are traverse the right subtree, traverse the left subtree or visit the
current node.
a) True
b) False
View Answer
Answer: b
Explanation: Left subtree is traversed first in post-order traversal, then the right subtree is traversed and then
the output current node.
9. The pre-order and in-order are traversals of a binary tree are T M L N P O Q and L M N T O P Q. Which
of following is post-order traversal of the tree?
a) L N M O Q P T
b) N M O P O L T
c) L M N O P Q T
d) O P L M N Q T
View Answer
Answer: a
Explanation: The tree generated by using given pre-order and in-order traversal is
Thus, L N M O Q P T will be the post-order traversal.

10. For a binary tree the first node visited in in-order and post-order traversal is same.
a) True
b) False
View Answer
Answer: b
Explanation: Consider a binary tree,
Its in-order traversal – 13 14 16 19

Its post-order traversal- 14 13 19 16. Here the first node visited is not same.
11. Find the postorder traversal of the binary tree shown below.
a) P Q R S T U V W X
b) W R S Q P V T U X
c) S W T Q X U V R P
d) S T W U X V Q R P
View Answer
Answer: c
Explanation: In postorder traversal the left subtree is traversed first and then the right subtree and then the
current node. So, the posturer traversal of the tree is, S W T Q X U V R P.
1. For the tree below, write the in-order traversal.
a) 6, 2, 5, 7, 11, 2, 5, 9, 4
b) 6, 5, 2, 11, 7, 4, 9, 5, 2
c) 2, 7, 2, 6, 5, 11, 5, 9, 4
d) 2, 7, 6, 5, 11, 2, 9, 5, 4
View Answer
Answer: a
Explanation: In-order traversal follows LNR(Left-Node-Right).
2. For the tree below, write the level-order traversal.
a) 2, 7, 2, 6, 5, 11, 5, 9, 4
b) 2, 7, 5, 2, 11, 9, 6, 5, 4
c) 2, 5, 11, 6, 7, 4, 9, 5, 2
d) 2, 7, 5, 6, 11, 2, 5, 4, 9
View Answer
Answer: b
Explanation: Level order traversal follows a breadth first search approach.
3. Select the code snippet which performs in-order traversal.
a)
public void inorder(Tree root)

{
inorder(root.left);
inorder(root.right);
}
b)

{
inorder(root.left);
}
c)

{
inorder(root.left);
}
d)

{
inorder(root.left);
}
View Answer
Answer: b
Explanation: In-order traversal follows LNR(Left-Node-Right).
4. Select the code snippet which performs level-order traversal.
a)
public static void levelOrder(Tree root)

{
Queue<Node> queue=new LinkedList<Node>();
queue.add(root);
while(!queue.isEmpty())
{
Node tempNode=queue.poll();
System.out.println("%d ",tempNode.data);
if(tempNode.left!=null)
queue.add(tempNode.left);
if(tempNode.right!=null)
queue.add(tempNode.right);
}
}
b)

{
queue.add(root);
{
}
}
c)

{
queue.add(root);
{
}
}
d)

{
queue.add(root);
{
queue.add(tempNode.left.left);
queue.add(tempNode.right.right);
}
}
View Answer
Answer: a
Explanation: Firstly add the root node to the queue. Then for all the remaining nodes, pop the front end of
the queue and print it, add the left and right children of the popped node to the queue.
5. What is the space complexity of the in-order traversal in the recursive fashion? (d is the tree depth and n is
the number of nodes)
a) O(1)
b) O(nlogd)
c) O(logd)
d) O(d)
View Answer
Answer: d
Explanation: In the worst case we have d stack frames in the recursive call, hence the complexity is O(d).
6. What is the time complexity of level order traversal?

a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)
View Answer
Answer: b
Explanation: Since you have to go through all the nodes, the complexity becomes O(n).
7. Which of the following graph traversals closely imitates level order traversal of a binary tree?
a) Depth First Search
b) Breadth First Search
c) Depth & Breadth First Search
d) Binary Search
View Answer
Answer: b
Explanation: Both level order tree traversal and breadth first graph traversal follow the principle that visit
your neighbors first and then move on to further nodes.
8. In a binary search tree, which of the following traversals would print the numbers in the ascending order?
a) Level-order traversal
b) Pre-order traversal
c) Post-order traversal
d) In-order traversal
View Answer
Answer: d
Explanation: In a binary search tree, a node’s left child is always lesser than the node and right child is
greater than the node, hence an in-order traversal would print them in a non decreasing fashion.
1. Which of the following is false about a binary search tree?
a) The left child is always lesser than its parent
b) The right child is always greater than its parent
c) The left and right sub-trees should also be binary search trees
d) In order sequence gives decreasing order of elements
View Answer
Answer: d
Explanation: In order sequence of binary search trees will always give ascending order of elements.
Remaining all are true regarding binary search trees.
2. How to search for a key in a binary search tree?

a)
public Tree search(Tree root, int key)

{
if( root == null || root.key == key )
{
return root;
}
if( root.key < key )
{
return search(root.right,key);
}
else
return search(root.left,key);
}
b)

{
if( root == null || root.key == key )
{
return root;
}
{
}
else
}
c)

{
if( root == null)
{
return root;
}
{
}
else
}
d)

{
if( root == null)
{
return root;
}
{
return search(root.right.right,key);
}
else
return search(root.left.left,key);
}
View Answer
Answer: a
Explanation: As we know that the left child is lesser than the parent, if the root’s key is greater than the
given key, we look only into the left sub-tree, similarly for right sub-tree.
3. What is the speciality about the inorder traversal of a binary search tree?
a) It traverses in a non increasing order
b) It traverses in an increasing order
c) It traverses in a random fashion
d) It traverses based on priority of the node
View Answer
Answer: b
Explanation: As a binary search tree consists of elements lesser than the node to the left and the ones greater
than the node to the right, an inorder traversal will give the elements in an increasing order.
4. What does the following piece of code do?
public void func(Tree root)

{
func(root.left());
func(root.right());
System.out.println(root.data());
}
a) Preorder traversal
b) Inorder traversal
c) Postorder traversal
d) Level order traversal
View Answer
Answer: c
Explanation: In a postorder traversal, first the left child is visited, then the right child and finally the parent.
5. What does the following piece of code do?
public void func(Tree root)

{
func(root.left());
func(root.right());
}
a) Preorder traversal
b) Inorder traversal
c) Postorder traversal
d) Level order traversal
View Answer
Answer: a
Explanation: In a preorder traversal, first the parent is visited, then the left child and finally the right child.
6. How will you find the minimum element in a binary search tree?
a)
public void min(Tree root)

{
while(root.left() != null)
{
root = root.left();
}
}
b)

{
while(root != null)
{
root = root.left();
}
}
c)

{
while(root.right() != null)
{
root = root.right();
}
}
d)

{
while(root != null)
{
}
}
View Answer
Answer: a
Explanation: Since all the elements lesser than a given node will be towards the left, iterating to the leftmost
leaf of the root will give the minimum element in a binary search tree.
7. How will you find the maximum element in a binary search tree?
a)
public void max(Tree root)

{
while(root.left() != null)
{
root = root.left();
}
}
b)

{
while(root != null)
{
root = root.left();
}
}
c)

{
while(root.right() != null)
{
}
}
d)

{
while(root != null)
{
}
}
View Answer
Answer: c
Explanation: Since all the elements greater than a given node are towards the right, iterating through the tree
to the rightmost leaf of the root will give the maximum element in a binary search tree.
8. What are the worst case and average case complexities of a binary search tree?
a) O(n), O(n)
b) O(logn), O(logn)
c) O(logn), O(n)
d) O(n), O(logn)
View Answer
Answer: d
Explanation: Worst case arises when the tree is skewed(either to the left or right) in which case you have to
process all the nodes of the tree giving O(n) complexity, otherwise O(logn) as you process only the left half
or the right half of the tree.
9. Given that 2 elements are present in the tree, write a function to find the LCA(Least Common Ancestor)
of the 2 elements.
a)
public void lca(Tree root,int n1, int n2)

{
while (root != NULL)
{
if (root.data() > n1 && root.data() > n2)
else if (root.data() < n1 && root.data() < n2)
root = root.left();
else break;
}
}
b)

{
{
if (root.data() > n1 && root.data() < n2)
root = root.left();
else if (root.data() < n1 && root.data() > n2)
else break;
}
}
c)

{
{
root = root.left();
else break;
}
}
d)

{
{
root = root.left.left();
root = root.right.right();
else break;
}
}
View Answer
Answer: c
Explanation: The property of a binary search tree is that the lesser elements are to the left and greater
elements are to the right, we use this property here and iterate through the tree such that we reach a point
where the 2 elements are on 2 different sides of the node, this becomes the least common ancestor of the 2
given elements.
10. What are the conditions for an optimal binary search tree and what is its advantage?
a) The tree should not be modified and you should know how often the keys are accessed, it improves the
lookup cost
b) You should know the frequency of access of the keys, improves the lookup time
c) The tree can be modified and you should know the number of elements in the tree before hand, it
improves the deletion time
d) The tree should be just modified and improves the lookup time
View Answer
Answer: a
Explanation: For an optimal binary search The tree should not be modified and we need to find how often
keys are accessed. Optimal binary search improves the lookup cost.
11. Construct a binary search tree with the below information.
The preorder traversal of a binary search tree 10, 4, 3, 5, 11, 12.
a)
b)
c)
d)
View Answer
Answer: c
Explanation: Preorder Traversal is 10, 4, 3, 5, 11, 12. Inorder Traversal of Binary search tree is equal to
ascending order of the nodes of the Tree. Inorder Traversal is 3, 4, 5, 10, 11, 12. The tree constructed using
Preorder and Inorder traversal is
1. What is an AVL tree?
a) a tree which is balanced and is a height balanced tree
b) a tree which is unbalanced and is a height balanced tree
c) a tree with three children
d) a tree with atmost 3 children
View Answer
Answer: a
Explanation: It is a self balancing tree with height difference atmost 1.
2. Why we need to a binary tree which is height balanced?

a) to avoid formation of skew trees
b) to save memory
c) to attain faster memory access
d) to simplify storing
View Answer
Answer: a
Explanation: In real world dealing with random values is often not possible, the probability that u are
dealing with non random values(like sequential) leads to mostly skew trees, which leads to worst case. hence
we make height balance by rotations.
3. Which of the below diagram is following AVL tree property?
i.
ii.
a) only i
b) only i and ii
c) only ii
d) i is not a binary search tree
View Answer
Answer: b
Explanation: The property of AVL tree is it is height balanced tree with difference of atmost 1 between left
and right subtrees. All AVL trees are binary search tree.
4. What is the maximum height of an AVL tree with p nodes?
a) p
b) log(p)
c) log(p)/2
d) p⁄2
View Answer
Answer: b
Explanation: Consider height of tree to be ‘he’, then number of nodes which totals to p can be written in
terms of height as N(he)=N(he-1)+1+N(he-2). since N(he) which is p can be written in terms of height as the
beside recurrence relation which on solving gives N(he)= O(logp) as worst case height.
5. To restore the AVL property after inserting a element, we start at the insertion point and move towards
root of that tree. is this statement true?
a) true
b) false
View Answer
Answer: a
Explanation: It is interesting to note that after insertion, only the path from that point to node or only that
subtrees are imbalanced interms of height.
6. Given an empty AVL tree, how would you construct AVL tree when a set of numbers are given without
performing any rotations?
a) just build the tree with the given input
b) find the median of the set of elements given, make it as root and construct the tree
c) use trial and error
d) use dynamic programming to build the tree
View Answer
Answer: b
Explanation: Sort the given input, find the median element among them, make it as root and construct left
and right subtrees with elements lesser and greater than the median element recursively. this ensures the
subtrees differ only by height 1.
7. What maximum difference in heights between the leafs of a AVL tree is possible?
a) log(n) where n is the number of nodes
b) n where n is the number of nodes
c) 0 or 1
d) atmost 1
View Answer
Answer: a
Explanation: At every level we can form a tree with difference in height between subtrees to be atmost 1 and
so there can be log(n) such levels since height of AVL tree is log(n).
8. Consider the pseudo code:
int avl(binarysearchtree root):

if(not root)
return 0
left_tree_height = avl(left_of_root)
if(left_tree_height== -1)
return left_tree_height
right_tree_height= avl(right_of_root)
if(right_tree_height==-1)
return right_tree_height
Does the above code can check if a binary search tree is an AVL tree?
a) yes
b) no
View Answer
Answer: a
Explanation: The condition to check the height difference between left and right subtrees is missing. if
(absolute(left_tree_height – right_tree_height)>1) must be added.
9. Consider the below left-left rotation pseudo code where the node contains value pointers to left, right
child nodes and a height value and Height() function returns height value stored at a particular node.
avltree leftrotation(avltreenode z):

avltreenode w =x-left
x-left=w-right
w-right=x
x-height=max(Height(x-left),Height(x-right))+1
w-height=max(missing)+1
return w
What is missing?
a) Height(w-left), x-height
b) Height(w-right), x-height
c) Height(w-left), x
d) Height(w-left)
View Answer
Answer: a
Explanation: In the code we are trying to make the left rotation and so we need to find maximum of those
two values.
10. Why to prefer red-black trees over AVL trees?

a) Because red-black is more rigidly balanced
b) AVL tree store balance factor in every node which costs space
c) AVL tree fails at scale
d) Red black is more efficient
View Answer
Answer: b
Explanation: Every node in an AVL tree need to store the balance factor (-1, 0, 1) hence space costs to O(n),
n being number of nodes. but in red-black we can use the sign of number (if numbers being stored are only
positive) and hence save space for storing balancing information. there are even other reasons where
redblack is mostly prefered.
1. What is the special property of red-black trees and what root should always be?
a) a color which is either red or black and root should always be black color only
b) height of the tree
c) pointer to next node
d) a color which is either green or black
View Answer
Answer: a
Explanation: An extra attribute which is a color red or black is used. root is black because if it is red then
one of red-black tree property which states that number of black nodes from root to null nodes must be
same, will be violated.
2. Why do we impose restrictions like

. root property is black
. every leaf is black
. children of red node are black
. all leaves have same black
a) to get logarithm time complexity
b) to get linear time complexity
c) to get exponential time complexity
d) to get constant time complexity
View Answer
Answer: a
Explanation: We impose such restrictions to achieve self balancing trees with logarithmic complexities for
insertions, deletions, search.
3. Cosider the below formations of red-black tree.
All the above formations are incorrect for it to be a redblack tree. then what may be the correct order?
a) 50-black root, 18-red left subtree, 100-red right subtree
b) 50-red root, 18-red left subtree, 100-red right subtree
c) 50-black root, 18-black left subtree, 100-red right subtree
d) 50-black root, 18-red left subtree, 100-black right subtree
View Answer
Answer: a
Explanation: Considering all the properties of red-black tree, 50 must be the black root and there are two
possibilities for subtrees. one is option “50-black root, 18-red left subtree, 100-red right subtree” and other is
making all nodes of the tree to be black.
4. What are the operations that could be performed in O(logn) time complexity by red-black tree?
a) insertion, deletion, finding predecessor, successor
b) only insertion
c) only finding predecessor, successor
d) for sorting
View Answer
Answer: a
Explanation: We impose restrictions to achieve logarithm time complexities.
impose restrictions are:
. root property is black
. every leaf is black
. children of red node are black
. all leaves have same black.
5. Which of the following is an application of Red-black trees and why?

a) used to store strings efficiently
b) used to store integers efficiently
c) can be used in process schedulers, maps, sets
d) for efficient sorting
View Answer
Answer: c
Explanation: RB tree is used for Linux kernel in the form of completely fair scheduler process scheduling
algorithm. It is used for faster insertions, retrievals.
advertisement
6. When it would be optimal to prefer Red-black trees over AVL trees?

a) when there are more insertions or deletions
b) when more search is needed
c) when tree must be balanced
d) when log(nodes) time complexity is needed
View Answer
Answer: a
Explanation: Though both trees are balanced, when there are more insertions and deletions to make the tree
balanced, AVL trees should have more rotations, it would be better to use red-black. but if more search is
required AVL trees should be used.
7. Why Red-black trees are preferred over hash tables though hash tables have constant time complexity?
a) no they are not preferred
b) because of resizing issues of hash table and better ordering in redblack trees
c) because they can be implemented using trees
d) because they are balanced
View Answer
Answer: b
Explanation: Redblack trees have O(logn) for ordering elements in terms of finding first and next elements.
also whenever table size increases or decreases in hash table you need to perform rehashing which can be
very expensive in real time. also red black stores elements in sorted order rather than input order.
8. How can you save memory when storing color information in Red-Black tree?
a) using least significant bit of one of the pointers in the node for color information
b) using another array with colors of each node
c) storing color information in the node structure
d) using negative and positive numbering
View Answer
Answer: a
Explanation: The node pointers can be used to store color with the help of significant bits. the exceptions of
this method are in languages like java where pointers are not used this may not work.
9. When to choose Red-Black tree, AVL tree and B-trees?

a) many inserts, many searches and when managing more items respectively
b) many searches, when managing more items respectively and many inserts respectively
c) sorting, sorting and retrieval respectively
d) retrieval, sorting and retrieval respectively
View Answer
Answer: a
Explanation: Red black when frequent inserts and deletes, AVL when less frequent inserts and deletes, B-
tree when using paging from a slow storage device.
10. What is the below pseudo code trying to do, where pt is a node pointer and root pointer?
redblack(Node root, Node pt) :

if (root == NULL)
return pt
if (pt.data < root.data)

{
root.left = redblack(root.left, pt);
root.left.parent = root
}
else if (pt.data > root.data)
{
root.right = redblackt(root.right, pt)
root.right.parent = root
}
return root
a) insert a new node

b) delete a node
c) search a node
d) count the number of nodes
View Answer
Answer: a
Explanation: The code is taking the root node and to be inserted node and is performing insertion operation.
Graph
1. Which of the following statements for a simple graph is correct?
a) Every path is a trail
b) Every trail is a path
c) Every trail is a path as well as every path is a trail
d) Path and trail have no relation
Answer: a
Explanation: In a walk if the vertices are distinct it is called a path, whereas if the edges are distinct it is
called a trail.
2. In the given graph identify the cut vertices.
a) B and E
b) C and D
c) A and E
d) C and B
Answer: d
Explanation: After removing either B or C, the graph becomes disconnected.
3. For the given graph(G), which of the following statements is true?
a) G is a complete graph
b) G is not a connected graph
c) The vertex connectivity of the graph is 2
d) The edge connectivity of the graph is 1
Answer: c
Explanation: After removing vertices B and C, the graph becomes disconnected.
4. What is the number of edges present in a complete graph having n vertices?

a) (n*(n+1))/2
b) (n*(n-1))/2
c) n
d) Information given is insufficient
Answer: b
Explanation: Number of ways in which every vertex can be connected to each other is nC2.
5. The given Graph is regular.
a) True
b) False
Answer: a
Explanation: In a regular graph, degrees of all the vertices are equal. In the given graph the degree of every
vertex is 3.
advertisement
6. In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices.
a) True
b) False
Answer: b
Explanation: The sum of the degrees of the vertices is equal to twice the number of edges.
7. A connected planar graph having 6 vertices, 7 edges contains _____________ regions.

a) 15
b) 3
c) 1
d) 11
Answer: b
Explanation: By euler’s formula the relation between vertices(n), edges(q) and regions(r) is given by n-
q+r=2.
8. If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G'(Complement of
G) is ___________
a) (n*n-n-2*m)/2
b) (n*n+n+2*m)/2
c) (n*n-n-2*m)/2
d) (n*n-n+2*m)/2
Answer: a
Explanation: The union of G and G’ would be a complete graph so, the number of edges in G’= number of
edges in the complete form of G(nC2)-edges in G(m).
9. Which of the following properties does a simple graph not hold?

a) Must be connected
b) Must be unweighted
c) Must have no loops or multiple edges
d) Must have no multiple edges
Answer: a
Explanation: A simple graph maybe connected or disconnected.
10. What is the maximum number of edges in a bipartite graph having 10 vertices?
a) 24
b) 21
c) 25
d) 16
Answer: c
Explanation: Let one set have n vertices another set would contain 10-n vertices.
Total number of edges would be n*(10-n), differentiating with respect to n, would yield the Answer.
11. Which of the following is true?
a) A graph may contain no edges and many vertices
b) A graph may contain many edges and no vertices
c) A graph may contain no edges and no vertices
d) A graph may contain no vertices and many edges
Answer: b
Explanation: A graph must contain at least one vertex.
12. For a given graph G having v vertices and e edges which is connected and has no cycles, which of the
following statements is true?
a) v=e
b) v = e+1
c) v + 1 = e
d) v = e-1
Answer: b
Explanation: For any connected graph with no cycles the equation holds true.
13. For which of the following combinations of the degrees of vertices would the connected graph be
eulerian?
a) 1,2,3
b) 2,3,4
c) 2,4,5
d) 1,3,5
Answer: a
Explanation: A graph is eulerian if either all of its vertices are even or if only two of its vertices are odd.
14. A graph with all vertices having equal degree is known as a __________
a) Multi Graph
b) Regular Graph
c) Simple Graph
d) Complete Graph
Answer: b
Explanation: The given statement is the definition of regular graphs.
15. Which of the following ways can be used to represent a graph?

a) Adjacency List and Adjacency Matrix
b) Incidence Matrix
c) Adjacency List, Adjacency Matrix as well as Incidence Matrix
d) No way to represent
Answer: c
Explanation: Adjacency Matrix, Adjacency List and Incidence Matrix are used to represent a graph.
1. The number of possible undirected graphs which may have self loops but no multiple edges and have n
vertices is ________
a) 2((n*(n-1))/2)
b) 2((n*(n+1))/2)
c) 2((n-1)*(n-1))/2)
d) 2((n*n)/2)
Answer: d
Explanation: There can be at most, n*n edges in an undirected graph.
2. Given a plane graph, G having 2 connected component, having 6 vertices, 7 edges and 4 regions. What
will be the number of connected components?
a) 1
b) 2
c) 3
d) 4
Answer: b
Explanation: Euler’s Identity says V – E + R = 1+ number of connected components.
3. Number of vertices with odd degrees in a graph having a eulerian walk is ________
a) 0
b) Can’t be predicted
c) 2
d) either 0 or 2
Answer: d
Explanation: If the start and end vertices for the path are same the Answer would be 0 otherwise 2.
4. How many of the following statements are correct?

i) All cyclic graphs are complete graphs.
ii) All complete graphs are cyclic graphs.
iii) All paths are bipartite.
iv) All cyclic graphs are bipartite.
v) There are cyclic graphs which are complete.
a) 1
b) 2
c) 3
d) 4
Answer: b
Explanation: Statements iii) and v) are correct.
5. All paths and cyclic graphs are bipartite graphs.

a) True
b) False
Answer: b
Explanation: Only paths and even cycles are bipartite graphs.
6. What is the number of vertices of degree 2 in a path graph having n vertices,here n>2.
a) n-2
b) n
c) 2
d) 0
Answer: a
Explanation: Only the first and the last vertex would have degree 1, others would be of degree 2.
7. All trees with n vertices consists of n-1 edges.

a) True
b) False
Answer: a
Explanation: A trees is acyclic in nature.
8. Which of the following graphs are isomorphic to each other?
a) fig 1 and fig 2

b) fig 2 and fig 3
c) fig 1 and fig 3
d) fig 1, fig 2 and fig 3
Answer: d
Explanation: All three graphs are Complete graphs with 4 vertices.
9. In the given graph which edge should be removed to make it a Bipartite Graph?
a) A-C
b) B-E
c) C-D
d) D-E
Answer: a
Explanation: The resultant graph would be a Bipartite Graph having {A,C,E} and {D, B} as its subgroups.
10. What would the time complexity to check if an undirected graph with V vertices and E edges is Bipartite
or not given its adjacency matrix?
a) O(E*E)
b) O(V*V)
c) O(E)
d) O(V)
Answer: b
Explanation: A graph can be checked for being Bipartite by seeing if it is 2-colorable or not, which can be
obtained with the help of BFS.
1. Dijkstra’s Algorithm will work for both negative and positive weights?
a) True
b) False
Answer: b
Explanation: Dijkstra’s Algorithm assumes all weights to be non-negative.
2. A graph having an edge from each vertex to every other vertex is called a ___________
a) Tightly Connected
b) Strongly Connected
c) Weakly Connected
d) Loosely Connected
Answer: a
Explanation: This is a part of the nomenclature followed in Graph Theory.
3. What is the number of unlabeled simple directed graph that can be made with 1 or 2 vertices?
a) 2
b) 4
c) 5
d) 9
Answer: b
Explanation:
4. Floyd Warshall Algorithm used to solve the shortest path problem has a time complexity of __________
a) O(V*V)
b) O(V*V*V)
c) O(E*V)
d) O(E*E)
Answer: b
Explanation: The Algorithm uses Dynamic Programming and checks for every possible path.
5. All Graphs have unique representation on paper.

a) True
b) False
Answer: b
Explanation: Same Graph may be drawn in different ways on paper.
advertisement
6. Assuming value of every weight to be greater than 10, in which of the following cases the shortest path of
a directed weighted graph from 2 vertices u and v will never change?
a) add all values by 10
b) subtract 10 from all the values
c) multiply all values by 10
d) in both the cases of multiplying and adding by 10
Answer: c
Explanation: In case of addition or subtraction the shortest path may change because the number of edges
between different paths may be different, while in case of multiplication path wont change.
7. What is the maximum possible number of edges in a directed graph with no self loops having 8 vertices?
a) 28
b) 64
c) 256
d) 56
Answer: d
Explanation: If a graph has V vertices than every vertex can be connected to a possible of V-1 vertices.
8. What would be the DFS traversal of the given Graph?
a) ABCED
b) AEDCB
c) EDCBA
d) ADECB
Answer: a
Explanation: In this case two Answers are possible including ADEBC.
10. What is the maximum number of edges present in a simple directed graph with 7 vertices if there exists
no cycles in the graph?
a) 21
b) 7
c) 6
d) 49
Answer: c
Explanation: If the no cycles exists then the difference between the number of vertices and edges is 1.
1. The number of elements in the adjacency matrix of a graph having 7 vertices is __________
a) 7
b) 14
c) 36
d) 49
Answer: d
Explanation: There are n*n elements in the adjacency matrix of a graph with n vertices.
2. What would be the number of zeros in the adjacency matrix of the given graph?
a) 10
b) 6
c) 16
d) 0
Answer: b
Explanation: Total number of values in the matrix is 4*4=16, out of which 6 entries are non zero.
3. Adjacency matrix of all graphs are symmetric.

a) False
b) True
Answer: a
Explanation: Only undirected graphs produce symmetric adjacency matrices.
4. The time complexity to calculate the number of edges in a graph whose information in stored in form of
an adjacency matrix is ____________
a) O(V)
b) O(E2)
c) O(E)
d) O(V2)
Answer: d
Explanation: As V entries are 0, a total of V2-V entries are to be examined.
5. For the adjacency matrix of a directed graph the row sum is the _________ degree and the column sum is
the ________ degree.
a) in, out
b) out, in
c) in, total
d) total, out
Answer: b
Explanation: Row number of the matrix represents the tail, while Column number represents the head of the
edge.
6. What is the maximum number of possible non zero values in an adjacency matrix of a simple graph with
n vertices?
a) (n*(n-1))/2
b) (n*(n+1))/2
c) n*(n-1)
d) n*(n+1)
Answer: c
Explanation: Out of n*n possible values for a simple graph the diagonal values will always be zero.
7. On which of the following statements does the time complexity of checking if an edge exists between two
particular vertices is not, depends?
a) Depends on the number of edges
b) Depends on the number of vertices
c) Is independent of both the number of edges and vertices
d) It depends on both the number of edges and vertices
Answer: c
Explanation: To check if there is an edge between to vertices i and j, it is enough to see if the value of A[i][j]
is 1 or 0, here A is the adjacency matrix.
8. In the given connected graph G, what is the value of rad(G) and diam(G)?
a) 2, 3
b) 3, 2
c) 2, 2
d) 3, 3
Answer: a
Explanation: Value of eccentricity for vertices A, C is 2 whereas for F, B, D, E it is 3.
9. Which of these adjacency matrices represents a simple graph?

a) [ [1, 0, 0], [0, 1, 0], [0, 1, 1] ]
b) [ [1, 1, 1], [1, 1, 1], [1, 1, 1] ]
c) [ [0, 0, 1], [0, 0, 0], [0, 0, 1] ]
d) [ [0, 0, 1], [1, 0, 1], [1, 0, 0] ]
Answer: d
Explanation: A simple graph must have no-self loops, should be undirected.
10. Given an adjacency matrix A = [ [0, 1, 1], [1, 0, 1], [1, 1, 0] ], The total no. of ways in which every
vertex can walk to itself using 2 edges is ________
a) 2
b) 4
c) 6
d) 8
Answer: c
Explanation: A2 = [ [2, 1, 1], [1, 2, 1], [1, 1, 2] ], all the 3 vertices can reach to themselves in 2 ways, hence a
total of 3*2, 6 ways.
11. If A[x+3][y+5] represents an adjacency matrix, which of these could be the value of x and y.
a) x=5, y=3
b) x=3, y=5
c) x=3, y=3
d) x=5, y=5
Answer: a
Explanation: All adjacency matrices are square matrices.
12. Two directed graphs(G and H) are isomorphic if and only if A=PBP-1, where P and A are adjacency
matrices of G and H respectively.
a) True
b) False
Answer: a
Explanation: This is a property of isomorphic graphs.
13. Given the following program, what will be the 3rd number that’d get printed in the output sequence for
the given input?
#include <bits/stdc++.h>
using namespace std;
int cur=0;
int G[10][10];
bool visited[10];
deque <int> q;
void fun(int n);
int main()
{
int num=0;
int n;
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>G[i][j];
visited[i]=false;
fun(n);
return 0;
}
void fun(int n)
{
cout<<cur<<" ";
visited[cur]=true;
q.push_back(cur);
do
{
{
if(G[cur][j]==1 && !visited[j])
{
q.push_back(j);
cout<<j<<" ";
visited[j]=true;
}
q.pop_front();
if(!q.empty())
cur=q.front();
}while(!q.empty());
}
Input Sequence:-
9
0 1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 1
0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0
0 0 1 0 0 0 1 0 0
0 0 0 0 0 1 0 1 1
0 0 0 0 1 0 1 0 0
1 0 1 0 0 0 1 0 0
a) 2
b) 6
c) 8
d) 4
Answer: c
Explanation: The given code performs the breadth first search routine on the Graph.
The sequence obtained would be 0 1 8 2 6 3 4 5 7.
14. For which type of graph, the given program won’t run infinitely? The Input would be in the form of an
adjacency Matrix and n is its dimension (1<n<10).
#include <bits/stdc++.h>
using namespace std;
int G[10][10];
void fun(int n);
int main()
{
int num=0;
int n;
cin>>n;
cin>>G[i][j];
fun(n);
return 0;
}
void fun(int n)
{
if(G[i][j]==1)
j--;
}
a) All Fully Connected Graphs

b) All Empty Graphs
c) All Bipartite Graphs
d) All simple graphs
Answer: b
Explanation: For any graph (except empty graph) having edges, the condition G[i][j]==1 would hold true,
which would result in an infinite loop.
15. Given the following adjacency matrix of a graph(G) determine the number of components in the G.
[0 1 1 0 0 0],
[1 0 1 0 0 0],
[1 1 0 0 0 0],
[0 0 0 0 1 0],
[0 0 0 1 0 0],
[0 0 0 0 0 0].
a) 1
b) 2
c) 3
d) 4
Answer: c
Explanation: 0th 1st and 2nd vertices form a component, 3rd and 4th forms another and 5th vertex forms a
component of a single vertex.
1. Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E
(edges) is ___________
a) O(E)
b) O(V*V)
c) O(E+V)
d) O(V)
Answer: c
Explanation: In an adjacency list for every vertex there is a linked list which have the values of the edges to
which it is connected.
2. For some sparse graph an adjacency list is more space efficient against an adjacency matrix.
a) True
b) False
Answer: a
Explanation: Space complexity for adjacency matrix is always O(V*V) while space complexity for
adjacency list in this case would be O(V).
3. Time complexity to find if there is an edge between 2 particular vertices is _________

a) O(V)
b) O(E)
c) O(1)
d) O(V+E)
Answer: a
Explanation: The maximum edges a vertex can have is V-1.
4. For the given conditions, which of the following is in the correct order of increasing space requirement?
i) Undirected, no weight
ii) Directed, no weight
iii) Directed, weighted
iv) Undirected, weighted
a) ii iii i iv
b) i iii ii iv
c) iv iii i ii
d) i ii iii iv
Answer: a
Explanation: i) takes v+4e, ii) takes v+2e, iii) takes v+3e, iv) takes v +6e space.
5. Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E
(edges) is __________
a) O(V)
b) O(E*E)
c) O(E)
d) O(E+V)
Answer: c
Explanation: In an adjacency list for every vertex there is a linked list which have the values of the edges to
which it is connected.
6. Complete the given snippet of code for the adjacency list representation of a weighted directed graph.
class neighbor
{
int vertex, weight;
____ next;
}
class vertex
{
string name;
_____ adjlist;
}
vertex adjlists[101];
a) vertex, vertex
b) neighbor, vertex
c) neighbor, neighbor
d) vertex, neighbor
Answer: c
Explanation: Vertex would have a name and a linked list attached to it.
7. In which case adjacency list is preferred in front of an adjacency matrix?

a) Dense graph
b) Sparse graph
c) Adjacency list is always preferred
d) Complete graph
Answer: b
Explanation: In case of sparse graph most of the entries in the adjacency matrix would be 0, hence adjacency
list would be preferred.
8. To create an adjacency list C++’s map container can be used.

a) True
b) False
Answer: a
Explanation: We can create a mapping from string to a vector, where string would be the name of the vertex
and vector would contains the name of the vertices to which it is connected.
9. What would be the time complexity of the following function which adds an edge between two vertices i
and j, with some weight ‘weigh’ to the graph having V vertices?
vector<int> adjacent[15] ;
vector<int> weight[15];
void addEdge(int i,int j,int weigh)

{
adjacent[a].push_back(i);
adjacent[b].push_back(j);
weight[a].push_back(weigh);
weight[b].push_back(weigh);
}
a) O(1)
b) O(V)
c) O(V*V)
d) O(log V)
Answer: a
Explanation: The function win in the constant time as all the four step takes constant time.
10. What would be the time complexity of the BFS traversal of a graph with n vertices and n1.25 edges?
a) O(n)
b) O(n1.25)
c) O(n2.25)
d) O(n*n)
Answer: b
Explanation: The time complexity for BFS is O(|V| + |E|) = O(n + n1.25) = O(n1.25).
1. Breadth First Search is equivalent to which of the traversal in the Binary Trees?
a) Pre-order Traversal
b) Post-order Traversal
c) Level-order Traversal
d) In-order Traversal
Answer: c
Explanation: The Breadth First Search Algorithm searches the nodes on the basis of level. It takes a node
(level 0), explores it’s neighbors (level 1) and so on.
2. Time Complexity of Breadth First Search is? (V – number of vertices, E – number of edges)
a) O(V + E)
b) O(V)
c) O(E)
d) O(V*E)
Answer: a
Explanation: The Breadth First Search explores every node once and every edge once (in worst case), so it’s
time complexity is O(V + E).
3. The Data structure used in standard implementation of Breadth First Search is?
a) Stack
b) Queue
c) Linked List
d) Tree
Answer: b
Explanation: The Breadth First Search explores every node once and put that node in queue and then it takes
out nodes from the queue and explores it’s neighbors.
4. The Breadth First Search traversal of a graph will result into?

a) Linked List
b) Tree
c) Graph with back edges
d) Arrays
Answer: b
Explanation: The Breadth First Search will make a graph which don’t have back edges (a tree) which is
known as Breadth First Tree.
5. A person wants to visit some places. He starts from a vertex and then wants to visit every place connected
to this vertex and so on. What algorithm he should use?
c) Trim’s algorithm
d) Kruskal’s algorithm
Answer: b
Explanation: This is the definition of the Breadth First Search. Exploring a node, then it’s neighbors and so
on.
6. Which of the following is not an application of Breadth First Search?

a) Finding shortest path between two nodes
b) Finding bipartiteness of a graph
c) GPS navigation system
d) Path Finding
Answer: d
Explanation: Breadth First Search can be applied to Bipartite a graph, to find the shortest path between two
nodes, in GPS Navigation. In Path finding, Depth First Search is used.
7. When the Breadth First Search of a graph is unique?
a) When the graph is a Binary Tree
b) When the graph is a Linked List
c) When the graph is a n-ary Tree
d) When the graph is a Ternary Tree
Answer: b
Explanation: When Every node will have one successor then the Breadth First Search is unique. In all other
cases, when it will have more than one successor, it can choose any of them in arbitrary order.
8. Regarding implementation of Breadth First Search using queues, what is the maximum distance between
two nodes present in the queue? (considering each edge length 1)
a) Can be anything
b) 0
c) At most 1
d) Insufficient Information
Answer: c
Explanation: In the queue, at a time, only those nodes will be there whose difference among levels is 1.
Same as level order traversal of the tree.
9. In BFS, how many times a node is visited?

a) Once
b) Twice
c) Equivalent to number of indegree of the node
d) Thrice
Answer: c
Explanation: In Breadth First Search, we have to see whether the node is visited or not by it’s ancestor. If it
is visited, we won’t let it enter it in the queue.
1. Depth First Search is equivalent to which of the traversal in the Binary Trees?
a) Pre-order Traversal
b) Post-order Traversal
c) Level-order Traversal
d) In-order Traversal
Answer: a
Explanation: In Depth First Search, we explore all the nodes aggressively to one path and then backtrack to
the node. Hence, it is equivalent to the pre-order traversal of a Binary Tree.
2. Time Complexity of DFS is? (V – number of vertices, E – number of edges)

a) O(V + E)
b) O(V)
c) O(E)
d) O(V*E)
Answer: a
Explanation: The Depth First Search explores every node once and every edge once (in worst case), so it’s
time complexity is O(V + E).
3. The Data structure used in standard implementation of Breadth First Search is?
a) Stack
b) Queue
c) Linked List
d) Tree
Answer: a
Explanation: The Depth First Search is implemented using recursion. So, stack can be used as data structure
to implement depth first search.
4. The Depth First Search traversal of a graph will result into?

a) Linked List
b) Tree
c) Graph with back edges
d) Array
Answer: b
Explanation: The Depth First Search will make a graph which don’t have back edges (a tree) which is
known as Depth First Tree.
5. A person wants to visit some places. He starts from a vertex and then wants to visit every vertex till it
finishes from one vertex, backtracks and then explore other vertex from same vertex. What algorithm he
should use?
c) Trim’s algorithm
d) Kruskal’s Algorithm
Answer: a
Explanation: This is the definition of the Depth First Search. Exploring a node, then aggressively finding
nodes till it is not able to find any node.
6. Which of the following is not an application of Depth First Search?

a) For generating topological sort of a graph
b) For generating Strongly Connected Components of a directed graph
c) Detecting cycles in the graph
d) Peer to Peer Networks
Answer: d
Explanation: Depth First Search is used in the Generation of topological sorting, Strongly Connected
Components of a directed graph and to detect cycles in the graph. Breadth First Search is used in peer to
peer networks to find all neighbourhood nodes.
7. When the Depth First Search of a graph is unique?
a) When the graph is a Binary Tree
b) When the graph is a Linked List
c) When the graph is a n-ary Tree
d) When the graph is a ternary Tree
Answer: b
Explanation: When Every node will have one successor then the Depth First Search is unique. In all other
cases, when it will have more than one successor, it can choose any of them in arbitrary order.
8. Regarding implementation of Depth First Search using stacks, what is the maximum distance between
two nodes present in the stack? (considering each edge length 1)
a) Can be anything
b) 0
c) At most 1
d) Insufficient Information
Answer: a
Explanation: In the stack, at a time, there can be nodes which can differ in many levels. So, it can be the
maximum distance between two nodes in the graph.
9. In Depth First Search, how many times a node is visited?

a) Once
b) Twice
c) Equivalent to number of indegree of the node
d) Thrice
Answer: c
Explanation: In Depth First Search, we have to see whether the node is visited or not by it’s ancestor. If it is
visited, we won’t let it enter it in the stack.
1. Which of the following data structure is used to implement DFS?

a) linked list
b) tree
c) stack
d) queue
Answer: c
Explanation: Stack is used in the standard implementation of depth first search. It is used to store the
elements which are to be explored.
2. Which of the following traversal in a binary tree is similar to depth first traversal?
a) level order
b) post order
c) pre order
d) in order
Answer: c
Explanation: In DFS we keep on exploring as far as possible along each branch before backtracking. It
terminates when all nodes are visited. So it is similar to pre order traversal in binary tree.
3. What will be the result of depth first traversal in the following tree?
a) 4 2 5 1 3
b) 1 2 4 5 3
c) 4 5 2 3 1
d) 1 2 3 4 5
Answer: b
Explanation: Depth first search is similar to pre order traversal in a tree. So here we will get the same result
as for the pre order traversal (root,left right).
4. Which of the following is a possible result of depth first traversal of the given graph(consider 1 to be
source element)?
a) 1 2 3 4 5
b) 1 2 3 1 4 5
c) 1 4 5 3 2
d) 1 4 5 1 2 3
Answer: a
Explanation: As 1 is the source element so it will be considered first. Then we start exploring the vertices
which are connected to 1. So there will be two possible results-1 2 3 4 5 and 1 4 5 2 3.
5. Which of the following represent the correct pseudo code for non recursive DFS algorithm?
a)
procedure DFS-non_recursive(G,v):
//let St be a stack
St.push(v)
while St is not empty
v = St.pop()
if v is not discovered:
label v as discovered
for all adjacent vertices of v do
St.push(a) //a being the adjacent vertex
b)
advertisement
//let St be a stack
St.pop()
v = St.push(v)
c)
//let St be a stack
St.push(v)
v = St.pop()
St.push(v)
d)
//let St be a stack
St.pop(v)
v = St.pop()
Answer: a
Explanation: In the iterative approach we first push the source node into the stack. If the node has not been
visited then it is printed and marked as visited. Then the unvisited adjacent nodes are added to the stack.
Then the same procedure is repeated for each node of the stack.
6. What will be the time complexity of the iterative depth first traversal code(V=no. of vertices E=no.of
edges)?
a) O(V+E)
b) O(V)
c) O(E)
d) O(V*E)
Answer: a
Explanation: As the time required to traverse a full graph is V+E so its worst case time complexity becomes
O(V+E). The time complexity of iterative and recursive DFS are same.
7. Which of the following functions correctly represent iterative DFS?
a)
void DFS(int s)
{
vector<bool> discovered(V, true);
stack<int> st;
st.push(s);
while (!st.empty())
{
s = st.top();
st.pop();
if (!discovered[s])
{
cout << s << " ";
discovered[s] = true;
}
for (auto i = adjacent[s].begin(); i != adjacent[s].end(); ++i)
if (!discovered[*i])
st.push(*i);
}
}
b)
void DFS(int s)
{
vector<bool> discovered(V, false);
stack<int> st;
st.push(s);
while (!st.empty())
{
s = st.top();
st.pop();
if (!discovered[s])
{
cout << s << " ";
}
st.push(*i);
}
}
c)
void DFS(int s)
{
stack<int> st;
st.push(s);
while (!st.empty())
{
st.pop();
s = st.top();
if (!discovered[s])
{
cout << s << " ";
}
st.push(*i);
}
}
d)
void DFS(int s)
{
stack<int> st;
st.push(s);
while (!st.empty())
{
s = st.top();
st.pop();
if (!discovered[s])
{
cout << s << " ";
discovered[s] = false;
}
if (discovered[*i])
st.push(*i);
}
}
Answer: b
Explanation: In the correct version we first push the source node into the stack. If the node has not been
visited then it is printed and marked as visited. Then the unvisited adjacent nodes are added to the stack.
Then the same procedure is repeated for each node of the stack.
8. What is the space complexity of standard DFS(V: no. of vertices E: no. of edges)?
a) O(V+E)
b) O(V)
c) O(E)
d) O(V*E)
Answer: b
Explanation: In the worst case the space complexity of DFS will be O(V) in the case when all the vertices
are stored in stack. This space complexity is excluding the space required to store the graph.
9. Which of the following data structure is used to implement BFS?

a) linked list
b) tree
c) stack
d) queue
Answer: d
Explanation: Queue is used in the standard implementation of breadth first search. It is used to store the
vertices according to the code algorithm.
10. Choose the incorrect statement about DFS and BFS from the following?
a) BFS is equivalent to level order traversal in trees
b) DFS is equivalent to post order traversal in trees
c) DFS and BFS code has the same time complexity
d) BFS is implemented using queue
Answer: b
Explanation: DFS is equivalent to pre order traversal in trees, not post order traversal. It is so because in
DFS we keep on exploring as far as possible along each branch before backtracking. So it should be
equivalent to pre order traversal.
1. Branch and bound is a __________

a) problem solving technique
b) data structure
c) sorting algorithm
d) type of tree
Answer: a
Explanation: Branch and bound is a problem solving technique generally used for solving combinatorial
optimization problems. Branch and bound helps in solving them faster.
2. Which of the following is not a branch and bound strategy to generate branches?
a) LIFO branch and bound
b) FIFO branch and bound
c) Lowest cost branch and bound
d) Highest cost branch and bound
Answer: d
Explanation: LIFO, FIFO and Lowest cost branch and bound are different strategies to generate branches.
Lowest cost branch and bound helps us find the lowest cost path.
3. Which data structure is used for implementing a LIFO branch and bound strategy?
a) stack
b) queue
c) array
d) linked list
Answer: a
Explanation: Stack is the data structure is used for implementing LIFO branch and bound strategy. This
leads to depth first search as every branch is explored until a leaf node is discovered.
4. Which data structure is used for implementing a FIFO branch and bound strategy?
a) stack
b) queue
c) array
d) linked list
Answer: b
Explanation: Queue is the data structure is used for implementing FIFO branch and bound strategy.
Thisleads to breadth first search as every branch at depth is explored first before moving to the nodes at
greater depth.
5. Which data structure is most suitable for implementing best first branch and bound strategy?
a) stack
b) queue
c) priority queue
d) linked list
Answer: c
Explanation: Priority Queue is the data structure is used for implementing best first branch and bound
strategy. Dijkstra’s algorithm is an example of best first search algorithm.
6. Which of the following branch and bound strategy leads to breadth first search?
Answer: b
FIFO branch and bound leads to breadth first search.
7. Which of the following branch and bound strategy leads to depth first search?
Answer: a
LIFO branch and bound leads to depth first search.
8. Both FIFO branch and bound strategy and backtracking leads to depth first search.
a) true
b) false
Answer: b
Explanation: FIFO branch and bound leads to breadth first search. Whereas backtracking leads to depth first
search.
9. Both LIFO branch and bound strategy and backtracking leads to depth first search.
a) true
b) false
Answer: a
Explanation: Both backtrackings as well as branch and bound are problem solving algorithms. Both LIFO
branch and bound strategy and backtracking leads to depth first search.
10. Choose the correct statement from the following.
a) branch and bound is more efficient than backtracking
b) branch and bound is not suitable where a greedy algorithm is not applicable
c) branch and bound divides a problem into at least 2 new restricted sub problems
d) backtracking divides a problem into at least 2 new restricted sub problems
Answer: c
Explanation: Both backtracking as well as branch and bound are problem solving algorithms. Branch and
bound is less efficient than backtracking. Branch and bound divides a problem into at least 2 new restricted
sub problems.
11. Which of the following can traverse the state space tree only in DFS manner?
a) branch and bound
b) dynamic programming
c) greedy algorithm
d) backtracking
Answer: d
Explanation: Both backtracking as well as branch and bound are problem solving algorithms. Branch and
bound can traverse in DFS as well as BFS manner whereas backtracking only traverses in DFS manner.
1. Is Best First Search a searching algorithm used in graphs.

a) True
b) False
Answer: a
Explanation: Best First Search is a searching algorithm used in graphs. It explores it by choosing a node by
heuristic evaluation rule. It is used in solving searching for related problems.
2. Who described this Best First Search algorithm using heuristic evaluation rule?
a) Judea Pearl
b) Max Bezzel
c) Franz Nauck
d) Alan Turing
Answer: a
Explanation: The best first search algorithm using heuristic evaluation rule or function was proposed by an
Israeli – American computer scientist and philosopher Judea Pearl.
3. Which type of best first search algorithm was used to predict the closeness of the end of path and its
solution?
a) Greedy BFS
b) Divide and Conquer
c) Heuristic BFS
d) Combinatorial
Answer: a
Explanation: The greedy best first search algorithm was used to predict the closeness of the end of the path
and its solution by some of the computer scientists.
4. What is the other name of the greedy best first search?
a) Heuristic Search
b) Pure Heuristic Search
c) Combinatorial Search
d) Divide and Conquer Search
Answer: b
Explanation: The greedy best first search algorithm was used to predict the closeness of the end of the path
and its solution by some of the computer scientists. It is also known as Pure Heuristic Search.
5. Which algorithm is used in graph traversal and path finding?

a) A*
b) C*
c) D*
d) E*
Answer: a
Explanation: In computer science A* algorithm is used in graph traversal and path finding. It is a process of
node finding in between a path. It is an example of the best first search.
advertisement
6. Which algorithm is used to find the least cost path from source node to destination node?
a) A* BFS
b) C* BFS
c) D* BFS
d) B* BFS
Answer: d
Explanation: In computer science, B* algorithm is used to find the least cost path between the source node
and the destination node. It is an example of the best first search.
7. Which of the following is an example of Best First Search algorithm?

a) A*
b) B*
c) C*
d) Both A* and B*
Answer: d
Explanation: In computer science, A* algorithm is used in graph traversal and path finding. It is a process of
node finding in between a path. B* algorithm is used to find the least cost path between the source node and
the destination node.
8. Which of the following is the greedy best first search?
a) Pure Heuristic Search
b) A*
c) B*
d) Both A* and B*
Answer: a
Explanation: Pure Heuristic Search is also called greedy best first search while A* and B* search algorithms
are not greedy best first search.
9. Which of the following scientists didn’t publish A* algorithm?

a) Peter Hart
b) Nils Nilsson
c) Bertram Raphael
d) Hans Berliner
Answer: d
Explanation: Peter Hart Nils Nilsson Bertram Raphael are the three scientists of SRI International who first
published the A* search algorithm which uses heuristics for better performance. Hans Berliner published B*
algorithm.
10. Who published the B* search algorithm?

a) Peter Hart
b) Nils Nilsson
c) Bertram Raphael
d) Hans Berliner
Answer: d
Explanation: Hans Berliner was a Computer Science professor who first published the B* search algorithm
in 1979. While Peter Hart Nils Nilsson Bertram Raphael are the three scientists of SRI International who
first published the A* search algorithm which uses heuristics for better performance.
Hash Table and Heap
1. What is a hash table?
a) A structure that maps values to keys
b) A structure that maps keys to values
c) A structure used for storage
d) A structure used to implement stack and queue
View Answer
Answer: b
Explanation: A hash table is used to implement associative arrays which has a key-value pair, so the has
table maps keys to values.
2. If several elements are competing for the same bucket in the hash table, what is it called?
a) Diffusion
b) Replication
c) Collision
d) Duplication
View Answer
Answer: c
Explanation: In a hash table, if sevaral elements are computing for the same bucket then there will be a clash
among elements. This condition is called Collision. The Collision is reduced by adding elements to a linked
list and head address of linked list is placed in hash table.
3. What is direct addressing?

a) Distinct array position for every possible key
b) Fewer array positions than keys
c) Fewer keys than array positions
d) Same array position for all keys
View Answer
Answer: a
Explanation: Direct addressing is possible only when we can afford to allocate an array that has one position
for every possible key.
4. What is the search complexity in direct addressing?

a) O(n)
b) O(logn)
c) O(nlogn)
d) O(1)
View Answer
Answer: d
Explanation: Since every key has a unique array position, searching takes a constant time.
5. What is a hash function?
a) A function has allocated memory to keys
b) A function that computes the location of the key in the array
c) A function that creates an array
d) A function that computes the location of the values in the array
View Answer
Answer: b
Explanation: In a hash table, there are fewer array positions than the keys, so the position of the key in the
array has to be computed, this is done using the hash function.
6. Which of the following is not a technique to avoid a collision?

a) Make the hash function appear random
b) Use the chaining method
c) Use uniform hashing
d) Increasing hash table size
View Answer
Answer: d
Explanation: On increasing hash table size, space complexity will increase as we need to reallocate the
memory size of hash table for every collision. It is not the best technique to avoid a collision. We can avoid
collision by making hash function random, chaining method and uniform hashing.
7. What is the load factor?

a) Average array size
b) Average key size
c) Average chain length
d) Average hash table length
View Answer
Answer: c
Explanation: In simple chaining, load factor is the average number of elements stored in a chain, and is
given by the ratio of number of elements stored to the number of slots in the array.
8. What is simple uniform hashing?

a) Every element has equal probability of hashing into any of the slots
b) A weighted probabilistic method is used to hash elements into the slots
c) Elements has Random probability of hashing into array slots
d) Elements are hashed based on priority
View Answer
Answer: a
Explanation: In simple uniform hashing, any given element is equally likely to hash into any of the slots
available in the array.
9. In simple uniform hashing, what is the search complexity?

a) O(n)
b) O(logn)
c) O(nlogn)
d) O(1)
View Answer
Answer: d
Explanation: There are two cases, once when the search is successful and when it is unsuccessful, but in
10. In simple chaining, what data structure is appropriate?
c) Circular linked list
d) Binary trees
View Answer
Answer: b
Explanation: Deletion becomes easier with doubly linked list, hence it is appropriate.
1. Which scheme uses a randomization approach?

a) hashing by division
b) hashing by multiplication
c) universal hashing
d) open addressing
View Answer
Answer: c
Explanation: Universal hashing scheme uses a randomization approach whereas hashing by division and
hashing by multiplication are heuristic in nature.
2. Which hash function satisfies the condition of simple uniform hashing?

a) h(k) = lowerbound(km)
b) h(k)= upperbound(mk)
c) h(k)= lowerbound(k)
d) h(k)= upperbound(k)
View Answer
Answer: a
Explanation: If the keys are known to be random real numbers k independently and uniformly distributed in
the range 0<=k<=1, the hash function which satisfies the condition of simple uniform hashing is
h(k)= lowerbound(km).
3. A good hash approach is to derive the hash value that is expected to be dependent of any patterns that
might exist in the data.
a) True
b) False
View Answer
Answer: b
Explanation: A hash value is expected to be unrelated or independent of any patterns in the distribution of
keys.
4. Interpret the given character string as an integer expressed in suitable radix notation.
Character string = pt
a) 14963
b) 14392
c) 12784
d) 14452
View Answer
Answer: d
Explanation: The given character string can be interpreted as (112,116) (Ascii values) then expressed as a
radix-128 integer, hence the value is 112*128 + 116 = 14452.
5. What is the hash function used in the division method?

a) h(k) = k/m
b) h(k) = k mod m
c) h(k) = m/k
d) h(k) = m mod k
View Answer
Answer: b
Explanation: In division method for creating hash functions, k keys are mapped into one of m slots by taking
the reminder of k divided by m.
6. What can be the value of m in the division method?

a) Any prime number
b) Any even number
c) 2p – 1
d) 2p
View Answer
Answer: a
Explanation: A prime number not too close to an exact power of 2 is often a good choice for m since it
reduces the number of collisions which are likely to occur.
7. Which scheme provides good performance?

a) open addressing
b) universal hashing
c) hashing by division
d) hashing by multiplication
View Answer
Answer: b
Explanation: Universal hashing scheme provides better performance than other schemes because it uses a
unique randomisation approach.
8. Using division method, in a given hash table of size 157, the key of value 172 be placed at position ____
a) 19
b) 72
c) 15
d) 17
View Answer
Answer: c
Explanation: The key 172 can be placed at position 15 by using the formula
H(k) = k mod m
H(k) = 172 mod 157
H(k) = 15.
9. How many steps are involved in creating a hash function using a multiplication method?
a) 1
b) 4
c) 3
d) 2
View Answer
Answer: d
Explanation: In multiplication method 2 steps are involved. First multiplying the key value by a constant.
Then multiplying this value by m.
10. What is the hash function used in multiplication method?

a) h(k) = floor( m(kA mod 1))
b) h(k) = ceil( m(kA mod 1))
c) h(k) = floor(kA mod m)
d) h(k) = ceil( kA mod m)
View Answer
Answer: a
Explanation: The hash function can be computed by multiplying m with the fractional part of kA (kA mod
1) and then computing the floor value of the result.
11. What is the advantage of the multiplication method?

a) only 2 steps are involved
b) using constant
c) value of m not critical
d) simple multiplication
View Answer
Answer: c
Explanation: The value of m can be simply in powers of 2 since we can easily implement the function in
most computers. m=2p where p is an integer.
12. What is the table size when the value of p is 7 in multiplication method of creating hash functions?
a) 14
b) 128
c) 49
d) 127
View Answer
Answer: b
Explanation: In multiplication method of creating hash functions the table size can be taken in integral
13. What is the value of h(k) for the key 123456?
Given: p=14, s=2654435769, w=32
a) 123
b) 456
c) 70
d) 67
View Answer
Answer: d
Explanation: A = s/2w
A = 2654435769/ 232
k.A = 123456 * (2654435769/ 232)
= (76300 * 232) + 17612864
Hence r1= 76300; r0=17612864
Since w=14 the 14 most significant bits of r0 yield the value of h(k) as 67.
14. What is the average retrieval time when n keys hash to the same slot?
a) Theta(n)
b) Theta(n2)
c) Theta(nlog n)
d) Big-Oh(n2)
View Answer
Answer: a
Explanation: The average retrieval time when n keys hash to the same slot is given by Theta(n) as the
collision occurs in the hash table.
15. Collisions can be reduced by choosing a hash function randomly in a way that is independent of the keys
that are actually to be stored.
a) True
b) False
View Answer
Answer: a
Explanation: Because of randomization, the algorithm can behave differently on each execution, providing
good average case performance for any input.
1. In a max-heap, element with the greatest key is always in the which node?
a) Leaf node
b) First node of left sub tree
c) root node
d) First node of right sub tree
View Answer
Answer: c
Explanation: This is one of the property of max-heap that root node must have key greater than its children.
2. Heap exhibits the property of a binary tree?

a) True
b) False
View Answer
Answer: a
Explanation: Yes, because the leaf nodes are present at height h or h-1, which is a property of complete
binary tree.
3. What is the complexity of adding an element to the heap.
a) O(log n)
b) O(h)
c) O(log n) & O(h)
d) O(n)
View Answer
Answer: c
Explanation: The total possible operation in re locating the new location to a new element will be equal to
height of the heap.
4. The worst case complexity of deleting any arbitrary node value element from heap is __________
a) O(logn)
b) O(n)
c) O(nlogn)
d) O(n2)
View Answer
Answer: a
Explanation: The total possible operation in deleting the existing node and re locating new position to all its
connected nodes will be equal to height of the heap.
advertisement
5. Heap can be used as ________________

a) Priority queue
b) Stack
c) A decreasing order array
d) Normal Array
View Answer
Answer: a
Explanation: The property of heap that the value of root must be either greater or less than both of its
children makes it work like a priority queue.
6. If we implement heap as min-heap, deleting root node (value 1)from the heap. What would be the value of
root node after second iteration if leaf node (value 100) is chosen to replace the root at start.
a) 2
b) 100
c) 17
d) 3
View Answer
Answer: a
Explanation: As the root is deleted and node with value 100 is used as replaced one. There is a violation of
property that root node must have value less than its children. So there will be shuffling of node with value
7. If we implement heap as maximum heap , adding a new node of value 15 to the left most node of right
subtree. What value will be at leaf nodes of the right subtree of the heap.
a) 15 and 1
b) 25 and 1
c) 3 and 1
d) 2 and 3
View Answer
Answer: a
Explanation: As 15 is less than 25 so there would be no violation and the node will remain at that position.
So leaf nodes with value 15 and 1 will be at the position in right sub tree.
8. An array consists of n elements. We want to create a heap using the elements. The time complexity of
building a heap will be in order of
a) O(n*n*logn)
b) O(n*logn)
c) O(n*n)
d) O(n *logn *logn)
View Answer
Answer: b
Explanation: The total time taken will be N times the complexity of adding a single element to the heap.
And adding a single element takes logN time, so That is equal to N*logN.
1. Descending priority queue can be implemented using ______

a) max heap
b) min heap
c) min-max heap
d) trie
View Answer
Answer: a
Explanation: Descending priority queue arranges the elements based on their priority or value and allows
removing the elements in descending order. So, it can be efficiently implemented using max heap.
2. Min heap can be used to implement selection sort.

a) True
b) False
View Answer
Answer: a
Explanation: In min heap, the insertion and deletion operation takes O(logn) time. Therefore, a selection sort
with n insertions and n deletions can be implemented using a min heap in O(nlogn) operations.
3. Which of the following is the valid min heap?
a)
b)
c)
d)
View Answer
Answer: d
Explanation: In min heap the smallest is located at the root and the largest elements are located at the leaf
nodes. So, all leaf nodes need to be checked to find the largest element.
4. The procedure given below is used to maintain min-order in the min heap. Find out the missing
statements, represented as X.
procedure TrickleDownMin(i)
if A[i] has children then
m := index of smallest of the children
or grandchildren (if any) of A[i]
if A[m] is a grandchild of A[i] then
if A[m] < A[i] then
swap A[i] and A[m]
X: _______________________
____________________
endif
TrickleDownMin(m)
endif
else //{A[m] is a child of A[i]}
if A[m] < A[i] then
swap A[i] and A[m]
endif
endif
a) if A[m] > A[parent(m)] then

swap A[m] and A[parent(m)]
b) if A[m] > A[parent(m)] then
swap A[i] and A[parent(m)]
c) if A[m] < A[parent(m)] then
swap A[m] and A[parent(m)]
d) if A[m] > A[parent(m)] then
swap A[i] and A[parent(m)]
View Answer
Answer: a
Explanation: In TrickleDownMin() procedure, we maintain the min-ordering of the min heap. In this
procedure, we locate the lowest child or grandchild of the element at positions i. If the lowest element is
grandchild then we check that it is smaller than both, its parent and A[i].
5. The ascending heap property is ___________
a) A[Parent(i)] =A[i]
b) A[Parent(i)] <= A[i]
c) A[Parent(i)] >= A[i]
d) A[Parent(i)] > 2 * A[i]
View Answer
Answer: b
Explanation: The min heap is also known as ascending heap. Min heap of size n is an almost complete
binary tree of n nodes such that the element at each node is greater than or equal to the element at its parent
node.
6. The procedure FindMin() to find the minimum element and the procedure DeleteMin() to delete the
minimum element in min heap take _________
a) logarithmic and linear time constant respectively
b) constant and linear time respectively
c) constant and quadratic time respectively
d) constant and logarithmic time respectively
View Answer
Answer: d
Explanation: In the min heap, the root is the maximum element in the tree. So, locating it takes constant
time, but deleting it takes logarithmic time. Because after deleting it, the root is replaced with last element
and then the procedure to maintain the min ordering is invoked.
7. Which one of the following array elements represents a binary min heap?
a) 12 10 8 25 14 17
b) 8 10 12 25 14 17
c) 25 17 14 12 10 8
d) 14 17 25 10 12 8
View Answer
Answer: b
Explanation: A tree is min heap when data at every node in the tree is smaller than or equal to it’s children’ s
data. So, only 8 10 12 25 14 17 generates required tree.
8. In a binary min heap containing n elements, the largest element can be found in __________ time.
a) O(n)
b) O(nlogn)
c) O(logn)
d) O(1)
View Answer
Answer: a
Explanation: In min heap the smallest is located at the root and the largest elements are located at the leaf
nodes. So, all leaf nodes need to be checked to find the largest element. Thus, worst case time will be O (n).
9. Min heap is a complete binary tree.
a) True
b) False
View Answer
Answer: a
Explanation: A tree, in which all levels are fully filled, except possibly the last level, is called as the
complete binary tree. And min heap maintains shape property, so it is a complete binary tree. The shape
property ensures that all levels in the min heap are fully filled, except the last one, and, if the last level is not
filled completely, then fill the elements from left to right.
10. What will be the position of 5, when a max heap is constructed on the input elements 5, 70, 45, 7, 12, 15,
13, 65, 30, 25?
a) 5 will be at root
b) 5 will be at last level
c) 5 will be at second level
d) 5 can be anywhere in heap
View Answer
Answer: b
Explanation: In max heap the greatest element is at the root and the smallest elements are at the last level.
As 5 is the smallest input element, it will be at the last level.
1. Which of the following problems occur due to linear probing?

a) Primary collision
b) Secondary collision
c) Separate chaining
d) Extendible hashing
View Answer
Answer: a
Explanation: Primary collision occurs due to linear probing technique. It is overcome using a quadratic
probing technique.
2. How many probes are required on average for insertion and successful search?
a) 4 and 10
b) 2 and 6
c) 2.5 and 1.5
d) 3.5 and 1.5
View Answer
Answer: c
Explanation: Using formula, the average number of probes required for insertion is 2.5 and for a successful
search, it is 1.5.
3. What is the load factor for an open addressing technique?
a) 1
b) 0.5
c) 1.5
d) 0
View Answer
Answer: b
Explanation: The load factor for an open addressing technique should be 0.5. For separate chaining
technique, the load factor is 1.
4. Which of the following is not a collision resolution strategy for open addressing?
a) Linear probing
b) Quadratic probing
c) Double hashing
d) Rehashing
View Answer
Answer: d
Explanation: Linear probing, quadratic probing and double hashing are all collision resolution strategies for
open addressing whereas rehashing is a different technique.
5. In linear probing, the cost of an unsuccessful search can be used to compute the average cost of a
successful search.
a) True
b) False
View Answer
Answer: a
Explanation: Using random collision resolution algorithm, the cost of an unsuccessful search can be used to
compute the average cost of a successful search.
6. Which of the following is the correct function definition for linear probing?
a) F(i)= 1
b) F(i)=i
c) F(i)=i2
d) F(i)=i+1
View Answer
Answer: b
Explanation: The function used in linear probing is defined as, F(i)=I where i=0,1,2,3….,n.
7. ___________ is not a theoretical problem but actually occurs in real implementations of probing.
a) Hashing
b) Clustering
c) Rehashing
d) Collision
View Answer
Answer: b
Explanation: Clustering is not a theoretical problem but it occurs in implementations of hashing. Rehashing
is a kind of hashing.
8. What is the hash function used in linear probing?
a) H(x)= key mod table size
b) H(x)= (key+ F(i2)) mod table size
c) H(x)= (key+ F(i)) mod table size
d) H(x)= X mod 17
View Answer
Answer: c
Explanation: The hash function used in linear probing is defined to be H(x)= (key+ F(i)) mod table size
where i=0,1,2,3,…,n.
9. Hashing can be used in online spelling checkers.

a) True
b) False
View Answer
Answer: a
Explanation: If misspelling detection is important, an entire dictionary can be pre-hashed and words can be
checked in constant time.
10. In the following given hash table, use linear probing to find the location of 49.
0
1
2
3
4
5
6
7
8 18
9 89
a) 7
b) 6
c) 2
d) 0
View Answer
Answer: d
Explanation: Initially, collision occurs while hashing 49 for the first time.
Hence, after setting f(i)=1, the hashed location is found to be 0.
11. What is the formula to find the expected number of probes for an unsuccessful search in linear probing?
a) 121+1(1−⅄)
b) 121+1(1−⅄)2
c) 121+1(1+⅄)
d) 121+1(1+⅄)(1−⅄)
View Answer
Answer: b
Explanation: The mathematical formula for calculating the number of probes for an unsuccessful search is
121+1(1−⅄)2. For insertion, it is 121+1(1−⅄)
Greedy Algo
1. Fractional knapsack problem is also known as __________
a) 0/1 knapsack problem
b) Continuous knapsack problem
c) Divisible knapsack problem
d) Non continuous knapsack problem
View Answer
Answer: b
Explanation: Fractional knapsack problem is also called continuous knapsack problem. Fractional knapsack
is solved using dynamic programming.
2. Fractional knapsack problem is solved most efficiently by which of the following algorithm?
a) Divide and conquer
b) Dynamic programming
c) Greedy algorithm
d) Backtracking
View Answer
Answer: c
Explanation: Greedy algorithm is used to solve this problem. We first sort items according to their
value/weight ratio and then add item with highest ratio until we cannot add the next item as a whole. At the
end, we add the next item as much as we can.
3. What is the objective of the knapsack problem?

a) To get maximum total value in the knapsack
b) To get minimum total value in the knapsack
c) To get maximum weight in the knapsack
d) To get minimum weight in the knapsack
View Answer
Answer: a
Explanation: The objective is to fill the knapsack of some given volume with different materials such that
the value of selected items is maximized.
4. Which of the following statement about 0/1 knapsack and fractional knapsack problem is correct?
a) In 0/1 knapsack problem items are divisible and in fractional knapsack items are indivisible
b) Both are the same
c) 0/1 knapsack is solved using a greedy algorithm and fractional knapsack is solved using dynamic
programming
d) In 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisible
View Answer
Answer: d
Explanation: In fractional knapsack problem we can partially include an item into the knapsack whereas in
0/1 knapsack we have to either include or exclude the item wholly.
5. Time complexity of fractional knapsack problem is ____________
a) O(n log n)
b) O(n)
c) O(n2)
d) O(nW)
View Answer
Answer: a
Explanation: As the main time taking a step is of sorting so it defines the time complexity of our code. So
the time complexity will be O(n log n) if we use quick sort for sorting.
6. Fractional knapsack problem can be solved in time O(n).

a) True
b) False
View Answer
Answer: a
Explanation: It is possible to solve the problem in O(n) time by adapting the algorithm for finding weighted
medians.
7. Given items as {value,weight} pairs {{40,20},{30,10},{20,5}}. The capacity of knapsack=20. Find the
maximum value output assuming items to be divisible.
a) 60
b) 80
c) 100
d) 40
View Answer
Answer: a
Explanation: The value/weight ratio are-{2,3,4}. So we include the second and third items wholly into the
knapsack. This leaves only 5 units of volume for the first item. So we include the first item partially.
Final value = 20+30+(40/4)=60.
8. The result of the fractional knapsack is greater than or equal to 0/1 knapsack.
a) True
b) False
View Answer
Answer: a
Explanation: As fractional knapsack gives extra liberty to include the object partially which is not possible
with 0/1 knapsack, thus we get better results with a fractional knapsack.
9. The main time taking step in fractional knapsack problem is ___________

a) Breaking items into fraction
b) Adding items into knapsack
c) Sorting
d) Looping through sorted items
View Answer
Answer: c
Explanation: The main time taking step is to sort the items according to their value/weight ratio. It defines
the time complexity of the code.
10. Given items as {value,weight} pairs {{60,20},{50,25},{20,5}}. The capacity of knapsack=40. Find the
maximum value output assuming items to be divisible and nondivisible respectively.
a) 100, 80
b) 110, 70
c) 130, 110
d) 110, 80
View Answer
Answer: d
Explanation: Assuming items to be divisible-
The value/weight ratio are {3, 2, 4}.So we include third and first items wholly. So, now only 15 units of
volume are left for second item. So we include it partially.
Final volume = 20+60+50x(15/25)=80+30=110
Assuming items to be indivisible- In this case we will have to leave one item due to insufficient capacity.
Final volume = 60 + 20 = 80.
1. Which of the following algorithms is the best approach for solving Huffman codes?
a) exhaustive search
b) greedy algorithm
c) brute force algorithm
d) divide and conquer algorithm
View Answer
Answer: b
Explanation: Greedy algorithm is the best approach for solving the Huffman codes problem since it greedily
searches for an optimal solution.
2. How many printable characters does the ASCII character set consists of?
a) 120
b) 128
c) 100
d) 98
View Answer
Answer: c
Explanation: Out of 128 characters in an ASCII set, roughly, only 100 characters are printable while the rest
are non-printable.
3. Which bit is reserved as a parity bit in an ASCII set?

a) first
b) seventh
c) eighth
d) tenth
View Answer
Answer: c
Explanation: In an ASCII character set, seven bits are reserved for character representation while the eighth
bit is a parity bit.
4. How many bits are needed for standard encoding if the size of the character set is X?
a) log X
b) X+1
c) 2X
d) X2
View Answer
Answer: a
Explanation: If the size of the character set is X, then [log X] bits are needed for representation in a standard
encoding.
5. The code length does not depend on the frequency of occurrence of characters.
a) true
b) false
View Answer
Answer: b
Explanation: The code length depends on the frequency of occurrence of characters. The more frequent the
character occurs, the less is the length of the code.
6. In Huffman coding, data in a tree always occur?

a) roots
b) leaves
c) left sub trees
d) right sub trees
View Answer
Answer: b
Explanation: In Huffman encoding, data is always stored at the leaves of a tree inorder to compute the
codeword effectively.
7. From the following given tree, what is the code word for the character ‘a’?
a) 011
b) 010
c) 100
d) 101
View Answer
Answer: a
Explanation: By recording the path of the node from root to leaf, the code word for character ‘a’ is found to
be 011.
8. From the following given tree, what is the computed codeword for ‘c’?
a) 111
b) 101
c) 110
d) 011
View Answer
Answer: c
Explanation: By recording the path of the node from root to leaf, assigning left branch as 0 and right branch
as 1, the codeword for c is 110.
9. What will be the cost of the code if character ci is at depth di and occurs at frequency fi?
a) cifi
b) ∫cifi
c) ∑fidi
d) fidi
View Answer
Answer: c
Explanation: If character ci is at depth di and occurs at frequency fi, the cost of the codeword obtained is
∑fidi.
10. An optimal code will always be present in a full tree.

a) true
b) false
View Answer
Answer: a
Explanation: An optimal tree will always have the property that all nodes are either leaves or have two
children. Otherwise, nodes with one child could move up a level.
11. The type of encoding where no character code is the prefix of another character code is called?
a) optimal encoding
b) prefix encoding
c) frequency encoding
d) trie encoding
View Answer
Answer: b
Explanation: Even if the character codes are of different lengths, the encoding where no character code is the
prefix of another character code is called prefix encoding.
12. What is the running time of the Huffman encoding algorithm?

a) O(C)
b) O(log C)
c) O(C log C)
d) O( N log C)
View Answer
Answer: c
Explanation: If we maintain the trees in a priority queue, ordered by weight, then the running time is given
by O(C log C).
13. What is the running time of the Huffman algorithm, if its implementation of the priority queue is done
using linked lists?
a) O(C)
b) O(log C)
c) O(C log C)
d) O(C2)
View Answer
Answer: d
Explanation: If the implementation of the priority queue is done using linked lists, the running time of
Huffman algorithm is O(C2).
1. Which of the following is false in the case of a spanning tree of a graph G?
a) It is tree that spans G
b) It is a subgraph of the G
c) It includes every vertex of the G
d) It can be either cyclic or acyclic
View Answer
Answer: d
Explanation: A graph can have many spanning trees. Each spanning tree of a graph G is a subgraph of the
graph G, and spanning trees include every vertex of the gram. Spanning trees are always acyclic.
2. Every graph has only one minimum spanning tree.

a) True
b) False
View Answer
Answer: b
Explanation: Minimum spanning tree is a spanning tree with the lowest cost among all the spacing trees.
Sum of all of the edges in the spanning tree is the cost of the spanning tree. There can be many minimum
spanning trees for a given graph.
3. Consider a complete graph G with 4 vertices. The graph G has ____ spanning trees.
a) 15
b) 8
c) 16
d) 13
View Answer
Answer: c
Explanation: A graph can have many spanning trees. And a complete graph with n vertices has n(n-2)
spanning trees. So, the complete graph with 4 vertices has 4(4-2) = 16 spanning trees.
4. The travelling salesman problem can be solved using _________

a) A spanning tree
b) A minimum spanning tree
c) Bellman – Ford algorithm
d) DFS traversal
View Answer
Answer: b
Explanation: In the travelling salesman problem we have to find the shortest possible route that visits every
city exactly once and returns to the starting point for the given a set of cities. So, travelling salesman
problem can be solved by contracting the minimum spanning tree.
5. Consider the graph M with 3 vertices. Its adjacency matrix is shown below. Which of the following is
true?
a) Graph M has no minimum spanning tree

b) Graph M has a unique minimum spanning trees of cost 2
c) Graph M has 3 distinct minimum spanning trees, each of cost 2
d) Graph M has 3 spanning trees of different costs
View Answer
Answer: c
Explanation: Here all non-diagonal elements in the adjacency matrix are 1. So, every vertex is connected
every other vertex of the graph. And, so graph M has 3 distinct minimum spanning trees.
6. Consider a undirected graph G with vertices { A, B, C, D, E}. In graph G, every edge has distinct weight.
Edge CD is edge with minimum weight and edge AB is edge with maximum weight. Then, which of the
following is false?
a) Every minimum spanning tree of G must contain CD
b) If AB is in a minimum spanning tree, then its removal must disconnect G
c) No minimum spanning tree contains AB
d) G has a unique minimum spanning tree
View Answer
Answer: c
Explanation: Every MST will contain CD as it is smallest edge. So, Every minimum spanning tree of G must
contain CD is true. And G has a unique minimum spanning tree is also true because the graph has edges
with distinct weights. So, no minimum spanning tree contains AB is false.
7. If all the weights of the graph are positive, then the minimum spanning tree of the graph is a minimum
cost subgraph.
a) True
b) False
View Answer
Answer: a
Explanation: A subgraph is a graph formed from a subset of the vertices and edges of the original graph.
And the subset of vertices includes all endpoints of the subset of the edges. So, we can say MST of a graph
is a subgraph when all weights in the original graph are positive.
8.
8. Consider the graph shown below. Which of the following are the edges in the MST of the given graph?
a) (a-c)(c-d)(d-b)(d-b)
b) (c-a)(a-d)(d-b)(d-e)
c) (a-d)(d-c)(d-b)(d-e)
d) (c-a)(a-d)(d-c)(d-b)(d-e)
View Answer
Answer: c
Explanation: The minimum spanning tree of the given graph is shown below. It has cost 56.
9. Which of the following is not the algorithm to find the minimum spanning tree of the given graph?
a) Boruvka’s algorithm
b) Prim’s algorithm
c) Kruskal’s algorithm
d) Bellman–Ford algorithm
View Answer
Answer: d
Explanation: The Boruvka’s algorithm, Prim’s algorithm and Kruskal’s algorithm are the algorithms that can
be used to find the minimum spanning tree of the given graph.
The Bellman-Ford algorithm is used to find the shortest path from the single source to all other vertices.
10. Which of the following is false?

a) The spanning trees do not have any cycles
b) MST have n – 1 edges if the graph has n edges
c) Edge e belonging to a cut of the graph if has the weight smaller than any other edge in the same cut, then
the edge e is present in all the MSTs of the graph
d) Removing one edge from the spanning tree will not make the graph disconnected
View Answer
Answer: d
Explanation: Every spanning tree has n – 1 edges if the graph has n edges and has no cycles. The MST
follows the cut property, Edge e belonging to a cut of the graph if has the weight smaller than any other edge
in the same cut, then the edge e is present in all the MSTs of the graph.
1. Kruskal’s algorithm is used to ______
a) find minimum spanning tree
b) find single source shortest path
c) find all pair shortest path algorithm
d) traverse the graph
View Answer
Answer: a
Explanation: The Kruskal’s algorithm is used to find the minimum spanning tree of the connected graph. It
construct the MST by finding the edge having the least possible weight that connects two trees in the forest.
2. Kruskal’s algorithm is a ______

a) divide and conquer algorithm
b) dynamic programming algorithm
c) greedy algorithm
d) approximation algorithm
View Answer
Answer: c
Explanation: Kruskal’s algorithm uses a greedy algorithm approach to find the MST of the connected
weighted graph. In the greedy method, we attempt to find an optimal solution in stages.
3. Consider the given graph.
What is the weight of the minimum spanning tree using the Kruskal’s algorithm?
a) 24
b) 23
c) 15
d) 19
View Answer
Answer: d
Explanation: Kruskal’s algorithm constructs the minimum spanning tree by constructing by adding the edges
to spanning tree one-one by one. The MST for the given graph is,
So, the weight of the MST is 19.

4. What is the time complexity of Kruskal’s algorithm?
a) O(log V)
b) O(E log V)
c) O(E2)
d) O(V log E)
View Answer
Answer: b
Explanation: Kruskal’s algorithm involves sorting of the edges, which takes O(E logE) time, where E is a
number of edges in graph and V is the number of vertices. After sorting, all edges are iterated and union-find
algorithm is applied. union-find algorithm requires O(logV) time. So, overall Kruskal’s algorithm requires
O(E log V) time.
5. Consider the following graph. Using Kruskal’s algorithm, which edge will be selected first?
a) GF
b) DE
c) BE
d) BG
View Answer
Answer: c
Explanation: In Krsuskal’s algorithm the edges are selected and added to the spanning tree in increasing
order of their weights. Therefore, the first edge selected will be the minimal one. So, correct option is BE.
advertisement
6. Which of the following edges form minimum spanning tree on the graph using kruskals algorithm?
a) (B-E)(G-E)(E-F)(D-F)
b) (B-E)(G-E)(E-F)(B-G)(D-F)
c) (B-E)(G-E)(E-F)(D-E)
d) (B-E)(G-E)(E-F)(D-F)(D-G)
View Answer
Answer: a
Explanation: Using Krushkal’s algorithm on the given graph, the generated minimum spanning tree is
shown below.
So, the edges in the MST are, (B-E)(G-E)(E-F)(D-F).

a) Prim’s algorithm can also be used for disconnected graphs
b) Kruskal’s algorithm can also run on the disconnected graphs
c) Prim’s algorithm is simpler than Kruskal’s algorithm
d) In Kruskal’s sort edges are added to MST in decreasing order of their weights
View Answer
Answer: b
Explanation: Prim’s algorithm iterates from one node to another, so it can not be applied for disconnected
graph. Kruskal’s algorithm can be applied to the disconnected graphs to construct the minimum cost forest.
Kruskal’s algorithm is comparatively easier and simpler than prim’s algorithm.
8. Which of the following is false about the Kruskal’s algorithm?
a) It is a greedy algorithm
b) It constructs MST by selecting edges in increasing order of their weights
c) It can accept cycles in the MST
d) It uses union-find data structure
View Answer
Answer: c
Explanation: Kruskal’s algorithm is a greedy algorithm to construct the MST of the given graph. It
constructs the MST by selecting edges in increasing order of their weights and rejects an edge if it may form
the cycle. So, using Kruskal’s algorithm is never formed.
9. Kruskal’s algorithm is best suited for the dense graphs than the prim’s algorithm.
a) True
b) False
View Answer
Answer: b
Explanation: Prim’s algorithm outperforms the Kruskal’s algorithm in case of the dense graphs. It is
significantly faster if graph has more edges than the Kruskal’s algorithm.
10. Consider the following statements.

S1. Kruskal’s algorithm might produce a non-minimal spanning tree.
S2. Kruskal’s algorithm can efficiently implemented using the disjoint-set data structure.
a) S1 is true but S2 is false
b) Both S1 and S2 are false
c) Both S1 and S2 are true
d) S2 is true but S1 is false
View Answer
Answer: d
Explanation: In Kruskal’s algorithm, the disjoint-set data structure efficiently identifies the components
containing a vertex and adds the new edges. And Kruskal’s algorithm always finds the MST for the
connected graph.

a) Prim’s algorithm initialises with a vertex
b) Prim’s algorithm initialises with a edge
c) Prim’s algorithm initialises with a vertex which has smallest edge
d) Prim’s algorithm initialises with a forest
View Answer
Answer: a
Explanation: Steps in Prim’s algorithm: (I) Select any vertex of given graph and add it to MST (II) Add the
edge of minimum weight from a vertex not in MST to the vertex in MST; (III) It MST is complete the stop,
otherwise go to step (II).
2. Consider the given graph.
What is the weight of the minimum spanning tree using the Prim’s algorithm,starting from vertex a?
a) 23
b) 28
c) 27
d) 11
View Answer
Answer: c
Explanation: In Prim’s algorithm, we select a vertex and add it to the MST. Then we add the minimum edge
from the vertex in MST to vertex not in MST. From, figure shown below weight of MST = 27.
3. Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used?
a) O(log V)
b) O(V2)
c) O(E2)
d) O(V log E)
View Answer
Answer: b
Explanation: Use of adjacency matrix provides the simple implementation of the Prim’s algorithm. In Prim’s
algorithm, we need to search for the edge with a minimum for that vertex. So, worst case time complexity
will be O(V2), where V is the number of vertices.
4. Prim’s algorithm is a ______

a) Divide and conquer algorithm
b) Greedy algorithm
c) Dynamic Programming
d) Approximation algorithm
View Answer
Answer: b
Explanation: Prim’s algorithm uses a greedy algorithm approach to find the MST of the connected weighted
graph. In greedy method, we attempt to find an optimal solution in stages.
5. Prim’s algorithm resembles Dijkstra’s algorithm.
a) True
b) False
View Answer
Answer: a
Explanation: In Prim’s algorithm, the MST is constructed starting from a single vertex and adding in new
edges to the MST that link the partial tree to a new vertex outside of the MST. And Dijkstra’s algorithm also
rely on the similar approach of finding the next closest vertex. So, Prim’s algorithm resembles Dijkstra’s
algorithm.
6. Kruskal’s algorithm is best suited for the sparse graphs than the prim’s algorithm.
a) True
b) False
View Answer
Answer: a
Explanation: Prim’s algorithm and Kruskal’s algorithm perform equally in case of the sparse graphs. But
Kruskal’s algorithm is simpler and easy to work with. So, it is best suited for sparse graphs.
7. Consider the graph shown below.
Which of the following edges form the MST of the given graph using Prim’a algorithm, starting from vertex
4.
a) (4-3)(5-3)(2-3)(1-2)
b) (4-3)(3-5)(5-1)(1-2)
c) (4-3)(3-5)(5-2)(1-5)
d) (4-3)(3-2)(2-1)(1-5)
View Answer
Answer: d
Explanation: The MST for the given graph using Prim’s algorithm starting from vertex 4 is,
So, the MST contains edges (4-3)(3-2)(2-1)(1-5).

8. Prim’s algorithm is also known as __________
a) Dijkstra–Scholten algorithm
b) Borůvka’s algorithm
c) Floyd–Warshall algorithm
d) DJP Algorithm
View Answer
Answer: d
Explanation: The Prim’s algorithm was developed by Vojtěch Jarník and it was latter discovered by the duo
Prim and Dijkstra. Therefore, Prim’s algorithm is also known as DJP Algorithm.
9. Prim’s algorithm can be efficiently implemented using _____ for graphs with greater density.
a) d-ary heap
b) linear search
c) fibonacci heap
d) binary search
View Answer
Answer: a
Explanation: In Prim’s algorithm, we add the minimum weight edge for the chosen vertex which requires
searching on the array of weights. This searching can be efficiently implemented using binary heap for
dense graphs. And for graphs with greater density, Prim’s algorithm can be made to run in linear time using
d-ary heap(generalization of binary heap).
10. Which of the following is false about Prim’s algorithm?

a) It is a greedy algorithm
b) It constructs MST by selecting edges in increasing order of their weights
c) It never accepts cycles in the MST
d) It can be implemented using the Fibonacci heap
View Answer
Answer: b
Explanation: Prim’s algorithm can be implemented using Fibonacci heap and it never accepts cycles. And
Prim’s algorithm follows greedy approach. Prim’s algorithms span from one vertex to another.
1. Dijkstra’s Algorithm is used to solve _____________ problems.

a) All pair shortest path
b) Single source shortest path
c) Network flow
d) Sorting
View Answer
Answer: b
Explanation: Dijkstra’s Algorithm is used for solving single source shortest path problems. In this algorithm,
a single node is fixed as a source node and shortest paths from this node to all other nodes in graph is found.
2. Which of the following is the most commonly used data structure for implementing Dijkstra’s Algorithm?
a) Max priority queue
b) Stack
c) Circular queue
d) Min priority queue
View Answer
Answer: d
Explanation: Minimum priority queue is the most commonly used data structure for implementing Dijkstra’s
Algorithm because the required operations to be performed in Dijkstra’s Algorithm match with specialty of
a minimum priority queue.
3. What is the time complexity of Dijikstra’s algorithm?

a) O(N)
b) O(N3)
c) O(N2)
d) O(logN)
View Answer
Answer: c
Explanation: Time complexity of Dijkstra’s algorithm is O(N2) because of the use of doubly nested for
loops. It depends on how the table is manipulated.
4. Dijkstra’s Algorithm cannot be applied on ______________

a) Directed and weighted graphs
b) Graphs having negative weight function
c) Unweighted graphs
d) Undirected and unweighted graphs
View Answer
Answer: b
Explanation: Dijkstra’s Algorithm cannot be applied on graphs having negative weight function because
calculation of cost to reach a destination node from the source node becomes complex.
5. What is the pseudo code to compute the shortest path in Dijkstra’s algorithm?
a)
if(!T[w].Known)
if(T[v].Dist + C(v,w) < T[w].Dist) {
Decrease(T[w].Dist to T[v].Dist +C(v,w));
T[w].path=v; }
b)
if(T[w].Known)
Increase (T[w].Dist to T[v].Dist +C(v,w));
T[w].path=v; }
c)
if(!T[w].Known)
if(T[v].Dist + C(v,w) > T[w].Dist) {
Decrease(T[w].Dist to T[v].Dist +C(v,w);
T[w].path=v; }
d)
if(T[w].Known)
Increase(T[w].Dist to T[v].Dist);
T[w].path=v; }
View Answer
Answer: a
Explanation: If the known value of the adjacent vertex(w) is not set then check whether the sum of distance
from source vertex(v) and cost to travel from source to adjacent vertex is less than the existing distance of
the adjacent node. If so, perform decrease key operation.
6. How many priority queue operations are involved in Dijkstra’s Algorithm?

a) 1
b) 3
c) 2
d) 4
View Answer
Answer: b
Explanation: The number of priority queue operations involved is 3. They are insert, extract-min and
decrease key.
7. How many times the insert and extract min operations are invoked per vertex?
a) 1
b) 2
c) 3
d) 0
View Answer
Answer: a
Explanation: Insert and extract min operations are invoked only once per vertex because each vertex is
added only once to the set and each edge in the adjacency list is examined only once during the course of
algorithm.
8. The maximum number of times the decrease key operation performed in Dijkstra’s algorithm will be
equal to ___________
a) Total number of vertices
b) Total number of edges
c) Number of vertices – 1
d) Number of edges – 1
View Answer
Answer: b
Explanation: If the total number of edges in all adjacency list is E, then there will be a total of E number of
iterations, hence there will be a total of at most E decrease key operations.
9. What is running time of Dijkstra’s algorithm using Binary min- heap method?
a) O(V)
b) O(VlogV)
c) O(E)
d) O(ElogV)
View Answer
Answer: d
Explanation: Time required to build a binary min heap is O(V). Each decrease key operation takes O(logV)
and there are still at most E such operations. Hence total running time is O(ElogV).
10. The running time of Bellmann Ford algorithm is lower than that of Dijkstra’s Algorithm.
a) True
b) False
View Answer
Answer: b
Explanation: The number of iterations involved in Bellmann Ford Algorithm is more than that of Dijkstra’s
Algorithm.
11. Dijkstra’s Algorithm run on a weighted, directed graph G={V,E} with non-negative weight function w
and source s, terminates with d[u]=delta(s,u) for all vertices u in V.
a) True
b) False
View Answer
Answer: a
Explanation: The equality d[u]=delta(s,u) holds good when vertex u is added to set S and this equality is
maintained thereafter by the upper bound property.
12. Given pseudo code of Dijkstra’s Algorithm.
//Initialise single source(G,s)

S=0
Q=V[G]
While Q != 0
Do u=extract-min(Q)
S=S union {u}
For each vertex v in adj[u]
Do relax(u,v,w)
What happens when “While Q != 0” is changed to “while Q>1”?

a) While loop gets executed for v times
b) While loop gets executed for v-1 times
c) While loop gets executed only once
d) While loop does not get executed
View Answer
Answer: b
Explanation: In the normal execution of Dijkstra’s Algorithm, the while loop gets executed V times. The
change in the while loop statement causes it to execute only V – 1 times.
13. Consider the following graph.
If b is the source vertex, what is the minimum cost to reach f vertex?

a) 8
b) 9
c) 4
d) 6
View Answer
Answer: d
Explanation: The minimum cost to reach f vertex from b vertex is 6 by having vertices g and e as
intermediates.
b to g, cost is 1
g to e, cost is 4
e to f, cost is 1
hence total cost 1+4+1=6.
14. In the given graph, identify the shortest path having minimum cost to reach vertex E if A is the source
vertex.
a) a-b-e
b) a-c-e
c) a-c-d-e
d) a-c-d-b-e
View Answer
Answer: b
Explanation: The minimum cost required to travel from vertex A to E is via vertex C
A to C, cost= 3
C to E, cost= 2
Hence the total cost is 5.
15. Dijkstra’s Algorithm is the prime example for ___________

a) Greedy algorithm
b) Branch and bound
c) Back tracking
d) Dynamic programming
View Answer
Answer: a
Explanation: Dijkstra’s Algorithm is the prime example for greedy algorithms because greedy algorithms
generally solve a problem in stages by doing what appears to be the best thing at each stage.
1. You are given an array of elements where each array element represents the MAXIMUM number of
jumps that can be made in the forward direction from that element. You have to find the minimum number
of jumps that are required to reach the end of the array. Which of these methods can be used to solve the
problem?
a) Dynamic Programming
b) Greedy Algorithm
c) Recursion
d) Recursion and Dynamic Programming
View Answer
Answer: d
Explanation: Both recursion and dynamic programming can be used to solve minimum number of jumps
problem.
2. Consider the following array:
{1, 3, 5, 8, 9, 2, 6, 7, 6}
What is the minimum number of jumps required to reach the end of the array?
a) 1
b) 2
c) 3
d) 4
View Answer
Answer: c
Explanation: The jumps made will be:{1 -> 2 -> 4 -> 9}. So, the number of jumps is three.
3. Consider the following recursive implementation:
#include<stdio.h>
#include<limits.h>
int min_jumps(int *arr, int strt, int end)
{
int idx;
if(strt == end)
return 0;
if(arr[strt] == 0) // jump cannot be made
return INT_MAX;
int min = INT_MAX;
for(idx = 1; idx <= arr[strt] && strt + idx <= end; idx++)
{
int jumps = min_jumps(____,____,____) + 1;
if(jumps < min)
min = jumps;
}
return min;
}
int main()
{
int arr[] ={1, 3, 5, 8, 9, 2, 6, 7, 6},len = 9;
int ans = min_jumps(arr, 0, len-1);
printf("%d\n",ans);
return 0;
}
Which of these arguments should be passed by the min_jumps function represented by the blanks?
a) arr, strt + idx, end
b) arr + idx, strt, end
c) arr, strt, end
d) arr, strt, end + idx
View Answer
Answer: a
Explanation: arr, strt + idx, end should be passed as arguments.
4. For a given array, there can be multiple ways to reach the end of the array using minimum number of
jumps.
a) True
b) False
View Answer
Answer: a
Explanation: Consider the array {1,2,3,4,5}. It is possible to reach the end in the following ways: {1 -> 2 ->
3 -> 5} or {1 -> 2 -> 4 -> 5}.
5. What is the output of the following program?
#include<stdio.h>
#include<limits.h>
int min_jumps(int *arr, int strt, int end)
{
int idx;
if(strt == end)
return 0;
if(arr[strt] == 0) // jump cannot be made
return INT_MAX;
int min = INT_MAX;
for(idx = 1; idx <= arr[strt] && strt + idx <= end; idx++)
{
int jumps = min_jumps(arr, strt + idx, end) + 1;
if(jumps < min)
min = jumps;
}
return min;
}
int main()
{
int arr[] ={1, 2, 3, 4, 5, 4, 3, 2, 1},len = 9;
int ans = min_jumps(arr, 0, len-1);
printf("%d\n",ans);
return 0;
}
a) 4
b) 5
c) 6
d) 7
View Answer
Answer: a
Explanation: The program prints the minimum number of jumps required to reach the end of the array. One
way reach the end using minimum number of jumps is
{1 -> 2 -> 4 -> 8 -> 9}. So, the number of jumps is 4.
6. For any array, given that at most one element is non-zero, it is ALWAYS possible to reach the end of the
array using minimum jumps.
a) True
b) False
View Answer
Answer: b
Explanation: Consider the array {1,0,2,3,4}.
In this case, only one element is 0 but it is not possible to reach the end of the array.
7. Consider the following dynamic programming implementation of the minimum jumps problem:
#include<stdio.h>
#include<limits.h>
int min_jump(int *arr, int len)
{
int j, idx, jumps[len];
jumps[len - 1] = 0;
for(idx = len - 2; idx >= 0; idx--)
{
int tmp_min = INT_MAX;
for(j = 1; j <= arr[idx] && idx + j < len; j++)
{
if(jumps[idx + j] + 1 < tmp_min)
tmp_min = jumps[idx + j] + 1;
}
jumps[idx] = tmp_min;
}
return jumps[0];
}
int main()
{
int arr[] ={1, 1, 1, 1, 1, 1, 1, 1, 1},len = 9;
int ans = min_jump(arr,len);
printf("%d\n",ans);
return 0;
}
Which of the following “for” loops can be used instead of the inner for loop so that the output doesn’t
change?
a) for(j = 1; j < arr[idx] + len; j++)
b) for(j = 0; j < arr[idx] – len; j++)
c) for(j = idx + 1; j < len && j <= arr[idx] + idx; j++)
d) No change is required
View Answer
Answer: d
Explanation: None of the above mentioned “for” loops can be used instead of the inner for loop. Note, for(j
= idx + 1; j < len && j <= arr[idx] + idx; j++) covers the same range as the inner for loop but it produces the
wrong output because the indexing inside the loops changes as “j” takes different values in the two “for”
loops.
]
8. What is the time complexity of the following dynamic programming implementation used to find the
minimum number of jumps?
#include<stdio.h>
#include<limits.h>
{
jumps[len - 1] = 0;
{
{
}
}
return jumps[0];
}
int main()
{
int arr[] ={1, 1, 1, 1, 1, 1, 1, 1, 1},len = 9;
printf("%d\n",ans);
return 0;
}
a) O(1)
b) O(n)
c) O(n2)
d) None of the mentioned
View Answer
Answer: c
Explanation: The time complexity of the above dynamic programming implementation is O(n2).
9. What is the space complexity of the following dynamic programming implementation used to find the
minimum number of jumps?
#include<stdio.h>
#include<limits.h>
{
jumps[len - 1] = 0;
{
{
}
}
return jumps[0];
}
int main()
{
int arr[] ={1, 1, 1, 1, 1, 1, 1, 1, 1},len = 9;
printf("%d\n",ans);
return 0;
}
a) O(1)
b) O(n)
c) O(n2)
d) O(5)
View Answer
Answer: b
Explanation: The space complexity of the above dynamic programming implementation is O(n).
#include<stdio.h>
#include<limits.h>
{
jumps[len - 1] = 0;
{
{
}
}
return jumps[0];
}
int main()
{
int arr[] ={1, 1, 1, 1, 1, 1, 1, 1, 1},len = 9;
printf("%d\n",ans);
return 0;
}
a) 7
b) 8
c) 9
d) 10
View Answer
Answer: b
Explanation: The program prints the minimum jumps required to reach the end of the array, which is 8 and
so the output is 8.
#include<stdio.h>
#include<limits.h>
{
jumps[len - 1] = 0;
{
{
}
}
return jumps[0];
}
int main()
{
int arr[] ={9, 9, 9, 9, 9, 9, 9, 9, 9},len = 9;
printf("%d\n",ans);
return 0;
}
a) 1
b) 6
c) 2
d) 7
View Answer
Answer: a
Explanation: The program prints the minimum jumps required to reach the end of the array, which is 1 and
so the output is 1.
Divied and Conquer
1. What is the advantage of recursive approach than an iterative approach?
a) Consumes less memory
b) Less code and easy to implement
c) Consumes more memory
d) More code has to be written
View Answer
Answer: b
Explanation: A recursive approach is easier to understand and contains fewer lines of code.
2. Choose the appropriate code that does binary search using recursion.
a)
public static int recursive(int arr[], int low, int high, int key)
{
int mid = low + (high - low)/2;
if(arr[mid] == key)
{
return mid;
}
else if(arr[mid] < key)
{
return recursive(arr,mid+1,high,key);
}
else
{
return recursive(arr,low,mid-1,key);
}
}
b)
{
int mid = low + (high + low)/2;
if(arr[mid] == key)
{
return mid;
}
{
return recursive(arr,mid-1,high,key);
}
else
{
return recursive(arr,low,mid+1,key);
}
}
c)
{
int mid = low + (high - low)/2;
if(arr[mid] == key)
{
return mid;
}
{
return recursive(arr,mid,high,key);
}
else
{
}
}
d)
{
int mid = low + ((high - low)/2)+1;
if(arr[mid] == key)
{
return mid;
}
{
return recursive(arr,mid,high,key);
}
else
{
}
}
View Answer
Answer: a
Explanation: Calculate the ‘mid’ value, and check if that is the key, if not, call the function again with 2 sub
arrays, one with till mid-1 and the other starting from mid+1.
3. Given an input arr = {2,5,7,99,899}; key = 899; What is the level of recursion?
a) 5
b) 2
c) 3
d) 4
View Answer
Answer: c
Explanation: level 1: mid = 7
level 2: mid = 99
level 3: mid = 899(this is the key).
4. Given an array arr = {45,77,89,90,94,99,100} and key = 99; what are the mid values(corresponding array
elements) in the first and second levels of recursion?
a) 90 and 99
b) 90 and 94
c) 89 and 99
d) 89 and 94
View Answer
Answer: a
Explanation: At first level key = 90
At second level key= 99
Here 90 and 99 are mid values.
5. What is the worst case complexity of binary search using recursion?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
View Answer
Answer: b
Explanation: Using the divide and conquer master theorem.
6. What is the average case time complexity of binary search using recursion?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
View Answer
Answer: b
Explanation: T(n) = T(n/2) + 1, Using the divide and conquer master theorem.
7. Which of the following is not an application of binary search?

a) To find the lower/upper bound in an ordered sequence
b) Union of intervals
c) Debugging
d) To search in unordered list
View Answer
Answer: d
Explanation: In Binary search, the elements in the list should be sorted. It is applicable only for ordered list.
Hence Binary search in unordered list is not an application.
8. Choose among the following code for an iterative binary search.

a)
public static int iterative(int arr[], int key)

{
int low = 0;
int mid = 0;
int high = arr.length-1;
while(low <= high)
{
mid = low + (high + low)/2;
if(arr[mid] == key)
{
return mid;
}
{
low = mid - 1;
}
else
{
high = mid + 1;
}
}
return -1;
}
b)

{
int low = 0;
int mid = 0;
while(low <= high)
{
mid = low + (high - low)/2;
if(arr[mid] == key)
{
return mid;
}
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return -1;
}
c)

{
int low = 0;
int mid = 0;
while(low <= high)
{
mid = low + (high + low)/2;
if(arr[mid] == key)
{
return mid;
}
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return -1;
}
d)

{
int low = 0;
int mid = 0;
while(low <= high)
{
mid = low + (high - low)/2;
if(arr[mid] == key)
{
return mid;
}
{
low = mid - 1;
}
else
{
high = mid + 1;
}
}
return -1;
}
View Answer
Answer: b
Explanation: Find the ‘mid’, check if it equals the key, if not, continue the iterations until low <= high.
9. Binary Search can be categorized into which of the following?

a) Brute Force technique
b) Divide and conquer
c) Greedy algorithm
View Answer
Answer: b
Explanation: Since ‘mid’ is calculated for every iteration or recursion, we are diving the array into half and
then try to solve the problem.
10. Given an array arr = {5,6,77,88,99} and key = 88; How many iterations are done until the element is
found?
a) 1
b) 3
c) 4
d) 2
View Answer
Answer: d
Explanation: Iteration1 : mid = 77; Iteration2 : mid = 88;
11. Given an array arr = {45,77,89,90,94,99,100} and key = 100; What are the mid values(corresponding
array elements) generated in the first and second iterations?
a) 90 and 99
b) 90 and 100
c) 89 and 94
d) 94 and 99
View Answer
Answer: a
Explanation: Trace the input with the binary search iterative code.
12. What is the time complexity of binary search with iteration?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
View Answer
Answer: b
Explanation: T(n) = T(n/2) + theta(1)
Using the divide and conquer master theorem, we get the time complexity as O(logn).
1. Merge sort uses which of the following technique to implement sorting?

a) backtracking
b) greedy algorithm
c) divide and conquer
d) dynamic programming
View Answer
Answer: c
Explanation: Merge sort uses divide and conquer in order to sort a given array. This is because it divides the
array into two halves and applies merge sort algorithm to each half individually after which the two sorted
halves are merged together.
2. What is the average case time complexity of merge sort?

a) O(n log n)
b) O(n2)
c) O(n2 log n)
d) O(n log n2)
View Answer
Answer: a
Explanation: The recurrence relation for merge sort is given by T(n) = 2T(n/2) + n. It is found to be equal to
O(n log n) using the master theorem.
3. What is the auxiliary space complexity of merge sort?

a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
View Answer
Answer: c
Explanation: An additional space of O(n) is required in order to merge two sorted arrays. Thus merge sort is
not an in place sorting algorithm.
4. Merge sort can be implemented using O(1) auxiliary space.

a) true
b) false
View Answer
Answer: a
Explanation: Standard merge sort requires O(n) space to merge two sorted arrays. We can optimize this
merging process so that it takes only constant space. This version is known as in place merge sort.
5. What is the worst case time complexity of merge sort?
a) O(n log n)
b) O(n2)
c) O(n2 log n)
d) O(n log n2)
View Answer
Answer: a
Explanation: The time complexity of merge sort is not affected by worst case as its algorithm has to
implement the same number of steps in any case. So its time complexity remains to be O(n log n).
6. Which of the following method is used for sorting in merge sort?

a) merging
b) partitioning
c) selection
d) exchanging
View Answer
Answer: a
Explanation: Merge sort algorithm divides the array into two halves and applies merge sort algorithm to
each half individually after which the two sorted halves are merged together. Thus its method of sorting is
called merging.
7. What will be the best case time complexity of merge sort?

a) O(n log n)
b) O(n2)
c) O(n2 log n)
d) O(n log n2)
View Answer
Answer: a
Explanation: The time complexity of merge sort is not affected in any case as its algorithm has to implement
the same number of steps. So its time complexity remains to be O(n log n) even in the best case.
8. Which of the following is not a variant of merge sort?

a) in-place merge sort
b) bottom up merge sort
c) top down merge sort
d) linear merge sort
View Answer
Answer: d
Explanation: In-place, top down and bottom up merge sort are different variants of merge sort. Whereas
linear merge sort is not a possible variant as it is a comparison based sort and the minimum time complexity
of any comparison based sort is O(n log n).
9. Choose the incorrect statement about merge sort from the following?
a) it is a comparison based sort
b) it is an adaptive algorithm
c) it is not an in place algorithm
d) it is stable algorithm
View Answer
Answer: b
Explanation: Merge sort is not an adaptive sorting algorithm. This is because it takes O(n log n) time
complexity irrespective of any case.
10. Which of the following is not in place sorting algorithm by default?

a) merge sort
b) quick sort
c) heap sort
d) insertion sort
View Answer
Answer: a
Explanation: Quick sort, heap sort, and insertion sort are in-place sorting algorithms, whereas an additional
space of O(n) is required in order to merge two sorted arrays. Even though we have a variation of merge sort
(to do in-place sorting), it is not the default option. So, among the given choices, merge sort is the most
appropriate answer.
11. Which of the following is not a stable sorting algorithm?

a) Quick sort
b) Cocktail sort
c) Bubble sort
d) Merge sort
View Answer
Answer: a
Explanation: Out of the given options quick sort is the only algorithm which is not stable. Merge sort is a
stable sorting algorithm.
12. Which of the following stable sorting algorithm takes the least time when applied to an almost sorted
array?
a) Quick sort
b) Insertion sort
c) Selection sort
d) Merge sort
View Answer
Answer: d
Explanation: Insertion sort takes linear time to sort a partially sorted array. Though merge and quick sort
takes O(n*logn) complexity to sort, merge sort is stable. Hence, Merge sort takes less time to sort partially
sorted array.
13. Merge sort is preferred for arrays over linked lists.

a) true
b) false
View Answer
Answer: b
Explanation: Merge sort is preferred for linked list over arrays. It is because in a linked list the insert.
14. Which of the following sorting algorithm makes use of merge sort?
a) tim sort
b) intro sort
c) bogo sort
d) quick sort
View Answer
Answer: a
Explanation: Tim sort is a hybrid sorting algorithm as it uses more than one sorting algorithm internally. It
makes use of merge sort and insertion sort.
15. Choose the correct code for merge sort.

a)
void merge_sort(int arr[], int left, int right)

{
if (left > right)
{
int mid = (right-left)/2;

merge_sort(arr, left, mid);
merge_sort(arr, mid+1, right);
merge(arr, left, mid, right); //function to merge sorted arrays

}
}
b)

{
if (left < right)
{
int mid = left+(right-left)/2;


}
}
c)

{
if (left < right)
{
int mid = left+(right-left)/2;

}
}
d)

{
if (left < right)
{
int mid = (right-left)/2;

}
}
View Answer
Answer: b
Explanation: Merge sort first sorts the two halves of the array individually. Then it merges the two sorted
halves in order to obtain sorted array.
16. Which of the following sorting algorithm does not use recursion?
a) quick sort
b) merge sort
c) heap sort
d) bottom up merge sort
View Answer
Answer: d
Explanation: Bottom up merge sort uses the iterative method in order to implement sorting. It begins by
merging a pair of adjacent array of size 1 each and then merge arrays of size 2 each in the next step and so
on.
1. Which of the following sorting algorithms is the fastest?

a) Merge sort
b) Quick sort
c) Insertion sort
d) Shell sort
View Answer
Answer: b
Explanation: Quick sort is the fastest known sorting algorithm because of its highly optimized inner loop.
2. Quick sort follows Divide-and-Conquer strategy.

a) True
b) False
View Answer
Answer: a
Explanation: In quick sort, the array is divided into sub-arrays and then it is sorted (divide-and-conquer
strategy).
3. What is the worst case time complexity of a quick sort algorithm?
a) O(N)
b) O(N log N)
c) O(N2)
d) O(log N)
View Answer
Answer: c
Explanation: The worst case performance of a quick sort algorithm is mathematically found to be O(N2).
4. Which of the following methods is the most effective for picking the pivot element?
a) first element
b) last element
c) median-of-three partitioning
d) random element
View Answer
Answer: c
Explanation: Median-of-three partitioning is the best method for choosing an appropriate pivot element.
Picking a first, last or random element as a pivot is not much effective.
5. Find the pivot element from the given input using median-of-three partitioning method.
8, 1, 4, 9, 6, 3, 5, 2, 7, 0.
a) 8
b) 7
c) 9
d) 6
View Answer
Answer: d
Explanation: Left element=8, right element=0,
Centre=[position(left+right)/2]=6.
6. Which is the safest method to choose a pivot element?

a) choosing a random element as pivot
b) choosing the first element as pivot
c) choosing the last element as pivot
d) median-of-three partitioning method
View Answer
Answer: a
Explanation: This is the safest method to choose the pivot element since it is very unlikely that a random
pivot would consistently provide a poor partition.
7. What is the average running time of a quick sort algorithm?

a) O(N2)
b) O(N)
c) O(N log N)
d) O(log N)
View Answer
Answer: c
Explanation: The best case and average case analysis of a quick sort algorithm are mathematically found to
be O(N log N).
8. Which of the following sorting algorithms is used along with quick sort to sort the sub arrays?
a) Merge sort
b) Shell sort
c) Insertion sort
d) Bubble sort
View Answer
Answer: c
Explanation: Insertion sort is used along with quick sort to sort the sub arrays.
It is used only at the end.
9. Quick sort uses join operation rather than merge operation.

a) true
b) false
View Answer
Answer: a
Explanation: Quick sort uses join operation since join is a faster operation than merge.
10. How many sub arrays does the quick sort algorithm divide the entire array into?
a) one
b) two
c) three
d) four
View Answer
Answer: b
Explanation: The entire array is divided into two partitions, 1st sub array containing elements less than the
pivot element and 2nd sub array containing elements greater than the pivot element.
11. Which is the worst method of choosing a pivot element?

a) first element as pivot
b) last element as pivot
c) median-of-three partitioning
d) random element as pivot
View Answer
Answer: a
Explanation: Choosing the first element as pivot is the worst method because if the input is pre-sorted or in
reverse order, then the pivot provides a poor partition.
12. Which among the following is the best cut-off range to perform insertion sort within a quick sort?
a) N=0-5
b) N=5-20
c) N=20-30
d) N>30
View Answer
Answer: b
Explanation: A good cut-off range is anywhere between N=5 and N=20 to avoid nasty degenerate cases.
1. Quick sort is a __________
a) greedy algorithm
b) divide and conquer algorithm
c) dynamic programming algorithm
d) backtracking algorithm
View Answer
Answer: b
Explanation: Quick sort is a divide and conquer algorithm. Quick sort first partitions a large array into two
smaller sub-arrays. And then recursively sorts the sub-arrays.
2. What is the worst case time complexity of the Quick sort?

a) O(nlogn)
b) O(n)
c) O(n3)
d) O(n2)
View Answer
Answer: d
Explanation: The worst case running time for Quick sort is O(n2). In Quick sort, the worst case behaviour
occurs when the partitioning routine produces two sub-arrays one with n – 1 element and other with 0
elements.
3. Apply Quick sort on a given sequence 7 11 14 6 9 4 3 12. What is the sequence after first phase, pivot is
first element?
a) 6 4 3 7 11 9 14 12
b) 6 3 4 7 9 14 11 12
c) 7 6 14 11 9 4 3 12
d) 7 6 4 3 9 14 11 12
View Answer
Answer: b
Explanation: Let’s apply Quick sort on the given sequence,
For first phase, pivot = 7
7 11 14 6 9 4 3 12
i j
7 11 14 6 9 4 3 12
i j
7 3 14 6 9 4 11 12
i j
7 3 4 6 9 14 11 12
i j
7 3 4 6 9 14 11 12
j i
6 3 4 7 9 14 11 12
4. The best case behaviour occurs for quick sort is, if partition splits the array of size n into __________
a) n/2 : (n/2) – 1
b) n/2 : n/3
c) n/4 : 3n/2
d) n/4 : 3n/4
View Answer
Answer: a
Explanation: The best case analysis of quick sort occurs when the partition splits the array into two
subarrays, each of size no more than n/2 since one is of size n/2 and one of size (n/2) – 1.
5. Quick sort is a stable sorting algorithm.
a) True
b) False
View Answer
Answer: b
Explanation: In stable sorting algorithm the records with equal keys appear in the same order in the sorted
sequence as they appear in the input unsorted sequence. Quick sort does not preserve the relative order of
equal sort items. Therefore, Quick sort is not a stable sort.
6. Consider the Quick sort algorithm in which the partitioning procedure splits elements into two sub-arrays
and each sub-array contains at least one-fourth of the elements. Let T(n) be the number of comparisons
required to sort array of n elements. Then T(n)<=?
a) T(n) <= 2 T(n/4) + cn
b) T(n) <= T(n/4) + T(3n/4) + cn
c) T(n) <= 2 T(3n/4) + cn
d) T(n) <= T(n/3) + T(3n/4) + cn
View Answer
Answer: b
Explanation: If there are n/4 elements in one sub-array then T(n/4) comparisons are needed for this sub-
array. And T(3n/4) comparison are required for the rest 4n/5 elements, and cn is time required for finding
the pivot. If there are more than n/4 elements in one sub-array then other sub-array will have less than 3n/4
elements and time complexity will be less than T(n/4) + T(3n/4) + cn.
7. Consider the Quick sort algorithm which sorts elements in ascending order using the first element as
pivot. Then which of the following input sequence will require a maximum number of comparisons when
this algorithm is applied on it?
a) 22 25 56 67 89
b) 52 25 76 67 89
c) 22 25 76 67 50
d) 52 25 89 67 76
View Answer
Answer: a
Explanation: If the input sequence is already sorted then worst case behaviour occurs for the Quick sort
algorithm which use the first element as pivot. Therefore, the input sequence given in 22 25 56 67 89 will
require a maximum number of comparisons.
8. A machine needs a minimum of 200 sec to sort 1000 elements by Quick sort. The minimum time needed
to sort 200 elements will be approximately __________
a) 60.2 sec
b) 45.54 sec
c) 31.11 sec
d) 20 sec
View Answer
Answer: c
Explanation: The Quick sort requires nlog2n comparisons in best case, where n is size of input array. So,
1000 * log21000 ≈ 9000 comparisons are required to sort 1000 elements, which takes 200 sec. To sort 200
elements minimum of 200 * log2200 ≈ 1400 comparisons are required. This will take 200 * 1400 / 9000 ≈
31.11 sec.
9. Which one of the following sorting algorithm is best suited to sort an array of 1 million elements?
a) Bubble sort
b) Insertion sort
c) Merge sort
d) Quick sort
View Answer
Answer: d
Explanation: The Quick sort is best suited to sort the array of 1 million elements. The practical
implementations of Quick sort use randomised version. In practice randomised Quick sort algorithms rarely
shows worst case behaviour and is almost always O(nlogn). And Quick sort requires little additional space
and exhibits good cache locality.
10. Quick sort is a space-optimised version of ____

a) Bubble sort
b) Selection sort
c) Insertion sort
d) Binary tree sort
View Answer
Answer: d
Explanation: Quick sort is a space-optimised version of the binary tree sort. In binary sort tree, the elements
are inserted sequentially into the binary search tree and Quick sort organises elements into a tree that is
implied by the recursive calls.
1. QuickSort can be categorized into which of the following?

a) Brute Force technique
b) Divide and conquer
c) Greedy algorithm
View Answer
Answer: b
Explanation: First you divide(partition) the array based on the pivot element and sort accordingly.
2. Select the appropriate recursive call for QuickSort.(arr is the array, low is the starting index and high is
the ending index of the array, partition returns the pivot element, we will see the code for partition very
soon)
a)
public static void quickSort(int[] arr, int low, int high)

{
int pivot;
if(high>low)
{
pivot = partition(arr, low, high);
quickSort(arr, low, pivot-1);
quickSort(arr, pivot+1, high);
}
}
b)

{
int pivot;
if(high<low)
{
quickSort(arr, low, pivot-1);
}
}
c)

{
int pivot;
if(high>low)
{
quickSort(arr, low, pivot);
quickSort(arr, pivot, high);
}
}
d)

{
int pivot;
if(high>low)
{
quickSort(arr, low, pivot);
}
}
View Answer
Answer: a
Explanation: Based on the pivot returned by the call to partition, recursive calls to quickSort sort the given
array.
3. What is the worst case complexity of QuickSort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
View Answer
Answer: d
Explanation: When the input array is already sorted.
4. What is a randomized QuickSort?

a) The leftmost element is chosen as the pivot
b) The rightmost element is chosen as the pivot
c) Any element in the array is chosen as the pivot
d) A random number is generated which is used as the pivot
View Answer
Answer: c
Explanation: QuickSort is randomized by placing the input data in the randomized fashion in the array or by
choosing a random element in the array as a pivot.
5. Which of the following code performs the partition operation in QuickSort?

a)
private static int partition(int[] arr, int low, int high)
{
int left, right, pivot_item = arr[low];

left = low;
right = high;
while(left > right)
{
while(arr[left] <= pivot_item)
{
left++;
}
while(arr[right] > pivot_item)
{
right--;
}
if(left < right)
{
swap(arr, left, right);
}
}
arr[low] = arr[right];
arr[right] = pivot_item;
return right;
}
b)
{

left = low;
right = high;
while(left <= right)
{
while(arr[left] <= pivot_item)
{
left++;
}
while(arr[right] > pivot_item)
{
right--;
}
if(left < right)
{
}
}
return right;
}
c)
{

left = low;
right = high;
while(left <= right)
{
while(arr[left] > pivot_item)
{
left++;
}
while(arr[right] <= pivot_item)
{
right--;
}
if(left < right)
{
}
}
return right;
}
d)
{
left = low;
right = high;
while(left > right)
{
while(arr[left] > pivot_item)
{
left++;
}
while(arr[right] <= pivot_item)
{
right--;
}
if(left < right)
{
}
}
return right;
}
View Answer
Answer: b
Explanation: The array is partitioned such that the elements left to the pivot are lesser than the pivot while
the elements right of the pivot are greater than the pivot.
6. What is the best case complexity of QuickSort?

a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
View Answer
Answer: a
Explanation: The array is partitioned into equal halves, using the Divide and Conquer master theorem, the
complexity is found to be O(nlogn).
7. The given array is arr = {2,3,4,1,6}. What are the pivots that are returned as a result of subsequent
partitioning?
a) 1 and 3
b) 3 and 1
c) 2 and 6
d) 6 and 2
View Answer
Answer: a
Explanation: The call to partition returns 1 and 3 as the pivot elements.
8. What is the average case complexity of QuickSort?

a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
View Answer
Answer: a
Explanation: The position of partition(split) is unknown, hence all(n) possibilities are considered, the
average is found by adding all and dividing by n.
9. The given array is arr = {2,6,1}. What are the pivots that are returned as a result of subsequent
partitioning?
a) 1 and 6
b) 6 and 1
c) 2 and 6
d) 1
View Answer
Answer: d
Explanation: There is only one pivot with which the array will be sorted, the pivot is 1.
10. Which of the following is not true about QuickSort?
a) in-place algorithm
b) pivot position can be changed
c) adaptive sorting algorithm
d) can be implemented as a stable sort
View Answer
Answer: b
Explanation: Once a pivot is chosen, its position is finalized in the sorted array, it cannot be modified.
1. Euclid’s algorithm is used for finding ___________

a) GCD of two numbers
b) GCD of more than three numbers
c) LCM of two numbers
d) LCM of more than two numbers
View Answer
Answer: a
Explanation: Euclid’s algorithm is basically used to find the GCD of two numbers. It cannot be directly
applied to three or more numbers at a time.
2. Who invented Euclid’s algorithm?

a) Sieve
b) Euclid
c) Euclid-Sieve
d) Gabriel lame
View Answer
Answer: b
Explanation: Euclid invented Euclid’s algorithm. Sieve provided an algorithm for finding prime numbers.
Gabriel lame proved a theorem in Euclid’s algorithm.
3. If 4 is the GCD of 16 and 12, What is the GCD of 12 and 4?

a) 12
b) 6
c) 4
d) 2
View Answer
Answer: c
Explanation: Euclid’s algorithm states that the GCD of two numbers does not change even if the bigger
number is replaced by a difference of two numbers. So, GCD of 16 and 12 and 12 and (16-12)=4 is the
same.
4. Which of the following is not an application of Euclid’s algorithm?

a) Simplification of fractions
b) Performing divisions in modular arithmetic
c) Solving quadratic equations
d) Solving diophantine equations
View Answer
Answer: c
Explanation: Solving quadratic equations is not an application of Euclid’s algorithm whereas the rest of the
options are mathematical applications of Euclid’s algorithm.
5. The Euclid’s algorithm runs efficiently if the remainder of two numbers is divided by the minimum of
two numbers until the remainder is zero.
a) True
b) False
View Answer
Answer: a
Explanation: The Euclid’s algorithm runs efficiently if the remainder of two numbers is divided by the
minimum of two numbers until the remainder is zero. This improvement in efficiency was put forth by
Gabriel Lame.
6. According to Gabriel lame, how many steps does Euclid’s algorithm require to solve a problem?
a) Less than five times the number of digits
b) More than five times the number of digits
c) Less than two times the number of digits
d) More than two times the number of digits
View Answer
Answer: a
Explanation: The Euclid’s algorithm requires less than five times the number of digits. It runs by dividing
two numbers. It stops when a remainder zero is reached.
7. Which of the following is the correct mathematical application of Euclid’s algorithm?

a) Determination of prime numbers
b) Lagrange’s four square theorem
c) Cauchy-Euler theorem
d) Residue theorem
View Answer
Answer: b
Explanation: Lagrange’s four square theorem is one of the mathematical applications of Euclid’s algorithm
and it is the basic tool for proving theorems in number theory. It can be generalized into other types of
numbers like the Gaussian integers.
8. If GCD of two numbers is 1, then the two numbers are said to be ________
a) Co-prime numbers
b) Prime numbers
c) Composite numbers
d) Rational numbers
View Answer
Answer: a
Explanation: If GCD of two numbers is 1, they are called as co-prime or relatively prime numbers. It does
not mean that they are prime numbers. They don’t have any prime factors in common.
9. What is the total running time of Euclid’s algorithm?

a) O(N)
b) O(N log M)
c) O(N log N)
d) O(log N +1)
View Answer
Answer: a
Explanation: The total running time of Euclid’s algorithm according to Lame’s analysis is found to be O(N).
10. Euclidean algorithm does not require the calculation of prime factors.
a) True
b) False
View Answer
Answer: a
Explanation: Euclid’s algorithm does not require the calculation of prime factors. We derive the answer
straight away using formula. And also, factorization is complex.
11. What is the formula for Euclidean algorithm?

a) GCD (m,n) = GCD (n, m mod n)
b) LCM(m,n)=LCM(n, m mod n)
c) GCD(m,n,o,p) = GCD (m, m mod n, o, p mod o)
d) LCM (m,n,o,p) = LCM (m, m mod n, o, p mod o)
View Answer
Answer: a
Explanation: The formula for computing GCD of two numbers using Euclidean algorithm is given as GCD
(m,n)= GCD (n, m mod n). It is used recursively until zero is obtained as a remainder.
12. What is the total running time of the binary GCD algorithm?
a) O(N)
b) O(N2)
c) O(log N)
d) O(N log N)
View Answer
Answer: b
Explanation: Binary GCD algorithm is a sub division of Euclidean algorithm with more faster operations. Its
running time is given by O(N2).
13. What is the GCD of 20 and 12 using Euclid’s algorithm?

a) 8
b) 2
c) 4
d) 6
View Answer
Answer: c
Explanation: GCD(m,n)=GCD(n, m mod n)
GCD(20,12)=GCD( 12,8)
= GCD(8,4)
= GCD(4,0) = 4.
1. What is the objective of tower of hanoi puzzle?

a) To move all disks to some other rod by following rules
b) To divide the disks equally among the three rods by following rules
c) To move all disks to some other rod in random order
d) To divide the disks equally among three rods in random order
View Answer
Answer: a
Explanation: Objective of tower of hanoi problem is to move all disks to some other rod by following the
following rules-1) Only one disk can be moved at a time. 2) Disk can only be moved if it is the uppermost
disk of the stack. 3) No disk should be placed over a smaller disk.
2. Which of the following is NOT a rule of tower of hanoi puzzle?

a) No disk should be placed over a smaller disk
b) Disk can only be moved if it is the uppermost disk of the stack
c) No disk should be placed over a larger disk
d) Only one disk can be moved at a time
View Answer
Answer: c
Explanation: The rule is to not put a disk over a smaller one. Putting a smaller disk over larger one is
allowed.
3. The time complexity of the solution tower of hanoi problem using recursion is _________
a) O(n2)
b) O(2n)
c) O(n log n)
d) O(n)
View Answer
Answer: b
Explanation: Time complexity of the problem can be found out by solving the recurrence relation:
T(n)=2T(n-1)+c. Result of this relation is found to be equal to 2n. It can be solved using substitution.
4. Recurrence equation formed for the tower of hanoi problem is given by _________
a) T(n) = 2T(n-1)+n
b) T(n) = 2T(n/2)+c
c) T(n) = 2T(n-1)+c
d) T(n) = 2T(n/2)+n
View Answer
Answer: c
Explanation: As there are 2 recursive calls to n-1 disks and one constant time operation so the recurrence
relation will be given by T(n) = 2T(n-1)+c.
5. Minimum number of moves required to solve a tower of hanoi problem with n disks is __________
a) 2n
b) 2n-1
c) n2
d) n2-1
View Answer
Answer: b
Explanation: Minimum number of moves can be calculated by solving the recurrence relation – T(n)=2T(n-
1)+c. Alternatively we can observe the pattern formed by the series of number of moves 1,3,7,15…..Either
way it turn out to be equal to 2n-1.
6. Space complexity of recursive solution of tower of hanoi puzzle is ________
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer
Answer: b
Explanation: Space complexity of tower of hanoi problem can be found out by solving the recurrence
relation T(n)=T(n-1)+c. Result of this relation is found out to be n. It can be solved using substitution.
7. Which of the following functions correctly represent the solution to tower of hanoi puzzle?
a)
void ToH(int n,int a,int b,int c)

{
If(n>0)
{
ToH(n-1,a,c,b);
cout<<”move a disk from” <<a<<” to”<< c;
ToH(n-1,b,a,c);
}
}
b)
void ToH(int n,int a,int b,int c

{
If(n>0)
{
ToH(n-1,a,b,c);
ToH(n-1,b,a,c);
}
}
c)

{
If(n>0)
{
ToH(n-1,a,c,b);
ToH(n-1,a,b,c);
}
}
d)

{
If(n>0)
{
ToH(n-1,b,a,c);
ToH(n-1,a,c,b);
}
}
View Answer
Answer: a
8. Recursive solution of tower of hanoi problem is an example of which of the following algorithm?
a) Dynamic programming
b) Backtracking
c) Greedy algorithm
d) Divide and conquer
View Answer
Answer: d
Explanation: The recursive approach uses divide and conquer algorithm as we break the problem into
smaller parts and then solve the smaller parts and finally combine their results to get the overall solution.
9. Tower of hanoi problem can be solved iteratively.

a) True
b) False
View Answer
Answer: a
Explanation: Iterative solution to tower of hanoi puzzle also exists. Its approach depends on whether the
total numbers of disks are even or odd.
10. Minimum time required to solve tower of hanoi puzzle with 4 disks assuming one move takes 2 seconds,
will be __________
a) 15 seconds
b) 30 seconds
c) 16 seconds
d) 32 seconds
View Answer
Answer: b
Explanation: Number of moves = 24-1=16-1=15
Time for 1 move = 2 seconds
Time for 15 moves = 15×2 = 30 seconds.
Dynamic Programming
1. Which of the following is/are property/properties of a dynamic programming problem?

a) Optimal substructure
b) Overlapping subproblems
c) Greedy approach
d) Both optimal substructure and overlapping subproblems
View Answer
Answer: d
Explanation: A problem that can be solved using dynamic programming possesses overlapping subproblems
as well as optimal substructure properties.
2. If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems,
the problem possesses ____________ property.
a) Overlapping subproblems
b) Optimal substructure
c) Memoization
d) Greedy
View Answer
Answer: b
Explanation: Optimal substructure is the property in which an optimal solution is found for the problem by
constructing optimal solutions for the subproblems.
3. If a problem can be broken into subproblems which are reused several times, the problem possesses
____________ property.
a) Overlapping subproblems
c) Memoization
d) Greedy
View Answer
Answer: a
Explanation: Overlapping subproblems is the property in which value of a subproblem is used several times.
4. If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is
called _____________
b) Greedy
c) Divide and conquer
d) Recursion
View Answer
Answer: c
Explanation: In divide and conquer, the problem is divided into smaller non-overlapping subproblems and
an optimal solution for each of the subproblems is found. The optimal solutions are then combined to get a
global optimal solution. For example, mergesort uses divide and conquer strategy.
5. When dynamic programming is applied to a problem, it takes far less time as compared to other methods
that don’t take advantage of overlapping subproblems.
a) True
b) False
View Answer
Answer: a
Explanation: Dynamic programming calculates the value of a subproblem only once, while other methods
that don’t take advantage of the overlapping subproblems property may calculate the value of the same
subproblem several times. So, dynamic programming saves the time of recalculation and takes far less time
as compared to other methods that don’t take advantage of the overlapping subproblems property.
6. A greedy algorithm can be used to solve all the dynamic programming problems.
a) True
b) False
View Answer
Answer: b
Explanation: A greedy algorithm gives optimal solution for all subproblems, but when these locally optimal
solutions are combined it may NOT result into a globally optimal solution. Hence, a greedy algorithm
CANNOT be used to solve all the dynamic programming problems.
7. In dynamic programming, the technique of storing the previously calculated values is called ___________
a) Saving value property
b) Storing value property
c) Memoization
d) Mapping
View Answer
Answer: c
Explanation: Memoization is the technique in which previously calculated values are stored, so that, these
values can be used to solve other subproblems.
8. When a top-down approach of dynamic programming is applied to a problem, it usually _____________

a) Decreases both, the time complexity and the space complexity
b) Decreases the time complexity and increases the space complexity
c) Increases the time complexity and decreases the space complexity
d) Increases both, the time complexity and the space complexity
View Answer
Answer: b
Explanation: The top-down approach uses the memoization technique which stores the previously calculated
values. Due to this, the time complexity is decreased but the space complexity is increased.
9. Which of the following problems is NOT solved using dynamic programming?

a) 0/1 knapsack problem
b) Matrix chain multiplication problem
c) Edit distance problem
d) Fractional knapsack problem
View Answer
Answer: d
Explanation: The fractional knapsack problem is solved using a greedy algorithm.
10. Which of the following problems should be solved using dynamic programming?
a) Mergesort
b) Binary search
c) Longest common subsequence
d) Quicksort
View Answer
Answer: c
Explanation: The longest common subsequence problem has both, optimal substructure and overlapping
subproblems. Hence, dynamic programming should be used the solve this problem.
1. The following sequence is a fibonacci sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21,…..
Which technique can be used to get the nth fibonacci term?
a) Recursion
c) A single for loop
d) Recursion, Dynamic Programming, For loops
View Answer
Answer: d
Explanation: Each of the above mentioned methods can be used to find the nth fibonacci term.
2. Consider the recursive implementation to find the nth fibonacci number:
int fibo(int n)
if n <= 1
return n
return __________
Which line would make the implementation complete?

a) fibo(n) + fibo(n)
b) fibo(n) + fibo(n – 1)
c) fibo(n – 1) + fibo(n + 1)
d) fibo(n – 1) + fibo(n – 2)
View Answer
Answer: d
Explanation: Consider the first five terms of the fibonacci sequence: 0,1,1,2,3. The 6th term can be found by
adding the two previous terms, i.e. fibo(6) = fibo(5) + fibo(4) = 3 + 2 = 5. Therefore,the nth term of a
fibonacci sequence would be given by:
fibo(n) = fibo(n-1) + fibo(n-2).
3. What is the time complexity of the recursive implementation used to find the nth fibonacci term?
a) O(1)
b) O(n2)
c) O(n!)
d) Exponential
View Answer
Answer: d
Explanation: The recurrence relation is given by fibo(n) = fibo(n – 1) + fibo(n – 2). So, the time complexity
is given by:
T(n) = T(n – 1) + T(n – 2)
Approximately,
T(n) = 2 * T(n – 1)
= 4 * T(n – 2)
= 8 * T(n – 3)
:
:
:
= 2k * T(n – k)
This recurrence will stop when n – k = 0
i.e. n = k
Therefore, T(n) = 2n * O(0) = 2n
Hence, it takes exponential time.
It can also be proved by drawing the recursion tree and counting the number of leaves.
4. Suppose we find the 8th term using the recursive implementation. The arguments passed to the function
calls will be as follows:
fibonacci(8)
fibonacci(7) + fibonacci(6)
fibonacci(6) + fibonacci(5) + fibonacci(5) + fibonacci(4)
fibonacci(5) + fibonacci(4) + fibonacci(4) + fibonacci(3) + fibonacci(4)
+ fibonacci(3) + fibonacci(3) + fibonacci(2)
:
:
:
Which property is shown by the above function calls?

a) Memoization
c) Overlapping subproblems
d) Greedy
View Answer
Answer: c
Explanation: From the function calls, we can see that fibonacci(4) is calculated twice and fibonacci(3) is
calculated thrice. Thus, the same subproblem is solved many times and hence the function calls show the
overlapping subproblems property.
#include<stdio.h>
int fibo(int n)
{
if(n<=1)
return n;
return fibo(n-1) + fibo(n-2);
}
int main()
{
int r = fibo(50000);
printf("%d",r);
return 0;
}
a) 1253556389
b) 5635632456
c) Garbage value
d) Runtime error
Answer: d
6. What is the space complexity of the recursive implementation used to find the nth fibonacci term?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)
View Answer
Answer: a
Explanation: The recursive implementation doesn’t store any values and calculates every value from scratch.
So, the space complexity is O(1).
7. Consider the following code to find the nth fibonacci term:
int fibo(int n)
if n == 0
return 0
else
prevFib = 0
curFib = 1
for i : 1 to n-1
nextFib = prevFib + curFib
__________
__________
return curFib
Complete the above code.

a)
prevFib = curFib
curFib = curFib
b)
prevFib = nextFib
curFib = prevFib
c)
prevFib = curFib
curFib = nextFib
d)
prevFib = nextFib
nextFib = curFib
View Answer
Answer: c
Explanation: The lines, prevFib = curFib and curFib = nextFib, make the code complete.
8. What is the time complexity of the following for loop method used to compute the nth fibonacci term?
int fibo(int n)
if n == 0
return 0
else
prevFib = 0
curFib = 1
for i : 1 to n-1
prevFib = curFib
curFib = nextFib
return curFib
a) O(1)
b) O(n)
c) O(n2)
d) Exponential
View Answer
Answer: b
Explanation: To calculate the nth term, the for loop runs (n – 1) times and each time a for loop is run, it
takes a constant time. Therefore, the time complexity is of the order of n.
9. What is the space complexity of the following for loop method used to compute the nth fibonacci term?
int fibo(int n)
if n == 0
return 0
else
prevFib = 0
curFib = 1
for i : 1 to n-1
prevFib = curFib
curFib = nextFib
return curFib
a) O(1)
b) O(n)
c) O(n2)
d) Exponential
View Answer
Answer: a
Explanation: To calculate the nth term, we just store the previous term and the current term and then
calculate the next term using these two terms. It takes a constant space to store these two terms and hence
O(1) is the answer.
10. What will be the output when the following code is executed?
#include<stdio.h>
int fibo(int n)
{
if(n==0)
return 0;
int i;
int prevFib=0,curFib=1;
for(i=1;i<=n-1;i++)
{
int nextFib = prevFib + curFib;
prevFib = curFib;
curFib = nextFib;
}
return curFib;
}
int main()
{
int r = fibo(10);
printf("%d",r);
return 0;
}
a) 34
b) 55
c) Compile error
d) Runtime error
View Answer
Answer: b
Explanation: The output is the 10th fibonacci number, which is 55.
11. Consider the following code to find the nth fibonacci term using dynamic programming:
1. int fibo(int n)
2. int fibo_terms[100000] //arr to store the fibonacci numbers
3. fibo_terms[0] = 0
5.
6. for i: 2 to n
7. fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
8.
9. return fibo_terms[n]
Which property is shown by line 7 of the above code?

a) Optimal substructure
b) Overlapping subproblems
c) Both overlapping subproblems and optimal substructure
d) Greedy substructure
View Answer
Answer: a
Explanation: We find the nth fibonacci term by finding previous fibonacci terms, i.e. by solving
subproblems. Hence, line 7 shows the optimal substructure property.
12. Consider the following code to find the nth fibonacci term using dynamic programming:
1. int fibo(int n)
5.
6. for i: 2 to n
8.
Which technique is used by line 7 of the above code?

a) Greedy
b) Recursion
c) Memoization
d) Overlapping subproblems
View Answer
Answer: c
Explanation: Line 7 stores the current value that is calculated, so that the value can be used later directly
without calculating it from scratch. This is memoization.
13. What is the time complexity of the following dynamic programming implementation used to compute
the nth fibonacci term?
1. int fibo(int n)
5.
6. for i: 2 to n
8.
a) O(1)
b) O(n)
c) O(n2)
d) Exponential
View Answer
Answer: b
Explanation: To calculate the nth term, the for loop runs (n – 1) times and each time a for loop is run, it
takes a constant time. Therefore, the time complexity is of the order of n.
14. What is the space complexity of the following dynamic programming implementation used to compute
the nth fibonacci term?
int fibo(int n)
int fibo_terms[100000] //arr to store the fibonacci numbers
fibo_terms[0] = 0
fibo_terms[1] = 1
for i: 2 to n
fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
return fibo_terms[n]
a) O(1)
b) O(n)
c) O(n2)
d) Exponential
View Answer
Answer: b
Explanation: To calculate the nth term, we store all the terms from 0 to n – 1. So, it takes O(n) space.
15. What will be the output when the following code is executed?
#include<stdio.
int fibo(int n)
{
int i;
int fibo_terms[100];
fibo_terms[0]=0;
fibo_terms[1]=1;
for(i=2;i<=n;i++)
fibo_terms[i] = fibo_terms[i-2] + fibo_terms[i-1];
return fibo_terms[n];
}
int main()
{
int r = fibo(8);
printf("%d",r);
return 0;
}
a) 34
b) 55
c) Compile error
d) 21
View Answer
Answer: d
Explanation: The program prints the 8th fibonacci term, which is 21.
1. Given a one-dimensional array of integers, you have to find a sub-array with maximum sum. This is the
maximum sub-array sum problem. Which of these methods can be used to solve the problem?
b) Two for loops (naive method)
c) Divide and conquer
d) Dynamic programming, naïve method and Divide and conquer methods
View Answer
Answer: d
Explanation: Dynamic programming, naïve method and Divide and conquer methods can be used to solve
the maximum sub array sum problem.
2. Find the maximum sub-array sum for the given elements.

{2, -1, 3, -4, 1, -2, -1, 5, -4}
a) 3
b) 5
c) 8
d) 6
View Answer
Answer: b
Explanation: The maximum sub-array sum is 5.
3. Find the maximum sub-array sum for the given elements.

{-2, -1, -3, -4, -1, -2, -1, -5, -4}
a) -3
b) 5
c) 3
d) -1
View Answer
Answer: d
Explanation: All the elements are negative. So, the maximum sub-array sum will be equal to the largest
element. The largest element is -1 and therefore, the maximum sub-array sum is -1.
4. Consider the following naive method to find the maximum sub-array sum:
#include<stdio.h>
int main()
{
int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9;
int cur_max, tmp_max, strt_idx, sub_arr_idx;
cur_max = arr[0];
for(strt_idx = 0; strt_idx < len; strt_idx++)
{
tmp_max=0;
for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
{
tmp_max +=arr[sub_arr_idx];
if(tmp_max > cur_max)
_____________;
}
}
printf("%d",cur_max);
return 0;
}
Which line should be inserted to complete the above code?

a) tmp_max = cur_max
b) break
c) continue
d) cur_max = tmp_max
View Answer
Answer: d
Explanation: If the tmp_max element is greater than the cur_max element, we make cur_max equal to
tmp_max, i.e. cur_max = tmp_max.
5. What is the time complexity of the following naive method used to find the maximum sub-array sum in an
array containing n elements?
#include<stdio.h>
int main()
{
int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9;
cur_max = arr[0];
{
tmp_max=0;
{
_____________;
}
}
return 0;
}
a) O(n2)
b) O(n)
c) O(n3)
d) O(1)
View Answer
Answer: a
6. What is the space complexity of the following naive method used to find the maximum sub-array sum in
an array containing n elements?
#include<stdio.h>
int main()
{
int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9;
cur_max = arr[0];
{
tmp_max=0;
{
_____________;
}
}
return 0;
}
a) O(n2)
b) O(1)
c) O(n3)
d) O(n)
View Answer
Answer: b
Explanation: The naive method uses only a constant space. So, the space complexity is O(1).
7. What is the output of the following naive method used to find the maximum sub-array sum?
#include<stdio.h>
int main()
{
int arr[1000] = {-2, -5, 6, -2, 3, -1, 0,-5, 6}, len = 9;
cur_max = arr[0];
{
tmp_max = 0;
{
tmp_max += arr[sub_arr_idx];
cur_max = tmp_max;
}
}
return 0;
}
a) 6
b) 9
c) 7
d) 4
View Answer
Answer: c
Explanation: The naive method prints the maximum sub-array sum, which is 7.
8. What is the time complexity of the divide and conquer algorithm used to find the maximum sub-array
sum?
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(n2)
View Answer
Answer: c
Explanation: The time complexity of the divide and conquer algorithm used to find the maximum sub-array
sum is O(nlogn).
9. What is the space complexity of the divide and conquer algorithm used to find the maximum sub-array
sum?
a) O(n)
b) O(1)
c) O(n!)
d) O(n2)
View Answer
Answer: b
Explanation: The divide and conquer algorithm uses a constant space. So, the space complexity is O(1).
1. The longest increasing subsequence problem is a problem to find the length of a subsequence from a
sequence of array elements such that the subsequence is sorted in increasing order and it’s length is
maximum. This problem can be solved using __________
a) Recursion
c) Brute force
d) Recursion, Dynamic programming, Brute force
View Answer
Answer: d
Explanation: The longest increasing subsequence problem can be solved using all of the mentioned methods.
2. Find the longest increasing subsequence for the given sequence:

{10, -10, 12, 9, 10, 15, 13, 14}
a) {10, 12, 15}
b) {10, 12, 13, 14}
c) {-10, 12, 13, 14}
d) {-10, 9, 10, 13, 14}
View Answer
Answer: d
Explanation: The longest increasing subsequence is {-10, 9, 10, 13, 14}.
3. Find the length of the longest increasing subsequence for the given sequence:
{-10, 24, -9, 35, -21, 55, -41, 76, 84}
a) 5
b) 4
c) 3
d) 6
View Answer
Answer: d
Explanation: The longest increasing subsequence is {-10, 24, 35, 55, 76, 84} and it’s length is 6.
4. For any given sequence, there will ALWAYS be a unique increasing subsequence with the longest length.
a) True
b) False
View Answer
Answer: b
Explanation: For a given sequence, it is possible that there is more than one subsequence with the longest
length.
Consider, the following sequence: {10,11,12,1,2,3}:
There are two longest increasing subsequences: {1,2,3} and {10,11,12}.
5. The number of increasing subsequences with the longest length for the given sequence are:
{10, 9, 8, 7, 6, 5}
a) 3
b) 4
c) 5
d) 6
View Answer
Answer: d
Explanation: Each array element individually forms a longest increasing subsequence and so, the length of
the longest increasing subsequence is 1. So, the number of increasing subsequences with the longest length
is 6.
6. In the brute force implementation to find the longest increasing subsequence, all the subsequences of a
given sequence are found. All the increasing subsequences are then selected and the length of the longest
subsequence is found. What is the time complexity of this brute force implementation?
a) O(n)
b) O(n2)
c) O(n!)
d) O(2n)
View Answer
Answer: d
Explanation: The time required to find all the subsequences of a given sequence is 2n, where ‘n’ is the
number of elements in the sequence. So, the time complexity is O(2n).
7. Complete the following dynamic programming implementation of the longest increasing subsequence
problem:
#include<stdio.h>
int longest_inc_sub(int *arr, int len)
{
int i, j, tmp_max;
int LIS[len]; // array to store the lengths of the longest increasing
subsequence
LIS[0]=1;
for(i = 1; i < len; i++)
{
tmp_max = 0;
for(j = 0; j < i; j++)
{
if(arr[j] < arr[i])
{
if(LIS[j] > tmp_max)
___________;
}
}
LIS[i] = tmp_max + 1;
}
int max = LIS[0];
for(i = 0; i < len; i++)
if(LIS[i] > max)
max = LIS[i];
return max;
}
int main()
{
int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
int ans = longest_inc_sub(arr, len);
printf("%d",ans);
return 0;
}
a) tmp_max = LIS[j]
b) LIS[i] = LIS[j]
c) LIS[j] = tmp_max
d) tmp_max = LIS[i]
View Answer
Answer: a
Explanation: tmp_max is used to store the maximum length of an increasing subsequence for any ‘j’ such
that: arr[j] < arr[i] and 0 < j < i.
So, tmp_max = LIS[j] completes the code.
8. What is the time complexity of the following dynamic programming implementation used to find the
length of the longest increasing subsequence?
#include<stdio.h>
{
int i, j, tmp_max;
subsequence
LIS[0]=1;
for(i = 1; i < len; i++)
{
tmp_max = 0;
for(j = 0; j < i; j++)
{
if(arr[j] < arr[i])
{
tmp_max = LIS[j];
}
}
}
int max = LIS[0];
for(i = 0; i < len; i++)
if(LIS[i] > max)
max = LIS[i];
return max;
}
int main()
{
int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
printf("%d",ans);
return 0;
}
a) O(1)
b) O(n)
c) O(n2)
d) O(nlogn)
View Answer
Answer: c
Explanation: The time complexity of the above dynamic programming implementation used to find the
length of the longest increasing subsequence is O(n2).
9. What is the space complexity of the following dynamic programming implementation used to find the
length of the longest increasing subsequence?
#include<stdio.h>
{
int i, j, tmp_max;
subsequence
LIS[0]=1;
for(i = 1; i < len; i++)
{
tmp_max = 0;
for(j = 0; j < i; j++)
{
if(arr[j] < arr[i])
{
tmp_max = LIS[j];
}
}
}
int max = LIS[0];
for(i = 0; i < len; i++)
if(LIS[i] > max)
max = LIS[i];
return max;
}
int main()
{
int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
printf("%d",ans);
return 0;
}
a) O(1)
b) O(n)
c) O(n2)
d) O(nlogn)
View Answer
Answer: b
Explanation: The above dynamic programming implementation uses space equal to the length of the
sequence. So, the space complexity of the above dynamic programming implementation used to find the
length of the longest increasing subsequence is O(n).
#include<stdio.h>
{
int i, j, tmp_max;
subsequence
LIS[0]=1;
for(i = 1; i < len; i++)
{
tmp_max = 0;
for(j = 0; j < i; j++)
{
if(arr[j] < arr[i])
{
tmp_max = LIS[j];
}
}
}
int max = LIS[0];
for(i = 0; i < len; i++)
if(LIS[i] > max)
max = LIS[i];
return max;
}
int main()
{
int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
printf("%d",ans);
return 0;
}
a) 3
b) 4
c) 5
d) 6
View Answer
Answer: d
Explanation: The program prints the length of the longest increasing subsequence, which is 6.
11. What is the value stored in LIS[5] after the following program is executed?
#include<stdio.h>
{
int i, j, tmp_max;
subsequence
LIS[0]=1;
for(i = 1; i < len; i++)
{
tmp_max = 0;
for(j = 0; j < i; j++)
{
if(arr[j] < arr[i])
{
tmp_max = LIS[j];
}
}
}
int max = LIS[0];
for(i = 0; i < len; i++)
if(LIS[i] > max)
max = LIS[i];
return max;
}
int main()
{
int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
printf("%d",ans);
return 0;
}
a) 2
b) 3
c) 4
d) 5
View Answer
Answer: c
Explanation: The value stored in LIS[5] after the program is executed is 4.
1. The Knapsack problem is an example of ____________

a) Greedy algorithm
b) 2D dynamic programming
c) 1D dynamic programming
View Answer
Answer: b
Explanation: Knapsack problem is an example of 2D dynamic programming.
2. Which of the following methods can be used to solve the Knapsack problem?
a) Brute force algorithm
b) Recursion
c) Dynamic programming
d) Brute force, Recursion and Dynamic Programming
View Answer
Answer: d
Explanation: Brute force, Recursion and Dynamic Programming can be used to solve the knapsack problem.
3. You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20,
30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the
knapsack?
a) 160
b) 200
c) 170
d) 90
View Answer
Answer: a
Explanation: The maximum value you can get is 160. This can be achieved by choosing the items 1 and 3
that have a total weight of 60.
4. Which of the following problems is equivalent to the 0-1 Knapsack problem?

a) You are given a bag that can carry a maximum weight of W. You are given N items which have a weight
of {w1, w2, w3,…., wn} and a value of {v1, v2, v3,…., vn}. You can break the items into smaller pieces.
Choose the items in such a way that you get the maximum value
b) You are studying for an exam and you have to study N questions. The questions take {t1, t2, t3,…., tn}
time(in hours) and carry {m1, m2, m3,…., mn} marks. You can study for a maximum of T hours. You can
either study a question or leave it. Choose the questions in such a way that your score is maximized
c) You are given infinite coins of denominations {v1, v2, v3,….., vn} and a sum S. You have to find the
minimum number of coins required to get the sum S
d) You are given a suitcase that can carry a maximum weight of 15kg. You are given 4 items which have a
weight of {10, 20, 15,40} and a value of {1, 2, 3,4}. You can break the items into smaller pieces. Choose the
items in such a way that you get the maximum value
View Answer
Answer: b
Explanation: In this case, questions are used instead of items. Each question has a score which is same as
each item having a value. Also, each question takes a time t which is same as each item having a weight w.
You have to maximize the score in time T which is same as maximizing the value using a bag of weight W.
5. What is the time complexity of the brute force algorithm used to solve the Knapsack problem?
a) O(n)
b) O(n!)
c) O(2n)
d) O(n3)
View Answer
Answer: c
Explanation: In the brute force algorithm all the subsets of the items are found and the value of each subset
is calculated. The subset of items with the maximum value and a weight less than equal to the maximum
allowed weight gives the answer. The time taken to calculate all the subsets is O(2n).
6. The 0-1 Knapsack problem can be solved using Greedy algorithm.
a) True
b) False
View Answer
Answer: b
Explanation: The Knapsack problem cannot be solved using the greedy algorithm.
7. Consider the following dynamic programming implementation of the Knapsack problem:
#include<stdio.h>
int find_max(int a, int b)
{
if(a > b)
return a;
return b;
}
int knapsack(int W, int *wt, int *val,int n)
{
int ans[n + 1][W + 1];
int itm,w;
for(itm = 0; itm <= n; itm++)
ans[itm][0] = 0;
for(w = 0;w <= W; w++)
ans[0][w] = 0;
{
for(w = 1; w <= W; w++)
{
if(wt[itm - 1] <= w)
ans[itm][w] = ______________;
else
ans[itm][w] = ans[itm - 1][w];
}
}
return ans[n][W];
}
int main()
{
int w[] = {10,20,30}, v[] = {60, 100, 120}, W = 50;
int ans = knapsack(W, w, v, 3);
printf("%d",ans);
return 0;
}
Which of the following lines completes the above code?

a) find_max(ans[itm – 1][w – wt[itm – 1]] + val[itm – 1], ans[itm – 1][w])
b) find_max(ans[itm – 1][w – wt[itm – 1]], ans[itm – 1][w])
c) ans[itm][w] = ans[itm – 1][w];
d) ans[itm+1][w] = ans[itm – 1][w];
View Answer
Answer: a
Explanation: find_max(ans[itm – 1][w – wt[itm – 1]] + val[itm – 1], ans[itm – 1][w]) completes the above
code.
8. What is the time complexity of the following dynamic programming implementation of the Knapsack
problem with n items and a maximum weight of W?
#include<stdio.h>
{
if(a > b)
return a;
return b;
}
{
int ans[n + 1][W + 1];
int itm,w;
ans[itm][0] = 0;
for(w = 0;w <= W; w++)
ans[0][w] = 0;
{
for(w = 1; w <= W; w++)
{
ans[itm][w] = find_max(ans[itm - 1][w-wt[itm - 1]]+val[itm - 1],
ans[itm - 1][w]);
else
}
}
return ans[n][W];
}
int main()
{
int w[] = {10,20,30}, v[] = {60, 100, 120}, W = 50;
printf("%d",ans);
return 0;
}
a) O(n)
b) O(n + w)
c) O(nW)
d) O(n2)
View Answer
Answer: c
Explanation: The time complexity of the above dynamic programming implementation of the Knapsack
problem is O(nW).
9. What is the space complexity of the following dynamic programming implementation of the Knapsack
problem?
#include<stdio.h>
{
if(a > b)
return a;
return b;
}
{
int ans[n + 1][W + 1];
int itm,w;
ans[itm][0] = 0;
for(w = 0;w <= W; w++)
ans[0][w] = 0;
{
for(w = 1; w <= W; w++)
{
ans[itm][w] = find_max(ans[itm - 1][w - wt[itm - 1]]+val[itm - 1],
ans[itm - 1][w]);
else
}
}
return ans[n][W];
}
int main()
{
int w[] = {10,20,30}, v[] = {60, 100, 120}, W = 50;
printf("%d",ans);
return 0;
}
a) O(n)
b) O(n + w)
c) O(nW)
d) O(n2)
View Answer
Answer: c
Explanation: The space complexity of the above dynamic programming implementation of the Knapsack
problem is O(nW).
10. What is the output of the following code?
#include<stdio.h>
{
if(a > b)
return a;
return b;
}
{
int ans[n + 1][W + 1];
int itm,w;
ans[itm][0] = 0;
for(w = 0;w <= W; w++)
ans[0][w] = 0;
{
for(w = 1; w <= W; w++)
{
ans[itm][w] = find_max(ans[itm - 1][w-wt[itm - 1]]+val[itm - 1],
ans[itm - 1][w]);
else
}
}
return ans[n][W];
}
int main()
{
int w[] = {10,20,30}, v[] = {60, 100, 120}, W = 50;
printf("%d",ans);
return 0;
}
a) 120
b) 100
c) 180
d) 220
View Answer
Answer: d
Explanation: The output of the above code is 220
1. Which of the following methods can be used to solve the longest common subsequence problem?
a) Recursion
c) Both recursion and dynamic programming
d) Greedy algorithm
View Answer
Answer: c
Explanation: Both recursion and dynamic programming can be used to solve the longest subsequence
problem.
2. Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common
subsequence?
a) 9
b) 8
c) 7
d) 6
View Answer
Answer: c
Explanation: The longest common subsequence is “PRTPQRS” and its length is 7.
3. Which of the following problems can be solved using the longest subsequence problem?
a) Longest increasing subsequence
b) Longest palindromic subsequence
c) Longest bitonic subsequence
d) Longest decreasing subsequence
View Answer
Answer: b
Explanation: To find the longest palindromic subsequence in a given string, reverse the given string and then
find the longest common subsequence in the given string and the reversed string.
4. Longest common subsequence is an example of ____________

a) Greedy algorithm
b) 2D dynamic programming
c) 1D dynamic programming
View Answer
Answer: b
Explanation: Longest common subsequence is an example of 2D dynamic programming.
5. What is the time complexity of the brute force algorithm used to find the longest common subsequence?
a) O(n)
b) O(n2)
c) O(n3)
d) O(2n)
View Answer
Answer: d
Explanation: The time complexity of the brute force algorithm used to find the longest common
subsequence is O(2n).
6. Consider the following dynamic programming implementation of the longest common subsequence
problem:
#include<stdio.h>
#include<string.h>
int max_num(int a, int b)
{
if(a > b)
return a;
return b;
}
int lcs(char *str1, char *str2)
{
int i,j,len1,len2;
len1 = strlen(str1);
int arr[len1 + 1][len2 + 1];
for(i = 0; i <= len1; i++)
arr[i][0] = 0;
for(i = 0; i <= len2; i++)
arr[0][i] = 0;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
if(str1[i-1] == str2[j - 1])
______________;
else
arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
}
}
return arr[len1][len2];
}
int main()
{
char str1[] = " abcedfg", str2[] = "bcdfh";
int ans = lcs(str1,str2);
printf("%d",ans);
return 0;
}
Which of the following lines completes the above code?

a) arr[i][j] = 1 + arr[i][j].
b) arr[i][j] = 1 + arr[i – 1][j – 1].
c) arr[i][j] = arr[i – 1][j – 1].
d) arr[i][j] = arr[i][j].
View Answer
Answer: b
Explanation: The line, arr[i][j] = 1 + arr[i – 1][j – 1] completes the above code.
7. What is the time complexity of the following dynamic programming implementation of the longest
common subsequence problem where length of one string is “m” and the length of the other string is “n”?
#include<stdio.h>
#include<string.h>
{
if(a > b)
return a;
return b;
}
{
int i,j,len1,len2;
for(i = 0; i <= len1; i++)
arr[i][0] = 0;
for(i = 0; i <= len2; i++)
arr[0][i] = 0;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
if(str1[i-1] == str2[j - 1])
arr[i][j] = 1 + arr[i - 1][j - 1];
else
}
}
}
int main()
{
printf("%d",ans);
return 0;
}
a) O(n)
b) O(m)
c) O(m + n)
d) O(mn)
View Answer
Answer: d
Explanation: The time complexity of the above dynamic programming implementation of the longest
common subsequence is O(mn).
8. What is the space complexity of the following dynamic programming implementation of the longest
common subsequence problem where length of one string is “m” and the length of the other string is “n”?
#include<stdio.h>
#include<string.h>
{
if(a > b)
return a;
return b;
}
{
int i,j,len1,len2;
for(i = 0; i <= len1; i++)
arr[i][0] = 0;
for(i = 0; i <= len2; i++)
arr[0][i] = 0;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
if(str1[i-1] == str2[j - 1])
arr[i][j] = 1 + arr[i - 1][j - 1];
else
}
}
}
int main()
{
printf("%d",ans);
return 0;
}
a) O(n)
b) O(m)
c) O(m + n)
d) O(mn)
View Answer
Answer: d
Explanation: The space complexity of the above dynamic programming implementation of the longest
common subsequence is O(mn).
#include<stdio.h>
#include<string.h>
{
if(a > b)
return a;
return b;
}
{
int i,j,len1,len2;
for(i = 0; i <= len1; i++)
arr[i][0] = 0;
for(i = 0; i <= len2; i++)
arr[0][i] = 0;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
if(str1[i-1] == str2[j - 1])
arr[i][j] = 1 + arr[i - 1][j - 1];
else
}
}
}
int main()
{
char str1[] = "hbcfgmnapq", str2[] = "cbhgrsfnmq";
printf("%d",ans);
return 0;
}
a) 3
b) 4
c) 5
d) 6
View Answer
Answer: b
Explanation: The program prints the length of the longest common subsequence, which is 4.
10. Which of the following is the longest common subsequence between the strings “hbcfgmnapq” and
“cbhgrsfnmq” ?
a) hgmq
b) cfnq
c) bfmq
d) fgmna
View Answer
Answer: d
Explanation: The length of the longest common subsequence is 4. But ‘fgmna’ is not the longest common
subsequence as its length is 5.
11. What is the value stored in arr[2][3] when the following code is executed?
#include<stdio.h>
#include<string.h>
{
if(a > b)
return a;
return b;
}
{
int i,j,len1,len2;
for(i = 0; i <= len1; i++)
arr[i][0] = 0;
for(i = 0; i <= len2; i++)
arr[0][i] = 0;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
if(str1[i-1] == str2[j - 1])
arr[i][j] = 1 + arr[i - 1][j - 1];
else
}
}
}
int main()
{
char str1[] = "hbcfgmnapq", str2[] = "cbhgrsfnmq";
printf("%d",ans);
return 0;
}
a) 1
b) 2
c) 3
d) 4
View Answer
Answer: a
Explanation: The value stored in arr[2][3] is 1.
#include<stdio.h>
#include<string.h>
{
if(a > b)
return a;
return b;
}
{
int i,j,len1,len2;
for(i = 0; i <= len1; i++)
arr[i][0] = 0;
for(i = 0; i <= len2; i++)
arr[0][i] = 0;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
if(str1[i-1] == str2[j - 1])
arr[i][j] = 1 + arr[i - 1][j - 1];
else
}
}
}
int main()
{
char str1[] = "abcd", str2[] = "efgh";
printf("%d",ans);
return 0;
}
a) 3
b) 2
c) 1
d) 0
View Answer
Answer: d
Explanation: The program prints the length of the longest common subsequence, which is 0.
Backtracking
1. Which of the problems cannot be solved by backtracking method?
a) n-queen problem
b) subset sum problem
c) hamiltonian circuit problem
d) travelling salesman problem
View Answer
Answer: d
Explanation: N-queen problem, subset sum problem, Hamiltonian circuit problems can be solved by
backtracking method whereas travelling salesman problem is solved by Branch and bound method.
2. Backtracking algorithm is implemented by constructing a tree of choices called as?

a) State-space tree
b) State-chart tree
c) Node tree
d) Backtracking tree
View Answer
Answer: a
Explanation: Backtracking problem is solved by constructing a tree of choices called as the state-space tree.
Its root represents an initial state before the search for a solution begins.
3. What happens when the backtracking algorithm reaches a complete solution?

a) It backtracks to the root
b) It continues searching for other possible solutions
c) It traverses from a different route
d) Recursively traverses through the same route
View Answer
Answer: b
Explanation: When we reach a final solution using a backtracking algorithm, we either stop or continue
searching for other possible solutions.
4. A node is said to be ____________ if it has a possibility of reaching a complete solution.

a) Non-promising
b) Promising
c) Succeeding
d) Preceding
View Answer
Answer: b
Explanation: If a node has a possibility of reaching the final solution, it is called a promising node.
Otherwise, it is non-promising.
5. In what manner is a state-space tree for a backtracking algorithm constructed?
a) Depth-first search
b) Breadth-first search
c) Twice around the tree
d) Nearest neighbour first
View Answer
Answer: a
Explanation: A state-space tree for a backtracking algorithm is constructed in the manner of depth-first
search so that it is easy to look into.
6. The leaves in a state-space tree represent only complete solutions.

a) true
b) false
View Answer
Answer: b
Explanation: The leaves in a state space tree can either represent non-promising dead ends or complete
solutions found by the algorithm.
7. In general, backtracking can be used to solve?

a) Numerical problems
b) Exhaustive search
c) Combinatorial problems
d) Graph coloring problems
View Answer
Answer: c
Explanation: Backtracking approach is used to solve complex combinatorial problems which cannot be
solved by exhaustive search algorithms.
8. Which one of the following is an application of the backtracking algorithm?

a) Finding the shortest path
b) Finding the efficient quantity to shop
c) Ludo
d) Crossword
View Answer
Answer: d
Explanation: Crossword puzzles are based on backtracking approach whereas the rest are travelling
salesman problem, knapsack problem and dice game.
9. Backtracking algorithm is faster than the brute force technique

a) true
b) false
View Answer
Answer: a
Explanation: Backtracking is faster than brute force approach since it can remove a large set of answers in
one test.
10. Which of the following logical programming languages is not based on backtracking?
a) Icon
b) Prolog
c) Planner
d) Fortran
View Answer
Answer: d
Explanation: Backtracking algorithm form the basis for icon, planner and prolog whereas fortran is an
ancient assembly language used in second generation computers.
11. The problem of finding a list of integers in a given specific range that meets certain conditions is called?
a) Subset sum problem
b) Constraint satisfaction problem
c) Hamiltonian circuit problem
d) Travelling salesman problem
View Answer
Answer: b
Explanation: Constraint satisfaction problem is the problem of finding a list of integers under given
constraints. Constraint satisfaction problem is solved using a backtracking approach.
12. Who coined the term ‘backtracking’?

a) Lehmer
b) Donald
c) Ross
d) Ford
View Answer
Answer: a
Explanation: D.H. Lehmer was the first person to coin the term backtracking. Initially, the backtracking
facility was provided using SNOBOL.
13. ___________ enumerates a list of promising nodes that could be computed to give the possible solutions
of a given problem.
a) Exhaustive search
b) Brute force
c) Backtracking
View Answer
Answer: c
Explanation: Backtracking is a general algorithm that evaluates partially constructed candidates that can be
developed further without violating problem constraints.
14. The problem of finding a subset of positive integers whose sum is equal to a given positive integer is
called as?
a) n- queen problem
b) subset sum problem
c) knapsack problem
d) hamiltonian circuit problem
View Answer
Answer: b
Explanation: Subset sum problem is the problem of finding a subset using the backtracking algorithm when
summed, equals a given integer.
15. The problem of placing n queens in a chessboard such that no two queens attack each other is called as?
a) n-queen problem
b) eight queens puzzle
c) four queens puzzle
d) 1-queen problem
View Answer
Answer: a
Explanation: The problem of placing n-queens in a chessboard such that no two queens are vertical or
horizontal or diagonal to each other is an n-queen problem. The problem only exists for n = 1, 4, 8.
1. Who published the eight queens puzzle?

a) Max Bezzel
b) Carl
c) Gauss
d) Friedrich
View Answer
Answer: a
Explanation: The first Eight Queen Puzzle was published by Max Friedrich William Bezzel, who was a
chess composer by profession in 1848. He was a German chess composer and the first person to publish the
puzzle.
2. When was the Eight Queen Puzzle published?

a) 1846
b) 1847
c) 1848
d) 1849
View Answer
Answer: c
Explanation: The first Eight Queen Puzzle was published by Max Friedrich William Bezzel, who was a
German chess composer by profession. He published the puzzle in 1848.
3. Who published the first solution of the eight queens puzzle?
a) Franz Nauck
b) Max Bezzel
c) Carl
d) Friedrich
View Answer
Answer: a
Explanation: The first solution to the Eight Queen Puzzle was given by Franz Nauck in 1850. While the first
Eight Queen Puzzle was published by Max Friedrich William Bezzel, who was a German chess composer.
4. When was the first solution to Eight Queen Puzzle published?

a) 1850
b) 1847
c) 1848
d) 1849
View Answer
Answer: a
Explanation: The first solution to the Eight Queen Puzzle was given by Franz Nauck in 1850. Max Friedrich
William Bezzel, who was a German chess composer by profession published the puzzle in 1848.
5. Who published the extended version of eight queens puzzle?

a) Franz Nauck
b) Max Bezzel
c) Carl
d) Friedrich
View Answer
Answer: a
Explanation: The first extended version to the Eight Queen Puzzle was given by Franz Nauck in 1850. Max
Friedrich William Bezzel published the puzzle in 1848.
6. For how many queens was the extended version of Eight Queen Puzzle applicable for n*n squares?
a) 5
b) 6
c) 8
d) n
View Answer
Answer: d
Explanation: The extended version given by Franz Nauck of the Eight Queen Puzzle was for n queens on
n*n square chessboard. Earlier the puzzle was proposed with 8 queens on 8*8 board.
7. Who was the first person to find the solution of Eight Queen Puzzle using determinant?
a) Max Bezzel
b) Frank Nauck
c) Gunther
d) Friedrich
View Answer
Answer: c
Explanation: S. Gunther was the first person to propose a solution to the eight queen puzzle using
determinant. Max Friedrich William Bezzel published the puzzle and the first solution to the Eight Queen
Puzzle was given by Franz Nauck.
8. Who proposed the depth first backtracking algorithm?
a) Edsger Dijkshtra
b) Max Bezzel
c) Frank Nauck
d) Carl Friedrich
View Answer
Answer: a
Explanation: In 1972, depth first backtracking algorithm was proposed by Edsger Dijkshtra to illustrate the
Eight Queen Puzzle. Max Friedrich William Bezzel published the puzzle and the first solution to the Eight
Queen Puzzle was given by Franz Nauck.
9. How many solutions are there for 8 queens on 8*8 board?

a) 12
b) 91
c) 92
d) 93
View Answer
Answer: c
Explanation: For 8*8 chess board with 8 queens there are total of 92 solutions for the puzzle. There are total
of 12 fundamental solutions to the eight queen puzzle.
10. Who publish the bitwise operation method to solve the eight queen puzzle?
a) Zongyan Qiu
b) Martin Richard
c) Max Bezzel
d) Frank Nauck
View Answer
Answer: a
Explanation: The first person to publish the bitwise operation method to solve the eight queen puzzle was
Zongyan Qiu. After him, it was published by Martin Richard.
11. How many fundamental solutions are there for the eight queen puzzle?
a) 92
b) 10
c) 11
d) 12
View Answer
Answer: d
Explanation: There are total of 12 fundamental solutions to the eight queen puzzle after removing the
symmetrical solutions due to rotation. For 8*8 chess board with 8 queens there are total of 92 solutions for
the puzzle.
12. Is it possible to have no four queens in a straight line as the part of one of the solution to the eight queen
puzzle.
a) True
b) False
View Answer
Answer: b
Explanation: No three queens lie in a straight line in one of the fundamental solution of the eight queen
puzzle.
13. How many fundamental solutions are the for 3 queens on a 3*3 board?
a) 1
b) 12
c) 3
d) 0
View Answer
Answer: d
Explanation: There are in total zero solution to the 3 queen puzzle for 3*3 chess board. Hence there are no
fundamental solutions. For 8*8 chess board with 8 queens there are total of 12 fundamental solutions for the
puzzle.
14. The six queen puzzle has a fewer solution than the five queen puzzle.
a) True
b) False
View Answer
Answer: a
Explanation: There are total 4 solutions for the six queen puzzle and one fundamental solution while there
are total of 10 solutions for 5 queen puzzle and 2 fundamental solutions.
15. Which ordered board is the highest enumerated board till now?
a) 25*25
b) 26*26
c) 27*27
d) 28*28
View Answer
Answer: c
Explanation: The 27*27 board has the highest order board with total 234,907,967,154,122,528 solutions. It
also has total of 29,363,495,934,315,694 fundamental solution
1. In how many directions do queens attack each other?

a) 1
b) 2
c) 3
d) 4
View Answer
Answer: c
Explanation: Queens attack each other in three directions- vertical, horizontal and diagonal.
2. Placing n-queens so that no two queens attack each other is called?

a) n-queen’s problem
b) 8-queen’s problem
c) Hamiltonian circuit problem
d) subset sum problem
View Answer
Answer: a
Explanation: Placing n queens so that no two queens attack each other is n-queens problem. If n=8, it is
called as 8-queens problem.
3. Where is the n-queens problem implemented?
a) carom
b) chess
c) ludo
d) cards
View Answer
Answer: b
Explanation: N-queens problem occurs in chess. It is the problem of placing n- queens in a n*n chess board.
4. Not more than 2 queens can occur in an n-queens problem.

a) true
b) false
View Answer
Answer: b
Explanation: Unlike a real chess game, n-queens occur in a n-queen problem since it is the problem of
dealing with n-queens.
5. In n-queen problem, how many values of n does not provide an optimal solution?
a) 1
b) 2
c) 3
d) 4
View Answer
Answer: b
Explanation: N-queen problem does not provide an optimal solution of only three values of n (i.e.) n=2,3.
6. Which of the following methods can be used to solve n-queen’s problem?

a) greedy algorithm
b) divide and conquer
c) iterative improvement
d) backtracking
View Answer
Answer: d
Explanation: Of the following given approaches, n-queens problem can be solved using backtracking. It can
also be solved using branch and bound.
7. Of the following given options, which one of the following is a correct option that provides an optimal
solution for 4-queens problem?
a) (3,1,4,2)
b) (2,3,1,4)
c) (4,3,2,1)
d) (4,2,3,1)
View Answer
Answer: a
Explanation: Of the following given options for optimal solutions of 4-queens problem, (3, 1, 4, 2) is the
right option.
8. How many possible solutions exist for an 8-queen problem?
a) 100
b) 98
c) 92
d) 88
View Answer
Answer: c
Explanation: For an 8-queen problem, there are 92 possible combinations of optimal solutions.
9. How many possible solutions occur for a 10-queen problem?

a) 850
b) 742
c) 842
d) 724
View Answer
Answer: d
Explanation: For a 10-queen problem, 724 possible combinations of optimal solutions are available.
10. If n=1, an imaginary solution for the problem exists.

a) true
b) false
View Answer
Answer: b
Explanation: For n=1, the n-queen problem has a trivial and real solution and it is represented by
11. What is the domination number for 8-queen’s problem?

a) 8
b) 7
c) 6
d) 5
View Answer
Answer: d
Explanation: The minimum number of queens needed to occupy every square in n-queens problem is called
domination number. While n=8, the domination number is 5.
12. Of the following given options, which one of the following does not provides an optimal solution for 8-
queens problem?
a) (5,3,8,4,7,1,6,2)
b) (1,6,3,8,3,2,4,7)
c) (4,1,5,8,6,3,7,2)
d) (6,2,7,1,4,8,5,3)
View Answer
Answer: b
Explanation: The following given options for optimal solutions of 8-queens problem, (1,6,3,8,3,2,4,7) does
not provide an optimal solution.
1. Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?
a) branch and bound
b) iterative improvement
c) divide and conquer
d) greedy algorithm
View Answer
Answer: a
Explanation: The Hamiltonian path problem can be solved efficiently using branch and bound approach. It
can also be solved using a backtracking approach.
2. The problem of finding a path in a graph that visits every vertex exactly once is called?
a) Hamiltonian path problem
b) Hamiltonian cycle problem
c) Subset sum problem
d) Turnpike reconstruction problem
View Answer
Answer: a
Explanation: Hamiltonian path problem is a problem of finding a path in a graph that visits every node
exactly once whereas Hamiltonian cycle problem is finding a cycle in a graph.
3. Hamiltonian path problem is _________

a) NP problem
b) N class problem
c) P class problem
d) NP complete problem
View Answer
Answer: d
Explanation: Hamiltonian path problem is found to be NP complete. Hamiltonian cycle problem is also an
NP- complete problem.
4. There is no existing relationship between a Hamiltonian path problem and Hamiltonian circuit problem.
a) true
b) false
View Answer
Answer: b
Explanation: There is a relationship between Hamiltonian path problem and Hamiltonian circuit problem.
The Hamiltonian path in graph G is equal to Hamiltonian cycle in graph H under certain conditions.
5. Which of the following problems is similar to that of a Hamiltonian path problem?

a) knapsack problem
b) closest pair problem
c) travelling salesman problem
d) assignment problem
View Answer
Answer: c
Explanation: Hamiltonian path problem is similar to that of a travelling salesman problem since both the
problem traverses all the nodes in a graph exactly once.
6. Who formulated the first ever algorithm for solving the Hamiltonian path problem?
a) Martello
b) Monte Carlo
c) Leonard
d) Bellman
View Answer
Answer: a
Explanation: The first ever problem to solve the Hamiltonian path was the enumerative algorithm
formulated by Martello.
7. In what time can the Hamiltonian path problem can be solved using dynamic programming?
a) O(N)
b) O(N log N)
c) O(N2)
d) O(N2 2N)
View Answer
Answer: d
Explanation: Using dynamic programming, the time taken to solve the Hamiltonian path problem is
mathematically found to be O(N2 2N).
8. In graphs, in which all vertices have an odd degree, the number of Hamiltonian cycles through any fixed
edge is always even.
a) true
b) false
View Answer
Answer: a
Explanation: According to a handshaking lemma, in graphs, in which all vertices have an odd degree, the
number of Hamiltonian cycles through any fixed edge is always even.
9. Who invented the inclusion-exclusion principle to solve the Hamiltonian path problem?
a) Karp
b) Leonard Adleman
c) Andreas Bjorklund
d) Martello
View Answer
Answer: c
Explanation: Andreas Bjorklund came up with the inclusion-exclusion principle to reduce the counting of
number of Hamiltonian cycles.
10. For a graph of degree three, in what time can a Hamiltonian path be found?
a) O(0.251n)
b) O(0.401n)
c) O(0.167n)
d) O(0.151n)
View Answer
Answer: a
Explanation: For a graph of maximum degree three, a Hamiltonian path can be found in time O(0.251n).
11. What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using
permutation)?
a) O(N!)
b) O(N! * N)
c) O(log N)
d) O(N)
View Answer
Answer: b
Explanation: For a graph having N vertices traverse the permutations in N! iterations and it traverses the
permutations to see if adjacent vertices are connected or not takes N iterations (i.e.) O(N! * N).
12. How many Hamiltonian paths does the following graph have?
a) 1
b) 2
c) 3
d) 4
View Answer
Answer: a
Explanation: The above graph has only one Hamiltonian path that is from a-b-c-d-e.
13. How many Hamiltonian paths does the following graph have?
a) 1
b) 2
c) 0
d) 3
View Answer
Answer: c
Explanation: The above graph has no Hamiltonian paths. That is, we cannot traverse the graph with meeting
vertices exactly once.

DS ALL MCQs

Uploaded by

Copyright:

Available Formats

DS ALL MCQs

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DS ALL MCQs

Uploaded by

Copyright:

Available Formats

Linked List

i) Insertion at the front of the linked list

9. Consider the following definition in c programming language.

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

2. Linked lists are not suitable for the implementation of ___________

4. In Linked List implementation, a node carries information regarding ___________

5. Linked list data structure offers considerable saving in _____________

void fun1(struct node* head)

a) Prints all nodes of linked lists

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

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

8. Which of these is not an application of a linked list?

3. What is a memory efficient double linked list?

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

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

6. What does ‘stack overflow’ refer to?

10. Minimum number of queues to implement stack is ___________

2. In linked list implementation of a queue, where does a new element be inserted?

2. Which of the following is not an application of priority queue?

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

7. Which of the following is not an advantage of a priority queue?

4. What are the applications of dequeue?

3. A queue follows __________

4. Circular Queue is also known as ________

8. Queues serve major role in ______________

9. Which of the following is not the type of queue?

2. What is/are the disadvantages of implementing tree using normal arrays?

//e.g:-consider -complete binary tree:-height-3, [1,2,3,4,5,6,7]-answer must be 23

for binary heap

2. Disadvantages of linked list representation of binary trees over arrays?

3. Which of the following traversing algorithm is not used to traverse in a tree?

4. Level order traversal of a tree is formed with the help of

checkSum(struct bin-treenode *root , int sum) :

a) swapping of left and right nodes is missing

10. What is the code below trying to print?

void print(tree *root,tree *node)

a) just printing all nodes

2. The following given tree is an example for?

3. A binary tree is a rooted tree but not an ordered tree.

4. How many common operations are performed in a binary tree?

6. How many types of insertion are performed in a binary tree?

7. What operation does the following diagram depict?

a) inserting a leaf node

8. General ordered tree can be encoded into binary trees.

10. The average depth of a binary tree is given as?

13. Using what formula can a parent node be located in an array?

15. Construct a binary tree using the following data.

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

public void preorder(Tree root)

public void preorder(Tree root)

public void preorder(Tree root)

public void postorder(Tree root)

public void postorder(Tree root)

public void postorder(Tree root)

public void preOrder(Tree root)

public void preOrder(Tree root)

public void postorder(Tree root)

public void postorder(Tree root)

public void postorder(Tree root)

void print(tree root,tree node)