Data Structure – module 2

1.A linear collection of data elements where the linear node is given by means of pointer is called?
a) Linked list
b) Node list
c) Primitive list
d) Unordered list
Answer: a
Explanation: In Linked list each node has its own data and the address of next node. These nodes are linked by using pointers. Node list is an object that consists of a list of all nodes in a document with in a particular selected set of nodes.

2.Consider an implementation of unsorted singly linked list. Suppose it has its representation with a head pointer only.
Given the representation, which of the following operation can be implemented in O(1) time?
i) Insertion at the front of the linked list
ii) Insertion at the end of the linked list
iii) Deletion of the front node of the linked list
iv) Deletion of the last node of the linked list
a) I and II
b) I and III
c) I, II and III
d) I, II and IV
Answer: b
Explanation: We know the head node in the given linked list. Insertion and deletion of elements at the front of the linked list completes in O (1) time whereas for insertion and deletion at the last node requires to traverse through every node in the linked list. Suppose there are n elements in a linked list, we need to traverse through each node. Hence time complexity becomes O(n).

3.In linked list each node 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.

4.What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list?
a) O(1)
b) O(n)
c) θ(n)
d) θ(1)
Answer: c
Explanation: In case of a linked list having n elements, we need to travel through every node of the list to add the element at the end of the list. Thus asymptotic time complexity is θ(n).

5.What would be the asymptotic time complexity to insert an element at the front of the linked list (head is known)?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)
Answer: a
Explanation: To add an element at the front of the linked list, we will create a new node which holds the data to be added to the linked list and pointer which points to head position in the linked list. The entire thing happens within O (1) time. Thus the asymptotic time complexity is O (1).

6.What would be the asymptotic time complexity to find an element in the linked list?
a) O(1)
b) O(n)
c) O(n2)
d) O(n4)
Answer: b
Explanation: If the required element is in the last position, we need to traverse the entire linked list. This will take O (n) time to search the element.

7.What would be the asymptotic time complexity to insert an element at the second position in the linked list?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)
Answer: a
Explanation: A new node is created with the required element. The pointer of the new node points the node to which the head node of the linked list is also pointing. The head node pointer is changed and it points to the new node which we created earlier. The entire process completes in O (1) time. Thus the asymptotic time complexity to insert an element in the second position of the linked list is O (1).

8.The concatenation of two 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.

9.Consider the following definition in c programming language
struct node
{
int data;
struct node * next;
}
typedef struct node NODE;
NODE *ptr;
Which of the following c code is used to create new node?
a) ptr = (NODE*)malloc(sizeof(NODE));
b) ptr = (NODE*)malloc(NODE);
c) ptr = (NODE*)malloc(sizeof(NODE*));
d) ptr = (NODE)malloc(sizeof(NODE));
Answer: a
Explanation: As it represents the right way to create a node.

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

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

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

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

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

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

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

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

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

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

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

21.Which of the following performs deletion of the last element in the list? Given below is the Node class.
class Node
{
protected Node next;
protected Object ele;
Node(Object e,Node n)
{
ele = e;
next = n;
}
public void setNext(Node n)
{
next = n;
}
public void setEle(Object e)
{
ele = e;
}
public Node getNext()
{
return next;
}
public Object getEle()
{
return ele;
}
}
class SLL 
{
Node head;
int size;
SLL()
{
size = 0;
}
}

a) public Node removeLast()
{
if(size == 0)
return null;
Node cur;
Node temp;
cur = head;
while(cur.getNext() != null)
{
temp = cur;
cur = cur.getNext();
        }
temp.setNext(null);
size–;
return cur;
}

b)public void removeLast()
{
if(size == 0)
return null;
Node cur;
Node temp;
cur = head;
while(cur != null)
{
temp = cur;
cur = cur.getNext();
        }
temp.setNext(null);
return cur;
}

c)public void removeLast()
{
if(size == 0)
    return null;
Node cur;
Node temp;
cur = head;
while(cur != null)
{
cur = cur.getNext();
temp = cur;
}
temp.setNext(null);
return cur;
}

