Abstract Data Types MCQ [Free PDF] – Objective Question Answer for Abstract Data Types Quiz

CS MCQ, DS Structure

1. 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 initialized
D. Array is not a data structure

Answer: b

An array contains elements only of the same type. If the component type of an array is T, then the type of the array itself is written T [].

 

2. How do you initialize an array in C?

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

Answer: c

You can initialize an array in C either one by one or using a single statement as follows i.e

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

To initialize an array in C with the same value, the naive way is to provide an initializer list. We use this with small arrays. int num[5] = {1, 1, 1, 1, 1}; This will initialize the num array with value 1 at all index.

 

3. How do you instantiate an array in Java?

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

Answer: c

You can initialize an array in Java either one by one or using a single statement as follows i.e

int arr[] = new int[3];

Note that int arr[]; is declaration whereas int arr[] = new int[3]; is to instantiate an array. 

 

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

The syntax to declare multidimensional array in java is either int[][] arr; or int arr[][]; 

 

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

Array indexing starts from 0. 

 

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

Trying to access an element beyond the limits of an array gives ArrayIndexOutOfBoundsException. 

 

7. When does the ArrayIndexOutOfBoundsException occur?

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

Answer: b

ArrayIndexOutOfBoundsException occurs when we access an array, or a Collection, that is backed by an array with an invalid index.

ArrayIndexOutOfBoundsException is a run-time exception and the compilation is error-free. 

 

8. Which of the following concepts make extensive use of arrays?

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

Answer: D

Whenever a particular memory location is referred to, it is likely that the locations nearby are also referred to, arrays are stored as contiguous blocks in memory, so if you want to access array elements, spatial locality makes it to access quickly. 

 

9. 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 the first element of an array is 1
D. Easier to store elements of the same data type

Answer: D

The advantages of an array are

  • In an array, accessing an element is very easy by using the index number.
  • The search process can be applied to an array easily.
  • 2D Array is used to represent matrices.
  • Arrays store elements of the same data type and are present in continuous memory locations. 

 

10. What are the disadvantages of arrays?

A. Data structures 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

Disadvantages of arrays:

  • The number of elements to be stored in arrays should be known beforehand.
  • An array is static.
  • Insertion and deletion are quite difficult in an array.
  • Allocating more memory than required leads to wastage of memory.

 

11. Assuming int is of 4bytes, what is the size of int arr[15];?

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

Answer: D

Since there are 15 int elements and each int is of 4bytes, we get 15*4 = 60bytes. 

 

12. In general, the index of the first element in an array is __________

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

Answer: a

In general, Array Indexing starts from 0. Thus, the index of the first element in an array is 0. 

 

13. Elements in an array are accessed _____________

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

Answer: a

Elements in an array are accessed randomly. In Linked lists, elements are accessed sequentially. 

 

1. Process of inserting an element in stack is called ____________

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

Answer: b

Push operation allows users to insert elements into 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

Elements in the stack are removed using pop operation. Pop operation removes the topmost 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

  • In a stack, if a user tries to remove an element from an empty stack it is called Underflow.
  • 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 a stack already having five elements and stack size of 5, then the stack becomes ___________

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

Answer: a

Pushing an element into a stack already having five elements and a stack size of 5, then the stack becomes Overflow.

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

In the stack data structure, elements are added one by one using the 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

Data transfer between the two asynchronous processes uses the queue data structure for synchronization. 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

  • In the entire parenthesis balancing method when the incoming token is a left parenthesis, it is pushed into the stack.
  • A right parenthesis makes a pop operation to delete the elements in the stack till we the get left parenthesis as the topmost element.
  • 3 elements are there in the stack before the right parentheses come. Therefore, the maximum number of elements in the 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

  • In the entire parenthesis balancing method when the incoming token is a left parenthesis, it is pushed into the stack.
  • A right parenthesis makes a pop operation to delete the elements in the stack till we get the left parenthesis as the topmost element.
  • 2 left parenthesis are pushed whereas one right parenthesis removes one of the left parenthesis.
  • 2 elements are there before the right parenthesis which is the maximum number of elements in the 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

Postfix Expression is (6*(3-(2+4))) results in -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

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. 

 

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

