Intermediate Questions (Yash Nangre)
Based on Data Structure
Made by @tevavo8922
0
0
3
6
1: Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?
30s
Insertion Sort
Quick Sort
Heap Sort
Merge Sort
2: In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
30s
log(2*n)
n/2
log(2*n) -1
n
3: Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best known algorithm to delete the node Q from the list?
30s
O(n)
O(log2 n)
O(logn)
O(1)
4: What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order ?
30s
Θ(n)
Θ(n log n)
Θ(n2)
Θ(1)
5: Which of the following is true about linked list implementation of stack?
30s
In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end.
In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning.
Both of the above
None of the above
6: Which one of the following is an application of Stack Data Structure?
30s
Managing function calls
The stock span problem
Arithmetic expression evaluation
All of the above
7: The five items: A, B, C, D, and E are pushed in a stack, one after other starting from A. The stack is popped four items and each element is inserted in a queue. The two elements are deleted from the queue and pushed back on the stack. Now one item is popped from the stack. The popped item is
30s
A
B
C
D
8: Stack A has the entries a, b, c (with a on top). Stack B is empty. An entry popped out of stack A can be printed immediately or pushed to stack B. An entry popped out of the stack B can be only be printed. In this arrangement, which of the following permutations of a, b, c are not possible?
30s
b a c
b c a
c a b
a b c
9: Which one of the following is an application of Queue Data Structure?
30s
When a resource is shared among multiple consumers.
When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes
Load Balancing
All of the above
10: Which of the following option is not correct?
30s
If the queue is implemented with a linked list, keeping track of a front pointer, Only rear pointer s will change during an insertion into an non-empty queue.
Queue data structure can be used to implement least recently used (LRU) page fault algorithm and Quick short algorithm.
Queue data structure can be used to implement Quick short algorithm but not least recently used (LRU) page fault algorithm.
Both (A) and (C)
11: The minimum number of stacks needed to implement a queue is
30s
3
1
2
4
12: What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?
30s
Θ(√n)
Θ(log2(n))
Θ(n2)
Θ(n)
13: Consider a binary tree with n nodes, where each node can have at most two children. The height of the tree is defined as the maximum number of edges between the root node and any leaf node. Which of the following statements is true regarding the height h of this binary tree?
30s
The height of the tree is always equal to n-1.
The height of the tree can be greater than or equal to n-1.
The height of the tree is always equal to log₂(n).
The height of the tree can be greater than or equal to log₂(n).
14: Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is
30s
Ω(logn)
Ω(n)
Ω(nlogn)
Ω(n2)
15: Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?
30s
7 5 1 0 3 2 4 6 8 9
0 2 4 3 1 6 5 9 8 7
0 1 2 3 4 5 6 7 8 9
9 8 6 4 2 3 0 1 5 7
16: The average depth of a binary search tree is:
30s
O(n0.5)
O(n)
O(log n)
O(n log n)
17: The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?
30s
2
3
4
6
18: The postorder traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the same tree is 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is ________ .
30s
2
3
4
5
19: What is the worst case time complexity of inserting n2 elements into an AVL-tree with n elements initially ?
30s
Θ(n4)
Θ(n2)
Θ(n2 log n)
Θ(n3)
20: Which of the following is TRUE?
30s
The cost of searching an AVL tree is θ (log n) but that of a binary search tree is O(n)
The cost of searching an AVL tree is θ (log n) but that of a complete binary tree is θ (n log n)
The cost of searching a binary search tree is O (log n ) but that of an AVL tree is θ(n)
The cost of searching an AVL tree is θ (n log n) but that of a binary search tree is O(n)
21: Which of the following points is/are true about Linked List data structure when it is compared with array?
30s
Arrays have better cache locality that can make them better in terms of performance.
Random access is not allowed in a typical implementation of Linked Lists
It is easy to insert and delete elements in Linked List
All of the above
22: Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest?
30s
union
membership
cardinality
union, intersection
23: Consider the function f defined below. For a given linked list p, the function f returns 1 if and only if
30s
not all elements in the list have the same data value.
the elements in the list are sorted in non-decreasing order of data value
the elements in the list are sorted in non-increasing order of data value
None of them
24: A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time?
30s
rear node
front node
not possible with a single pointer
node next to front
25: What are the time complexities of finding 8th element from beginning and 8th element from end in a singly linked list? Let n be the number of nodes in linked list, you may assume that n > 8.
30s
O(1) and O(n)
O(1) and O(1)
O(n) and O(1)
O(n) and O(n)
26: Is it possible to create a doubly linked list using only one pointer with every node.
30s
Not Possible
Yes, possible by storing XOR of addresses of previous and next nodes.
Yes, possible by storing XOR of current node and next node
Yes, possible by storing XOR of current node and previous node
27: 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?
30s
Possible if X is not last node. Use following two steps (a) Copy the data of next of X to X. (b)Update the pointer of node X to the node after the next node. Delete next of X.
Possible if size of linked list is even.
Possible if size of linked list is odd
Possible if X is not first node. Use following two steps (a) Copy the data of next of X to X. (b) Delete next of X.
28: Which of the following is an application of XOR-linked lists?
30s
Implementing stacks
Implementing queues
Memory-efficient linked list representation
Caching data structures
29: Consider the following function to traverse a linked list. Which of the following is FALSE about above function?
30s
The function may crash when the linked list is empty
The function doesn't print the last node when the linked list is not empty
The function is implemented incorrectly because it changes head
None of the above
30: What are the application(s) of linked list?
30s
Implementation of stacks and queues.
Maintaining a directory of names
None of the above
Both a and b
31: The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of a list should be used?
30s
singly linked list
doubly linked list
circular doubly linked list
array implementation of lists
32: In a doubly linked list, the number of pointers affected for an insertion operation will be
30s
5
0
1
None of these
33: Consider an implementation of unsorted single linked list. Suppose it has its representation with a head and a tail pointer (i.e. pointers to the first and last nodes of the linked list). Given the representation, which of the following operation can not be implemented in O(1) time ?
30s
Insertion at the front of the linked list.
Deletion of the front node of the linked list.
Insertion at the end of the linked list.
Deletion of the last node of the linked list.
34: The following steps in a linked listresult in which type of operation?
30s
pop operation in stack
removal of a node
inserting a node at beginning
modifying an existing node
35: In DNA sequence alignment, which string-matching algorithm is commonly used to identify similarities between two DNA sequences efficiently?
30s
Rabin-Karp algorithm
Knuth-Morris-Pratt algorithm
Z function
None of the above
36: Which of the following operations is performed more efficiently by doubly linked list than by linear linked list?
30s
Deleting a node whose location is given
Searching an unsorted list for a given item
Inserting a node after the node with a given location
Traversing the list to process each node
37: The time required to search an element in a linked list of length n is
30s
O (log n)
O (n)
O (1)
O (n2)
38: Consider a singly linked list of the form where F is a pointer to the first element in the linked list and L is the pointer to the last element in the list. The time of which of the following operations depends on the length of the list?
30s
Delete the last element of the list
Delete the first element of the list
Add an element after the last element of the list
Interchange the first two elements of the list
39: In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
30s
log(2*n)
n/2
log(2*n) -1
n
40: The minimum number of fields with each node of doubly linked list is
30s