d)public void removeLast()
{
if(size == 0)
return null;
Node cur;
Node temp;
cur = head;
while(cur.getNext() != null)
{
cur = cur.getNext();
temp = cur;
}
temp.setNext(null);
return cur;
}

Answer: a
Explanation: Since you have to traverse to the end of the list and delete the last node, you need two reference pointers. ‘cur’ to traverse all the way and find the last node, and ‘temp’ is a trailing pointer to ‘cur’. Once you reach the end of the list, setNext of ‘temp’ to null, ‘cur’ is not being pointed to by any node, and hence it is available for garbage collection.

22.What is the functionality of the following code?
public void function(Node node)
{
if(size == 0)
head = node;
else
{
Node temp,cur;
for(cur = head; (temp = cur.getNext())!=null; cur = temp);
cur.setNext(node);
}
size++;
}
a) Inserting a node at the beginning of the list
b) Deleting a node at the beginning of the list
c) Inserting a node at the end of the list
d) Deleting a node at the end of the list
Answer: c
Explanation: The for loop traverses through the list and then inserts a new node as cur.setNext(node);  

23.What is the space complexity for deleting a linked list?
a) O(1)
b) O(n)
c) Either O(1) or O(n)
d) O(logn)
Answer: a
Explanation: You need a temp variable to keep track of current node, hence the space complexity is O(1).

24.How would you delete a node in the singly linked list? The position to be deleted is given.
a)public void delete(int pos)
{
if(pos < 0)
pos = 0;
if(pos > size)
pos = size;
if( size == 0)
return;
if(pos == 0)
head = head.getNext();
else
{
    Node temp = head;
    for(int i=1; i<pos; i++)
            {
temp = temp.getNext();
            }
    temp.setNext(temp.getNext().getNext());
}
    size–;
}

b)public void delete(int pos)
{
if(pos < 0)
pos = 0;
if(pos > size)
pos = size;
if( size == 0)
return;
if(pos == 0)
head = head.getNext();
else
{
    Node temp = head;
   for(int i=1; i<pos; i++)
    {
temp = temp.getNext();
    }
    temp.setNext(temp.getNext());
}
    size–;
}

c)public void delete(int pos)
{
        if(pos < 0)
pos = 0;
if(pos > size)
pos = size;
if( size == 0)
return;
if(pos == 0)
head = head.getNext();
else
{
    Node temp = head;
    for(int i=1; i<pos; i++)
    {
temp = temp.getNext().getNext();
            }
    temp.setNext(temp.getNext().getNext());
}
    size–;
}

d)public void delete(int pos)
{
        if(pos < 0)
        pos = 0;
        if(pos > size)
        pos = size;
        if( size == 0)
return;
if(pos == 0)
head = head.getNext();
else
{
    Node temp = head;
    for(int i=0; i<pos; i++)
    {
temp = temp.getNext();
    }
    temp.setNext(temp.getNext().getNext());
}
size–;
}
Answer: a
Explanation: Loop through the list to get into position one behind the actual position given. temp.setNext(temp.getNext().getNext()) will delete the specified node.

  

25.Which of these is not an application of a linked list?
a) To implement file systems
b) For separate chaining in hash-tables
c) To implement non-binary trees
d) Random Access of elements
Answer: d
Explanation: To implement file system, for separate chaining in hash-tables and to implement non-binary trees linked lists are used. Elements are accessed sequentially in linked list. Random access of elements is not an applications of linked list.

26.Which of the following piece of code has the functionality of counting the number of elements in the list?
a)public int length(Node head)
{
int size = 0;
Node cur = head;
while(cur!=null)
{
    size++;
    cur = cur.getNext();
}
return size;
}

b)public int length(Node head)
{
        int size = 0;
Node cur = head;
while(cur!=null)
{
    cur = cur.getNext();
    size++;
}
return size;
}

c)public int length(Node head)
{
int size = 0;
Node cur = head;
while(cur!=null)
{
    size++;
    cur = cur.getNext();
}
}