(((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/ 

 

2. The data structure required to check whether an expression contains a balanced parenthesis is?

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

Answer: a

  • The data structure required to check whether an expression contains a balanced parenthesis is Stack.
  • 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, the parenthesis is balanced otherwise it is unbalanced. 

 

3. What data structure would you most likely see in the non-recursive implementation of a recursive algorithm?

A. Linked List
B. Stack
C. Queue
D. Tree

Answer: b

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. 

 

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

  • The process of accessing data stored in a serial access memory is similar to manipulating data on a Stack.
  • In serial access memory, data records are stored one after the other and they are created and accessed sequentially.
  • In the stack data structure, elements are accessed sequentially. Stack data structure resembles the serial access memory. 

 

5. The postfix form of A*B+C/D is?

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

Answer: b

Infix expression is (A*B)+(C/D)
AB*+(C/D)
AB*CD/+.

Thus postfix expression is AB*CD/+. 

 

6. Which data structure is needed to convert infix notation to postfix notation?

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

Answer: D

The Stack data structure is used to convert infix expression to postfix expression. The purpose of the 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. 

 

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

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. 

 

8. What is the result of the following operation?
Top (Push (S, X))

A. X
B. X+S
C. S
D. XS

Answer: a

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. 

 

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

Given Infix Expression is ((p+q)-(r*t))
(+pq)-(r*t)
(-+pq)(r*t)
-+pq*rt.

Thus prefix expression is -+pq*rt. 

 

10. Which data structure is used for implementing recursion?

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

Answer: b

Stack is a LIFO data structure i.e. ( Last In First Out) and hence it is used to implement recursion.

The High-level Programming languages, such as Pascal, C, etc. that provides support for recursion use stack for bookkeeping.

 

1. The result of evaluating the postfix expression 5, 4, 6, +, *, 4, 9, 3, /, +, * is?

A. 600
B. 350
C. 650
D. 588

Answer: b

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. 

 

2. Convert the following infix expressions into their 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

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 +)

 

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

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 * +)

 

4. Which of the following statement(s) about stack data structure is/are NOT correct?

A. Linked List is used for implementing Stacks
B. Top of the Stack always contains 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

Stack is not FIFO data structure Stack follows LIFO. 

 

5. 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 operations, the number of elements present in the stack is?

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

Answer: a

The number of elements present in the stack is equal to the difference between a number of push operations and a number of pop operations. The number of elements is 5-4=1. 

 

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

Job Scheduling is not performed using stacks. Job scheduling is the process of allocating system resources to many different tasks by an operating system (OS).

 

7. The type of expression in which the operator succeeds its operands is?

A. Infix Expression
B. Prefix Expression
C. Postfix Expression
D. Both Prefix and Postfix Expressions

Answer: c

The expression in which the operator succeeds its operands is called the postfix expression. The expression in which the operator precedes the operands is called prefix expression. If an operator is present between two operands, then it is called infix expressions. 

 

8. Assume that the operators +,-, and X is left-associative and ^ are 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

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

 

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

Stack follows LIFO(Last In First Out). So the removal order of elements is DCBA. 

 

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

A. Linked list
B. Node list
C. Primitive list
D. Unordered list

Answer: a

In the Linked list each node has its own data and the address of the next node. These nodes are linked by using pointers. A node list is an object that consists of a list of all nodes in a document within a particular selected set of nodes. 

 

2. Consider an implementation of an 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

We know the head node in the given linked list. Insertion and deletion of elements at the front of the linked list are complete in O (1) time whereas for insertion and deletion at the last node require traversing 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 the linked list each node contains a minimum of two fields. One field is a 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

In the linked list each node contains a minimum of two fields. One field is a data field to store the data second field is Pointer to node.

Each node in a linked list contains data and a pointer (reference) to the next node. The second field contains a pointer to the node. 

 

4. What would be the asymptotic time complexity to add a node at the end of a 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

In the 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

To add an element at the front of the linked list, we will create a new node that holds the data to be added to the linked list and a pointer that points to the 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

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

  • A new node is created with the required element. The pointer of the new node points to the node to which the head node of the linked list is also pointing.
  • The head node pointer is changed and it points to the new node which we created earlier. The entire process completes in O (1) time.
  • Thus the asymptotic time complexity to insert an element in the second position of the linked list is O (1). 

 

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

A. Singly linked list
B. Doubly linked list
C. Circular doubly linked list
D. Array implementation of list

Answer: c

  • We can easily concatenate two lists in O (1) time using a singly or doubly linked list, provided that we have a pointer to the last node in at least one of the lists.
  • But in the case of circular doubly linked lists, we will break the link in both lists and hook them together.
  • Thus circular doubly linked list concatenates two lists in O (1) time. 

 

9. Consider the following definition in the 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 a 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

It represents the right way to create a node.

ptr = (NODE*)malloc(sizeof(NODE)); 

 

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

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

 

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

A. Insertion sort
B. Radix sort
C. Polynomial manipulation
D. Binary search

Answer: D

Linked lists are not suitable for the implementation of Binary search. It cannot be implemented using linked lists. 

 

3. Linked list is considered as an example of ___________ type of memory allocation.

A. Dynamic
B. Static
C. Compile time
D. Heap

Answer: a

A linked list is considered as an example of a Dynamic type of memory allocation.

As memory is allocated at the run time. 

 

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

A. Data
B. Link
C. Data and Link
D. Node

Answer: b

A linked list is a collection of objects linked together by references from one object to another object.

By convention, these objects are named nodes. A linked list consists of nodes where each node contains one or more data fields and a reference(link) to the next node. 

 

5. Linked list data structure offers considerable saving in _____________

A. Computational Time
B. Space Utilization
C. Space Utilization and Computational Time
D. Speed Utilization

Answer: c

A linked list is the most sought-after data structure when it comes to handling dynamic data elements. A linked list consists of a data element known as a node.

Linked list data structure offers considerable savings in  Space Utilization and Computational Time. Linked lists save both space and time.

 

6. Which of the following points is/are not true about Linked List data structure when it is compared with an array?

A. Arrays have better cache locality which can make them better in terms of performance
B. It is easy to insert and delete elements on Linked List
C. Random access is not allowed in a typical implementation of Linked Lists
D. Access to elements in a linked list takes less time than compared arrays

Answer: D

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

 

7. What does the following function do for a given Linked List with the first node as the 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 the linked list in reverse order
C. Prints alternate nodes of Linked List
D. Prints alternate nodes in reverse order

Answer: b

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. 

 

8. Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?

A. Insertion Sort
B. Quick Sort
C. Heap Sort
D. Merge Sort

Answer: D

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 the worst-case time complexity of Merge Sort is O(nLogn) and Insertion sort is O(n2), merge sort is preferred. 

 

1. The following function reverse() is supposed to reverse a singly linked list. There is one line missing at the end of the function.

/* Link list node */
struct node
{
int data;
struct node* next;
};
 
/* head_ref is a double pointer which points to head (or start) pointer 
of linked list */
static void reverse(struct node** head_ref)
{
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL)
{
next = current->next; 
current->next = prev; 
prev = current;
current = next;
}
/*ADD A STATEMENT HERE*/
}

 

