Get Latest Exam Updates, Free Study materials and Tips

[MCQ’s] Data Structure and Analysis [IT]

Module 01

1.Which of the following is/are the levels of implementation of data structure
a.Abstract level
b.Application level
c.Implementation level
d.All of the above             
Answer: (d).All of the above

2.……………….. level is where the model becomes compatible executable code.
a.Abstract level
b.Application level
c.Implementation level
d.All of the above
Answer: (c).Implementation level

3. …………… is not the component of data structure.
 a.Operations
b.Storage Structures
c.Algorithms
d.None of the above      
Answer: (d).None of the above

4.Which of the following is not the part of ADT description?
 a.Data
 b.Operations
 c.Both of the above
d.None of the above         
Answer: (d).None of the above

5.Which of the following is non-linear data structure?
 a.Stacks
 b.List
 c.Strings
 d.Trees             
Answer: (d).Trees

6.Which of the following data structure is non linear type?
a.Strings
 b.Lists
c.Stacks
d.Graph        
Answer: (d).Graph

7.Which of the following data structure is linear type?
a.Graph
b.Trees
c.Binary tree
d.Stack                                
Answer: (d).Stack

8.To represent hierarchical relationship between elements, Which data structure is suitable?
a.Dequeue
b.Priority
c.Tree
d.Graph                       
Answer: (c).Tree

9. Match the following.a) Completeness i) How long does it take to find a solutionb) Time Complexity ii) How much memory need to perform the search.c) Space Complexity iii) Is the strategy guaranteed to find the solution when there in one.
a.a-iii, b-ii, c-i
b.a-i, b-ii, c-iii
c.a-iii, b-i, c-ii
d.a-i, b-iii, c-ii            
Answer: (c).a-iii, b-i, c-ii

10. When new data are to be inserted into a data structure, but there is not available space; this situation is usually called ….
a.Underflow
b.overflow
c.houseful
d.saturated                          
Answer: (b).overflow

11. Which of the following is true about the characteristics of abstract data types?
i) It exports a type.
ii) It exports a set of operations.
a.True, False
b.False.True
c.True,True
d.False, False
Answer : c. True,True

12.Which of the following data structures are indexed structures?
a.Linear arrays
b.Linked lists
c.Queue
d.Stack
Answer : a.Linear arrays

13.Operations on a data structure may be …..
a.creation
b.destruction
c.selection
d.all of the above
  Answer : d.all of the above

14.Which of the following are the operations applicable an primitive data structures?
a.create
b.destroy
c.update
d.all of the above                                                        
Answer: (d).all of the above

15.Which of the following data structure is non-linear type?
a.Strings
b.Lists
c.Stacks 
d.Tree
 Answer: (d).Tree

16.The indirect change of the values of a variable in one module by another module is called
a.internal change
b.inter-module change
c.side effect
d.side-module update
Answer: (c).side effect

17.The operation of processing each element in the list is known as

a.Sorting
b.Merging
c.Inserting
d.Traversal
Answer: (d).Traversal

18.Finding the location of the element with a given value is:
a.Traversal
b.Search
c.Sort
d.None of above
 Answer: (b).Search

19.Which of the following data structure can’t store the non-homogeneous data elements?

a.Arrays
b.Records
c.Pointers
d.None of the above
 Answer: (a).Arrays

20.Which of the following data structures store the homogeneous data elements?
a.Arrays
b.Records
c.Pointers
d.None of the above
 Answer: (b).Records

21.Which of these best describes an array?
a) A data structure that shows a hierarchical behavior
b) Container of objects of similar types
c) Arrays are immutable once initialised
d) Array is not a data structure
 Answer: b
Explanation: Array contains elements only of the same type.

22.How do you initialize an array in C?
a) int arr[3] = (1,2,3);
b) int arr(3) = {1,2,3};
c) int arr[3] = {1,2,3};
d) int arr(3) = (1,2,3);
 Answer: c
Explanation: This is the syntax to initialize an array in C.

23.How do you instantiate an array in Java?
a) int arr[] = new int(3);
b) int arr[];
c) int arr[] = new int[3];
d) int arr() = new int(3);
Answer: c
Explanation: Note that int arr[]; is declaration whereas int arr[] = new int[3]; is to instantiate an array.

24.Which of the following is the correct way to declare a multidimensional array in Java?
a) int[] arr;
b) int arr[[]];
c) int[][]arr;
d) int[[]] arr;
Answer: c
Explanation: The syntax to declare multidimensional array in java is either int[][] arr; or int arr[][];

25.What is the output of the following Java code?
 public class array

{

public static void main(String args[])

{

int []arr = {1,2,3,4,5};

System.out.println(arr[2]);

System.out.println(arr[4]);

}

}

a) 3 and 5
b) 5 and 3
c) 2 and 4
d) 4 and 2
 Answer: a

26. Explanation: Array indexing starts from 0.
What is the output of the following Java code?

public class array
{
public static void main(String args[])
{
int []arr = {1,2,3,4,5};
System.out.println(arr[5]);
}
}
a) 4
b) 5
c) ArrayIndexOutOfBoundsException
d) InavlidInputException
 Answer: c
Explanation: Trying to access an element beyond the limits of an array gives ArrayIndexOutOfBoundsException.

27.When does the ArrayIndexOutOfBoundsException occur?
a) Compile-time
b) Run-time
c) Not an error
d) Not an exception at all
 Answer: b
Explanation: ArrayIndexOutOfBoundsException is a run-time exception and the compilation is error-free.

28.Which of the following concepts make extensive use of arrays?
a) Binary trees
b) Scheduling of processes
c) Caching
d) Spatial locality
Answer: d
Explanation: Whenever a particular memory location is referred to, it is likely that the locations nearby are also referred, arrays are stored as contiguous blocks in memory, so if you want to access array elements, spatial locality makes it to access quickly.

29.What are the disadvantages of arrays?
a) Data structure like queue or stack cannot be implemented
b) There are chances of wastage of memory space if elements inserted in an array are lesser than the allocated size
c) Index value of an array can be negative
d) Elements are sequentially accessed
 Answer: b
Explanation: Arrays are of fixed size. If we insert elements less than the allocated size, unoccupied positions can’t be used again. Wastage will occur in memory.

30.What are the advantages of arrays?
a) Objects of mixed data types can be stored
b) Elements in an array cannot be sorted
c) Index of first element of an array is 1
d) Easier to store elements of same data type
Answer: d
Explanation: Arrays store elements of the same data type and present in continuous memory locations.

31. Process of inserting an element in stack is called ____________
a) Create
b) Push
c) Evaluation
d) Pop
Answer: b
Explanation: Push operation allows users to insert elements in the stack. If the stack is filled completely and trying to perform push operation stack – overflow can happen.

32.Process of removing an element from stack is called __________
a) Create
b) Push
c) Evaluation
d) Pop
Answer: d
Explanation: Elements in the stack are removed using pop operation. Pop operation removes the top most element in the stack i.e. last entered element.

33.In a stack, if a user tries to remove an element from an empty stack it is called _________
a) Underflow
b) Empty collection
c) Overflow
d) Garbage Collection
Answer: a
Explanation: Underflow occurs when the user performs a pop operation on an empty stack. Overflow occurs when the stack is full and the user performs a push operation. Garbage Collection is used to recover the memory occupied by objects that are no longer used.

34.Pushing an element into stack already having five elements and stack size of 5, then stack becomes ___________
a) Overflow
b) Crash
c) Underflow
d) User flow
Answer: a
Explanation: The stack is filled with 5 elements and pushing one more element causes a stack overflow. This results in overwriting memory, code and loss of unsaved work on the computer.

35.Entries in a stack are “ordered”. What is the meaning of this statement?
a) A collection of stacks is sortable
b) Stack entries may be compared with the ‘<‘ operation
c) The entries are stored in a linked list
d) There is a Sequential entry that is one by one
Answer: d
Explanation: In stack data structure, elements are added one by one using push operation. Stack follows LIFO Principle i.e. Last In First Out(LIFO).

36.Which of the following is not the application of stack?
a) A parentheses balancing program
b) Tracking of local variables at run time
c) Compiler Syntax Analyzer
d) Data Transfer between two asynchronous process
Answer: d
Explanation: Data transfer between the two asynchronous process uses the queue data structure for synchronisation. The rest are all stack applications.

37.Consider the usual algorithm for determining whether a sequence of parentheses is balanced. The maximum number of parentheses that appear on the stack AT ANY ONE TIME when the algorithm analyzes: (()(())(()))?
a) 1
b) 2
c) 3
d) 4 or more
Answer: c
Explanation: In the entire parenthesis balancing method when the incoming token is a left parenthesis it is pushed into stack. A right parenthesis makes pop operation to delete the elements in stack till we get left parenthesis as top most element. 3 elements are there in stack before right parentheses comes. Therefore, maximum number of elements in stack at run time is 3.

38.Consider the usual algorithm for determining whether a sequence of parentheses is balanced. Suppose that you run the algorithm on a sequence that contains 2 left parentheses and 3 right parentheses (in some order). The maximum number of parentheses that appear on the stack AT ANY ONE TIME during the computation?
a) 1
b) 2
c) 3
d) 4 or more
Answer: b
Explanation: In the entire parenthesis balancing method when the incoming token is a left parenthesis it is pushed into stack. A right parenthesis makes pop operation to delete the elements in stack till we get left parenthesis as top most element. 2 left parenthesis are pushed whereas one right parenthesis removes one of left parenthesis. 2 elements are there before right parenthesis which is the maximum number of elements in stack at run time.

39.What is the value of the postfix expression 6 3 2 4 + – *?
a) 1
b) 40
c) 74
d) -18
Answer: d
Explanation: Postfix Expression is (6*(3-(2+4))) which results -18 as output.