d)public int length(Node head)
{
int size = 0;
Node cur = head;
while(cur!=null)
{
    size++;
    cur = cur.getNext().getNext();
}
return size;
}
Answer: a
Explanation: ‘cur’ pointer traverses through list and increments the size variable until the end of list is reached.

  
27.How do you insert an element at the beginning of the list?
a)public void insertBegin(Node node)
{
node.setNext(head);
head = node;
size++;
}
b)public void insertBegin(Node node)
{
head = node;
node.setNext(head);
size++;
}
c)public void insertBegin(Node node)
{
Node temp = head.getNext()
node.setNext(temp);
head = node;
size++;
}
d)public void insertBegin(Node node)
{
Node temp = head.getNext()
node.setNext(temp);
node = head;
size++;
}
Answer: a
Explanation: Set the ‘next’ pointer point to the head of the list and then make this new node as the head.

  
28.What is the functionality of the following piece of code?
public int function(int data)
{
Node temp = head;
int var = 0;
while(temp != null)
{
if(temp.getData() == data)
{
return var;
}
var = var+1;
temp = temp.getNext();
}
return Integer.MIN_VALUE;
}
a) Find and delete a given element in the list
b) Find and return the given element in the list
c) Find and return the position of the given element in the list
d) Find and insert a new element in the list
Answer: c
Explanation: When temp is equal to data, the position of data is returned.

29.Which of the following is false about a doubly linked list?
a) We can navigate in both the directions
b) It requires more space than a singly linked list
c) The insertion and deletion of a node take a bit longer
d) Implementing a doubly linked list is easier than singly linked list
Answer: d
Explanation: A doubly linked list has two pointers ‘left’ and ‘right’ which enable it to traverse in either direction. Compared to singly liked list which has only a ‘next’ pointer, doubly linked list requires extra space to store this extra pointer. Every insertion and deletion requires manipulation of two pointers, hence it takes a bit longer time. Implementing doubly linked list involves setting both left and right pointers to correct nodes and takes more time than singly linked list.

30.Given the Node class implementation, select one of the following that correctly inserts a node at the tail of the list.
public class Node
{
protected int data;
protected Node prev;
protected Node next;
public Node(int data)
{
this.data = data;
prev = null;
next = null;
}
public Node(int data, Node prev, Node next)
{
this.data = data;
this.prev = prev;
this.next = next;
}
public int getData()
{
return data;
}
public void setData(int data)
{
this.data = data;
}
public Node getPrev()
{
return prev;
}
public void setPrev(Node prev)
{
this.prev = prev;
}
public Node getNext
{
return next;
}
public void setNext(Node next)
{
this.next = next;
}
}
public class DLL
{
protected Node head;
protected Node tail;
int length;
public DLL()
{
head = new Node(Integer.MIN_VALUE,null,null);
tail = new Node(Integer.MIN_VALUE,null,null);
head.setNext(tail);
length = 0;
}
}

a)public void insertRear(int data)
{
Node node = new Node(data,tail.getPrev(),tail);
node.getPrev().setNext(node);
tail.setPrev(node);
length++;
}
b)public void insertRear(int data)
{
Node node = new Node(data,tail.getPrev(),tail);
node.getPrev().getPrev().setNext(node);
tail.setPrev(node);
length++;
}

c)public void insertRear(int data)
{
Node node = new Node(data,tail.getPrev(),tail);
node.getPrev().setNext(tail);
tail.setPrev(node);
length++;
}

d)public void insertRear(int data)
{
Node node = new Node(data,head,tail);
node.getPrev().setNext(node);
tail.setPrev(node);
length++;
}
Answer: a
Explanation: First create a new node whose ‘prev’ points to the node pointed to by the ‘prev’ of tail. The ‘next’ of the new node should point to tail. Set the ‘prev’ of tail to point to new node and the ‘prev’ of new node to point to the new node.

  

