Free Printable DSA HOTS MCQ

Worksheets

DSA HOTS MCQ

Total questions: 15

Worksheet time: 30mins

Name

Class

Date

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?

O(n²)

O(2n)

O(n)

O(1)

The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?

10,20,15,23,25,35,42,39,30

15,10,25,23,20,42,35,39,30

15,20,10,23,25,42,35,39,30

15,10,23,25,20,35,42,39,30

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

2^h-1

2^h-1-1

2^h+1-1

2^h+1

A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be ___________

log₂n

2ⁿ+1

2ⁿ-1

The B-trees of the order 4 and height 3 would have a maximum of ________ keys.

188

277

163

255

A single array A[1..MAXSIZE] is used to implement two stacks, The two stacks grow from opposite ends of the array. Variables top1 and top2 (top1 < top2) point to the location of the topmost element in each of the stacks, If the space is to be used efficiently, the condition for "stack full" is

(top1=MAXSIZE/2) and (top2=MAXSIZE/2 + 1)

top1 + top2 = MAXSIZE

(top1=MAXSIZE/2) and (top2=MAXSIZE)

top1 = top2 - 1

Suppose you are given an array s[1..n] and a procedure reverse (s, i, j) which reverse the order of elements in s between positions i and j (both inclusive). What does the following sequence do, where 1≤k<n:

reverse (s, 1, k);
reverse (s, k+1, k);
reverse (s, 1, n);

Rotates S left by K positions

Reverse all elements of S

Leaves S Unchanged

Rotates S left by K+1 positions

Consider the C functions given in picture in which size is the number of elements in the array E.

The value returned by the function MyX is the ______.

Maximum possible sum of elements in any sub-array of array E.

Maximum element in any sub-array of array E.

Sum of the maximum elements in all possible sub-arrays of array E.

The sum of all elements in the array E.

A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let enqueue be implemented by inserting a new node at the head, and dequeue be implemented by deletion of a node from the tail.

Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?

$\theta\left(1\right),\ \theta\left(n\right)$

$\theta\left(1\right),\ \theta\left(1\right)$

$\theta\left(n\right),\ \left(1\right)$

$\theta\left(n\right),\theta\left(n\right)$

10.

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?

Both Operation can be performed in O(1) time

At most one operation can be performed in O(1) time but the worst case time for the other operation will be $\Omega\left(n\right)$

The worst case time complexity for both operation will be $\Omega\left(n\right)$

he worst case time complexity for both operation will be $\Omega\left(\log n\right)$

11.

N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed.

An algorithm performs the following operations on the list in this order:
Θ(N) for delete, O(log⁡N) for insert, O(log⁡N) for fund, and Θ(N) for decrease-key.

What is the time complexity of all these operations put together?

$O\left(\log^2n\right)$

O (N)

O(N²)

$O\left(N^2\log\ n\right)$

12.

Two matrices M₁ and M₂ are to be stored in arrays A and B respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to compute M₁× M₂ will be_____

Best if A is in row-major and B is in Column-major order

Best if both are in row-major order

Best if both are inn column-major order

Independent to the storage scheme

13.

An n × n array v is defined as follows V [i, j] = i - j for all i, j, 1≤i≤n,1≤j≤n

The sum of the elements of the array v is _____.

n-1

n²-3n+2

n²(n+1)/2

14.

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

$\theta\left(n\right)$

$\theta\left(n+m\right)$

$\theta\left(n^2\right)$

$\theta\left(m^2\right)$

15.

A function f defined on stacks of integers satisfies the following properties. f(∅) = 0 and

f (push (S, i)) = max (f(S), 0) + i for all stacks S and integers i. If a stack S contains the integers

2, -3, 2, -1, 2 in order from bottom to top, what is f(S)?

Reset

DSA HOTS MCQ

Total questions: 15

Worksheet time: 30mins

Similar Resources on Wayground