DSA HOTS MCQ

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

• 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?

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