31.What is a memory efficient double linked list?
a) Each node has only one pointer to traverse the list back and forth
b) The list has breakpoints for faster traversal
c) An auxiliary singly linked list acts as a helper list to traverse through the doubly linked list
d) A doubly linked list that uses bitwise AND operator for storing addresses
Answer: a
Explanation: Memory efficient doubly linked list has only one pointer to traverse the list back and forth. The implementation is based on pointer difference. It uses bitwise XOR operator to store the front and rear pointer addresses. Instead of storing actual memory address, every node store the XOR address of previous and next nodes.

 

32.Which of the following piece of code removes the node from a given position?
a)public void remove(int pos)
{
if(pos<0 || pos>=size)
{
System.out.println(“Invalid position”);
return;
}
else
{
if(head == null)
return;
if(pos == 0)
{
head = head.getNext();
if(head == null)
tail = null;
}
        else
        {
Node temp = head;
for(int i=1; i<position; i++)
temp = temp.getNext();
}
temp.getNext().setPrev(temp.getPrev());
temp.getPrev().setNext(temp.getNext());
}
size–;
}

b)public void remove(int pos)
{
if(pos<0 || pos>=size
{
System.out.println(“Invalid position”);
return;
}
else
{
if(head == null)
return;
if(pos == 0)
{
head = head.getNext();
if(head == null)
tail = null;
}
else
{
Node temp = head;
for(int i=1; i<position; i++)
temp = temp.getNext();
}
temp.getNext().setPrev(temp.getNext());
temp.getPrev().setNext(temp.getPrev());
}
size–;
}

c)public void remove(int pos)
{
if(pos<0 || pos>=size)
{
System.out.println(“Invalid position”);
return;
}
else
{
if(head == null)
return;
if(pos == 0)
{
head = head.getNext();
if(head == null)
tail = null;
}
else
{
Node temp = head;
for(int i=1; i<position; i++)
temp = temp.getNext().getNext();
}
temp.getNext().setPrev(temp.getPrev());
temp.getPrev().setNext(temp.getNext());
}
size–;
}

d)public void remove(int pos)
{
if(pos<0 || pos>=size)
{
System.out.println(“Invalid position”);
return;
}
else
{
if(head == null)
return;
if(pos == 0)
{
head = head.getNext();
if(head == null)
tail = null;
}
else
{
Node temp = head;
for(int i=1; i<position; i++)
temp = temp.getNext().getNext();
}
temp.getNext().setPrev(temp.getNext());
temp.getPrev().setNext(temp.getPrev());
}
size–;
}

Answer: a
Explanation: If the position to be deleted is not the head, advance to the given position and manipulate the previous and next pointers of next and previous nodes respectively.

33.How do you calculate the pointer difference in a memory efficient double linked list?
a) head xor tail
b) pointer to previous node xor pointer to next node
c) pointer to previous node – pointer to next node
d) pointer to next node – pointer to previous node
Answer: b
Explanation: The pointer difference is calculated by taking XOR of pointer to previous node and pointer to the next node.

34.What is the worst case time complexity of inserting a node in a doubly linked list?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)
Answer: c
Explanation: In the worst case, the position to be inserted maybe at the end of the list, hence you have to traverse through the entire list to get to the correct position, hence O(n).

35.How do you insert a node at the beginning of the list?
a)public class insertFront(int data)
{
Node node = new Node(data, head, head.getNext());
node.getNext().setPrev(node);
head.setNext(node);
size++;
}
b)public class insertFront(int data)
{
Node node = new Node(data, head, head);
node.getNext().setPrev(node);
head.setNext(node);
size++;
}
c)public class insertFront(int data)
{
Node node = new Node(data, head, head.getNext());
node.getNext().setPrev(head);
head.setNext(node);
size++;
}