40.Here is an infix expression: 4 + 3*(6*3-12). Suppose that we are using the usual stack algorithm to convert the expression from infix to postfix notation. The maximum number of symbols that will appear on the stack AT ONE TIME during the conversion of this expression?
a) 1
b) 2
c) 3
d) 4
Answer: d
Explanation: When we perform the conversion from infix to postfix expression +, *, (, * symbols are placed inside the stack. A maximum of 4 symbols are identified during the entire conversion.

41.The postfix form of the expression (A+ B)*(C*D- E)*F / G is?
a) AB+ CD*E – FG /**
b) AB + CD* E – F **G /
c) AB + CD* E – *F *G /
d) AB + CDE * – * F *G /
Answer: c
Explanation: (((A+ B)*(C*D- E)*F) / G) is converted to postfix expression as
(AB+(*(C*D- E)*F )/ G)
(AB+CD*E-*F) / G
(AB+CD*E-*F * G/). Thus Postfix expression is AB+CD*E-*F*G/

42.The data structure required to check whether an expression contains a balanced parenthesis is?
a) Stack
b) Queue
c) Array
d) Tree
Answer: a
Explanation: The stack is a simple data structure in which elements are added and removed based on the LIFO principle. Open parenthesis is pushed into the stack and a closed parenthesis pops out elements till the top element of the stack is its corresponding open parenthesis. If the stack is empty, parenthesis is balanced otherwise it is unbalanced.

43.What data structure would you mostly likely see in non recursive implementation of a recursive algorithm?
a) Linked List
b) Stack
c) Queue
d) Tree
Answer: b
Explanation: In recursive algorithms, the order in which the recursive process comes back is the reverse of the order in which it goes forward during execution. The compiler uses the stack data structure to implement recursion. In the forwarding phase, the values of local variables, parameters and the return address are pushed into the stack at each recursion level. In the backing-out phase, the stacked address is popped and used to execute the rest of the code.

44.The process of accessing data stored in a serial access memory is similar to manipulating data on a ________
a) Heap
b) Binary Tree
c) Array
d) Stack
Answer: d
Explanation: In serial access memory data records are stored one after the other in which they are created and are accessed sequentially. In stack data structure, elements are accessed sequentially. Stack data structure resembles the serial access memory.

45.The postfix form of A*B+C/D is?
a) *AB/CD+
b) AB*CD/+
c) A*BC+/D
d) ABCD+/*
Answer: b
Explanation: Infix expression is (A*B)+(C/D)
AB*+(C/D)
AB*CD/+. Thus postfix expression is AB*CD/+.

46.Which data structure is needed to convert infix notation to postfix notation?
a) Branch
b) Tree
c) Queue
d) Stack
Answer: d
Explanation: The Stack data structure is used to convert infix expression to postfix expression. The purpose of stack is to reverse the order of the operators in the expression. It also serves as a storage structure, as no operator can be printed until both of its operands have appeared.

47.The prefix form of A-B/ (C * D ^ E) is?
a) -/*^ACBDE
b) -ABCD*^DE
c) -A/B*C^DE
d) -A/BC*^DE
Answer: c
Explanation: Infix Expression is (A-B)/(C*D^E)
(-A/B)(C*D^E)

-A/B*C^DE. Thus prefix expression is -A/B*C^DE.

48.What is the result of the following operation?
Top (Push (S, X))
a) X
b) X+S
c) S
d) XS
Answer: a
Explanation: The function Push(S,X) pushes the value X in the stack S. Top() function gives the value which entered last. X entered into stack S at last.

49.The prefix form of an infix expression (p + q) – (r * t) is?
a) + pq – *rt
b) – +pqr * t
c) – +pq * rt
d) – + * pqrt
Answer: c
Explanation: Given Infix Expression is ((p+q)-(r*t))
(+pq)-(r*t)
(-+pq)(r*t)
-+pq*rt. Thus prefix expression is -+pq*rt.

50.Which data structure is used for implementing recursion?
a) Queue
b) Stack
c) Array
d) List
Answer: b
Explanation: Stacks are used for the implementation of Recursion.

51.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
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.

52.The data structure required for Breadth First Traversal on a graph is?
a) Stack
b) Array
c) Queue
d) Tree
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.

53.A queue follows __________
a) FIFO (First In First Out) principle
b) LIFO (Last In First Out) principle
c) Ordered array
d) Linear tree
Answer: a
Explanation: Element first added in queue will be deleted first which is FIFO principle.

54.Circular Queue is also known as ________
a) Ring Buffer
b) Square Buffer
c) Rectangle Buffer
d) Curve Buffer
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.

55.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
Answer: a
Explanation: Queue follows FIFO approach. i.e. First in First Out Approach. So, the order of removal elements are ABCD.

56.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.

57.A normal queue, if implemented using an array of size MAX_SIZE, gets full when?
a) Rear = MAX_SIZE – 1
b) Front = (rear + 1)mod MAX_SIZE
c) Front = rear + 1
d) Rear = front
Answer: a
Explanation: When Rear = MAX_SIZE – 1, there will be no space left for the elements to be added in queue. Thus queue becomes full.

58.Queues serve major role in ______________
a) Simulation of recursion
b) Simulation of arbitrary linked list
c) Simulation of limited resource allocation
d) Simulation of heap sort
Answer: c
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.

59.Which of the following is not the type of queue?
a) Ordinary queue
b) Single ended queue
c) Circular queue
d) Priority queue
Answer: b
Explanation: Queue always has two ends. So, single ended queue is not the type of queue.

60.Which of the following properties is associated with a queue?
a) First In Last Out
b) First In First Out
c) Last In First Out
d) Last In Last Out
Answer: b
Explanation: Queue follows First In First Out structure.

61.In a circular queue, how do you increment the rear end of the queue?
a) rear++
b) (rear+1) % CAPACITY
c) (rear % CAPACITY)+1
d) rear–
Answer: b
Explanation: Ensures rear takes the values from 0 to (CAPACITY-1).

62.What is the term for inserting into a full queue known as?
a) overflow
b) underflow
c) null pointer exception
d) program won’t be compiled
Answer: a
Explanation: Just as stack, inserting into a full queue is termed overflow.

163.What is the time complexity of enqueue operation?
a) O(logn)
b) O(nlogn)
c) O(n)
d) O(1)
Answer: d
Explanation: Enqueue operation is at the rear end, it takes O(1) time to insert a new item into the queue.

64.What does the following Java code do?
public Object function()
{
if(isEmpty())
return 999;
else
{
Object high;
high = q[front];
return high;
}
}
a) Dequeue
b) Enqueue
c) Return the front element
d) Return the last element
Answer: c
Explanation: q[front] gives the element at the front of the queue, since we are not moving the ‘front’ to the next element,
it is not a dequeue operation.

65.What is the need for a circular queue?
a) effective usage of memory
b) easier computations
c) to delete elements based on priority
d) implement LIFO principle in queues
Answer: a
Explanation: In a linear queue, dequeue operation causes the starting elements of the array to be empty, and there is no way you can use that space, while in a circular queue, you can effectively use that space. Priority queue is used to delete the elements based on their priority. Higher priority elements will be deleted first whereas lower priority elements will be deleted next. Queue data structure always follows FIFO principle.

66.Which of the following represents a dequeue operation? (count is the number of elements in the queue)
a)public Object dequeue()
{
if(count == 0)
{
System.out.println(“Queue underflow”);
return 0;
}
else
{
Object ele = q[front];
q[front] = null;
front = (front+1)%CAPACITY;
count–;
return ele;
}
}

b)
public Object dequeue()
{
if(count == 0)
{
System.out.println(“Queue underflow”);
return 0;
}
else
{
Object ele = q[front];
front = (front+1)%CAPACITY;
q[front] = null;
count–;
return ele;
}
}

c)
public Object dequeue()
{
if(count == 0)
{
System.out.println(“Queue underflow”);
return 0;
}
else
{
front = (front+1)%CAPACITY;
Object ele = q[front];
q[front] = null;
count–;
return ele;
}
}

d)
public Object dequeue()
{
if(count == 0)
{
System.out.println(“Queue underflow”);
return 0;
}
else
{
Object ele = q[front];
q[front] = null;
front = (front+1)%CAPACITY;
return ele;
count–;
}
}
Answer: a
Explanation: Dequeue removes the first element from the queue, ‘front’ points to the front end of the queue and returns the first element.

67.Which of the following best describes the growth of a linear queue at runtime? (Q is the original queue, size() returns the number of elements in the queue)
a)

private void expand()
{
int length = size();
int[] newQ = new int[length<<1];
for(int i=front; i<=rear; i++)
{
newQ[ifront] = Q[i%CAPACITY];
}
Q = newQ;
front = 0;
rear = size()1;
}

b)
private void expand()
{
int length = size();
int[] newQ = new int[length<<1];
for(int i=front; i<=rear; i++)
{
newQ[ifront] = Q[i%CAPACITY];
}
Q = newQ;
}

c)
private void expand()
{
int length = size();
int[] newQ = new int[length<<1];
for(int i=front; i<=rear; i++)
{
newQ[ifront] = Q[i];
}
Q = newQ;
front = 0;
rear = size()1;
}

d)
private void expand()
{
int length = size();
int[] newQ = new int[length*2];
for(int i=front; i<=rear; i++)
{
newQ[ifront] = Q[i%CAPACITY];
}
Q = newQ;
}
Answer: a
Explanation: A common technique to expand the size of array at run time is simply to double the size. Create a new array of double the previous size and copy all the elements, after copying do not forget to assign front = 0 and rear = size()-1, as these are necessary to maintain the decorum of the queue operations.

68.What is the space complexity of a linear queue having n elements?
a) O(n)
b) O(nlogn)
c) O(logn)
d) O(1)
Answer: a
Explanation: Because there are n elements.

69.What is the output of the following Java code?
public class CircularQueue
{
protected static final int CAPACITY = 100;
protected int size,front,rear;
protected Object q[];
int count = 0;
public CircularQueue()
{
this(CAPACITY);
}
public CircularQueue (int n)
{
size = n;
front = 0;
rear = 0;
q = new Object[size];
}
public void enqueue(Object item)
{
if(count == size)
{
System.out.println(“Queue overflow”);
return;
}
else
{
q[rear] = item;
rear = (rear+1)%size;
count++;
}
}
public Object dequeue()
{
if(count == 0)
{
System.out.println(“Queue underflow”);
return 0;
}
else
{
Object ele = q[front];
q[front] = null;
front = (front+1)%size;
count–;
return ele;
}
}
public Object frontElement()
{
if(count == 0)
return 999;
else
{
Object high;
high = q[front];
return high;
}
}
public Object rearElement()
{
if(count == 0)
return 999;
else
{
Object low;
rear = (rear1)%size;
low = q[rear];
rear = (rear+1)%size;
return low;
}
}
}
public class CircularQueueDemo
{
public static void main(String args[])
{
Object var;
CircularQueue myQ = new CircularQueue();
myQ.enqueue(10);
myQ.enqueue(3);
var = myQ.rearElement();
myQ.dequeue();
myQ.enqueue(6);
var = mQ.frontElement();
System.out.println(var+” “+var);
}
}
a) 3 3
b) 3 6
c) 6 6
d) 10 6
Answer: a
Explanation: First enqueue 10 and 3 into the queue, followed by a dequeue(removes 10), followed by an enqueue(6), At this point, 3 is at the front end of the queue and 6 at the rear end, hence a call to frontElement() will return 3 which is displayed twice.

 

70.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
Answer: d
Explanation: Since front pointer is used for deletion, so worst time for the other two cases.

71.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
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.

72.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
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).

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

a) Pointer to character
b) Pointer to integer
c) Pointer to node
d) Node
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.

74.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)
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).

75.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)
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).

76.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)
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.

77.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)
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).

78.The concatenation of two list can performed in O(1) time. Which of the following variation of linked list can be used?
a) Singly linked list
b) Doubly linked list
c) Circular doubly linked list
d) Array implementation of list
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.

79.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));
Answer: a
Explanation: As it represents the right way to create a node.

80.What kind of linked list is best to answer questions like “What is the item at position n?”
a) Singly linked list
b) Doubly linked list
c) Circular linked list
d) Array implementation of linked list
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.

81.Linked lists are not suitable for the implementation of ___________
a) Insertion sort
b) Radix sort
c) Polynomial manipulation
d) Binary search
Answer: d
Explanation: It cannot be implemented using linked lists.

82.Linked list is considered as an example of ___________ type of memory allocation.
a) Dynamic
b) Static
c) Compile time
d) Heap
Answer: a
Explanation: As memory is allocated at the run time.

83.In Linked List implementation, a node carries information regarding ___________
a) Data
b) Link
c) Data and Link
d) Node
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.

84.Linked list data structure offers considerable saving in _____________
a) Computational Time
b) Space Utilization
c) Space Utilization and Computational Time
d) Speed Utilization
Answer: c
Explanation: Linked lists saves both space and time.

85.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
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.

86.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
Answer: b
Explanation: fun1() prints the given Linked List in a reverse manner.
For Linked List 1->2->3->4->5, fun1() prints 5->4->3->2->1. 

87.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
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.

88.Which of the following is not a disadvantage to the usage of array?
a) Fixed size
b) There are chances of wastage of memory space if elements inserted in an array are lesser than the allocated size
c) Insertion based on position
d) Accessing elements at specified positions
Answer: d
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.

89.What is the time complexity of inserting at the end in dynamic arrays?
a) O(1)
b) O(n)
c) O(logn)
d) Either O(1) or O(n)
Answer: d
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.

90.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)
Answer: b
Explanation: To count the number of elements, you have to traverse through the entire list, hence complexity is O(n).

Module 02

1.A Trees are implemented using?
a) Colors
b) Levels
c) Node size
d) Heaps
Answer: b
Explanation: AA Trees are implemented using levels instead of colors to overcome the disadvantages of Red-Black trees.

2.Which of the following is the correct definition for a horizontal link?
a) connection between node and a child of equal levels
b) connection between two nodes
c) connection between two child nodes
d) connection between root node and leaf node
Answer: a
Explanation: A horizontal link is a connection between a node and a child of equal levels.

3.How will you remove a left horizontal link in an AA-tree?
a) by performing right rotation
b) by performing left rotation
c) by deleting both the elements
d) by inserting a new element
Answer: a
Explanation: A left horizontal link is removed by right rotation.  A right horizontal link is removed by left rotation.

4.What are the two different operations done in an AA-Tree?
a) shift and color
b) skew and split
c) zig and zag
d) enqueue and dequeue
Answer: b
Explanation: A skew removes a left horizontal link by right rotation and a split removes a right horizontal link by left rotation.

5.In an AA-tree, we process split first, followed by a skew.

a) True
b) False
Answer: b
Explanation: In an AA-tree, skew is processed first followed by a split.

6.How many different shapes does maintenance of AA-Tree need to consider?
a) 7
b) 5
c) 2
d) 3
Answer: c
Explanation: An AA-Tree needs to consider only two shapes unlike a red-black tree which needs to consider seven shapes of transformation.

7.What is the prime condition of AA-tree which makes it simpler than a red-black tree?
a) Only right children can be red
b) Only left children can be red
c) Right children should strictly be black
d) There should be no left children
Answer: a
Explanation: The prime condition of AA-Tree is that only the right children can be red to eliminate possible restructuring cases.

8.Which of the following trees is similar to that of an AA-Tree?
a) Splay Tree
b) B+ Tree
c) AVL Tree
d) Red-Black Tree
Answer: d
Explanation: AA- Tree is a small variation of Red-Black tree. AA-Trees overcome the complexity faced in performing insertion and deletion in Red-Black Trees.

9.What is the worst case analysis of an AA-Tree?
a) O(N)
b) O(log N)
c) O( N log N)
d) O(N2)
Answer: b
Explanation: The worst case analysis of an AA-Tree is mathematically found to be O(log N).

10.What is the worst case analysis of an AA-Tree?
a) O(N)
b) O(log N)
c) O( N log N)
d) O(N2)
Answer: b
Explanation: The worst case analysis of an AA-Tree is mathematically found to be O(log N).

11.AA-Trees makes more rotations than a red-black tree.
a) True
b) False
Answer: a
Explanation: AA- trees make more rotations than a red-black tree since only two shapes are considered for an AA-Tree whereas seven shapes are considered in Red-Black trees.

12.Who is the inventor of AA-Tree?
a) Arne Anderson
b) Daniel Sleator
c) Rudolf Bayer
d) Jon Louis Bentley
Answer: a
Explanation: AA-tree is invented by Arne Anderson. Daniel Sleator invented Splay Tree. Rudolf Bayer invented a Red-Black tree. Jon Louis Bentley invented K-d tree.

13.What should be the condition for the level of a left node?
a) It should be less than or equal to that of its parent
b) It should be greater than that of its parent
c) It should be strictly less than that of its parent
d) The level should be equal to one
Answer: c
Explanation: The level of a left node should be strictly less than that of its parent. The level of a right node is less than or equal to that of its parent.

14.Of the following rules that are followed by an AA-tree, which of the following is incorrect?
1- Only right children can be red
2- Procedures are coded recursively
3- Instead of storing colors, the level of a node is stored
4- There should not be any left children

a) 1
b) 2
c) 3
d) 4
find and replace in word
Answer: d

Explanation: In an AA-Tree, both left and right children can be present. The only condition is that only right children can be red.

 

 

15.Comparing the speed of execution of Red-Black trees and AA-trees, which one has the faster search time?
a) AA-tree
b) Red-Black tree
c) Both have an equal search time
d) It depends
Answer: a
Explanation: Since an AA-tree tends to be flatter, AA-tree has a faster search time than a Red-Black tree.

16.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
Answer: a
Explanation: It is a self balancing tree with height difference atmost 1.

17.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
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.

18.What is the maximum height of an AVL tree with p nodes?
a) p
b) log(p)
c) log(p)/2
d) p⁄2
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.

19.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
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.

20.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

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.

21.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
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).

22.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
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.

23.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)
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.

24.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
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.

25.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
Answer: c
Explanation: Can have atmost 2 nodes.

26.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
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.

27.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
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.

28.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
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.

30.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
Answer: a
Explanation: Floor of w-1/2 because we can’t miss a node.

31.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
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.

32.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;)
{
for(j=1;j<=pow(2,currentlevel-1);j++) //present level is initialized to 1 and sum is initialized to  0
{
sum=sum+a[i];
i=i+1;
}
//missing logic
}
a)   i=i+pow(2,currentlevel);
currentlevel=currentlevel+2;
j=1;
b)advertisement
var adpushup = adpushup || {};
que = adpushup.que || [];
adpushup.que.push(function() {
adpushup.triggerAd(“21eae76a-c83f-42b0-aec5-01d590a53f37”);
});
i=i+pow(2,currentlevel);
currentlevel=currentlevel+2;
j=0;

c)   i=i-pow(2,currentlevel);
currentlevel=currentlevel+2;
j=1;

d)   i=i+pow(2,currentlevel);
currentlevel=currentlevel+1;
j=1;
Answer: a
Explanation: The i value must skip through all nodes in the next level and current level must be one+next level.

33.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
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.

34.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
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.

35.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
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.

36.What is the maximum number of children that a binary tree node can have?
a) 0
b) 1
c) 2
d) 3
Answer: c
Explanation: In a binary tree, a node can have atmost 2 nodes (i.e.) 0,1 or 2 left and right child.

37.A binary tree is a rooted tree but not an ordered tree.
a) true
b) false
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.

38.How many common operations are performed in a binary tree?
a) 1
b) 2
c) 3
d) 4
Answer: c
Explanation: Three common operations are performed in a binary tree- they are insertion, deletion and traversal.

39.What is the traversal strategy used in the binary tree?
a) depth-first traversal
b) breadth-first traversal
c) random traversal
d) Priority traversal
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.

40.How many types of insertion are performed in a binary tree?
a) 1
b) 2
c) 3
d) 4
Answer: b
Explanation: Two kinds of insertion operation is performed in a binary tree- inserting a leaf node and inserting an internal node.

41.General ordered tree can be encoded into binary trees.
a) true
b) false
Answer: a
Explanation: General ordered tree can be mapped into binary tree by representing them in a left-child-right-sibling way.

42.How many bits would a succinct binary tree occupy?
a) n+O(n)
b) 2n+O(n)
c) n/2
d) n
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.

43.The average depth of a binary tree is given as?
a) O(N)
b) O(√N)
c) O(N2)
d) O(log N)
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).

44.How many orders of traversal are applicable to a binary tree (In General)?
a) 1
b) 4
c) 2
d) 3
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.

45.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
Answer: a
Explanation: If binary trees are represented in arrays, left children are located at indices 2i+1 and right children at 2i+2.

46.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
Answer: b
Explanation: If a binary tree is represented in an array, parent nodes are found at indices (i-1)/2.

47.Which of the following properties are obeyed by all three tree – traversals?
a) Left subtrees are visited before right subtrees
b) Right subtrees are visited before left subtrees
c) Root node is visited before left subtree
d) Root node is visited before right subtree
Answer: a
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.

48.Which of the following is the most widely used external memory data structure?
a) AVL tree
b) B-tree
c) Red-black tree
d) Both AVL tree and Red-black tree
Answer: b
Explanation: In external memory, the data is transferred in form of blocks. These blocks have data valued and pointers. And B-tree can hold both the data values and pointers. So B-tree is used as an external memory data structure.

49.B-tree of order n is a order-n multiway tree in which each non-root node contains __________
a) at most (n – 1)/2 keys
b) exact (n – 1)/2 keys
c) at least 2n keys
d) at least (n – 1)/2 keys
Answer: d
Explanation: A non-root node in a B-tree of order n contains at least (n – 1)/2 keys. And contains a maximum of (n – 1) keys and n sons.

50.A B-tree of order 4 and of height 3 will have a maximum of _______ keys.
a) 255
b) 63
c) 127
d) 188
Answer: a
Explanation:  A B-tree of order m of height h will have the maximum number of keys when all nodes are completely filled. So, the B-tree will have n = (mh+1 – 1) keys in this situation. So, required number of maximum keys = 43+1 – 1 = 256 – 1 = 255.

51.Five node splitting operations occurred when an entry is inserted into a B-tree. Then how many nodes are written?
a) 14
b) 7
c) 11
d) 5
Answer: c
Explanation: If s splits occur in a B-tree, 2s + 1 nodes are written (2 halves of each split and the parent of the last node split). So, if 5 splits occurred, then 2 * 5 + 1 , i.e. 11 nodes are written.

52.B-tree and AVL tree have the same worst case time complexity for insertion and deletion.
a) True
b) False
Answer: a
Explanation: Both the B-tree and the AVL tree have O(log n) as worst case time complexity for insertion and deletion.

53.2-3-4 trees are B-trees of order 4. They are an isometric of _____ trees.
a) AVL
b) AA
c) 2-3
d) Red-Black
Answer: d
Explanation: 2-3-4 trees are isometric of Red-Black trees. It means that, for every 2-3-4 tree, there exists a Red-Black tree with data elements in the same order.

54.What is the best case height of a B-tree of order n and which has k keys?
a) logn (k+1) – 1
b) nk
c) logk (n+1) – 1
d) klogn
Answer: a
Explanation: B-tree of order n and with height k has best case height h, where h = logn (k+1) – 1. The best case occurs when all the nodes are completely filled with keys.

55.Compression techniques can be used on the keys to reduce both space and time requirements in a B-tree.
a) True
b) False
Answer: a
Explanation: The front compression and the rear compression are techniques used to reduce space and time requirements in B-tree. The compression enables to retain more keys in a node so that the number of nodes needed can be reduced.

56.Which of the following is true?
a) larger the order of B-tree, less frequently the split occurs
b) larger the order of B-tree, more frequently the split occurs
c) smaller the order of B-tree, more frequently the split occurs
d) smaller the order of B-tree, less frequently the split occurs
Answer: a
Explanation: The average probability of the split is 1/(⌈m / 2⌉ – 1), where m is the order of B-tree. So, if m larger, the probability of split will be less.

57.In a B+ tree, both the internal nodes and the leaves have keys.
a) True
b) False
Answer: b
Explanation: In a B+ -tree, only the leaves have keys, and these keys are replicated in non-leaf nodes for defining the path for locating individual records.

58.Which of the following is true?
a) B + tree allows only the rapid random access
b) B + tree allows only the rapid sequential access
c) B + tree allows rapid random access as well as rapid sequential access
d) B + tree allows rapid random access and slower sequential access
Answer: c
Explanation: The B+ -tree being a variation of B-tree allows rapid random access. In a B+ -tree the leaves are linked together, so it also provides rapid sequential access.

59.A B+ tree can contain a maximum of 7 pointers in a node. What is the minimum number of keys in leaves?
a) 6
b) 3
c) 4
d) 7
Answer: b
Explanation: Maximum number of pointers in a node is 7, i.e. the order of the B+ -tree is 7. In a  B+ tree of order n each leaf node contains at most n – 1 key and at least ⌈(n − 1)/2⌉ Therefore, a minimum number of keys each leaf can have = ⌈(7 – 1)/2⌉ = 3.

60.Which of the following is false?
a) A B+ -tree grows downwards
b) A B+ -tree is balanced
c) In a B+ -tree, the sibling pointers allow sequential searching
d) B+ -tree is shallower than B-tree
Answer: a
Explanation: A B+ -tree always grows upwards. And In a B+tree –  i)The path from the root to every leaf node is of the same length, so the tree is balanced. ii) Leaves are linked, so allow sequential searching. iii) An index is built with a single key per block of data rather than with one key per data record, so it is shallower than B-tree.

61.Statement 1: When a node is split during insertion, the middle key is promoted to the parent as well as retained in right half-node.

Statement 2: When a key is deleted from the leaf, it is also deleted from the non-leaf nodes of the tree.

a) Statement 1 is true but statement 2 is false
b) Statement 2 is true but statement 1 is false
c) Both the statements are true
d) Both the statements are false
Answer: a
Explanation: During the split, the middle key is retained in the right half node and also promoted to parent node. When a key is deleted from the leaf, it is retained in non-leaves, because it can be still a valid separator between keys in nodes below.

62.Efficiency of finding the next record in B+ tree is ____
a) O(n)
b) O(log n)
c) O(nlog n)
d) O(1)
Answer: d
Explanation: In a B+ -tree finding the next recored (successor) involves accessing an additional leaf at most. So, the efficiency of finding the next record is O(1).

63.What is the maximum number of keys that a B+ -tree of order 3 and of height 3 have?
a) 3
b) 80
c) 27
d) 26
Answer: d
Explanation: A B+ tree of order n and height h can have at most nh – 1 keys. Therefore maximum number of keys = 33 -1 = 27 -1 = 26.

64.Which of the following is false?
a) Compared to B-tree, B+ -tree has larger fanout
b) Deletion in B-tree is more complicated than in B+ -tree
c) B+ -tree has greater depth than corresponding B-tree
d) Both B-tree and B+ -tree have same search and insertion efficiencies
Answer: c
Explanation: A B+ -tree has larger fanout and therefore have a depth smaller than that of corresponding B-tree.

65.Which one of the following data structures are preferred in database-system implementation?
a) AVL tree
b) B-tree
c) B+ -tree
d) Splay tree
Answer: c
Explanation: The database-system implementations use B+ -tree data structure because they can be used for multilevel indexing.

Module 03

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.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. 

3.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.

4.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

5.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).

6.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.

7.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. 

7.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. 

8.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. 

9.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. 

10.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. 

11.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.  

12.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.

13.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).

14.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.

15.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.

17.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?
a) Depth First Search
b) Breadth First Search
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.

18.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.

19.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.

20.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.

21.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.

22.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.

23.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).

24.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.

25.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.

26.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?
a) Depth First Search
b) Breadth First Search
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.

27.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.

28.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.

29.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.

30.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.

Module 04

1. Recursion is a method in which the solution of a problem depends on ____________
a) Larger instances of different problems
b) Larger instances of the same problem
c) Smaller instances of the same problem
d) Smaller instances of different problems
Answer: c
Explanation: In recursion, the solution of a problem depends on the solution of smaller instances of the same problem.

2. Which of the following problems can’t be solved using recursion?
a) Factorial of a number
b) Nth fibonacci number
c) Length of a string
d) Problems without base case
Answer: d
Explanation: Problems without base case leads to infinite recursion call. In general, we will assume a base case to avoid infinite recursion call. Problems like finding Factorial of a number, Nth Fibonacci number and Length of a string can be solved using recursion.

3. Recursion is similar to which of the following?
a) Switch Case
b) Loop
c) If-else
d) if elif else
Answer: b
Explanation: Recursion is similar to a loop.

4. In recursion, the condition for which the function will stop calling itself is ____________
a) Best case
b) Worst case
c) Base case
d) There is no such condition
Answer: c
Explanation: For recursion to end at some point, there always has to be a condition for which the function will not call itself. This condition is known as base case.

5. Consider the following code snippet:

void my_recursive_function()
{
   my_recursive_function();
}
int main()
{
   my_recursive_function();
   return 0;
}

What will happen when the above snippet is executed?
a) The code will be executed successfully and no output will be generated
b) The code will be executed successfully and random output will be generated
c) The code will show a compile time error
d) The code will run for some time and stop when the stack overflows
Answer: d
Explanation: Every function call is stored in the stack memory. In this case, there is no terminating condition(base case). So, my_recursive_function() will be called continuously till the stack overflows and there is no more space to store the function calls. At this point of time, the program will stop abruptly.

6. What is the output of the following code?

void my_recursive_function(int n)
{
    if(n == 0)
    return;
    printf("%d ",n);
    my_recursive_function(n-1);
}
int main()
{
    my_recursive_function(10);
    return 0;
}

a) 10
b) 1
c) 10 9 8 … 1 0
d) 10 9 8 … 1
Answer: d
Explanation: The program prints the numbers from 10 to 1.

7. What is the base case for the following code?

void my_recursive_function(int n)
{
     if(n == 0)
     return;
     printf("%d ",n);
     my_recursive_function(n-1);
}
int main()
{
     my_recursive_function(10);
     return 0;
}

a) return
b) printf(“%d “, n)
c) if(n == 0)
d) my_recursive_function(n-1)
Answer: c
Explanation: For the base case, the recursive function is not called. So, “if(n == 0)” is the base case.

8. How many times is the recursive function called, when the following code is executed?

void my_recursive_function(int n)
{
     if(n == 0)
     return;
     printf("%d ",n);
     my_recursive_function(n-1);
}
int main()
{
     my_recursive_function(10);
     return 0;
}

a) 9
b) 10
c) 11
d) 12
Answer: c
Explanation: The recursive function is called 11 times.

9. What does the following recursive code do?

void my_recursive_function(int n)
{
     if(n == 0)
     return;
     my_recursive_function(n-1);
     printf("%d ",n);
}
int main()
{
     my_recursive_function(10);
     return 0;
}

a) Prints the numbers from 10 to 1
b) Prints the numbers from 10 to 0
c) Prints the numbers from 1 to 10
d) Prints the numbers from 0 to 10
Answer: c
Explanation: The above code prints the numbers from 1 to 10.

10. Which of the following statements is true?
a) Recursion is always better than iteration
b) Recursion uses more memory compared to iteration
c) Recursion uses less memory compared to iteration
d) Iteration is always better and simpler than recursion
Answer: b
Explanation: Recursion uses more memory compared to iteration because every time the recursive function is called, the function call is stored in stack.

11. What will be the output of the following code?

int cnt=0;
void my_recursive_function(int n)
{
     if(n == 0)
     return;
     cnt++;
     my_recursive_function(n/10);
}
int main()
{
     my_recursive_function(123456789);
     printf("%d",cnt);
     return 0;
}

a) 123456789
b) 10
c) 0
d) 9
Answer: d
Explanation: The program prints the number of digits in the number 123456789, which is 9.

12. What will be the output of the following code?

void my_recursive_function(int n)
{
    if(n == 0)
    {
         printf("False");
	   return;
    }
    if(n == 1)
    {
         printf("True");
         return;
    }
    if(n%2==0)
    my_recursive_function(n/2);
    else
    {
         printf("False");
         return;
    }
 
}
int main()
{
     my_recursive_function(100);
     return 0;
}

a) True
b) False
Answer: b
Explanation: The function checks if a number is a power of 2. Since 100 is not a power of 2, it prints false.

13. What is the output of the following code?

int cnt = 0;
void my_recursive_function(char *s, int i)
{
     if(s[i] == '\0')
        return;
     if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')
     cnt++;
     my_recursive_function(s,i+1);
}
int main()
{
     my_recursive_function("thisisrecursion",0);
     printf("%d",cnt);
     return 0;
}

a) 6
b) 9
c) 5
d) 10
Answer: a
Explanation: The function counts the number of vowels in a string. In this case the number is vowels is 6.

14. What is the output of the following code?

void my_recursive_function(int *arr, int val, int idx, int len)
{
    if(idx == len)
    {
         printf("-1");
         return ;
    }
    if(arr[idx] == val)
    {
         printf("%d",idx);
         return;
    }
    my_recursive_function(arr,val,idx+1,len);
}
int main()
{
     int array[10] = {7, 6, 4, 3, 2, 1, 9, 5, 0, 8};
     int value = 2;
     int len = 10;
     my_recursive_function(array, value, 0, len);
     return 0;
}

a) 3
b) 4
c) 5
d) 6
Answer: b
Explanation: The program searches for a value in the given array and prints the index at which the value is found. In this case, the program searches for value = 2. Since, the index of 2 is 4(0 based indexing), the program prints 4.

Module 05

1. Where is linear searching used?
a) When the list has only a few elements
b) When performing a single search in an unordered list
c) Used all the time
d) When the list has only a few elements and When performing a single search in an unordered list
Answer: d
Explanation: It is practical to implement linear search in the situations mentioned in When the list has only a few elements and When performing a single search in an unordered list, but for larger elements the complexity becomes larger and it makes sense to sort the list and employ binary search or hashing.

2. Select the code snippet which performs unordered linear search iteratively?
a)
int unorderedLinearSearch(int arr[], int size, int data)

{
    int index;
    for(int i = 0; i < size; i++)
    {
        if(arr[i] == data)
        {
            index = i;
            break;
        }
    }
    return index;
}

b)
int unorderedLinearSearch(int arr[], int size, int data)

{
    int index;
    for(int i = 0; i < size; i++)
    {
        if(arr[i] == data)
        {
            break;
        }
    }
    return index;
}

c)
int unorderedLinearSearch(int arr[], int size, int data)

{
    int index;
    for(int i = 0; i <= size; i++)
    {
        if(arr[i] == data)
        {
            index = i;
            break;
        }
    }
    return index;
}

d)
int unorderedLinearSearch(int arr[], int size, int data)

{
    int index;
    for(int i = 0; i < size-1; i++)
    {
        if(arr[i] == data)
        {
            index = i;
            break;
        }
    }
    return index;
}

Answer: a
Explanation: Unordered term refers to the given array, that is, the elements need not be ordered. To search for an element in such an array, we need to loop through the elements until the desired element is found.

3. What is the best case for linear search?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)
Answer: d
Explanation: The element is at the head of the array, hence O(1).

4. What is the worst case for linear search?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)
Answer: c
Explanation: Worst case is when the desired element is at the tail of the array or not present at all, in this case you have to traverse till the end of the array, hence the complexity is O(n).

5. Select the code snippet which performs ordered linear search iteratively?
a)

public int linearSearch(int arr[],int key,int size) 
{
       int index = -1;
	   int i = 0;
       while(size > 0) 
       {
             if(data[i] == key) 
             {
		  index = i;
             }
             if(data[i] > key)) 
             {
		 index = i;
                 break;
             }
             i++;
       }
       return index;
}
b)

public int linearSearch(int arr[],int key,int size) 

{
       int index = -1;
	   int i = 0;
       while(size > 0) 
       {
             if(data[i] == key) 
             {
		  index = i;
             }
             if(data[i] > key)) 
             {
                  break;
             }
             i++;
       }
       return index;
}

c)
public int linearSearch(int arr[],int key,int size) 

{
       int index = -1;
	   int i = 0;
       while(size > 0) 
       {
             if(data[i] == key) 
             {
		break;
             }
             if(data[i] > key)) 
             {
                 index = i;
             }
             i++;
        }
        return index;
}

d)
public int linearSearch(int arr[],int key,int size) 

{
       int index = -1;
	   int i = 0;
       while(size > 0) 
       {
             if(data[i] == key) 
             {
		break;
             }
             if(data[i] > key)) 
             {
                 break;
                 index=i; 
             }
             i++;
        }
        return index;
}

Answer: b
Explanation: The term ordered refers to the items in the array being sorted(here we assume ascending order). So traverse through the array until the element, if at any time the value at i exceeds key value, it means the element is not present in the array. This provides a slightly better efficiency than unordered linear search.

 6. What is the best case and worst case complexity of ordered linear search?
a) O(nlogn), O(logn)
b) O(logn), O(nlogn)
c) O(n), O(1)
d) O(1), O(n)
Answer: d
Explanation: Although ordered linear search is better than unordered when the element is not present in the array, the best and worst cases still remain the same, with the key element being found at first position or at last position.

7. Choose the code snippet which uses recursion for linear search.
a)
public void linSearch(int[] arr, int first, int last, int key)

{
	if(first == last)
        {
		System.out.print("-1");
	}
	else
        {
		if(arr[first] == key)
                {
			System.out.print(first);
		}
		else
                {
			linSearch(arr, first+1, last, key);
		}
	}
}

b)
public void linSearch(int[] arr, int first, int last, int key)

      {
		if(first == last)
                {
			System.out.print("-1");
		}
		else
                {
			if(arr[first] == key)
                        {
				System.out.print(first);
			}
			else
                        {
				linSearch(arr, first+1, last-1, key);
			}
		}
      }

c)
public void linSearch(int[] arr, int first, int last, int key)

{
	if(first == last)
        {
		System.out.print("-1");
	}
	else
        {
		if(arr[first] == key)
                {
			System.out.print(last);
		}
		else
                {
			linSearch(arr, first+1, last, key);
		}
	}
}

d)
public void linSearch(int[] arr, int first, int last, int key)

{
	if(first == last)
        {
		System.out.print("-1");
	}
	else
        {
		if(arr[first] == key)
                {
			System.out.print(first);
		}
		else
                {
			linSearch(arr, first+1, last+1, key);
		}
	}
}

Answer: a
Explanation: Every time check the key with the array value at first index, if it is not equal then call the function again with an incremented first index.

 8. What does the following piece of code do?
for (int i = 0; i < arr.length1; i++)

{
    for (int j = i+1; j < arr.length; j++)
    {
        if( (arr[i].equals(arr[j])) && (i != j) )
        {
            System.out.println(arr[i]);
        }
    }
}

a) Print the duplicate elements in the array
b) Print the element with maximum frequency
c) Print the unique elements in the array
d) Prints the element with minimum frequnecy
Answer: a
Explanation: The print statement is executed only when the items are equal and their indices are not.

9. Select the code snippet which prints the element with maximum frequency.
a)
public int findPopular(int[] a) 

{
	if (a == null || a.length == 0)
		return 0;
	Arrays.sort(a);
	int previous = a[0];
	int popular = a[0];
	int count = 1;
	int maxCount = 1;
	for (int i = 1; i < a.length; i++)
        {
		if (a[i] == previous)
		count++;
		else 
                {
			if (count > maxCount) 
                        {
				popular = a[i-1];
				maxCount = count;
			}
		previous = a[i];
		count = 1;
		}
	}
	return count > maxCount ? a[a.length-1] : popular;
}

b)
public int findPopular(int[] a) 

{
	if (a == null || a.length == 0)
		return 0;
	Arrays.sort(a);
	int previous = a[0];
	int popular = a[0];
	int count = 1;
	int maxCount = 1;
	for (int i = 1; i < a.length; i++) 
        {
		if (a[i] == previous)
			count++;
		else 
                {
			if (count > maxCount) 
                        {
				popular = a[i];
				maxCount = count;
			}
			previous = a[i];
			count = 1;
		}
	}
	return count > maxCount ? a[a.length-1] : popular;
}

c)
public int findPopular(int[] a) 

{
	if (a == null || a.length == 0)
		return 0;
	Arrays.sort(a);
	int previous = a[0];
	int popular = a[0];
	int count = 1;
	int maxCount = 1;
	for (int i = 1; i < a.length; i++) 
        {
		if (a[i+1] == previous)
			count++;
		else 
                {
			if (count > maxCount) 
                        {
				popular = a[i-1];
				maxCount = count;
			}
			previous = a[i];
			count = 1;
		}
	}
	return count > maxCount ? a[a.length-1] : popular;
}

d)
public int findPopular(int[] a) 

{
	if (a == null || a.length == 0)
		return 0;
	Arrays.sort(a);
	int previous = a[0];
	int popular = a[0];
	int count = 1;
	int maxCount = 1;
	for (int i = 1; i < a.length; i++) 
        {
		if (a[i+2] == previous)
			count++;
		else 
                {
			if (count > maxCount) 
                        {
				popular = a[i-1];
				maxCount = count;
			}
			previous = a[i];
			count = 1;
		}
	}
	return count > maxCount ? a[a.length-1] : popular;
}

Answer: a
Explanation: Traverse through the array and see if it is equal to the previous element, since the array is sorted this method works with a time complexity of O(nlogn), without sorting a Brute force technique must be applied for which the time complexity will be O(n2).

10. Which of the following is a disadvantage of linear search?
a) Requires more space
b) Greater time complexities compared to other searching algorithms
c) Not easy to understand
d) Not easy to implement
Answer: b
Explanation: The complexity of linear search as the name suggests is O(n) which is much greater than other searching techniques like binary search(O(logn)). Linear search is easy to implement and understand than other searching techniques.

11. 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
Answer: b
Explanation: A recursive approach is easier to understand and contains fewer lines of code.

12. 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)
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);
	}
}

c)
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,high,key);
	}
	else
	{
		return recursive(arr,low,mid-1,key);
	}
}

d)
public static int recursive(int arr[], int low, int high, int key)

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

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.

13. 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
Answer: c
Explanation: level 1: mid = 7
level 2: mid = 99
level 3: mid = 899(this is the key).

14. 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
Answer: a
Explanation: At first level key = 90
At second level key= 99
Here 90 and 99 are mid values.

15. What is the worst case complexity of binary search using recursion?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: b
Explanation: Using the divide and conquer master theorem.

16. What is the average case time complexity of binary search using recursion?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: b
Explanation: T(n) = T(n/2) + 1, Using the divide and conquer master theorem.

17. 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
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.

18. 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;
		}
		else if(arr[mid] < key)
		{
			low = mid - 1;
		}
		else
		{
			high = mid + 1;
		}
	}
	return -1;
}

b)
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;
		}
		else if(arr[mid] < key)
		{
			low = mid + 1;
		}
		else
		{
			high = mid - 1;
		}
	}
	return -1;
}

c)

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;
		}
		else if(arr[mid] < key)
		{
			low = mid + 1;
		}
		else
		{
			high = mid - 1;
		}
	}
	return -1;
}

d)

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;
		}
		else if(arr[mid] < key)
		{
			low = mid - 1;
		}
		else
		{
			high = mid + 1;
		}
	}
	return -1;
}

Answer: b
Explanation: Find the ‘mid’, check if it equals the key, if not, continue the iterations until low <= high.

19. Binary Search can be categorized into which of the following?
a) Brute Force technique
b) Divide and conquer
c) Greedy algorithm
d) Dynamic programming
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.

20. 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
Answer: d
Explanation: Iteration1 : mid = 77; Iteration2 : mid = 88;

21. In which of the cases uniform binary search fails compared to binary search?
a) A table lookup is generally faster than an addition and a shift
b) Many searches will be performed on the same array
c) Many searches will be performed on several arrays of the same length
d) Complexity of code
Answer: d
Explanation: Uniform binary search code is more complex to implement than binary search as it involves mid points to be computed in hand before search.

22. Which of the following is a suitable lookup table that can be used in the uniform binary search?(N is the number of elements in the array and the delta array is global)
a)
public static void make_delta(int N) 

{
       int power = 1;
       int i = 0;
       do 
       {
            int half = power;
            power <<= 1;
            delta[i] = (N + half) / power;
       } 
       while (delta[i++] != 0);
}

b)
public static void make_delta(int N) 

{
       int power = 0;
       int i = 0;
       do 
       {
            int half = power;
            power <<= 1;
            delta[i] = (N + half) / power;
       } 
       while (delta[i++] != 0);
}

c)

public static void make_delta(int N) 

{
       int power = 1;
       int i = 0;
       do 
       {
            int half = power;
            power >>= 1;
            delta[i] = (N + half) / power;
       }
       while (delta[i++] != 0);
}

d)

public static void make_delta(int N) 

{
       int power = 1;
       int i = 0;
       do 
       {
            int half = power;
            power <<= 1;
            delta[i] = (N - half) / power;
       } 
       while (delta[i++] != 0);
}

Answer: a
Explanation: This provides a single lookup index and the values are dependent on the the number of elements(N) in the array.

23. Given delta[4] is a global array and number of elements in the sorted array is 10, what are the values in the delta array?
a) 4, 3, 1, 0
b) 5, 3, 1, 0
c) 4, 2, 1, 1
d) 5, 2, 1, 1
Answer: b
Explanation: Trace with respect to the make_delta function, always note that the last element is always 0.

24. Choose the appropriate code snippet that performs uniform binary search.
a)

public static int unisearch(int key) 

{
       int i = delta[0] - 1; 
       int j = 0;
       while (true) 
       {
            if (key == arr[i])
                return i;
            else if (delta[j] == 0)
                return -1;
            else 
            {
                if (key < arr[i])
                    i += delta[++j];
                else
                    i -= delta[++j];
            }
       }
}

b)

public static int unisearch(int key) 

{
       int i = delta[1] - 1; 
       int j = 0;
       while (true) 
       {
            if (key == arr[i])
                return i;
            else if (delta[j] == 0)
                return -1;
            else 
            {
                if (key < arr[i])
                    i -= delta[++j];
                else
                    i += delta[++j];
            }
       }
}

c)
public static int unisearch(int key) 

{
       int i = delta[0] - 1; 
       int j = 0;
       while (true) 
       {
            if (key == arr[i])
                return i;
            else if (delta[j] == 0)
                return -1;
            else 
            {
                if (key < arr[i])
                    i -= delta[++j];
                else
                    i += delta[++j];
            }
       }
}

d)
public static int unisearch(int key) 

{
       int i = delta[0] - 1; 
       int j = 0;
       while (true) 
       {
            if (key == arr[i])
                return i;
            else if (delta[j] == 0)
                return -1;
            else 
            {
                if (key < arr[i])
                    i += delta[++j];
                else
                    i += delta[++j];
            }
       }
}

Answer: c
Explanation: Unlike the usual binary search which a low, high and a mid variable and every time comparing the key with the mid value, the comparing index is obtained from the lookup delta table, choosing the left or right side of the array is same as with the normal binary search.

25. What is the time complexity of uniform binary search?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: b
Explanation: With every iteration we are dividing the array into two parts(though not equal halves), the complexity remains same as the normal binary search.

26. Given, arr = {1,3,5,6,7,9,14,15,17,19} key = 17 and delta = {5,3,1,0}
How many key comparisons are made?(exclude the comparison used to decide the left or right sub array)
a) 4
b) 3
c) 5
d) 6
Answer: b
Explanation: Tracing with the above code, comparison #1: i=4, comparison #2: i=7, comparison #3: i=8

27. How can Jump Search be improved?
a) Start searching from the end
b) Begin from the kth item, where k is the step size
c) Cannot be improved
d) Step size should be other than sqrt(n)
Answer: b
Explanation: This gives a very slight improvement as you are skipping the first k elements.

28. Which of the following false about Jump Search?
a) Jump Search is better than Linear Search
b) Useful when jumping back is more costly than jumping forward
c) Jump Search is worse than Binary Search
d) Jump search starts from the index 0 even though specified index is k
Answer: d
Explanation: Linear search has O(n) complexity and Binary search has O(logn) complexity, in Jump search you have to jump backwards only once, hence it is preferable if jumping backwards is costly. Jump search starts from index k (specified index) and searches for the element. It won’t start searching from index 0.

29. 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
Answer: a
Explanation: Trace the input with the binary search iterative code.

30. What is the time complexity of binary search with iteration?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
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).

31. How many passes does an insertion sort algorithm consist of?
a) N
b) N-1
c) N+1
d) N2
Answer: b
Explanation: An insertion algorithm consists of N-1 passes when an array of N elements is given.

32. Which of the following algorithm implementations is similar to that of an insertion sort?
a) Binary heap
b) Quick sort
c) Merge sort
d) Radix sort
Answer: a
Explanation: Insertion sort is similar to that of a binary heap algorithm because of the use of temporary variable to swap.

33. What is the average case running time of an insertion sort algorithm?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N2)
Answer: d
Explanation: The average case analysis of a tight bound algorithm is mathematically achieved to be O(N2).

34. Any algorithm that sorts by exchanging adjacent elements require O(N2) on average.
a) True
b) False
Answer: a
Explanation: Each swap removes only one inversion, so O(N2) swaps are required.

35. What is the average number of inversions in an array of N distinct numbers?
a) N(N-1)/4
b) N(N+1)/2
c) N(N-1)/2
d) N(N-1)/3
Answer: a
Explanation: The total number of pairs in a list L is N(N-1)/2. Thus, an average list has half this amount, or N(N-1)/4 inversions.

36. What is the running time of an insertion sort algorithm if the input is pre-sorted?
a) O(N2)
b) O(N log N)
c) O(N)
d) O(M log N)
Answer: c
Explanation: If the input is pre-sorted, the running time is O(N), because the test in the inner for loop always fails immediately and the algorithm will run quickly.

37. What will be the number of passes to sort the elements using insertion sort?
14, 12,16, 6, 3, 10
a) 6
b) 5
c) 7
d) 1
Answer: b
Explanation: The number of passes is given by N-1. Here, N=6. Therefore,
6-1=5 passes.

38. For the following question, how will the array elements look like after second pass?
34, 8, 64, 51, 32, 21
a) 8, 21, 32, 34, 51, 64
b) 8, 32, 34, 51, 64, 21
c) 8, 34, 51, 64, 32, 21
d) 8, 34, 64, 51, 32, 21
Answer: d
Explanation: After swapping elements in the second pass, the array will look like, 8, 34, 64, 51, 32, 21.

39. Which of the following real time examples is based on insertion sort?
a) arranging a pack of playing cards
b) database scenarios and distributes scenarios
c) arranging books on a library shelf
d) real-time systems
Answer: a
Explanation: Arranging a pack of cards mimics an insertion sort. Database scenario is an example for merge sort, arranging books is a stack and real-time systems uses quick sort.

30. In C, what are the basic loops required to perform an insertion sort?
a) do- while
b) if else
c) for and while
d) for and if
Answer: c
Explanation: To perform an insertion sort, we use two basic loops- an outer for loop and an inner while loop.

41. What is an in-place sorting algorithm?
a) It needs O(1) or O(logn) memory to create auxiliary locations
b) The input is already sorted and in-place
c) It requires additional storage
d) It requires additional space
Answer: a
Explanation: Auxiliary memory is required for storing the data temporarily.

42. In the following scenarios, when will you use selection sort?
a) The input is already sorted
b) A large file has to be sorted
c) Large values need to be sorted with small keys
d) Small values need to be sorted with large keys
Answer: c
Explanation: Selection is based on keys, hence a file with large values and small keys can be efficiently sorted with selection sort.

43. What is the worst case complexity of selection sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: d
Explanation: Selection sort creates a sub-list, LHS of the ‘min’ element is already sorted and RHS is yet to be sorted. Starting with the first element the ‘min’ element moves towards the final element.

44. Select the appropriate code that performs selection sort.
a)

        int min;

	for(int j=0; j<arr.length-1; j++)
	{
		min = j;
		for(int k=j+1; k<=arr.length-1; k++)
		{
			if(arr[k] < arr[min])
				min = k;
		}
		int temp = arr[min];
		arr[min] = arr[j];
		arr[j] = temp;
       }

b)
       int min;

	for(int j=0; j<arr.length-1; j++)
	{
		min = j;
		for(int k=j+1; k<=arr.length; k++)
		{
			if(arr[k] < arr[min])
				min = k;
		}
		int temp = arr[min];
		arr[min] = arr[j];
		arr[j] = temp;
	}

c)

        int min;
	for(int j=0; j<arr.length-1; j++)
	{
		min = j;
		for(int k=j+1; k<=arr.length-1; k++)
		{
			if(arr[k] > arr[min])
				min = k;
		}
		int temp = arr[min];
		arr[min] = arr[j];
		arr[j] = temp;
	}

d)

        int min;
	for(int j=0; j<arr.length-1; j++)
	{
		min = j;
		for(int k=j+1; k<=arr.length; k++)
		{
			if(arr[k] > arr[min])
				min = k;
		}
		int temp = arr[min];
		arr[min] = arr[j];
		arr[j] = temp;
	}

Answer: a
Explanation: Starting with the first element as ‘min’ element, selection sort loops through the list to select the least element which is then swapped with the ‘min’ element.

45. What is the advantage of selection sort over other sorting techniques?
a) It requires no additional storage space
b) It is scalable
c) It works best for inputs which are already sorted
d) It is faster than any other sorting technique
Answer: a
Explanation: Since selection sort is an in-place sorting algorithm, it does not require additional storage.

46. What is the average case complexity of selection sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: d
Explanation: In the average case, even if the input is partially sorted, selection sort behaves as if the entire array is not sorted. Selection sort is insensitive to input.

47. What is the disadvantage of selection sort?
a) It requires auxiliary memory
b) It is not scalable
c) It can be used for small keys
d) It takes linear time to sort the elements
Answer: b
Explanation: As the input size increases, the performance of selection sort decreases.

48. The given array is arr = {3,4,5,2,1}. The number of iterations in bubble sort and selection sort respectively are,
a) 5 and 4
b) 4 and 5
c) 2 and 4
d) 2 and 5
Answer: a
Explanation: Since the input array is not sorted, bubble sort takes 5 iterations and selection sort takes 4(n-1) iterations.

49. The given array is arr = {1,2,3,4,5}. (bubble sort is implemented with a flag variable)The number of iterations in selection sort and bubble sort respectively are,
a) 5 and 4
b) 1 and 4
c) 0 and 4
d) 4 and 1
Answer: d
Explanation: Selection sort is insensitive to input, hence 4(n-1) iterations. Whereas bubble sort iterates only once to set the flag to 0 as the input is already sorted.

40. What is the best case complexity of selection sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2
Answer: d
Explanation: The best, average and worst case complexities of selection sort is O(n2).
(n-1) + (n-2) + (n-3) + …. + 1 = (n(n-1))/2 ~ (n2)/2.

41. What is an in-place sorting algorithm?
a) It needs O(1) or O(logn) memory to create auxiliary locations
b) The input is already sorted and in-place
c) It requires additional storage
d) It requires additional space
Answer: a
Explanation: Auxiliary memory is required for storing the data temporarily.

42. In the following scenarios, when will you use selection sort?
a) The input is already sorted
b) A large file has to be sorted
c) Large values need to be sorted with small keys
d) Small values need to be sorted with large keys
Answer: c
Explanation: Selection is based on keys, hence a file with large values and small keys can be efficiently sorted with selection sort.

43. What is the worst case complexity of selection sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: d
Explanation: Selection sort creates a sub-list, LHS of the ‘min’ element is already sorted and RHS is yet to be sorted. Starting with the first element the ‘min’ element moves towards the final element.

44. Select the appropriate code that performs selection sort.
a)

        int min;
	for(int j=0; j<arr.length-1; j++)
	{
		min = j;
		for(int k=j+1; k<=arr.length-1; k++)
		{
			if(arr[k] < arr[min])
				min = k;
		}
		int temp = arr[min];
		arr[min] = arr[j];
		arr[j] = temp;
       }

b)

        int min;
	for(int j=0; j<arr.length-1; j++)
	{
		min = j;
		for(int k=j+1; k<=arr.length; k++)
		{
			if(arr[k] < arr[min])
				min = k;
		}
		int temp = arr[min];
		arr[min] = arr[j];
		arr[j] = temp;
	}

c)

        int min;
	for(int j=0; j<arr.length-1; j++)
	{
		min = j;
		for(int k=j+1; k<=arr.length-1; k++)
		{
			if(arr[k] > arr[min])
				min = k;
		}
		int temp = arr[min];
		arr[min] = arr[j];
		arr[j] = temp;
	}

d)

        int min;
	for(int j=0; j<arr.length-1; j++)
	{
		min = j;
		for(int k=j+1; k<=arr.length; k++)
		{
			if(arr[k] > arr[min])
				min = k;
		}
		int temp = arr[min];
		arr[min] = arr[j];
		arr[j] = temp;
	}

Answer: a
Explanation: Starting with the first element as ‘min’ element, selection sort loops through the list to select the least element which is then swapped with the ‘min’ element.

45. What is the advantage of selection sort over other sorting techniques?
a) It requires no additional storage space
b) It is scalable
c) It works best for inputs which are already sorted
d) It is faster than any other sorting technique
Answer: a
Explanation: Since selection sort is an in-place sorting algorithm, it does not require additional storage.

46. What is the average case complexity of selection sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: d
Explanation: In the average case, even if the input is partially sorted, selection sort behaves as if the entire array is not sorted. Selection sort is insensitive to input.

47. What is the disadvantage of selection sort?
a) It requires auxiliary memory
b) It is not scalable
c) It can be used for small keys
d) It takes linear time to sort the elements
Answer: b
Explanation: As the input size increases, the performance of selection sort decreases.

48. The given array is arr = {3,4,5,2,1}. The number of iterations in bubble sort and selection sort respectively are,
a) 5 and 4
b) 4 and 5
c) 2 and 4
d) 2 and 5
Answer: a
Explanation: Since the input array is not sorted, bubble sort takes 5 iterations and selection sort takes 4(n-1) iterations.

49. The given array is arr = {1,2,3,4,5}. (bubble sort is implemented with a flag variable)The number of iterations in selection sort and bubble sort respectively are,
a) 5 and 4
b) 1 and 4
c) 0 and 4
d) 4 and 1
Answer: d
Explanation: Selection sort is insensitive to input, hence 4(n-1) iterations. Whereas bubble sort iterates only once to set the flag to 0 as the input is already sorted.

50. What is the best case complexity of selection sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: d
Explanation: The best, average and worst case complexities of selection sort is O(n2).
(n-1) + (n-2) + (n-3) + …. + 1 = (n(n-1))/2 ~ (n2)/2.

51. Merge sort uses which of the following technique to implement sorting?
a) backtracking
b) greedy algorithm
c) divide and conquer
d) dynamic programming
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.

52. 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)
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.

53. What is the auxiliary space complexity of merge sort?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
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.

54. Merge sort can be implemented using O(1) auxiliary space.
a) true
b) false
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.

55. 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)
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).

56. Which of the following method is used for sorting in merge sort?
a) merging
b) partitioning
c) selection
d) exchanging
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.

57. 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)
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.

58. 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
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).

59. 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
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.

60. Which of the following is not in place sorting algorithm?
a) merge sort
b) quick sort
c) heap sort
d) insertion sort
Answer: a
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.

61. Which of the following sorting algorithms is the fastest?
a) Merge sort
b) Quick sort
c) Insertion sort
d) Shell sort
Answer: b
Explanation: Quick sort is the fastest known sorting algorithm because of its highly optimized inner loop.

62. Quick sort follows Divide-and-Conquer strategy.
a) True
b) False
Answer: a
Explanation: In quick sort, the array is divided into sub-arrays and then it is sorted (divide-and-conquer strategy).

63. 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)
Answer: c
Explanation: The worst case performance of a quick sort algorithm is mathematically found to be O(N2).

64. 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
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.

65. 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
Answer: d
Explanation: Left element=8, right element=0,
Centre=[position(left+right)/2]=6.

66. 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
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.

67. 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)
Answer: c
Explanation: The best case and average case analysis of a quick sort algorithm are mathematically found to be O(N log N).

68. 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
Answer: c
Explanation: Insertion sort is used along with quick sort to sort the sub arrays.
It is used only at the end.

69. Quick sort uses join operation rather than merge operation.
a) true
b) false
Answer: a
Explanation: Quick sort uses join operation since join is a faster operation than merge.

70. How many sub arrays does the quick sort algorithm divide the entire array into?
a) one
b) two
c) three
d) four

71. Which of the following is the distribution sort?
a) Heap sort
b) Smooth sort
c) Quick sort
d) LSD radix sort
Answer: d
Explanation: In Distribution sort the inputted values are distributed to multiple intermediate structures which are then combined and placed on the output. And LSD radix sort distributes values into buckets based on the digits within values, so it is a distribution sort.

72. What is the worst case time complexity of LSD radix sort?
a) O(nlogn)
b) O(wn)
c) O(n)
d) O(n + w)
Answer: b
Explanation: Time complexity of LSD radix sort depends upon the word size and the number on items. It runs in O(wn) time in worst case, where n is the number of inputted elements and w is the number of digits in the largest number.

73. LSD radix sort requires _____ passes to sort N elements.
a) (w/logR)
b) N(w/logR)
c) (w/log(RN))
d) (wN/log(N))
Answer: a
Explanation: LSD radix sort sorts the N elements in (w/logR) passes where w is the number of digits in largest number and R(radix) is extra space required for performing the sorting operation.

74. Which of the following is false?
a) LSD radix sort is an integer sorting algorithm
b) LSD radix sort is a comparison sorting algorithm
c) LSD radix sort is a distribution sort
d) LSD radix sort uses bucket sort
Answer: b
Explanation: LSD radix sort uses bucket sort for grouping the keys based on the digits at that value. And as it grouped the keys based on the digits at that values, it is integer sorting algorithm.

75. Which of the following sorting algorithm is stable?
a) Heap sort
b) Selection sort
c) In-place MSD radix sort
d) LSD radix sort
Answer: d
Explanation: In LSD radix sort after sorting the multiple elements with the same key will be in the same order as they were in the input array. So LSD radix sort is stable sort.

76. LSD radix sort is faster than comparison sorts.
a) True
b) False
Answer: b
Explanation: LSD radix sort is faster than comparison sorts when the word size is less than logn. But LSD radix sort runs slowly for elements with larger word size and smaller radix.

77. Which of the following should be used to sort a huge database on a fixed-length key field?
a) Insertion sort
b) Merge sort
c) LSD radix sort
d) Quick sort
Answer: c
Explanation: LSD radix requires only w passes to sort a fixed-length string, where w is a length of the strings. So, LSD radix sort is best suited to sort a huge database on a fixed-length key field.

78. Which of the following is a combination of LSD and MSD radix sorts?
a) Forward radix sort
b) 3-way radix quick sort
c) Trie base radix sort
d) Flash sort
Answer: a
Explanation: Forward radix sort combines the advantages of LSD and MSD radix sort. Forward radix sort inspects a complete horizontal strip at a time just like LSD radix sort.

79. Which of the following is true for the LSD radix sort?
a) works best for variable length strings
b) accesses memory randomly
c) inner loop has less instructions
d) sorts the keys in left-to-right order
Answer: b
Explanation: LSD radix sort sorts the keys in right-to-left order, working with Least Significant Digit first. The inner loop has a lot of instructions and LSD radix sort is used to sort fixed-length strings.

80. LSD radix sort is in-place sorting algorithm.
a) False
b) True
Answer: a
Explanation: LSD radix is not an in-place sorting algorithm. It needs extra memory to store the elements in bucket and its worst case space complexity is O(w + R).

Module 06

1. Express -15 as a 6-bit signed binary number.
a) 001111
b) 101111
c) 101110
d) 001110
Answer: b
Explanation: The first 4 1s from the right represent the number 15, 2 more bits are padded to make it 6 digits and the leftmost bit is a 1 to represent that it is -15.

2. Which of the following code snippet is used to convert decimal to binary numbers?
a)
public void convertBinary(int num)

{
     int bin[] = new int[50];
     int index = 0;
     while(num > 0)
     {
       bin[index++] = num%2;
       num = num/2;
     }
     for(int i = index-1;i >= 0;i--)
     {
       System.out.print(bin[i]);
     }
}

b)
public void convertBinary(int num)

{
     int bin[] = new int[50];
     int index = 0;
     while(num > 0)
     {
       bin[++index] = num%2;
       num = num/2;
     }
     for(int i = index-1;i >= 0;i--)
     {
       System.out.print(bin[i]);
     }
}

c)
public void convertBinary(int num)

{
     int bin[] = new int[50];
     int index = 0;
     while(num > 0)
     {
         bin[index++] = num/2;
         num = num%2;
     }
     for(int i = index-1;i >= 0;i--)
     {
         System.out.print(bin[i]);
     }
}

d)
public void convertBinary(int num)

 {
     int bin[] = new int[50];
     int index = 0;
     while(num > 0)
     {
         bin[++index] = num/2;
         num = num%2;
     }
     for(int i = index-1;i >= 0;i--)
     {
         System.out.print(bin[i]);
     }
  }

Answer: a
Explanation: Take the modulus by 2 of the number and store in an array while halving the number during each iteration and then display the contents of the array.

3. Which is the predefined method available in Java to convert decimal to binary numbers?
a) toBinaryInteger(int)
b) toBinaryValue(int)
c) toBinaryNumber(int)
d) toBinaryString(int)
Answer: d
Explanation: The method toBinaryString() takes an integer argument and is defined in java.lang package. Usage is java.lang.Integer.toBinaryString(int) this returns the string representation of the unsigned integer value.

4. Using stacks, how to obtain the binary representation of the number?
a)
public void convertBinary(int num)

{
    Stack<Integer> stack = new Stack<Integer>();
    while (num != 0)
    {
        int digit = num / 2;
        stack.push(digit);
        num = num % 2;
    } 
    System.out.print("\nBinary representation is:");
    while (!(stack.isEmpty() ))
    {
        System.out.print(stack.pop());
    }
 }
b)

public void convertBinary(int num)

{
    Stack<Integer> stack = new Stack<Integer>();
    while (num != 0)
    {
        int digit = num % 2;
        stack.push(digit);
    } 
    System.out.print("\nBinary representation is:");
    while (!(stack.isEmpty() ))
    {
        System.out.print(stack.pop());
    }
 }

c)
public void convertBinary(int num)

{
    Stack<Integer> stack = new Stack<Integer>();
    while (num != 0)
    {
        int digit = num % 2;
        stack.push(digit);
        num = num / 2;
    } 
    System.out.print("\nBinary representation is:");
    while (!(stack.isEmpty() ))
    {
        System.out.print(stack.pop());
    }
 }

d)
public void convertBinary(int num)

{
    Stack<Integer> stack = new Stack<Integer>();
    while (num != 0)
    {
        int digit = num % 2;
        stack.push(digit%2);
        num = num / 2;
    } 
    System.out.print("\nBinary representation is:");
    while (!(stack.isEmpty() ))
    {
        System.out.print(stack.pop());
    }
 }

Answer: c
Explanation: Here instead of adding the digits to an array, you push it into a stack and while printing, pop it from the stack.

 5. What is the time complexity for converting decimal to binary numbers?
a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)
Answer: c
Explanation: Since each time you are halving the number, it can be related to that of a binary search algorithm, hence the complexity is O(logn).

6. Write a piece of code which returns true if the string contains balanced parenthesis, false otherwise.
a)
public boolean isBalanced(String exp)

{
	int len = exp.length();
	Stack<Integer> stk = new Stack<Integer>();
	for(int i = 0; i < len; i++)
        {
		char ch = exp.charAt(i);
                if (ch == '(')
                stk.push(i);
                else if (ch == ')')
                {
			if(stk.peek() == null)
                        {
				return false;
			}
			stk.pop();
		}
	}
	return true;
}

b)
public boolean isBalanced(String exp)

{
	int len = exp.length();
	Stack<Integer> stk = new Stack<Integer>();
	for(int i = 0; i < len; i++)
            {
		char ch = exp.charAt(i);
                if (ch == '(')
                stk.push(i);
                else if (ch == ')')
                {
			if(stk.peek() != null)
                        {
				return true;
			}
			stk.pop();
		}
	}
	return false;
  }
c)

public boolean isBalanced(String exp)

{
	int len = exp.length();
	Stack<Integer> stk = new Stack<Integer>();
	for(int i = 0; i < len; i++)
        {
	       char ch = exp.charAt(i);
               if (ch == ')')
               stk.push(i);
               else if (ch == '(')
               {
			if(stk.peek() == null)
                        {
				return false;
			}
			stk.pop();
		}
	}
	return true;
}

d)
public boolean isBalanced(String exp)

{
	int len = exp.length();
	Stack<Integer> stk = new Stack<Integer>();
	for(int i = 0; i < len; i++)
        {
		char ch = exp.charAt(i);
                if (ch == '(')
                stk.push(i);
                else if (ch == ')')
                {
			if(stk.peek() != null)
                        {
				return false;
			}
			stk.pop();
		}
	}
	return true;
  }

Answer: a
Explanation: Whenever a ‘(‘ is encountered, push it into the stack, and when a ‘)’ is encountered check the top of the stack to see if there is a matching ‘(‘, if not return false, continue this till the entire string is processed and then return true.

7. What is the time complexity of the following code?
public boolean isBalanced(String exp)

{
	int len = exp.length();
	Stack<Integer> stk = new Stack<Integer>();
	for(int i = 0; i < len; i++)
        {
		char ch = exp.charAt(i);
                if (ch == '(')
                stk.push(i);
                else if (ch == ')')
                {
			if(stk.peek() == null)
                        {
				return false;
			}
			stk.pop();
		}
	}
	return true;
}

a) O(logn)
b) O(n)
c) O(1)
d) O(nlogn)
Answer: b
Explanation: All the characters in the string have to be processed, hence the complexity is O(n).

8. Which of the following program prints the index of every matching parenthesis?
a)
public void dispIndex(String exp)

{
    Stack<Integer> stk = new Stack<Integer>();
    for (int i = 0; i < len; i++)
    {    
        char ch = exp.charAt(i);
        if (ch == '(')
        stk.push(i);
        else if (ch == ')')
        {
          try
          {
            int p = stk.pop() + 1;
            System.out.println("')' at index "+(i+1)+" matched with ')' at index "+p);
          }
          catch(Exception e)
          {
             System.out.println("')' at index "+(i+1)+" is unmatched");
          }
        }            
    }
    while (!stk.isEmpty() )
    System.out.println("'(' at index "+(stk.pop() +1)+" is unmatched");
}

b)
public void dispIndex(String exp)

{
    Stack<Integer> stk = new Stack<Integer>();
    for (int i = 0; i < len; i++)
    {    
        char ch = exp.charAt(i);
        if (ch == '(')
        stk.push(i);
        else if (ch == ')')
        {
           try
           {
             int p = stk.pop() + 1;
             System.out.println("')' at index "+(i)+" matched with ')' at index "+p);
           }
           catch(Exception e)
           {
              System.out.println("')' at index "+(i)+" is unmatched");
           }
        }            
    }
    while (!stk.isEmpty() )
    System.out.println("'(' at index "+(stk.pop() +1)+" is unmatched");
}

c)
public void dispIndex(String exp)

{
    Stack<Integer> stk = new Stack<Integer>();
    for (int i = 0; i < len; i++)
    {    
        char ch = exp.charAt(i);
        if (ch == ')')
        stk.push(i);
        else if (ch == '(')
        {
          try
          {
            int p = stk.pop() +1;
            System.out.println("')' at index "+(i+1)+" matched with ')' at index "+p);
          }
          catch(Exception e)
          {
             System.out.println("')' at index "+(i+1)+" is unmatched");
          }
        }            
    }
    while (!stk.isEmpty() )
    System.out.println("'(' at index "+(stk.pop() +1)+" is unmatched");
}

d)
public void dispIndex(String exp)

{
    Stack<Integer> stk = new Stack<Integer>();
    for (int i = 0; i < len; i++)
    {    
        char ch = exp.charAt(i);
        if (ch == ')')
        stk.push(i);
        else if (ch == '(')
        {
          try
          {
            int p = stk.pop();
            System.out.println("')' at index "+(i+1)+" matched with ')' at index "+p);
          }
          catch(Exception e)
          {
            System.out.println("')' at index "+(i+1)+" is unmatched");
          }
        }            
    }
    while (!stk.isEmpty() )
    System.out.println("'(' at index "+(stk.pop() +1)+" is unmatched");
}

Answer: a
Explanation: Whenever a ‘(‘ is encountered, push the index of that character into the stack, so that whenever a corresponding ‘)’ is encountered, you can pop and print it.

8. How many stacks are required for applying evaluation of infix expression algorithm?
a) one
b) two
c) three
d) four
Answer: b
Expression: Two stacks are required for evaluation of infix expression – one for operands and one for operators.

9. How many passes does the evaluation of infix expression algorithm makes through the input?
a) One
b) Two
c) Three
d) Four
Answer: a
Explanation: Evaluation of infix expression algorithm is linear and makes only one pass through the input.

10. Identify the infix expression from the list of options given below.
a) a/b+(c-d)
b) abc*+d+ab+cd+*ce-f-
c) ab-c-
d) +ab
Answer: a
Explanation: a/b+(c-d) is an infix expression since the operators are placed in between the operands.

11. Which of the following statement is incorrect with respect to evaluation of infix expression algorithm?
a) Operand is pushed on to the stack
b) If the precedence of operator is higher, pop two operands and evaluate
c) If the precedence of operator is lower, pop two operands and evaluate
d) The result is pushed on to the operand stack
Answer: b
Explanation: If the precedence of the operator is higher than the stack operator, then it is pushed on to the stack operator.

12. Evaluate the following statement using infix evaluation algorithm and choose the correct answer. 1+2*3-2
a) 3
b) 6
c) 5
d) 4
Answer: c
Explanation: According to precedence of operators, * is evaluated first. + and – have equal priorities. Hence, 1+6-2= 5.

13. Evaluation of infix expression is done based on precedence of operators.
a) True
b) False
Answer: a
Explanation: During evaluation of infix expression, the operators with higher precedence are evaluated first, followed by operators with lower precedence.

13. Of the following choices, which operator has the lowest precedence?
a) ^
b) +
c) /
d) #
Answer: d
Explanation: The operator with the lowest precedence is #, preceded by +, / and then ^.

14. The system throws an error if parentheses are encountered in an infix expression evaluation algorithm.
a) True
b) False
Answer: b
Explanation: The algorithm holds good for infix expression with parentheses. The system does not throw error.

15. Evaluate the following and choose the correct answer.
a/b+c*d where a=4, b=2, c=2, d=1.
a) 1
b) 4
c) 5
d) 2
Answer: b
Explanation: * and / have higher priority. Hence, they are evaluated first. Then, + is evaluated. Hence, 2+2=4.

16. Evaluate the following statement using infix evaluation algorithm and choose the correct answer. 4*2+3-5/5
a) 10
b) 11
c) 16
d) 12
Answer: a
Explanation: 4*2 and 5/5 are evaluated first and then, 8+3-1 is evaluated and the result is obtained as 10.

17. Using the evaluation of infix expression, evaluate a^b+c and choose the correct answer. (a=2, b=2, c=2)
a) 12
b) 8
c) 10
d) 6
Answer: d
Explanation: ^ has the highest precedence. Hence, 2^2 is evaluated and then 4+2 gives 6.

18. Evaluate the following infix expression using algorithm and choose the correct answer. a+b*c-d/e^f where a=1, b=2, c=3, d=4, e=2, f=2.
a) 6
b) 8
c) 9
d) 7
View Answer

Answer: a
Explanation: ^ has the highest order of precedence. Hence, 2^2 is evaluated first, and then, 2*3 and 4/4 are evaluated. Therefore, 1+6-1=6.

19. From the given expression tree, identify the infix expression, evaluate it and choose the correct result.

a) 5
b) 10
c) 12
d) 16
Answer: c
Explanation: From the given expression tree, the result of the infix expression is evaluated to be 12.

20. How many stacks are required for evaluation of prefix expression?
a) one
b) two
c) three
d) four
Answer: b
Explanation: 2 stacks are required for evaluation of prefix expression, one for integers and one for characters.

21. While evaluating a prefix expression, the string is read from?
a) left to right
b) right to left
c) center to right
d) center to left to right
Answer: b
Explanation: The string is read from right to left because a prefix string has operands to its right side.

22. The associativity of an exponentiation operator ^ is right side.
a) True
b) False
Answer: a
Explanation: The associativity of ^ is right side while the rest of the operators like +,-,*,/ has its associativity to its left.

23. How many types of input characters are accepted by this algorithm?
a) one
b) two
c) three
d) four
Answer: c
Explanation: Three kinds of input are accepted by this algorithm- numbers, operators and new line characters.

24. What determines the order of evaluation of a prefix expression?
a) precedence and associativity
b) precedence only
c) associativity only
d) depends on the parser
Answer: a
Explanation: Precedence is a very important factor in determining the order of evaluation. If two operators have the same precedence, associativity comes into action.

25. Find the output of the following prefix expression
*+2-2 1/-4 2+-5 3 1
a) 2
b) 12
c) 10
d) 4
Answer: a
Explanation: The given prefix expression is evaluated using two stacks and the value is given by (2+2-1)*(4-2)/(5-3+1)= 2.

26. An error is thrown if the character ‘\n’ is pushed in to the character stack.
a) true
b) false
Answer: b
Explanation: The input character ‘\n’ is accepted as a character by the evaluation of prefix expression algorithm.

27. Using the evaluation of prefix algorithm, evaluate +-9 2 7.
a) 10
b) 4
c) 17
d) 14
Answer: d
Explanation: Using the evaluation of prefix algorithm, +-9 2 7 is evaluated as 9-2+7=14.

28. If -*+abcd = 11, find a, b, c, d using evaluation of prefix algorithm.
a) a=2, b=3, c=5, d=4
b) a=1, b=2, c=5, d=4
c) a=5, b=4, c=7,d=5
d) a=1, b=2, c=3, d=4
Answer: b
Explanation: The given prefix expression is evaluated as ((1+2)*5)-4 =11 while a=1, b=2, c=5, d=4.

29. In the given C snippet, find the statement number that has error.
//C code to push an element into a stack
1. void push( struct stack *s, int x)

2. {
3.           if(s->top==MAX-1)
4.          {
5.               printf(“stack overflow”);
6.          }
7.          else
8.          {
9.                  s->items[++s->top]=x;
10.                 s++;
11.         }   
12.}

a) 1
b) 9
c) 10
d) 11
Answer: c
Explanation: The stack’s top position is incremented twice at the same time. So, when the next element is pushed, there is unit gap between this element and the previous element.

30. For the given expression tree, write the correct postfix expression.

a) abc*+
b) abc+*
c) ab+c*
d) a+bc*
Answer: a
Explanation: Evaluating the given expression tree gives the infix expression a+b*c. Converting it to postfix, we get, abc*+.

31. What is the other name for a postfix expression?
a) Normal polish Notation
b) Reverse polish Notation
c) Warsaw notation
d) Infix notation
Answer: b
Explanation: Reverse polish Notation is the other name for a postfix expression whereas Polish Notation, Warsaw notation are the other names for a prefix expression.

32. Which of the following is an example for a postfix expression?
a) a*b(c+d)
b) abc*+de-+
c) +ab
d) a+b-c
Answer: b
Explanation: abc*+de-+ is a postfix expression. +ab is a prefix expression and others are infix expressions.

33. Reverse Polish Notation is the reverse of a Polish Notation
a) True
b) False
Answer: b
Explanation: Reverse Polish Notation is not the reverse of a polish notation. Though both NPN and RPN read the expression from left to right, they follow different strategies.

34. What is the time complexity of evaluation of postfix expression algorithm?
a) O (N)
b) O (N log N)
c) O (N2)
d) O (M log N)
Answer: a
Explanation: The time complexity of evaluation of infix, prefix and postfix expressions is O (N).

35. In Postfix expressions, the operators come after the operands.
a) True
b) False
Answer: a
Explanation: In postfix expressions, the operators follow operands. In prefix expressions, the operands follow operators.

36. Which of these operators have the highest order of precedence?
a) ‘(‘ and ‘)’
b) ‘*’ and ‘/’
c) ‘~’ and ‘^’
d) ‘+’ and ‘-‘
Answer: c
Explanation: The highest order of precedence is ~ and ^ followed by ‘*’ ,’ /’, ‘+’ ,’-‘ and then braces ‘(‘ ‘)’.

37. Which of the following is not an application of stack?
a) evaluation of postfix expression
b) conversion of infix to postfix expression
c) balancing symbols
d) line at ticket counter
Answer: d
Explanation: Line at ticket counter is an application of queue whereas conversion of infix to postfix expression, balancing symbols, line at ticket counter are stack applications.

38. While evaluating a postfix expression, when an operator is encountered, what is the correct operation to be performed?
a) push it directly on to the stack
b) pop 2 operands, evaluate them and push the result on to the stack
c) pop the entire stack
d) ignore the operator
Answer: b
Explanation: When an operator is encountered, the first two operands are popped from the stack, they are evaluated and the result is pushed into the stack.

39. Which of the following statement is incorrect?
a) Postfix operators use value to their right
b) Postfix operators use value to their left
c) Prefix operators use value to their right
d) In postfix expression, operands are followed by operators
Answer: a
Explanation: All prefix operators use values to their right and all postfix operators use values to their left.

40. What is the result of the given postfix expression? abc*+ where a=1, b=2, c=3.
a) 4
b) 5
c) 6
d) 7
Answer: d
Explanation: The infix expression is a+b*c. Evaluating it, we get 1+2*3=7.

41. When an operand is read, which of the following is done?
a) It is placed on to the output
b) It is placed in operator stack
c) It is ignored
d) Operator stack is emptied
Answer: a
Explanation: While converting an infix expression to a postfix expression, when an operand is read, it is placed on to the output. When an operator is read, it is placed in the operator stack.

42. What should be done when a left parenthesis ‘(‘ is encountered?
a) It is ignored
b) It is placed in the output
c) It is placed in the operator stack
d) The contents of the operator stack is emptied
Answer: c
Explanation: When a left parenthesis is encountered, it is placed on to the operator stack. When the corresponding right parenthesis is encountered, the stack is popped until the left parenthesis and remove both the parenthesis.

43. Which of the following is an infix expression?
a) (a+b)*(c+d)
b) ab+c*
c) +ab
d) abc+*
Answer: a
Explanation: (a+b)*(c+d) is an infix expression. +ab is a prefix expression and ab+c* is a postfix expression.

44. What is the time complexity of an infix to postfix conversion algorithm?
a) O(N log N)
b) O(N)
c) O(N2)
d) O(M log N)
Answer: b
Explanation: The time complexity of an infix to postfix expression conversion algorithm is mathematically found to be O(N).

45.What is the postfix expression for the corresponding infix expression?
a+b*c+(d*e)

a) abc*+de*+
b) abc+*de*+
c) a+bc*de+*
d) abc*+(de)*+
Answer: a
Explanation: Using the infix to postfix expression conversion algorithm, the corresponding postfix expression is found to be abc*+de*+.

46. Parentheses are simply ignored in the conversion of infix to postfix expression.
a) True
b) False
Answer: b
Explanation: When a parenthesis is encountered, it is placed on the operator stack. When the corresponding parenthesis is encountered, the stack is popped until the other parenthesis is reached and they are discarded.

47. It is easier for a computer to process a postfix expression than an infix expression.
a) True
b) False
Answer: a
Explanation: Computers can easily process a postfix expression because a postfix expression keeps track of precedence of operators.

48. What is the postfix expression for the infix expression?
abc

a) -ab-c
b) ab – c –
c) – -abc
d) -ab-c
Answer: b
Explanation: The corresponding postfix expression for the given infix expression is found to be ab-c- and not abc- -.

49. What is the postfix expression for the following infix expression?
a/b^cd

a) abc^/d-
b) ab/cd^-
c) ab/^cd-
d) abcd^/-
Answer: a
Explanation: Using the infix to postfix conversion algorithm, the corresponding postfix expression for the infix expression is found to be abc^/d-.

50. Which of the following statement is incorrect with respect to infix to postfix conversion algorithm?
a) operand is always placed in the output
b) operator is placed in the stack when the stack operator has lower precedence
c) parenthesis are included in the output
d) higher and equal priority operators follow the same condition
Answer: c
Explanation: Parentheses are not included in the output. They are placed in the operator stack and then discarded.

51. 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
Answer: b
Explanation: Greedy algorithm is the best approach for solving the Huffman codes problem since it greedily searches for an optimal solution.

52. How many printable characters does the ASCII character set consists of?
a) 120
b) 128
c) 100
d) 98
Answer: c
Explanation: Out of 128 characters in an ASCII set, roughly, only 100 characters are printable while the rest are non-printable.

53. Which bit is reserved as a parity bit in an ASCII set?
a) first
b) seventh
c) eighth
d) tenth
Answer: c
Explanation: In an ASCII character set, seven bits are reserved for character representation while the eighth bit is a parity bit.

54. 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
Answer: a
Explanation: If the size of the character set is X, then [log X] bits are needed for representation in a standard encoding.

55. The code length does not depend on the frequency of occurrence of characters.
a) true
b) false
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.

56. In Huffman coding, data in a tree always occur?
a) roots
b) leaves
c) left sub trees
d) right sub trees
Answer: b
Explanation: In Huffman encoding, data is always stored at the leaves of a tree inorder to compute the codeword effectively.

57. From the following given tree, what is the code word for the character ‘a’?

a) 011
b) 010
c) 100
d) 101
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.

58. From the following given tree, what is the computed codeword for ‘c’?

a) 111
b) 101
c) 110
d) 011
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.

59. 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
Answer: c
Explanation: If character ci is at depth di and occurs at frequency fi, the cost of the codeword obtained is ∑fidi.

60. An optimal code will always be present in a full tree.
a) true
b) false
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.

61. On which algorithm is heap sort based on?
a) Fibonacci heap
b) Binary tree
c) Priority queue
d) FIFO
Answer: c
Explanation: Heap sort is based on the algorithm of priority queue and it gives the best sorting time.

62. In what time can a binary heap be built?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N2)
Answer: a
Explanation: The basic strategy is to build a binary heap of N elements which takes O(N) time.

63. Heap sort is faster than Shell sort.
a) true
b) false
Answer: b
Explanation: Heap sort is slower than Shell sort because Shell sort uses Sedgewick’s increment sequence.

64. Consider the following heap after buildheap phase. What will be its corresponding array?

a) 26,53,41,97,58,59,31
b) 26,31,41,53,58,59,97
c) 26,41,53,97,31,58,59
d) 97,53,59,26,41,58,31
Answer: d
Explanation: Constructing a max heap using the elements 97,53,59,26,41,58,31 will cause the heap to look like that.

65. In what position does the array for heap sort contains data?
a) 0
b) 1
c) -1
d) anywhere in the array
Answer: a
Explanation: The array for heap sort contains data at position 0 whereas for a binary heap, array begins at 1. This is the reason for its complexity.

66. In heap sort, after deleting the last minimum element, the array will contain elements in?
a) increasing sorting order
b) decreasing sorting order
c) tree inorder
d) tree preorder
Answer: b
Explanation: By logic, after deleting minimum element, the heap will contain elements in decreasing sorting order. We can change this by altering the ordering property.

67. What is the typical running time of a heap sort algorithm?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N2)
Answer: b
Explanation: The total running time of a heap sort algorithm is mathematically found to be O(N log N).

68. How many arrays are required to perform deletion operation in a heap?
a) 1
b) 2
c) 3
d) 4
Answer: b
Explanation: To perform deletion operation in a heap, we require 2 arrays and that occupies extra memory space and hence increase in running time.

69. What is the time taken to perform a delete min operation?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N2)
Answer: c
Explanation: The time taken to perform a deletion of a minimum element is mathematically found to be O( log N).

70. Heap sort is an extremely stable algorithm.
a) true
b) false
Answer: a
Explanation: Heap sort uses fewer comparisons than other sorting algorithms and hence it is an extremely stable algorithm.

71. 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
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.

72. Every graph has only one minimum spanning tree.
a) True
b) False
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.

73. Consider a complete graph G with 4 vertices. The graph G has ____ spanning trees.
a) 15
b) 8
c) 16
d) 13
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.

74. The travelling salesman problem can be solved using _________
a) A spanning tree
b) A minimum spanning tree
c) Bellman – Ford algorithm
d) DFS traversal
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.

75. 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
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.

76. 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
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.

77. 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
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.

78. 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)
Answer: c
Explanation: The minimum spanning tree of the given graph is shown below. It has cost 56.

79. 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
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.

80. 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
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.

81. Which of the following is true?
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
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).

82. 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
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.

83. 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)
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.

84. Prim’s algorithm is a ______
a) Divide and conquer algorithm
b) Greedy algorithm
c) Dynamic Programming
d) Approximation algorithm
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.

85. Prim’s algorithm resembles Dijkstra’s algorithm.
a) True
b) False
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.

86. Kruskal’s algorithm is best suited for the sparse graphs than the prim’s algorithm.
a) True
b) False
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.

87. 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)
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).

88. Prim’s algorithm is also known as __________
a) Dijkstra–Scholten algorithm
b) Borůvka’s algorithm
c) Floyd–Warshall algorithm
d) DJP Algorithm
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.

89. 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
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).

90. 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
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.

91. 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
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.

92. Kruskal’s algorithm is a ______
a) divide and conquer algorithm
b) dynamic programming algorithm
c) greedy algorithm
d) approximation algorithm
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.

93. 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
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.

94. 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)
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.

95. Consider the following graph. Using Kruskal’s algorithm, which edge will be selected first?

a) GF
b) DE
c) BE
d) BG
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.

96. 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)
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).

97. Which of the following is true?
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
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.

98. 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
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.

99. Kruskal’s algorithm is best suited for the dense graphs than the prim’s algorithm.
a) True
b) False
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.

100. 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
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.

Prepare For Your Placements: https://lastmomenttuitions.com/courses/placement-preparation/

/ Youtube Channel: https://www.youtube.com/channel/UCGFNZxMqKLsqWERX_N2f08Q

Follow For Latest Updates, Study Tips & More Content!

/lastmomenttuition

/ Last Moment Tuitions

/ lastmomentdost