What should be added in place of “/*ADD A STATEMENT HERE*/”, so that the function correctly reverses a linked list?

A. *head_ref = prev;
B. *head_ref = current;
C. *head_ref = next;
D. *head_ref = NULL;

Answer: a

*head_ref = prev; At the end of the while loop, the prev pointer points to the last node of the original linked list.

We need to change *head_ref so that the head pointer now starts pointing to the last node. 

 

2. What is the output of the following function for start pointing to the first node of the following linked list?

1->2->3->4->5->6
void fun(struct node* start)
{
if(start == NULL)
return;
printf("%d ", start->datA.; 
if(start->next != NULL )
fun(start->next->next);
printf("%d ", start->datA.;
}

A. 1 4 6 6 4 1
B. 1 3 5 1 3 5
C. 1 2 3 5
D. 1 3 5 5 3 1

Answer: D

fun() prints alternate nodes of the given Linked List, first from head to end, and then from end to head.

If Linked List has an even number of nodes, then skip the last node. 

 

3. The following C function takes a simply-linked list as an input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank. Choose the correct alternative to replace the blank line.

typedef struct node 
{
int value;
struct node *next;
}Node;
 
Node *move_to_front(Node *heaD. 
{
Node *p, *q;
if ((head == NULL: || (head->next == NULL)) 
return head;
q = NULL; p = head;
while (p-> next !=NULL) 
{
q = p;
p = p->next;
}
_______________________________
return head;
}

A. q = NULL; p->next = head; head = p;
B. q->next = NULL; head = p; p->next = head;
C. head = p; p->next = q; q->next = NULL;
D. q->next = NULL; p->next = head; head = p;

Answer: D

When while loop completes its execution, node ‘p’ refers to the last node whereas the ‘q’ node refers to the node before ‘p’ in the linked list. q->next=NULL makes q the last node. p->next=head places p as the first node. the head must be modified to ‘p’ as ‘p’ is the starting node of the list (head=p). Thus the sequence of steps are q->next=NULL, p->next=head, head=p. 

 

4. The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, and 7 in the given order. What will be the contents of the list after the function completes execution?

struct node 
{
int value;
struct node *next;
};
void rearrange(struct node *list)
{
struct node *p, * q;
int temp;
if ((!list) || !list->next) 
return;
p = list;
q = list->next;
while(q) 
{
temp = p->value;
p->value = q->value;
q->value = temp;
p = q->next;
q = p?p->next:0;
}
}

A. 1, 2, 3, 4, 5, 6, 7
B. 2, 1, 4, 3, 6, 5, 7
C. 1, 3, 2, 5, 4, 7, 6
D. 2, 3, 4, 5, 6, 7, 1

Answer: b

The function rearranges () and exchanges every node’s data with its next node. It starts exchanging data from the first node itself. 

 

5. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is?

A. log2n
B. n⁄2
C. log2n – 1
D. n

Answer: D

In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is n.

In the worst case, the element to be searched has to be compared with all elements of the linked list. 

 

6. Given a pointer to a node X in a singly linked list. Only one pointer is given, and a pointer to the head node is not given, can we delete node X from the given linked list?

A. Possible if X is not the last node
B. Possible if the size of the linked list is even
C. Possible if the size of the linked list is odd
D. Possible if X is not the first node

Answer: a

Given a pointer to a node X in a singly linked list. Only one pointer is given, and if a pointer to the head node is not given then we can delete node X from the given linked list if X is not the last node.

The following are simple steps.

struct node *temp = X->next;
X->data = temp->data;
X->next = temp->next;
free(temp);

 

7. You are given pointers to the first and last nodes of a singly linked list, which of the following operations are dependent on the length of the linked list?

A. Delete the first element
B. Insert a new element as a first element
C. Delete the last element of the list
D. Add a new element at the end of the list

Answer: c

Deletion of the first element of the list is done in O (1) time by deleting memory and changing the first pointer.

Insertion of an element as a first element can be done in O (1) time. We will create a node that holds data and points to the head of the given linked list. The head pointer was changed to a newly created node.

Deletion of the last element requires a pointer to the previous node of last, which can only be obtained by traversing the list. This requires the length of the linked list.

Adding a new element at the end of the list can be done in O (1) by changing the pointer of the last node to the newly created node and the last is changed to a newly created node. 

 

8. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is?

A. log2 n
B. n⁄2
C. log2 n – 1
D. n

Answer: D

The worst case happens if the required element is at last or the element is absent in the list. For this, we need to compare every element in the linked list. If n elements are there, n comparisons will happen in the worst case. 

 

1. Which of the following is not a disadvantage to the usage of an 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

Array elements can be accessed in two steps. First, multiply the size of the data type by the specified position, second, add this value to the base address. Both of these operations can be done in constant time, hence accessing elements at a given index/position is faster. 

 

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

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

Answer: D

Depending on whether the array is full or not, the complexity of the 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 a full array, first you will have to allocate an array with double the size of the current array and then copy all the elements into it and finally insert the new element, this takes O(n) time. 

 

3. What is the time complexity to count the number of elements in the linked list?

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

Answer: b

To count the number of elements, you have to traverse through the entire list, hence complexity is O(n). 

 

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

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

Answer: a

You need a temp variable to keep track of the current node, hence the space complexity is O(1). 

 

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

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

Answer: D

To implement a file system, for separate chaining in hash tables, and to implement non-binary trees linked lists are used. Elements are accessed sequentially in the linked list. Random access to elements is not an application of a linked list. 

 

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

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

Answer: D

A doubly linked list has two pointers ‘left’ and ‘right’ which enable it to traverse in either direction. Compared to a singly liked list which has only a ‘next’ pointer, a 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 a doubly linked list involves setting both left and right pointers to correct nodes and takes more time than a singly linked list. 

 

3. What is a memory-efficient double-linked list?

A. Each node has only one pointer to traverse the list back and forth
B. The list has breakpoints for faster traversal
C. An auxiliary singly linked list acts as a helper list to traverse through the doubly linked list
D. A doubly linked list that uses a bitwise AND operator for storing addresses

Answer: a

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 a bitwise XOR operator to store the front and rear pointer addresses. Instead of storing the actual memory address, every node store the XOR address of the previous and next nodes. 

 

5. How do you calculate the pointer difference in a memory-efficient double-linked list?

A. head or 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 the previous node

Answer: b

The pointer difference is calculated by taking the XOR of the pointer to the previous node and the pointer to the next node. 

 

6. What is the worst-case time complexity of inserting a node in a doubly-linked list?

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

Answer: c

In the worst case, the position to be inserted may be at the end of the list, hence you have to traverse through the entire list to get to the correct position, hence O(n). 

 

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

The given sequence of operations performs the addition of nodes at the head and tail of the list. 

 

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

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. 

 

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

A new node is added to the head of the list and a node is deleted from the tail end of the list. 

 

1. What differentiates a circular linked list from a normal linked list?

A. You cannot have the ‘next’ pointer point to null in a circular linked list
B. It is faster to traverse the circular linked list
C. You may or may not have the ‘next’ pointer point to null in a circular linked list
D. Head node is known in a circular linked list

Answer: c

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

 

3. What is the functionality of the following piece of code? Select the most appropriate.

public void function(int datA.
{
int flag = 0;
if( head != null)
{
Node temp = head.getNext();
while((temp != heaD. && (!(temp.getItem() == datA.))
{
temp = temp.getNext();
flag = 1;
break;
}
}
if(flag)
System.out.println("success");
else
System.out.println("fail");
}

A. Print success if a particular element is not found
B. Print fails if a particular element is not found
C. Print success if a particular element is equal to 1
D. Print fail if the list is empty

Answer: b

The function prints fail if the given element is not found. Note that this option is inclusive of the option “Print fail if the list is empty”, the list being empty is one of the cases covered. 

 

4. What is the time complexity of searching for an element in a circular linked list?

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

Answer: a

The time complexity of searching for an element in a circular linked list is O(n).

In the worst case, you have to traverse through the entire list of n elements. 

 

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

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

Answer: c

Generally, the 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 use singly-linked lists. 

 

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

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

Answer: b

The time complexity of inserting a new node at the head of the list is O(n) because you have to traverse through the list to find the tail node. 

 

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

A. Keep one node as head and traverse another temp node till the end to check if its ‘next points to head
B. Have fast and slow pointers with the fast pointer advancing two nodes at a time and the 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

Advance the pointers in such a way that the fast pointer advances two nodes at a time and the 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 the slow pointer or if the fast pointer’s ‘next’ points to the slow pointer. This is applicable for smaller lists. 

 

1. Which of the following real-world scenarios would you associate with a stack data structure?

A. piling up of chairs one above the other
B. people standing in a line to be serviced at a counter
C. offer services based on the priority of the customer
D. tatkal Ticket Booking in IRCTC

Answer: a

Stack follows the Last In First Out (LIFO) policy. Piling up of chairs one above the other is based on LIFO, people standing in a line is a queue and if the service is based on priority, then it can be associated with a priority queue. Tatkal Ticket Booking Follows First in First Out Policy. People who click the book now first will enter the booking page first. 

 

3. What does ‘stack underflow’ refer to?

A. accessing item from an undefined stack
B. adding items to a full-stack
C. removing items from an empty stack
D. index out of bounds exception

Answer: c

An error condition occurs when an item is called for from the stack, but the stack is empty. Contrast with stack overflow. Removing items from an empty stack is termed stack underflow. 

 

5. What is the time complexity of pop() operation when the stack is implemented using an array?

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

Answer: a

The time complexity of pop() operation when the stack is implemented using an array is O(1).

pop() accesses only one end of the structure, and hence constant time. 

 

6. Which of the following array position will be occupied by a new element being pushed for a stack of size N elements(capacity of stack > N)?

A. S[N-1]
B. S[N]
C. S[1]
D. S[0]

Answer: b

S[N] array position will be occupied by a new element being pushed for a stack of size N elements. Elements are pushed at the end, hence N. 

 

7. What happens when you pop from an empty stack while implementing using the Stack ADT in Java?

A. Undefined error
B. Compiler displays a warning
C. EmptyStackException is thrown
D. NoStackException is thrown

Answer: c

The Stack ADT throws an EmptyStackException if the stack is empty and a pop() operation is tried on it. 

 

8. What is the functionality of the following piece of Java code?
Assume: ‘a’ is a non-empty array of integers, the Stack class creates an array of a specified size and provides a top pointer indicating TOS(top of stack), push, and pop have the normal meaning.

public void some_function(int[] A.
{
Stack S=new Stack(a.length);
int[] b=new int[a.length];
for(int i=0;i<a.length;i++)
{
S.push(a[i]);
}
for(int i=0;i<a.length;i++)
{
b[i]=(int)(S.pop());
}
System.out.println("output :");
for(int i=0;i<b.length;i++)
{
System.out.println(b[i]);
}
}

A. print alternate elements of the array
B. duplicate the given array
C. parentheses matching
D. reverse the array

Answer: D

Every element from the given array ‘a’ is pushed into the stack, and then the elements are popped out into the array ‘b’. Stack is a LIFO structure, this results in reversing the given array. 

 

9. Array implementation of Stack is not dynamic, which of the following statements supports this argument?

A. space allocation for the array is fixed and cannot be changed during run-time
B. user unable to give the input for stack operations
C. a runtime exception halts execution
D. improper program compilation

Answer: a

You cannot modify the size of an array once the memory has been allocated, adding fewer elements than the array size would cause wastage of space, and adding more elements than the array size at run time would cause Stack Overflow. 

 

10. Which of the following array element will return the top-of-the-stack-element for a stack of size N elements(capacity of stack > N)?

A. S[N-1]
B. S[N]
C. S[N-2]
D. S[N+1]

Answer: a

S[N] array element will return the top-of-the-stack-element for a stack of size N elements. Array indexing starts from 0, hence N-1 is the last index. 

 

1. What is the best case time complexity of deleting a node in a Singly Linked list?

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

Answer: D

Deletion of the head node in the linked list is taken as the best case. The successor of the head node is changed to head and deletes the predecessor of the newly assigned head node. This process completes in O(1) time. 

 

2. Which of the following statements are not correct with respect to the Singly Linked List(SLL) and Doubly Linked List(DLL)?

A. Complexity of Insertion and Deletion at known position is O(n) in SLL and O(1) in DLL
B. SLL uses lesser memory per node than DLL
C. DLL has more searching power than SLL
D. Number of node fields in SLL is more than in DLL

Answer: D

To insert and delete at known positions requires complete traversal of the list in the worst case in SLL, SLL consists of an item and a node field, while DLL has an item and two-node fields, hence SLL occupies lesser memory, DLL can be traversed both ways(left and right), while SLL can traverse in only one direction, hence more searching power of DLL. Node fields in SLL are 2 (data and address of next node) whereas in DLL is 3(data, address to next node, address to the previous node). 

 

6. What does ‘stack overflow’ refer to?

A. accessing item from an undefined stack
B. adding items to a full-stack
C. removing items from an empty stack
D. index out of bounds exception

Answer: b

A stack overflow is an undesirable condition in which a particular computer program tries to use more memory space than the call stack has available.  Stack overflow’ refers to adding items to a full-stack. 

 

8. Consider these functions:

push() : push an element into the stack
pop() : pop the top-of-the-stack element
top() : returns the item stored in top-of-the-stack-node
What will be the output after performing these sequence of operations

push(20);
push(4);
top();
pop();
pop();
pop();
push(5);
top();

A. 20
B. 4
C. stack underflow
D. 5

Answer: D

20 and 4 which were pushed are popped by the two pop() statements, the recent push() is 5, hence top() returns 5. 

 

9. Which of the following data structures can be used for parentheses matching?

A. n-ary tree
B. queue
C. priority queue
D. stack

Answer: D

For every opening brace, push it into the stack, and for every closing brace, pop it off the stack. Do not take action for any other character. In the end, if the stack is empty, then the input has balanced parentheses. 

 

10. Minimum number of queues to implement stack is ___________

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

Answer: c

Minimum number of queues to implement stack is 1. Use one queue and one counter to count the number of elements in the queue. 

 

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

Queue follows the First In First Out structure. The queue data structure follows the FIFO (First In First Out) principle, i.e. the element inserted at first in the list, is the first element to be removed from the list.

 

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

In a circular queue ensures the rear takes the values from (rear+1)% to (CAPACITY-1). 

 

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

Just as a stack, inserting into a full queue is termed overflow.  DeQueueing an empty queue is called underflow and EnQueuing an element in a full queue is called overflow.

 

4. What is the time complexity of enqueue operation?

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

Answer: D

Enqueue operation is at the rear end, it takes O(1) time to insert a new item into the queue. 

 

6. 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 the LIFO principle in queues

Answer: a

In a linear queue, the 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. A 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 the FIFO principle. 

 

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

The space complexity of an algorithm is the total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input. Because there are n elements the space complexity of a linear queue having n elements is O(n). 

 

1. In linked list implementation of queue, if the only front pointer is maintained, which of the following operation take the worst-case linear time?

A. Insertion
B. Deletion
C. To empty a queue
D. Both Insertion and To empty a queue

Answer: D

In linked list implementation of queue, if the only front pointer is maintained then both Insertion and To empty queue operation take the worst-case linear time.

Since the front pointer is used for deletion, so the worst time for the other two cases. 

 

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

A. At the head of the link list
B. At the center position in the link list
C. At the tail of the link list
D. At any position in the linked list

Answer: c

In the linked list implementation of a queue, a new element is inserted at the tail of the link list.

Since the queue follows FIFO so new element is inserted at last. 

 

3. In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into a NONEMPTY queue?

A. Only front pointer
B. Only rear pointer
C. Both front and rear pointer
D. No pointer will be changed

Answer: b

In linked list implementation of a queue, front and rear pointers are tracked then only the rear pointer will change during an insertion into a NONEMPTY queue.

Since the queue follows FIFO so new element is inserted at last. 

 

4. In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into the EMPTY queue?

A. Only front pointer
B. Only rear pointer
C. Both front and rear pointer
D. No pointer will be changed

Answer: c

In linked list implementation of a queue, front and rear pointers are tracked then both front and rear pointer will change during an insertion into the EMPTY queue.

Since it’s the start of the queue, so both values are changed. 

 

5. In case of insertion into a linked queue, a node borrowed from the __________ list is inserted in the queue.

A. AVAIL
B. FRONT
C. REAR
D. NULL

Answer: a

In case of insertion into a linked queue, a node borrowed from the AVAIL list is inserted in the queue. All the nodes are collected in the AVAIL list. 

 

6. In linked list implementation of a queue, from where is the item deleted?

A. At the head of the link list
B. At the center position in the link list
C. At the tail of the link list
D. Node before the tail

Answer: a

In the linked list implementation of a queue since the queue follows FIFO so new element was deleted from first. 

 

7. In linked list implementation of a queue, the important condition for a queue to be empty is?

A. FRONT is null
B. REAR is null
C. LINK is empty
D. FRONT==REAR-1

Answer: a

In linked list implementation of a queue, the important condition for a queue to be empty is FRONT is null because the front represents the deleted nodes. 

 

8. The essential condition which is checked before insertion in a linked queue is?

A. Underflow
B. Overflow
C. Front value
D. Rear value

Answer: b

The essential condition which is checked before insertion in a linked queue is overflow to check whether there is space in the queue or not. 

 

9. The essential condition which is checked before deletion in a linked queue is?

A. Underflow
B. Overflow
C. Front value
D. Rear value

Answer: a

The essential condition which is checked before deletion in a linked queue is underflow to check whether there is an element in the list or not. 

 

10. Which of the following is true about linked list implementation of the queue?

A. In a push operation, if new nodes are inserted at the beginning of the linked list, then in a pop operation, nodes must be removed from the end
B. In a push operation, if new nodes are inserted at the beginning, then in a pop operation, nodes must be removed from the beginning
C. In a push operation, if new nodes are inserted at the end, then in a pop operation, nodes must be removed from the end
D. In a push operation, if new nodes are inserted at the end, then in a pop operation, nodes must be removed from the beginning

Answer: a

In a linked queue, each node of the queue consists of two parts i.e. data part and the linked part. Each element of the queue points to its immediate next element in the memory. In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear pointer.

In a push operation, if new nodes are inserted at the beginning of the linked list, then in a pop operation, nodes must be removed from the end. 

 

1. With what data structure can a priority queue be implemented?

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

Answer: D

Priority queue can be implemented using an array, a list, a binary search tree, or a heap, although the most efficient one is the heap. 

 

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

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

Answer: c

Undo operation is achieved using a stack that is not an application of priority queue. 

 

4. What is the time complexity to insert a node based on a key in a priority queue?

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

Answer: c

The time complexity to insert a node based on a key in a priority queue is O(n). In the worst case, you might have to traverse the entire list. 

 

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

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

Answer: c

The lower priority process should wait until the CPU completes the processing higher priority process. Interrupt handling is an advantage as interrupts should be given more priority than tasks at hand so that interrupts can be serviced to produce desired results. 

 

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

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

Answer: D

In the worst case, the entire queue has to be searched for the element having the highest priority. This will take more time than usual. So deletion of elements is not an advantage. 

 

8. What is the time complexity to insert a node based on position in a priority queue?

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

Answer: c

The time complexity to insert a node based on position in a priority queue is O(n). In the worst case, you might have to traverse the entire list. 

 

1. What is a dequeue?

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

Answer: a

A dequeue or a double-ended queue is a queue with insert/delete defined for both front and rear ends of the queue. 

 

4. What are the applications of dequeue?

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

Answer: D

A dequeue or a double-ended queue is a queue with insert/delete defined for both front and rear ends of the queue.

The applications of dequeue are

  • A-Steal job scheduling algorithm
  • Can be used as both stack and queue
  • To find the maximum of all sub-arrays of size k
  • To avoid collision in hash tables

 

1. A Double-ended queue supports operations such as adding and removing items from both sides of the queue. They support four operations like addFront(adding item to the top of the queue), addRear(adding item to the bottom of the queue), remove front(removing the item from the top of the queue), and removeRear(removing the item from the bottom of the queue). You are given only stacks to implement this data structure. You can implement only push and pop operations. What is the total number of stacks required for this operation? (you can reuse the stack)

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

Answer: b

The addFront and removeFront operations can be performed using one stack itself as push and pop are supported (adding and removing elements from the top of the stack) but to perform addRear and removeRear you need to pop each element from the current stack and push it into another stack, push or pop the element as per the asked operation from this stack and in the end pop elements from this stack to the first stack. 

 

2. You are asked to perform a queue operation using a stack. Assume the size of the stack is some value ‘n’ and there are ‘m’ number of variables in this stack. The time complexity of performing the deQueue operation is (Using only stack operations like push and pop)(Tightly bound).

A. O(m)
B. O(n)
C. O(m*n)
D. Data is insufficient

Answer: a

To perform the deQueue operation you need to pop each element from the first stack and push it into the second stack. In this case, you need to pop ‘m’ times and need to perform push operations also ‘m’ times. Then you pop the first element from this second stack (constant time) and pass all the elements to the first stack (as done in the beginning)(‘m-1’ times). Therefore the time complexity is O(m). 

 

3. Consider you have an array of some random size. You need to perform a dequeue operation. You can perform it using stack operation (push and pop) or using queue operations themselves (enQueue and Dequeue). The output is guaranteed to be the same. Find some differences?

A. They will have different time complexities
B. The memory used will not be different
C. There are chances that output might be different
D. No differences

Answer: a

To perform operations such as Dequeue using stack operation you need to empty all the elements from the current stack and push them into the next stack, resulting in an O(number of elements) complexity whereas the time complexity of the dequeue operation itself is O(1). And there is a need for an extra stack. Therefore more memory is needed. 

 

4. Consider you have a stack whose elements in it are as follows.
5 4 3 2 << top
Where the top element is 2.
You need to get the following stack
6 5 4 3 2 << top
The operations that needed to be performed are (You can perform only push and pop):

A. Push(pop()), push(6), push(pop())
B. Push(pop()), push(6)
C. Push(pop()), push(pop()), push(6)
D. Push(6)

Answer: a

By performing push(pop()) on all elements on the current stack to the next stack you get 2 3 4 5 << top.Push(6) and perform push(pop()) you’ll get back 6 5 4 3 2 << top. You have actually performed enQueue operation using push and pop. 

 

5. A double-ended queue supports operations like adding and removing items from both sides of the queue. They support four operations like addFront(adding item to the top of the queue), addRear(adding item to the bottom of the queue), removeFront(removing item from the top of the queue), and removeRear(removing the item from the bottom of the queue). You are given only stacks to implement this data structure. You can implement only push and pop operations. What’s the time complexity of performing addFront and addRear? (Assume ‘m’ to be the size of the stack and ‘n’ to be the number of elements)

A. O(m) and O(n)
B. O(1) and O(n)
C. O(n) and O(1)
D. O(n) and O(m)

Answer: b

addFront is just a normal push operation. Push operation is of O(1). Whereas addRear is of O(n) as it requires two push(pop()) operations of all elements of a stack. 

 

6. Why is the implementation of stack operations on queues not feasible for a large dataset (Assume the number of elements in the stack to be n)?

A. Because of its time complexity O(n)
B. Because of its time complexity O(log(n))
C. Extra memory is not required
D. There are no problems

Answer: a

To perform Queue operations such as enQueue and deQueue there is a need of emptying all the elements of a current stack and pushing elements into the next stack and vice versa. Therefore it has a time complexity of O(n) and the need for an extra stack as well, which may not be feasible for a large dataset. 

h({});

 

7. Consider yourself to be on a planet where the computational power of chips is slow. You have an array of sizes 10. You want to perform enqueue some elements into this array. But you can perform only push and pop operations. Push and pop operation both take 1 sec respectively. The total time required to perform enQueue operation is?

A. 20
B. 40
C. 42
D. 43

Answer: D

First, you have to empty all the elements of the current stack into the temporary stack, push the required element and empty the elements of the temporary stack into the original stack. Therefore taking 10+10+1+11+11= 43 seconds. 

 

8. You have two jars, one jar which has 10 rings and the other has none. They are placed one above the other. You want to remove the last ring in the jar. And the second jar is weak and cannot be used to store rings for a long time.

A. Empty the first jar by removing it one by one from the first jar and placing it into the second jar
B. Empty the first jar by removing it one by one from the first jar and placing it into the second jar and empty the second jar by placing all the rings into the first jar one by one
C. There exists no possible way to do this
D. Break the jar and remove the last one

Answer: b

This is similar to performing a dequeue operation using push and pop only. Elements in the first jar are taken out and placed in the second jar. After removing the last element from the first jar, remove all the elements in the second jar and place them in the first jar. 

 

9. Given only a single array of size 10 and no other memory is available. Which of the following operation is not feasible to implement (Given only push and pop operation)?

A. Push
B. Pop
C. Enqueue
D. Returntop

Answer: c

To perform Enqueue using just push and pop operations, there is a need for another array of the same size. But as there is no extra available memory, the given operation is not feasible. 

 

10. Given an array of size n, let’s assume an element is ‘touched’ if and only if some operation is performed on it(for example, for performing a pop operation the top element is ‘touched’). Now you need to perform a Dequeue operation. Each element in the array is touched at least?

A. Once
B. Twice
C. Thrice
D. Four times

Answer: D

First, each element from the first stack is popped, then pushed into the second stack, the dequeue operation is done on the top of the stack and later each element of the second stack is popped and then pushed into the first stack. Therefore each element is touched four times.

 

1. To implement a stack using queue(with only enqueue and dequeue operations), how many queues will you need?

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

Answer: b

To implement a stack using a queue, 2 queues is needed. Either the push or the pop has to be a costly operation, and the costlier operation requires two queues.

Scroll to Top