d)public class insertFront(int data)
{
Node node = new Node(data, head, head.getNext());
node.getNext().setPrev(node);
head.setNext(node.getNext());
size++;
}
Answer: a
Explanation: The new node’s previous pointer will point to head and next pointer will point to the current next of head.

  
36.Consider the following doubly linked list: head-1-2-3-4-5-tail. What will be the list after performing the given sequence of operations?
Node temp = new Node(6,head,head.getNext());
Node temp1 = new Node(0,tail.getPrev(),tail);
head.setNext(temp);
temp.getNext().setPrev(temp);
tail.setPrev(temp1);
temp1.getPrev().setNext(temp1);
a) head-0-1-2-3-4-5-6-tail
b) head-1-2-3-4-5-6-tail
c) head-6-1-2-3-4-5-0-tail
d) head-0-1-2-3-4-5-tail
Answer: c
Explanation: The given sequence of operations performs addition of nodes at the head and tail of the list.

37.What is the functionality of the following piece of code?
public int function()
{
Node temp = tail.getPrev();
tail.setPrev(temp.getPrev());
temp.getPrev().setNext(tail);
size–;
return temp.getItem();
}
a) Return the element at the tail of the list but do not remove it
b) Return the element at the tail of the list and remove it from the list
c) Return the last but one element from the list but do not remove it
d) Return the last but one element at the tail of the list and remove it from the list
Answer: b
Explanation: The previous and next pointers of the tail and the last but one element are manipulated, this suggests that the last node is being removed from the list.

38.Consider the following doubly linked list: head-1-2-3-4-5-tail. What will be the list after performing the given sequence of operations?
Node temp = new Node(6,head,head.getNext());
head.setNext(temp);
temp.getNext().setPrev(temp);
Node temp1 = tail.getPrev();
tail.setPrev(temp1.getPrev());
temp1.getPrev().setNext(tail);
a) head-6-1-2-3-4-5-tail
b) head-6-1-2-3-4-tail
c) head-1-2-3-4-5-6-tail
d) head-1-2-3-4-5-tail
Answer: b
Explanation: A new node is added to the head of the list and a node is deleted from the tail end of the list.

39What differentiates a circular linked list from a normal linked list?
a) You cannot have the ‘next’ pointer point to null in a circular linked list
b) It is faster to traverse the circular linked list
c) You may or may not have the ‘next’ pointer point to null in a circular linked list
d) Head node is known in circular linked list
Answer: c
Explanation: The ‘next’ pointer points to null only when the list is empty, otherwise it points to the head of the list. Every node in a circular linked list can be a starting point(head).

40.What is the time complexity of searching for an element in a circular linked list?
a) O(n)
b) O(nlogn)
c) O(1)
d) O(n2)
Answer: a
Explanation: In the worst case, you have to traverse through the entire list of n elements.

41.Which of the following application makes use of a circular linked list?
a) Undo operation in a text editor
b) Recursive function calls
c) Allocating CPU to resources
d) Implement Hash Tables
Answer: c
Explanation: Generally, round robin fashion is employed to allocate CPU time to resources which makes use of the circular linked list data structure. Recursive function calls use stack data structure. Undo Operation in text editor uses doubly linked lists. Hash tables uses singly linked lists.

42.Which of the following is false about a circular linked list?
a) Every node has a successor
b) Time complexity of inserting a new node at the head of the list is O(1)
c) Time complexity for deleting the last node is O(n)
d) We can traverse the whole circular linked list by starting from any point
Answer: b
Explanation: Time complexity of inserting a new node at the head of the list is O(n) because you have to traverse through the list to find the tail node.

43.Consider a small circular linked list. How to detect the presence of cycles in this list effectively?
a) Keep one node as head and traverse another temp node till the end to check if its ‘next points to head
b) Have fast and slow pointers with the fast pointer advancing two nodes at a time and slow pointer advancing by one node at a time
c) Cannot determine, you have to pre-define if the list contains cycles
d) Circular linked list itself represents a cycle. So no new cycles cannot be generated
Answer: b
Explanation: Advance the pointers in such a way that the fast pointer advances two nodes at a time and slow pointer advances one node at a time and check to see if at any given instant of time if the fast pointer points to slow pointer or if the fast pointer’s ‘next’ points to the slow pointer. This is applicable for smaller lists.

 

 

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

