Intermediate Lakshay
Round 2
Made by @aaddad
0
0
1
41
1: Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?
30s
Insertion Sort
Merge Sort
Quick Sort
Heap 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) -1
n
n/2
n/2
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 log n)
Θ(n2)
Θ(1)
Θ(n)
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: 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
10: 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
11: 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)
12: The minimum number of stacks needed to implement a queue is
30s
3
2
1
4
13: 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)
14: 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).
15: 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)
16: 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
17: The average depth of a binary search tree is:
30s
O(n0.5)
O(n)
O(log n)
O(n log n)
18: 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
19: 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
20: 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)
21: 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 a binary search tree is O (log n ) but that of an AVL tree is θ(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 an AVL tree is θ (n log n) but that of a binary search tree is O(n)
22: Which of the following is AVL Tree?
30s
Only A
A and C
A, B and C
Only B
23: Consider the following left-rotate and right-rotate functions commonly used in self-adjusting BSTs
30s
O(1)
O(Logn)
O(LogLogn)
O(n)
24: What is the worst case possible height of AVL tree?
30s
2Logn (Assume base of log is 2)
1.44log n (Assume base of log is 2)
Depends upon implementation
Theta(n)
25: Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?
30s
In adjacency list representation, space is saved for sparse graphs.
Adding a vertex in adjacency list representation is easier than adjacency matrix representation.
DFS and BSF can be done in O(V + E) time for adjacency list representation. These operations take O(V^2) time in adjacency matrix representation. Here is V and E are number of vertices and edges respectively.
All of the above
26: What is the worst case efficiency for a path compression algorithm?
30s
O(M log N)
O(log N)
O(N log N)
O(N)
27: Trie is also known as
30s
Treap
Binomial Tree
2-3 Tree
Digital Tree
28: Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the following statements is always TRUE?
30s
There exists a cutset in G having all edges of maximum weight.
Edge e cannot be contained in a cycle.
There exists a cycle in G having all edges of maximum weight
All edges in G have the same weight
29: An advantage of chained hash table (external hashing) over the open addressing scheme is
30s
Worst case complexity of search operations is less
Space used is less
Deletion is easier
None of the above
30: Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is
30s
80
0.0125
8000
1.25
31: The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?
30s
A
B
C
D
32: A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.
30s
46, 42, 34, 52, 23, 33
34, 42, 23, 52, 33, 46
46, 34, 42, 23, 52, 33
42, 46, 33, 23, 34, 52
33: Which of the following correctly declares an array?
30s
int geeks[20];
nt geeks;
geeks{20};
array geeks[20];
34: A three dimensional array in ‘C++’ is declared as int A[x][y][z]. Consider that array elements are stored in row major order and indexing begins from 0. Here, the address of an item at the location A[p][q][r] can be computed as follows (where w is the word length of an integer):
30s
&A[0][0][0] + w(y * z * q + z * p + r)
&A[0][0][0] + w(y * z * p + z*q + r)
&A[0][0][0] + w(x * y * p + z * q+ r)
&A[0][0][0] + w(x * y * q + z * p + r)
35: Let A be a square matrix of size n x n. Consider the following program. What is the expected output?
30s
The matrix A itself
Transpose of matrix A
Adding 100 to the upper diagonal elements and subtracting 100 from diagonal elements of A
Inverse of matrix A
36: A program P reads in 500 integers in the range [0..100] representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?
30s
An array of 50 numbers
An array of 100 numbers
An array of 500 numbers
A dynamically allocated array of 550 numbers
37: Which of the following is FALSE about B/B+ tree
30s
B/B+ trees grow upward while Binary Search Trees grow downward.
Time complexity of search operation in B/B+ tree is better than Red Black Trees in general.
Number of child pointers in a B/B+ tree node is always equals to number of keys in it plus one.
A B/B+ tree is defined by a term minimum degree. And minimum degree depends on hard disk block size, key and address sizes.
38: The order of an internal node in a B+ tree index is the maximum number of children it can have. Suppose that a child pointer takes 6 bytes, the search field value takes 14 bytes, and the block size is 512 bytes. What is the order of the internal node?
30s
24
25
26
27
39: A B-Tree used as an index for a large database table has four levels including the root node. If a new key is inserted in this index, then the maximum number of nodes that could be newly created in the process are
30s
5
4
1
2
40: In a file which contains 1 million records and the order of the tree is 100, then what is the maximum number of nodes to be accessed if B+ tree index is used?
30s
5
4
3
10
41: B+ Trees are considered BALANCED because
30s