MCA 2024

Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?

• Insertion Sort

• Quick Sort

• Heap Sort

• Merge Sort

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?

• O(n)

• O(log2 n)

• O(logn)

• O(1)

Which one of the following is an application of Stack Data Structure?

• Managing function calls

• The stock span problem

• Arithmetic expression evaluation

• All of the above

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

• A

• B

• C

• D

The minimum number of stacks needed to implement a queue is

• 3

• 1

• 2

• 4

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?

• Θ(√n)

• Θ(log₂(n))

• Θ(n²)

• Θ(n)

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

• Ω(logn)

• Ω(n)

• Ω(nlogn)

• Ω(n²)

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?

• 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

The average depth of a binary search tree is:

• O(n^0.5)

• O(n)

• O(log n)

• O(n log n)

When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value 60?

• 35

• 64

• 128

• 5040