Data Structure – module 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21.The result of evaluating the postfix expression 5, 4, 6, +, *, 4, 9, 3, /, +, * is?
a) 600
b) 350
c) 650
d) 588
Answer: b
Explanation: The postfix expression is evaluated using stack. We will get the infix expression as
(5*(4+6))*(4+9/3). On solving the Infix Expression, we get
(5*(10))*(4+3)
= 50*7
= 350.

22.Convert the following infix expressions into its equivalent postfix expressions.
(A + B ⋀D)/(E – F)+G
a) (A B D ⋀ + E F – / G +)
b) (A B D +⋀ E F – / G +)
c) (A B D ⋀ + E F/- G +)
d) (A B D E F + ⋀ / – G +)
Answer: a
Explanation: The given infix expression is (A + B ⋀D)/(E – F)+G.
(A B D ^ + ) / (E – F) +G
(A B D ^ + E F – ) + G. ‘/’ is present in stack.
A B D ^ + E F – / G +. Thus Postfix Expression is A B D ^ + E F – / G +.

23.Convert the following Infix expression to Postfix form using a stack.
x + y * z + (p * q + r) * s, Follow usual precedence rule and assume that the expression is legal.
a) xyz*+pq*r+s*+
b) xyz*+pq*r+s+*
c) xyz+*pq*r+s*+
d) xyzp+**qr+s*+
Answer: a
Explanation: The Infix Expression is x + y * z + (p * q + r) * s.
(x y z ) + (p * q + r) * s. ‘+’, ‘*’ are present in stack.
(x y z * + p q * r) * s. ‘+’ is present in stack.
x y z * + p q * r + s * +. Thus Postfix Expression is x y z * + p q * r + s * +.

24.Which of the following statement(s) about stack data structure is/are NOT correct?
a) Linked List are used for implementing Stacks
b) Top of the Stack always contain the new node
c) Stack is the FIFO data structure
d) Null link is present in the last node at the bottom of the stack
Answer: c
Explanation: Stack follows LIFO.

25.Consider the following operation performed on a stack of size 5.
Push(1);
Pop();
Push(2);
Push(3);
Pop();
Push(4);
Pop();
Pop();
Push(5);
After the completion of all operation, the number of elements present in stack is?
a) 1
b) 2
c) 3
d) 4
Answer: a
Explanation: Number of elements present in stack is equal to the difference between number of push operations and number of pop operations. Number of elements is 5-4=1.

26.Which of the following is not an inherent application of stack?
a) Reversing a string
b) Evaluation of postfix expression
c) Implementation of recursion
d) Job scheduling
Answer: d
Explanation: Job Scheduling is not performed using stacks.

27.The type of expression in which operator succeeds its operands is?
a) Infix Expression
b) Prefix Expression
c) Postfix Expression
d) Both Prefix and Postfix Expressions
Answer: c
Explanation: The expression in which operator succeeds its operands is called postfix expression. The expression in which operator precedes the operands is called prefix expression. If an operator is present between two operands, then it is called infix expressions.

28.Assume that the operators +,-, X are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^, X, +, -. The postfix expression for the infix expression a + b X c – d ^ e ^ f is?
a) abc X+ def ^^ –
b) abc X+ de^f^ –
c) ab+c Xd – e ^f^
d) -+aXbc^ ^def
Answer: b
Explanation: Given Infix Expression is a + b X c – d ^ e ^ f.
(a b c X +) (d ^ e ^ f). ‘–‘ is present in stack.
(a b c X + d e ^ f ^ -). Thus the final expression is (a b c X + d e ^ f ^ -).

30.If the elements “A”, “B”, “C” and “D” are placed in a stack and are deleted one at a time, what is the order of removal?
a) ABCD
b) DCBA
c) DCAB
d) ABDC
Answer: b
Explanation: Stack follows LIFO(Last In First Out). So the removal order of elements are DCBA.

Data Structure – module 4

1.A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is known as _____________
a) Queue
b) Stack
c) Tree
d) Linked list
Answer: a
Explanation: Linear list of elements in which deletion is done at front side and insertion at rear side is called Queue. In stack we will delete the last entered element first.

