Data Structure MCQ
Data Structure Questions and Answers – Array and Array Operations
Next »
This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Array and Array Operations”.
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 initialised
d) Array is not a data structure
View Answer
Answer: b
Explanation: Array contains elements only of the same type.
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);
View Answer
Answer: c
Explanation: This is the syntax to initialize an array in C.
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);
View Answer
Answer: c
Explanation: Note that int arr[]; is declaration whereas int arr[] = new int[3]; is to instantiate an array.
Subscribe Now: Data Structure Newsletter | Important Subjects Newsletters
advertisement
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;
View Answer
Answer: c
Explanation: 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?
Participate in Data Structure I Certification Contest of the Month Now!
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
View Answer
Answer: a
Explanation: 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
View Answer
Answer: c
Explanation: 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
View Answer
Answer: b
Explanation: 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
View Answer
Answer: d
Explanation: Whenever a particular memory location is referred to, it is likely that the locations nearby are also referred, arrays are stored as contiguous blocks in memory, so if you want to access array elements, spatial locality makes it to access quickly.
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 first element of an array is 1
d) Easier to store elements of same data type
View Answer
Answer: d
Explanation: Arrays store elements of the same data type and present in continuous memory locations.
10. What are the disadvantages of arrays?
a) Data structure like queue or stack cannot be implemented
b) There are chances of wastage of memory space if elements inserted in an array are lesser than the allocated size
c) Index value of an array can be negative
d) Elements are sequentially accessed
View Answer
Answer: b
Explanation: Arrays are of fixed size. If we insert elements less than the allocated size, unoccupied positions can’t be used again. Wastage will occur in memory.
11. Assuming int is of 4bytes, what is the size of int arr[15];?
a) 15
b) 19
c) 11
d) 60
View Answer
Answer: d
Explanation: 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
View Answer
Answer: a
Explanation: 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
View Answer
Answer: a
Explanation: Elements in an array are accessed randomly. In Linked lists, elements are accessed sequentially.
This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Stack Operations – 1”.
1. Process of inserting an element in stack is called ____________
a) Create
b) Push
c) Evaluation
d) Pop
View Answer
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
View Answer
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
View Answer
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.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
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
View Answer
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
View Answer
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).
Check this: Computer Science MCQs | Computer Science Books
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
View Answer
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
View Answer
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
View Answer
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
View Answer
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
View Answer
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.
This set of Data Structure Interview Questions and Answers focuses on “Stack Operations – 2”.
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 /
View Answer
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/
2. The data structure required to check whether an expression contains a balanced parenthesis is?
a) Stack
b) Queue
c) Array
d) Tree
View Answer
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.
3. 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
View Answer
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.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
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
View Answer
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.
5. The postfix form of A*B+C/D is?
a) *AB/CD+
b) AB*CD/+
c) A*BC+/D
d) ABCD+/*
View Answer
Answer: b
Explanation: Infix expression is (A*B)+(C/D)
AB*+(C/D)
AB*CD/+. Thus postfix expression is AB*CD/+.
Check this: Computer Science Books | Programming MCQs
6. Which data structure is needed to convert infix notation to postfix notation?
a) Branch
b) Tree
c) Queue
d) Stack
View Answer
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.
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
View Answer
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.
8. What is the result of the following operation?
Top (Push (S, X))
a) X
b) X+S
c) S
d) XS
View Answer
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.
9. The prefix form of an infix expression (p + q) – (r * t) is?
a) + pq – *rt
b) – +pqr * t
c) – +pq * rt
d) – + * pqrt
View Answer
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.
10. Which data structure is used for implementing recursion?
a) Queue
b) Stack
c) Array
d) List
View Answer
Answer: b
Explanation: Stacks are used for the implementation of Recursion.
This set of Data Structure Questions and Answers for Freshers focuses on “Stack Operations – 3”.
1. The result of evaluating the postfix expression 5, 4, 6, +, *, 4, 9, 3, /, +, * is?
a) 600
b) 350
c) 650
d) 588
View Answer
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.
2. 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 +)
View Answer
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 +.
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*+
View Answer
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 * +.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
4. 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
View Answer
Answer: c
Explanation: 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);
Check this: Programming MCQs | Computer Science Books
After the completion of all operation, the number of elements present in stack is?
a) 1
b) 2
c) 3
d) 4
View Answer
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.
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
View Answer
Answer: d
Explanation: Job Scheduling is not performed using stacks.
7. 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
View Answer
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.
8. 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
View Answer
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 ^ -).
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
View Answer
Answer: b
Explanation: Stack follows LIFO(Last In First Out). So the removal order of elements are DCBA.
This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Queue Operations”.
1. A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is known as _____________
a) Queue
b) Stack
c) Tree
d) Linked list
View Answer
Answer: a
Explanation: Linear list of elements in which deletion is done at front side and insertion at rear side is called Queue. In stack we will delete the last entered element first.
2. The data structure required for Breadth First Traversal on a graph is?
a) Stack
b) Array
c) Queue
d) Tree
View Answer
Answer: c
Explanation: In Breadth First Search Traversal, BFS, starting vertex is first taken and adjacent vertices which are unvisited are also taken. Again, the first vertex which was added as an unvisited adjacent vertex list will be considered to add further unvisited vertices of the graph. To get the first unvisited vertex we need to follows First In First Out principle. Queue uses FIFO principle.
3. A queue follows __________
a) FIFO (First In First Out) principle
b) LIFO (Last In First Out) principle
c) Ordered array
d) Linear tree
View Answer
Answer: a
Explanation: Element first added in queue will be deleted first which is FIFO principle.
Subscribe Now: Data Structure Newsletter | Important Subjects Newsletters
advertisement
4. Circular Queue is also known as ________
a) Ring Buffer
b) Square Buffer
c) Rectangle Buffer
d) Curve Buffer
View Answer
Answer: a
Explanation: Circular Queue is also called as Ring Buffer. Circular Queue is a linear data structure in which last position is connected back to the first position to make a circle. It forms a ring structure.
5. If the elements “A”, “B”, “C” and “D” are placed in a queue and are deleted one at a time, in what order will they be removed?
a) ABCD
b) DCBA
c) DCAB
d) ABDC
View Answer
Answer: a
Explanation: Queue follows FIFO approach. i.e. First in First Out Approach. So, the order of removal elements are ABCD.
Get Free Certificate of Merit in Data Structure I Now!
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
View Answer
Answer: c
Explanation: In dequeuer, we can insert or delete elements from both the ends. In queue, we will follow first in first out principle for insertion and deletion of elements. Element with least priority will be deleted in a priority queue.
7. A normal queue, if implemented using an array of size MAX_SIZE, gets full when?
a) Rear = MAX_SIZE – 1
b) Front = (rear + 1)mod MAX_SIZE
c) Front = rear + 1
d) Rear = front
View Answer
Answer: a
Explanation: When Rear = MAX_SIZE – 1, there will be no space left for the elements to be added in queue. Thus queue becomes full.
8. Queues serve major role in ______________
a) Simulation of recursion
b) Simulation of arbitrary linked list
c) Simulation of limited resource allocation
d) Simulation of heap sort
View Answer
Answer: c
Explanation: Simulation of recursion uses stack data structure. Simulation of arbitrary linked lists uses linked lists. Simulation of resource allocation uses queue as first entered data needs to be given first priority during resource allocation. Simulation of heap sort uses heap data structure.
9. Which of the following is not the type of queue?
a) Ordinary queue
b) Single ended queue
c) Circular queue
d) Priority queue
View Answer
Answer: b
Explanation: Queue always has two ends. So, single ended queue is not the type of queue.
This set of Data Structure Interview Questions & Answers focuses on “Singly Linked List Operations – 1”.
1. A linear collection of data elements where the linear node is given by means of pointer is called?
a) Linked list
b) Node list
c) Primitive list
d) Unordered list
View Answer
Answer: a
Explanation: In Linked list each node has its own data and the address of next node. These nodes are linked by using pointers. Node list is an object that consists of a list of all nodes in a document with in a particular selected set of nodes.
2. Consider an implementation of unsorted singly linked list. Suppose it has its representation with a head pointer only. Given the representation, which of the following operation can be implemented in O(1) time?
i) Insertion at the front of the linked list
ii) Insertion at the end of the linked list
iii) Deletion of the front node of the linked list
iv) Deletion of the last node of the linked list
a) I and II
b) I and III
c) I, II and III
d) I, II and IV
View Answer
Answer: b
Explanation: We know the head node in the given linked list. Insertion and deletion of elements at the front of the linked list completes in O (1) time whereas for insertion and deletion at the last node requires to traverse through every node in the linked list. Suppose there are n elements in a linked list, we need to traverse through each node. Hence time complexity becomes O(n).
Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
3. In linked list each node contains a minimum of two fields. One field is data field to store the data second field is?
a) Pointer to character
b) Pointer to integer
c) Pointer to node
d) Node
View Answer
Answer: c
Explanation: Each node in a linked list contains data and a pointer (reference) to the next node. Second field contains pointer to node.
Take Data Structure I Tests Now!
4. What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list?
a) O(1)
b) O(n)
c) θ(n)
d) θ(1)
View Answer
Answer: c
Explanation: In case of a linked list having n elements, we need to travel through every node of the list to add the element at the end of the list. Thus asymptotic time complexity is θ(n).
5. What would be the asymptotic time complexity to insert an element at the front of the linked list (head is known)?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)
View Answer
Answer: a
Explanation: To add an element at the front of the linked list, we will create a new node which holds the data to be added to the linked list and pointer which points to head position in the linked list. The entire thing happens within O (1) time. Thus the asymptotic time complexity is O (1).
6. What would be the asymptotic time complexity to find an element in the linked list?
a) O(1)
b) O(n)
c) O(n2)
d) O(n4)
View Answer
Answer: b
Explanation: If the required element is in the last position, we need to traverse the entire linked list. This will take O (n) time to search the element.
7. What would be the asymptotic time complexity to insert an element at the second position in the linked list?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)
View Answer
Answer: a
Explanation: A new node is created with the required element. The pointer of the new node points the node to which the head node of the linked list is also pointing. The head node pointer is changed and it points to the new node which we created earlier. The entire process completes in O (1) time. Thus the asymptotic time complexity to insert an element in the second position of the linked list is O (1).
8. The concatenation of two lists can be performed in O(1) time. Which of the following variation of the linked list can be used?
a) Singly linked list
b) Doubly linked list
c) Circular doubly linked list
d) Array implementation of list
View Answer
Answer: c
Explanation: We can easily concatenate two lists in O (1) time using singly or doubly linked list, provided that we have a pointer to the last node at least one of the lists. But in case of circular doubly linked lists, we will break the link in both the lists and hook them together. Thus circular doubly linked list concatenates two lists in O (1) time.
9. Consider the following definition in c programming language.
struct node
{
int data;
struct node * next;
}
typedef struct node NODE;
NODE *ptr;
Which of the following c code is used to create new node?
a) ptr = (NODE*)malloc(sizeof(NODE));
b) ptr = (NODE*)malloc(NODE);
c) ptr = (NODE*)malloc(sizeof(NODE*));
d) ptr = (NODE)malloc(sizeof(NODE));
View Answer
Answer: a
Explanation: As it represents the right way to create a node.
This set of Data Structure Interview Questions and Answers for freshers focuses on “Singly Linked Lists Operations – 2”.
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
View Answer
Answer: d
Explanation: Arrays provide random access to elements by providing the index value within square brackets. In the linked list, we need to traverse through each element until we reach the nth position. Time taken to access an element represented in arrays is less than the singly, doubly and circular linked lists. Thus, array implementation is used to access the item at the position n.
2. Linked lists are not suitable for the implementation of ___________
a) Insertion sort
b) Radix sort
c) Polynomial manipulation
d) Binary search
View Answer
Answer: d
Explanation: It cannot be implemented using linked lists.
3. Linked list is considered as an example of ___________ type of memory allocation.
a) Dynamic
b) Static
c) Compile time
d) Heap
View Answer
Answer: a
Explanation: As memory is allocated at the run time.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
4. In Linked List implementation, a node carries information regarding ___________
a) Data
b) Link
c) Data and Link
d) Node
View Answer
Answer: c
Explanation: A linked list is a collection of objects linked together by references from an object to another object. By convention these objects are names as nodes. Linked list consists of nodes where each node contains one or more data fields and a reference(link) to the next node.
5. Linked list data structure offers considerable saving in _____________
a) Computational Time
b) Space Utilization
c) Space Utilization and Computational Time
d) Speed Utilization
View Answer
Answer: c
Explanation: Linked lists saves both space and time.
Check this: Data Structure Books | Computer Science Books
6. Which of the following points is/are not true about Linked List data structure when it is compared with an array?
a) Arrays have better cache locality that can make them better in terms of performance
b) It is easy to insert and delete elements in Linked List
c) Random access is not allowed in a typical implementation of Linked Lists
d) Access of elements in linked list takes less time than compared to arrays
View Answer
Answer: d
Explanation: To access an element in a linked list, we need to traverse every element until we reach the desired element. This will take more time than arrays as arrays provide random access to its elements.
7. What does the following function do for a given Linked List with first node as head?
void fun1(struct node* head)
{
if(head == NULL)
return;
fun1(head->next);
printf("%d ", head->data);
}
a) Prints all nodes of linked lists
b) Prints all nodes of linked list in reverse order
c) Prints alternate nodes of Linked List
d) Prints alternate nodes in reverse order
View Answer
Answer: b
Explanation: fun1() prints the given Linked List in reverse manner.
For Linked List 1->2->3->4->5, fun1() prints 5->4->3->2->1.
8. Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?
a) Insertion Sort
b) Quick Sort
c) Heap Sort
d) Merge Sort
View Answer
Answer: d
Explanation: Both Merge sort and Insertion sort can be used for linked lists. The slow random-access performance of a linked list makes other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible. Since worst case time complexity of Merge Sort is O(nLogn) and Insertion sort is O(n2), merge sort is preferred.
This set of Data Structure Questions and Answers for Experienced people focuses on “Singly Linked Lists Operations – 3”.
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;
View Answer
Answer: a
Explanation: *head_ref = prev; At the end of while loop, the prev pointer points to the last node of original linked list.
We need to change *head_ref so that the head pointer now starts pointing to the last node.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
2. What is the output of following function for start pointing to first node of 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
View Answer
Answer: d
Explanation: fun() prints alternate nodes of the given Linked List, first from head to end, and then from end to head.
If Linked List has even number of nodes, then skips the last node.
Check this: Computer Science MCQs | Data Structure Books
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;
View Answer
Answer: d
Explanation: 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 as 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, 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
View Answer
Answer: b
Explanation: The function rearrange() exchanges data of every node 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) log 2 n
b) n⁄2
c) log 2 n – 1
d) n
View Answer
Answer: d
Explanation: In the worst case, the element to be searched has to be compared with all elements of the linked list.
6. Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not given, can we delete the node X from given linked list?
a) Possible if X is not last node
b) Possible if size of linked list is even
c) Possible if size of linked list is odd
d) Possible if X is not first node
View Answer
Answer: a
Explanation: Following are simple steps.
struct node *temp = X->next;
X->data = temp->data;
X->next = temp->next;
free(temp);
7. You are given pointers to first and last nodes of a singly linked list, which of the following operations are dependent on the length of the linked list?
a) Delete the first element
b) Insert a new element as a first element
c) Delete the last element of the list
d) Add a new element at the end of the list
View Answer
Answer: c
Explanation: Deletion of the first element of the list is done in O (1) time by deleting memory and changing the first pointer.
Insertion of an element as a first element can be done in O (1) time. We will create a node that holds data and points to the head of the given linked list. The head pointer was changed to a newly created node.
Deletion of the last element requires a pointer to the previous node of last, which can only be obtained by traversing the list. This requires the length of the linked list.
Adding a new element at the end of the list can be done in O (1) by changing the pointer of the last node to the newly created node and last is changed to a newly created node.
8. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is?
a) log2 n
b) n⁄2
c) log2 n – 1
d) n
View Answer
Answer: d
Explanation: The worst-case happens if the required element is at last or the element is absent in the list. For this, we need to compare every element in the linked list. If n elements are there, n comparisons will happen in the worst case.
This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Singly Linked List”.
1. Which of the following is not a disadvantage to the usage of array?
a) Fixed size
b) There are chances of wastage of memory space if elements inserted in an array are lesser than the allocated size
c) Insertion based on position
d) Accessing elements at specified positions
View Answer
Answer: d
Explanation: Array elements can be accessed in two steps. First, multiply the size of the data type with the specified position, second, add this value to the base address. Both of these operations can be done in constant time, hence accessing elements at a given index/position is faster.
2. What is the time complexity of inserting at the end in dynamic arrays?
a) O(1)
b) O(n)
c) O(logn)
d) Either O(1) or O(n)
View Answer
Answer: d
Explanation: Depending on whether the array is full or not, the complexity in dynamic array varies. If you try to insert into an array that is not full, then the element is simply stored at the end, this takes O(1) time. If you try to insert into an array which is full, first you will have to allocate an array with double the size of the current array and then copy all the elements into it and finally insert the new element, this takes O(n) time.
3. What is the time complexity to count the number of elements in the linked list?
a) O(1)
b) O(n)
c) O(logn)
d) O(n2)
View Answer
Answer: b
Explanation: To count the number of elements, you have to traverse through the entire list, hence complexity is O(n).
Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
4. 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)
Take Data Structure I Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
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;
}
View Answer
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.
5. 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
View Answer
Answer: c
Explanation: The for loop traverses through the list and then inserts a new node as cur.setNext(node);
6. What is the space complexity for deleting a linked list?
a) O(1)
b) O(n)
c) Either O(1) or O(n)
d) O(logn)
View Answer
Answer: a
Explanation: You need a temp variable to keep track of current node, hence the space complexity is O(1).
7. 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--;
}
View Answer
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.
8. Which of these is not an application of a linked list?
a) To implement file systems
b) For separate chaining in hash-tables
c) To implement non-binary trees
d) Random Access of elements
View Answer
Answer: d
Explanation: To implement file system, for separate chaining in hash-tables and to implement non-binary trees linked lists are used. Elements are accessed sequentially in linked list. Random access of elements is not an applications of linked list.
9. 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;
}
View Answer
Answer: a
Explanation: ‘cur’ pointer traverses through list and increments the size variable until the end of list is reached.
10. 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++;
}
View Answer
Answer: a
Explanation: Set the ‘next’ pointer point to the head of the list and then make this new node as the head.
11. 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
View Answer
Answer: c
Explanation: When temp is equal to data, the position of data is returned.
This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Doubly Linked List”.
1. Which of the following is false about a doubly linked list?
a) We can navigate in both the directions
b) It requires more space than a singly linked list
c) The insertion and deletion of a node take a bit longer
d) Implementing a doubly linked list is easier than singly linked list
View Answer
Answer: d
Explanation: A doubly linked list has two pointers ‘left’ and ‘right’ which enable it to traverse in either direction. Compared to singly liked list which has only a ‘next’ pointer, doubly linked list requires extra space to store this extra pointer. Every insertion and deletion requires manipulation of two pointers, hence it takes a bit longer time. Implementing doubly linked list involves setting both left and right pointers to correct nodes and takes more time than singly linked list.
2. 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)
Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
public void insertRear(int data)
{
Node node = new Node(data,tail.getPrev(),tail);
node.getPrev().setNext(node);
tail.setPrev(node);
length++;
}
b)
Take Data Structure I Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
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++;
}
View Answer
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.
3. What is a memory efficient double linked list?
a) Each node has only one pointer to traverse the list back and forth
b) The list has breakpoints for faster traversal
c) An auxiliary singly linked list acts as a helper list to traverse through the doubly linked list
d) A doubly linked list that uses bitwise AND operator for storing addresses
View Answer
Answer: a
Explanation: Memory efficient doubly linked list has only one pointer to traverse the list back and forth. The implementation is based on pointer difference. It uses bitwise XOR operator to store the front and rear pointer addresses. Instead of storing actual memory address, every node store the XOR address of previous and next nodes.
4. 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--;
}
View Answer
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.
5. How do you calculate the pointer difference in a memory efficient double linked list?
a) head xor tail
b) pointer to previous node xor pointer to next node
c) pointer to previous node – pointer to next node
d) pointer to next node – pointer to previous node
View Answer
Answer: b
Explanation: The pointer difference is calculated by taking XOR of pointer to previous node and pointer to the next node.
6. What is the worst case time complexity of inserting a node in a doubly linked list?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)
View Answer
Answer: c
Explanation: In the worst case, the position to be inserted maybe at the end of the list, hence you have to traverse through the entire list to get to the correct position, hence O(n).
7. 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++;
}
View Answer
Answer: a
Explanation: The new node’s previous pointer will point to head and next pointer will point to the current next of head.
8. 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
View Answer
Answer: c
Explanation: The given sequence of operations performs 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
View Answer
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.
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
View Answer
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.
This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Circular Linked 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 circular linked list
View Answer
Answer: c
Explanation: The ‘next’ pointer points to null only when the list is empty, otherwise it points to the head of the list. Every node in a circular linked list can be a starting point(head).
2. How do you count the number of elements in the circular linked list?
a)
public int length(Node head)
{
int length = 0;
if( head == null)
return 0;
Node temp = head.getNext();
while(temp != head)
{
temp = temp.getNext();
length++;
}
return length;
}
b)
Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
public int length(Node head)
{
int length = 0;
if( head == null)
return 0;
Node temp = head.getNext();
while(temp != null)
{
temp = temp.getNext();
length++;
}
return length;
}
c)
Take Data Structure I Tests Now!
public int length(Node head)
{
int length = 0;
if( head == null)
return 0;
Node temp = head.getNext();
while(temp != head && temp != null)
{
temp = head.getNext();
length++;
}
return length;
}
d)
public int length(Node head)
{
int length = 0;
if( head == null)
return 0;
Node temp = head.getNext();
while(temp != head && temp == null)
{
temp = head.getNext();
length++;
}
return length;
}
View Answer
Answer: a
Explanation: If the head is null, it means that the list is empty. Otherwise, traverse the list until the head of the list is reached.
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 fail 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
View Answer
Answer: b
Explanation: The function prints fail if the given element is not found. Note that this option is inclusive of 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)
View Answer
Answer: a
Explanation: In the worst case, you have to traverse through the entire list of n elements.
5. Which of the following application makes use of a circular linked list?
a) Undo operation in a text editor
b) Recursive function calls
c) Allocating CPU to resources
d) Implement Hash Tables
View Answer
Answer: c
Explanation: Generally, round robin fashion is employed to allocate CPU time to resources which makes use of the circular linked list data structure. Recursive function calls use stack data structure. Undo Operation in text editor uses doubly linked lists. Hash tables uses singly linked lists.
6. Choose the code snippet which inserts a node to the head of the list?
a)
public void insertHead(int data)
{
Node temp = new Node(data);
Node cur = head;
while(cur.getNext() != head)
cur = cur.getNext()
if(head == null)
{
head = temp;
head.setNext(head);
}
else
{
temp.setNext(head);
head = temp;
cur.setNext(temp);
}
size++;
}
b)
public void insertHead(int data)
{
Node temp = new Node(data);
while(cur != head)
cur = cur.getNext()
if(head == null)
{
head = temp;
head.setNext(head);
}
else
{
temp.setNext(head.getNext());
cur.setNext(temp);
}
size++;
}
c)
public void insertHead(int data)
{
Node temp = new Node(data);
if(head == null)
{
head = temp;
head.setNext(head);
}
else
{
temp.setNext(head.getNext());
head = temp;
}
size++;
}
d)
public void insertHead(int data)
{
Node temp = new Node(data);
if(head == null)
{
head = temp;
head.setNext(head.getNext());
}
else
{
temp.setNext(head.getNext());
head = temp;
}
size++;
}
View Answer
Answer: a
Explanation: If the list is empty make the new node as ‘head’, otherwise traverse the list to the end and make its ‘next’ pointer point to the new node, set the new node’s next point to the current head and make the new node as the head.
7. What is the functionality of the following code? Choose the most appropriate answer.
public int function()
{
if(head == null)
return Integer.MIN_VALUE;
int var;
Node temp = head;
while(temp.getNext() != head)
temp = temp.getNext();
if(temp == head)
{
var = head.getItem();
head = null;
return var;
}
temp.setNext(head.getNext());
var = head.getItem();
head = head.getNext();
return var;
}
a) Return data from the end of the list
b) Returns the data and deletes the node at the end of the list
c) Returns the data from the beginning of the list
d) Returns the data and deletes the node from the beginning of the list
View Answer
Answer: d
Explanation: First traverse through the list to find the end node, then manipulate the ‘next’ pointer such that it points to the current head’s next node, return the data stored in head and make this next node as the head.
8. What is the functionality of the following code? Choose the most appropriate answer.
public int function()
{
if(head == null)
return Integer.MIN_VALUE;
int var;
Node temp = head;
Node cur;
while(temp.getNext() != head)
{
cur = temp;
temp = temp.getNext();
}
if(temp == head)
{
var = head.getItem();
head = null;
return var;
}
var = temp.getItem();
cur.setNext(head);
return var;
}
a) Return data from the end of the list
b) Returns the data and deletes the node at the end of the list
c) Returns the data from the beginning of the list
d) Returns the data and deletes the node from the beginning of the list
View Answer
Answer: b
Explanation: First traverse through the list to find the end node, also have a trailing pointer to find the penultimate node, make this trailing pointer’s ‘next’ point to the head and return the data stored in the ‘temp’ node.
9. Which of the following is false about a circular linked list?
a) Every node has a successor
b) Time complexity of inserting a new node at the head of the list is O(1)
c) Time complexity for deleting the last node is O(n)
d) We can traverse the whole circular linked list by starting from any point
View Answer
Answer: b
Explanation: Time complexity of inserting a new node at the head of the list is O(n) because you have to traverse through the list to find the tail node.
10. Consider a small circular linked list. How to detect the presence of cycles in this list effectively?
a) Keep one node as head and traverse another temp node till the end to check if its ‘next points to head
b) Have fast and slow pointers with the fast pointer advancing two nodes at a time and slow pointer advancing by one node at a time
c) Cannot determine, you have to pre-define if the list contains cycles
d) Circular linked list itself represents a cycle. So no new cycles cannot be generated
View Answer
Answer: b
Explanation: Advance the pointers in such a way that the fast pointer advances two nodes at a time and slow pointer advances one node at a time and check to see if at any given instant of time if the fast pointer points to slow pointer or if the fast pointer’s ‘next’ points to the slow pointer. This is applicable for smaller lists.
This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Stack using Array”.
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
View Answer
Answer: a
Explanation: Stack follows 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.
2. What does the following function check for? (all necessary headers to be included and function is called from main)
#define MAX 10
typedef struct stack
{
int top;
int item[MAX];
}stack;
int function(stack *s)
{
if(s->top == -1)
return 1;
else return 0;
}
a) full stack
b) invalid index
c) empty stack
d) infinite stack
View Answer
Answer: c
Explanation: An empty stack is represented with the top-of-the-stack(‘top’ in this case) to be equal to -1.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
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
View Answer
Answer: c
Explanation: Removing items from an empty stack is termed as stack underflow.
Check this: Programming MCQs | Data Structure Books
4. What is the output of the following program?
public class Stack
{
protected static final int CAPACITY = 100;
protected int size,top = -1;
protected Object stk[];
public Stack()
{
stk = new Object[CAPACITY];
}
public void push(Object item)
{
if(size_of_stack==size)
{
System.out.println("Stack overflow");
return;
}
else
{
top++;
stk[top]=item;
}
}
public Object pop()
{
if(top<0)
{
return -999;
}
else
{
Object ele=stk[top];
top--;
size_of_stack--;
return ele;
}
}
}
public class StackDemo
{
public static void main(String args[])
{
Stack myStack = new Stack();
myStack.push(10);
Object element1 = myStack.pop();
Object element2 = myStack.pop();
System.out.println(element2);
}
}
a) stack is full
b) 20
c) 0
d) -999
View Answer
Answer: d
Explanation: The first call to pop() returns 10, whereas the second call to pop() would result in stack underflow and the program returns -999.
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)
View Answer
Answer: a
Explanation: 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]
View Answer
Answer: b
Explanation: 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
View Answer
Answer: c
Explanation: 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 specified size and provides a top pointer indicating TOS(top of stack), push and pop have 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 array
b) duplicate the given array
c) parentheses matching
d) reverse the array
View Answer
Answer: d
Explanation: 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 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
View Answer
Answer: a
Explanation: 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]
View Answer
Answer: a
Explanation: Array indexing start from 0, hence N-1 is the last index.
This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Queue using Linked List”.
1. In linked list implementation of queue, if only front pointer is maintained, which of the following operation take worst case linear time?
a) Insertion
b) Deletion
c) To empty a queue
d) Both Insertion and To empty a queue
View Answer
Answer: d
Explanation: Since front pointer is used for deletion, so worst time for the other two cases.
2. In linked list implementation of a queue, where does a new element be inserted?
a) At the head of link list
b) At the centre position in the link list
c) At the tail of the link list
d) At any position in the linked list
View Answer
Answer: c
Explanation: Since queue follows FIFO so new element inserted at last.
3. In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into a NONEMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) No pointer will be changed
View Answer
Answer: b
Explanation: Since queue follows FIFO so new element inserted at last.
Subscribe Now: Data Structure Newsletter | Important Subjects Newsletters
advertisement
4. In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into EMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) No pointer will be changed
View Answer
Answer: c
Explanation: Since its the starting of queue, so both values are changed.
5. In case of insertion into a linked queue, a node borrowed from the __________ list is inserted in the queue.
a) AVAIL
b) FRONT
c) REAR
d) NULL
View Answer
Answer: a
Explanation: All the nodes are collected in AVAIL list.
Become Top Ranker in Data Structure I Now!
6. In linked list implementation of a queue, from where is the item deleted?
a) At the head of link list
b) At the centre position in the link list
c) At the tail of the link list
d) Node before the tail
View Answer
Answer: a
Explanation: Since queue follows FIFO so new element deleted from first.
7. In linked list implementation of a queue, the important condition for a queue to be empty is?
a) FRONT is null
b) REAR is null
c) LINK is empty
d) FRONT==REAR-1
View Answer
Answer: a
Explanation: Because front represents the deleted nodes.
8. The essential condition which is checked before insertion in a linked queue is?
a) Underflow
b) Overflow
c) Front value
d) Rear value
View Answer
Answer: b
Explanation: To check whether there is space in the queue or not.
9. The essential condition which is checked before deletion in a linked queue is?
a) Underflow
b) Overflow
c) Front value
d) Rear value
View Answer
Answer: a
Explanation: To check whether there is element in the list or not.
10. Which of the following is true about linked list implementation of queue?
a) In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end
b) In push operation, if new nodes are inserted at the beginning, then in pop operation, nodes must be removed from the beginning
c) In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from end
d) In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from beginning
View Answer
Answer: a
Explanation: It can be done by both the methods.
This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Priority Queue”.
1. With what data structure can a priority queue be implemented?
a) Array
b) List
c) Heap
d) Tree
View Answer
Answer: d
Explanation: Priority queue can be implemented using an array, a list, a binary search tree or a heap, although the most efficient one being the heap.
2. Which of the following is not an application of priority queue?
a) Huffman codes
b) Interrupt handling in operating system
c) Undo operation in text editors
d) Bayesian spam filter
View Answer
Answer: c
Explanation: Undo operation is achieved using a stack.
3. Select the appropriate code that inserts elements into the list based on the given key value.
(head and trail are dummy nodes to mark the end and beginning of the list, they do not contain any priority or element)
a)
Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
public void insert_key(int key,Object item)
{
if(key<0)
{
Systerm.our.println("invalid");
System.exit(0);
}
else
{
Node temp = new Node(key,item,null);
if(count == 0)
{
head.setNext(temp);
temp.setNext(trail);
}
else
{
Node dup = head.getNext();
Node cur = head;
while((key>dup.getKey()) && (dup!=trail))
{
dup = dup.getNext();
cur = cur.getNext();
}
cur.setNext(temp);
temp.setNext(dup);
}
count++;
}
}
b)
Take Data Structure I Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
public void insert_key(int key,Object item)
{
if(key<0)
{
Systerm.our.println("invalid");
System.exit(0);
}
else
{
Node temp = new Node(key,item,null);
if(count == 0)
{
head.setNext(temp);
temp.setNext(trail);
}
else
{
Node dup = head.getNext();
Node cur = dup;
while((key>dup.getKey()) && (dup!=trail))
{
dup = dup.getNext();
cur = cur.getNext();
}
cur.setNext(temp);
temp.setNext(dup);
}
count++;
}
}
c)
public void insert_key(int key,Object item)
{
if(key<0)
{
Systerm.our.println("invalid");
System.exit(0);
}
else
{
Node temp = new Node(key,item,null);
if(count == 0)
{
head.setNext(temp);
temp.setNext(trail);
}
else
{
Node dup = head.getNext();
Node cur = head;
while((key>dup.getKey()) && (dup!=trail))
{
dup = dup.getNext();
cur = cur.getNext();
}
cur.setNext(dup);
temp.setNext(cur);
}
count++;
}
}
d)
public void insert_key(int key,Object item)
{
if(key<0)
{
Systerm.our.println("invalid");
System.exit(0);
}
else
{
Node temp = new Node(key,item,null);
if(count == 0)
{
head.setNext(temp);
temp.setNext(trail);
}
else
{
Node dup = head.getNext();
Node cur = head;
while((key>dup.getKey()) && (dup!=trail))
{
dup = cur
cur = cur.getNext();
}
cur.setNext(dup);
temp.setNext(cur);
}
count++;
}
}
View Answer
Answer: a
Explanation: Have two temporary pointers ‘dup’ and ‘cur’ with ‘cur’ trailing behind ‘dup’. Traverse through the list until the given key is greater than some element with a lesser key, insert the new node ‘temp’ in that position.
4. What is the time complexity to insert a node based on key in a priority queue?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
View Answer
Answer: c
Explanation: In the worst case, you might have to traverse the entire list.
5. What is the functionality of the following piece of code?
public Object delete_key()
{
if(count == 0)
{
System.out.println("Q is empty");
System.exit(0);
}
else
{
Node cur = head.getNext();
Node dup = cur.getNext();
Object e = cur.getEle();
head.setNext(dup);
count--;
return e;
}
}
a) Delete the second element in the list
b) Return but not delete the second element in the list
c) Delete the first element in the list
d) Return but not delete the first element in the list
View Answer
Answer: c
Explanation: A pointer is made to point at the first element in the list and one more to point to the second element, pointer manipulations are done such that the first element is no longer being pointed by any other pointer, its value is returned.
6. What is not a disadvantage of priority scheduling in operating systems?
a) A low priority process might have to wait indefinitely for the CPU
b) If the system crashes, the low priority systems may be lost permanently
c) Interrupt handling
d) Indefinite blocking
View Answer
Answer: c
Explanation: The lower priority process should wait until the CPU completes the processing higher priority process. Interrupt handling is an advantage as interrupts should be given more priority than tasks at hand so that interrupt can be serviced to produce desired results.
7. Which of the following is not an advantage of a priority queue?
a) Easy to implement
b) Processes with different priority can be efficiently handled
c) Applications with differing requirements
d) Easy to delete elements in any case
View Answer
Answer: d
Explanation: In worst case, the entire queue has to be searched for the element having the highest priority. This will take more time than usual. So deletion of elements is not an advantage.
8. What is the time complexity to insert a node based on position in a priority queue?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
View Answer
Answer: c
Explanation: In the worst case, you might have to traverse the entire list.
This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Double Ended Queue (Dequeue)”.
1. What is a dequeue?
a) A queue with insert/delete defined for both front and rear ends of the queue
b) A queue implemented with a doubly linked list
c) A queue implemented with both singly and doubly linked lists
d) A queue with insert/delete defined for front side of the queue
View Answer
Answer: a
Explanation: A dequeue or a double ended queue is a queue with insert/delete defined for both front and rear ends of the queue.
2. Select the function which performs insertion at the front end of the dequeue?
a)
public void function(Object item)
{
Node temp = new Node(item,null);
if(isEmpty())
{
temp.setNext(trail);
head.setNext(temp);
}
else
{
Node cur = head.getNext();
temp.setNext(cur);
head.setNext(temp);
}
size++;
}
b)
Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
public void function(Object item)
{
Node temp = new Node(item,null);
if(isEmpty())
{
temp.setNext(trail);
head.setNext(trail);
}
else
{
Node cur = head.getNext();
temp.setNext(cur);
head.setNext(temp);
}
size++;
}
c)
Take Data Structure I Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
public void function(Object item)
{
Node temp = new Node(item,null);
if(isEmpty())
{
Node cur = head.getNext();
temp.setNext(cur);
head.setNext(temp);
}
else
{
temp.setNext(trail);
head.setNext(temp);
}
size++;
}
d)
public void function(Object item)
{
Node temp = new Node(item,null);
if(isEmpty())
{
Node cur = head.getNext();
temp.setNext(cur);
cur.setNext(temp);
}
else
{
head.setNext(trail);
trail.setNext(temp);
}
size++;
}
View Answer
Answer: a
Explanation: Create a new node, if the current list is empty, the ‘head’ points to this node and this new node points to ‘trail’. Otherwise, ‘head’ points to the new node and this in turn points to the current first element(head.getNext()).
3. What is the functionality of the following piece of code?
public void function(Object item)
{
Node temp=new Node(item,trail);
if(isEmpty())
{
head.setNext(temp);
temp.setNext(trail);
}
else
{
Node cur=head.getNext();
while(cur.getNext()!=trail)
{
cur=cur.getNext();
}
cur.setNext(temp);
}
size++;
}
a) Insert at the front end of the dequeue
b) Insert at the rear end of the dequeue
c) Fetch the element at the rear end of the dequeue
d) Fetch the element at the front end of the dequeue
View Answer
Answer: b
Explanation: If the list is empty, this new node will point to ‘trail’ and will be pointed at by ‘head’. Otherwise, traverse till the end of the list and insert the new node there.
4. What are the applications of dequeue?
a) A-Steal job scheduling algorithm
b) Can be used as both stack and queue
c) To find the maximum of all sub arrays of size k
d) To avoid collision in hash tables
View Answer
Answer: d
Explanation: All of the mentioned can be implemented with a dequeue.
5. Which of the following can be used to delete an element from the front end of the queue?
a)
public Object deleteFront() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = temp;
Object e = temp.getEle();
head.setNext(cur);
size--;
return e;
}
}
b)
public Object deleteFront() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = temp.getNext();
Object e = temp.getEle();
head.setNext(cur);
size--;
return e;
}
}
c)
public Object deleteFront() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = temp.getNext();
Object e = temp.getEle();
head.setNext(temp);
size--;
return e;
}
}
d)
public Object deleteFront() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = temp.getNext();
Object e = temp.getEle();
temp.setNext(cur);
size--;
return e;
}
}
View Answer
Answer: b
Explanation: Have two pointers, one(temp) pointing to the first element and the other(cur) pointing to the second element. Make the ‘head’ point to the second element, this removes all reference for ‘temp’.
6. Which of the following can be used to delete an element from the rear end of the queue?
a)
public Object deleteRear() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = temp;
while(temp.getNext() != trail)
{
temp = temp.getNext();
cur = cur.getNext();
}
Object e = temp.getEle();
cur.setNext(trail);
size--;
return e;
}
}
b)
public Object deleteRear() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = head;
while(temp != trail)
{
temp = temp.getNext();
cur = cur.getNext();
}
Object e = temp.getEle();
cur.setNext(trail);
size--;
return e;
}
}
c)
public Object deleteRear() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = head;
while(temp.getNext()!=trail)
{
temp = temp.getNext();
cur = cur.getNext();
}
Object e = temp.getEle();
cur.setNext(trail);
size--;
return e;
}
}
d)
public Object deleteRear() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = head;
while(temp.getNext()!=trail)
{
temp = temp.getNext();
cur = cur.getNext();
}
Object e = temp.getEle();
temp.setNext(trail);
size--;
return e;
}
}
View Answer
Answer: c
Explanation: Traverse till the end of the list with a pointer ‘temp’ and another ‘cur’ which is trailing behind temp, make ‘cur’ point to trail, this removes all reference for ‘temp’.
7. What is the time complexity of deleting from the rear end of the dequeue implemented with a singly linked list?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
View Answer
Answer: c
Explanation: Since a singly linked list is used, first you have to traverse till the end, so the complexity is O(n).
8. After performing these set of operations, what does the final list look contain?
InsertFront(10);
InsertFront(20);
InsertRear(30);
DeleteFront();
InsertRear(40);
InsertRear(10);
DeleteRear();
InsertRear(15);
display();
a) 10 30 10 15
b) 20 30 40 15
c) 20 30 40 10
d) 10 30 40 15
View Answer
Answer: d
Explanation: A careful tracing of the given operation yields the result.
10
20 10
20 10 30
10 30
10 30 40
10 30 40 10
10 30 40
10 30 40 15
This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Queue using Stacks”.
1. A Double-ended queue supports operations such as adding and removing items from both the sides of the queue. They support four operations like addFront(adding item to 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 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 are the total number of stacks required for this operation?(you can reuse the stack)
a) 1
b) 2
c) 3
d) 4
View Answer
Answer: b
Explanation: The addFront and removeFront operations can be performed using one stack itself as push and pop are supported (adding and removing element from 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 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
View Answer
Answer: a
Explanation: To perform 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). Therfore the time complexity is O(m).
3. Consider you have an array of some random size. You need to perform dequeue operation. You can perform it using stack operation (push and pop) or using queue operations itself (enQueue and Dequeue). The output is guaranteed to be 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
View Answer
Answer: a
Explanation: To perform operations such as Dequeue using stack operation you need to empty all the elements from the current stack and push it into the next stack, resulting in a O(number of elements) complexity whereas the time complexity of dequeue operation itself is O(1). And there is a need of a extra stack. Therefore more memory is needed.
Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
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)
View Answer
Answer: a
Explanation: 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 the sides of the queue. They support four operations like addFront(adding item to 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 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)
View Answer
Answer: b
Explanation: 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.
Take Data Structure I Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
6. Why is implementation of stack operations on queues not feasible for a large dataset (Asssume 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
View Answer
Answer: a
Explanation: 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. Therfore it has a time complexity of O(n) and the need of extra stack as well, may not be feasible for a large dataset.
7. Consider yourself to be in a planet where the computational power of chips to be slow. You have an array of size 10.You want to perform enqueue some element 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
View Answer
Answer: d
Explanation: 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. Therfore 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
View Answer
Answer: b
Explanation: This is similar to performing 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
View Answer
Answer: c
Explanation: To perform Enqueue using just push and pop operations, there is a need of another array of same size. But as there is no extra available memeory, 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 Dequeue operation. Each element in the array is touched atleast?
a) Once
b) Twice
c) Thrice
d) Four times
View Answer
Answer: d
Explanation: First each element from the first stack is popped, then pushed into the second stack, dequeue operation is done on the top of the stack and later the each element of second stack is popped then pushed into the first stack. Therfore each element is touched four times.
This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Stack using Queues”.
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
View Answer
Answer: b
Explanation: Either the push or the pop has to be a costly operation, and the costlier operation requires two queues.
2. Making the push operation costly, select the code snippet which implements the same.(let q1 and q2 be two queues)
a)
public void push(int x)
{
if(empty())
{
q1.offer(x);
}
else{
if(q1.size()>0)
{
q2.offer(x);
int size = q1.size();
while(size>0)
{
q2.offer(q1.poll());
size--;
}
}
else if(q2.size()>0)
{
q1.offer(x);
int size = q2.size();
while(size>0)
{
q1.offer(q2.poll());
size--;
}
}
}
}
b)
public void push(int x)
{
if(empty())
{
q1.offer(x);
}
else
{
if(q1.size()>0)
{
q1.offer(x);
int size = q1.size();
while(size>0)
{
q2.offer(q1.poll());
size--;
}
}
else if(q2.size()>0)
{
q2.offer(x);
int size = q2.size();
while(size>0)
{
q1.offer(q2.poll());
size--;
}
}
}
}
c)
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
public void push(int x)
{
if(empty())
{
q1.offer(x);
}
else
{
if(q1.size()>0)
{
q2.offer(x);
int size = q1.size();
while(size>0)
{
q1.offer(q2.poll());
size--;
}
}
else if(q2.size()>0)
{
q1.offer(x);
int size = q2.size();
while(size>0)
{
q2.offer(q1.poll());
size--;
}
}
}
}
d)
Check this: Programming Books | Computer Science MCQs
public void push(int x)
{
if(empty())
{
q1.offer(x);
}
else
{
if(q1.size()>0)
{
q2.offer(x);
int size = q1.size();
while(size>0)
{
q2.offer(q2.poll());
size--;
}
}
else if(q2.size()>0)
{
q1.offer(x);
int size = q2.size();
while(size>0)
{
q2.offer(q1.poll());
size--;
}
}
}
}
View Answer
Answer: a
Explanation: Stack follows LIFO principle, hence a new item added must be the first one to exit, but queue follows FIFO principle, so when a new item is entered into the queue, it will be at the rear end of the queue. If the queue is initially empty, then just add the new element, otherwise add the new element to the second queue and dequeue all the elements from the second queue and enqueue it to the first one, in this way, the new element added will be always in front of the queue. Since two queues are needed to realize this push operation, it is considered to be costlier.
3. Making the push operation costly, select the code snippet which implements the pop operation.
a)
public void pop()
{
if(q1.size()>0)
{
q2.poll();
}
else if(q2.size()>0)
{
q1.poll();
}
}
b)
public void pop()
{
if(q1.size()>0)
{
q1.poll();
}
else if(q2.size()>0)
{
q2.poll();
}
}
c)
public void pop()
{
q1.poll();
q2.poll();
}
d)
public void pop()
{
if(q2.size()>0)
{
q1.poll();
}
else
{
q2.poll();
}
}
View Answer
Answer: b
Explanation: As the push operation is costly, it is evident that the required item is in the front of the queue, so just dequeue the element from the queue.
4. Select the code snippet which returns the top of the stack.
a)
public int top()
{
if(q1.size()>0)
{
return q1.poll();
}
else if(q2.size()>0)
{
return q2.poll();
}
return 0;
}
b)
public int top()
{
if(q1.size()==0)
{
return q1.peek();
}
else if(q2.size()==0)
{
return q2.peek();
}
return 0;
}
c)
public int top()
{
if(q1.size()>0)
{
return q1.peek();
}
else if(q2.size()>0)
{
return q2.peek();
}
return 0;
}
d)
public int top()
{
if(q1.size()>0)
{
return q2.peek();
}
else if(q2.size()>0)
{
return q1.peek();
}
return 0;
}
View Answer
Answer: c
Explanation: Assuming its a push costly implementation, the top of the stack will be in the front end of the queue, note that peek() just returns the front element, while poll() removes the front element from the queue.
5. Select the code snippet which return true if the stack is empty, false otherwise.
a)
public boolean empty()
{
return q2.isEmpty();
}
b)
public boolean empty()
{
return q1.isEmpty() || q2.isEmpty();
}
c)
public boolean empty()
{
return q1.isEmpty();
}
d)
public boolean empty()
{
return q1.isEmpty() & q2.isEmpty();
}
View Answer
Answer: b
Explanation: If both the queues are empty, then the stack also is empty.
6. Making the pop operation costly, select the code snippet which implements the same.
a)
public int pop()
{
int res=-999,count=0;
if(q1.size()>0)
{
count = q1.size();
while(count>0)
q2.offer(q1.poll());
res = q1.poll();
}
if(q2.size()>0)
{
count = q2.size();
while(count>0)
q1.offer(q2.poll());
res = q2.poll();
}
return res;
}
b)
public int pop()
{
int res=-999,count=0;
if(q1.size()>0)
{
count = q1.size();
while(count>1)
q2.offer(q1.poll());
res = q2.poll();
}
if(q2.size()>0)
{
count = q2.size();
while(count>1)
q1.offer(q2.poll());
res = q1.poll();
}
return res;
}
c)
public int pop()
{
int res=-999,count=0;
if(q1.size()>0)
{
count = q1.size();
while(count>1)
q2.offer(q1.poll());
res = q1.poll();
}
if(q2.size()>0)
{
count = q2.size();
while(count>1)
q1.offer(q2.poll());
res = q2.poll();
}
return res;
}
d)
public int pop()
{
int res=-999,count=0;
if(q1.size()>0)
{
count = q2.size();
while(count>1)
q2.offer(q1.poll());
res = q1.poll();
}
if(q2.size()>0)
{
count = q1.size();
while(count>1)
q1.offer(q2.poll());
res = q2.poll();
}
return res;
}
View Answer
Answer: c
Explanation: Here the pop operation is costly, hence we need two queues, other than the first element, all the the elements from one queue are dequeued and enqueued to the second queue, hence only one element remains in the first queue which is the item we want, so dequeue it and return the result.
7. What is the functionality of the following piece of code?
public void fun(int x)
{
q1.offer(x);
}
a) Perform push() with push as the costlier operation
b) Perform push() with pop as the costlier operation
c) Perform pop() with push as the costlier operation
d) Perform pop() with pop as the costlier operation
View Answer
Answer: b
Explanation: offer() suggests that it is a push operation, but we see that it is performed with only one queue, hence the pop operation is costlier.
Subscribe to:
Posts (Atom)