2.The data structure required for Breadth First Traversal on a graph is?
a) Stack
b) Array
c) Queue
d) Tree
Answer: c
Explanation: In Breadth First Search Traversal, BFS, starting vertex is first taken and adjacent vertices which are unvisited are also taken. Again, the first vertex which was added as an unvisited adjacent vertex list will be considered to add further unvisited vertices of the graph. To get the first unvisited vertex we need to follows First In First Out principle. Queue uses FIFO principle.

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

4.Circular Queue is also known as ________
a) Ring Buffer
b) Square Buffer
c) Rectangle Buffer
d) Curve Buffer
Answer: a
Explanation: Circular Queue is also called as Ring Buffer. Circular Queue is a linear data structure in which last position is connected back to the first position to make a circle. It forms a ring structure.

5.If the elements “A”, “B”, “C” and “D” are placed in a queue and are deleted one at a time, in what order will they be removed?
a) ABCD
b) DCBA
c) DCAB
d) ABDC
Answer: a
Explanation: Queue follows FIFO approach. i.e. First in First Out Approach. So, the order of removal elements are ABCD.

6.A data structure in which elements can be inserted or deleted at/from both ends but not in the middle is?
a) Queue
b) Circular queue
c) Dequeue
d) Priority queue
Answer: c
Explanation: In dequeuer, we can insert or delete elements from both the ends. In queue, we will follow first in first out principle for insertion and deletion of elements. Element with least priority will be deleted in a priority queue.

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

8.Queues serve major role in ______________
a) Simulation of recursion
b) Simulation of arbitrary linked list
c) Simulation of limited resource allocation
d) Simulation of heap sort
Answer: c
Explanation: Simulation of recursion uses stack data structure. Simulation of arbitrary linked lists uses linked lists. Simulation of resource allocation uses queue as first entered data needs to be given first priority during resource allocation. Simulation of heap sort uses heap data structure.

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

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

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

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

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

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

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

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

17.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[i–front] = 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[i–front] = 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[i–front] = 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[i–front] = 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.

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

19.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 = (rear–1)%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.

 

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

21.In linked list implementation of a queue, where does a new element be inserted?
a) At the head of link list
b) At the centre position in the link list
c) At the tail of the link list
d) At any position in the linked list
Answer: c
Explanation: Since queue follows FIFO so new element inserted at last.

22.In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into a NONEMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) No pointer will be changed
Answer: b
Explanation: Since queue follows FIFO so new element inserted at last.

23.In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into EMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) No pointer will be changed
Answer: c
Explanation: Since its the starting of queue, so both values are changed.

24.In case of insertion into a linked queue, a node borrowed from the __________ list is inserted in the queue.
a) AVAIL
b) FRONT
c) REAR
d) NULL
Answer: a
Explanation: All the nodes are collected in AVAIL list.

25.In linked list implementation of a queue, from where is the item deleted?
a) At the head of link list
b) At the centre position in the link list
c) At the tail of the link list
d) Node before the tail
Answer: a
Explanation: Since queue follows FIFO so new element deleted from first.

26.In linked list implementation of a queue, the important condition for a queue to be empty is?
a) FRONT is null
b) REAR is null
c) LINK is empty
d) FRONT==REAR-1
Answer: a
Explanation: Because front represents the deleted nodes.

27.The essential condition which is checked before insertion in a linked queue is?
a) Underflow
b) Overflow
c) Front value
d) Rear value
Answer: b
Explanation: To check whether there is space in the queue or not.

28.The essential condition which is checked before deletion in a linked queue is?
a) Underflow
b) Overflow
c) Front value
d) Rear value
Answer: a
Explanation: To check whether there is element in the list or not.

29.Which of the following is true about linked list implementation of queue?
a) In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end
b) In push operation, if new nodes are inserted at the beginning, then in pop operation, nodes must be removed from the beginning
c) In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from end
d) In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from beginning
Answer: a
Explanation: It can be done by both the methods.

Data Structure – module 5

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.

Data Structure – module 6

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.

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