Data Structures and Algorithms

Question 1

Multiple choice

Let L₁ be a recursive language, and let L₂ be a recursively enumerable but not a recursive language. Which one of the following is true?

$\bar L_1$ is recursive and $\bar L_2$ is recursively enumerable
$\bar L_1$ and L2 are recursively enumerable
$\bar L_1$ is recursively enumerable and $\bar L_2$ is recursive

Reveal answer Fill a bubble to check yourself

Answer

$\bar L_1$ is recursive and $\bar L_2$ is not recursively enumerable

Question 2

Multiple choice

In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time

O(n log n)
O(n)
O(log n)
O(1)

Reveal answer Fill a bubble to check yourself

Answer

become O (n log n)

Answer

O (n log n)

Answer

Solves it using divide and conquer in time O(n log n)

Answer

O(n log n)

Answer

Takes $\Theta$(n³) time and space

Answer

Merge sort

Answer

d e b f g c a

Answer

1, 8, 10, −, −, −, 3

Answer

$\Theta$(log₂ log₂ n)

Answer

$\Theta$ (log₂ n)

Question 3

Multiple choice

The usual O(n²) implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will

remain O (n²)
become O (n (log n)²)
become O (n)

Reveal answer Fill a bubble to check yourself

Question 4

Multiple choice

In a permutation a₁ ... a_n, of n distinct integers, an inversion is a pair (a_i, a_j) such that i < j and ai > aj.

What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of 1. . . n with at most n inversions?

O(n²)
O (n^1.5)
O (n)

Reveal answer Fill a bubble to check yourself

Question 5

Multiple choice

In a binary max heap containing n numbers, the smallest element can be found in time

O (n)
O (log n)
O (log log n)
O (1)

Reveal answer Fill a bubble to check yourself

Question 6

Multiple choice

Which one of the following in place sorting algorithms needs the minimum number of swaps?

Quick sort
Insertion sort
Selection sort
Heap sort

Reveal answer Fill a bubble to check yourself

Question 7

Multiple choice

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
2n + 1
2ⁿ - 1

Reveal answer Fill a bubble to check yourself

Question 8

Multiple choice

An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array

Solves it in linear time using a left to right pass of the array
Solves it in linear time using a right to left pass of the array
Solves it in time O(n²)

Reveal answer Fill a bubble to check yourself

Question 9

Multiple choice

The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which the median is selected as pivot?

O(n)
O(n)³
O(n)²

Reveal answer Fill a bubble to check yourself

Question 10

Multiple choice

Given two arrays of numbers a₁,..........., a_n and b₁,............, b_n where each number is 0 or 1, the fastest algorithm to find the largest span (i, j ) such that a_i + a_i+1 + .........+ a_j = b_i + b_{i + 1} +...........+ b_j or report that there is not such span,

Takes $\Theta$(3ⁿ) and $\Omega$(2ⁿ) time if hashing is permitted
Takes $\Theta$(n³) and $\Omega$ (n^2.5) time in the key comparison model
Takes $\Theta$($\sqrt{n}$) time only if the sum of the 2n elements is an even number

Reveal answer Fill a bubble to check yourself

Question 11

Multiple choice

Which of the following sorting algorithms has the lowest worst-case complexity?

Bubble sort
Quick sort
Selection sort

Reveal answer Fill a bubble to check yourself

Question 12

Multiple choice

The in order and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively The post order traversal of the binary tree is:

e d b g f c a
e d b f g c a
d e f g b c a

Reveal answer Fill a bubble to check yourself

Question 13

Multiple choice

Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that − denotes an empty location in the table.

8, −, −, −, −, −, 10
1, −, −, −, −, −, 3
1, 10, 8, −, −, −, 3

Reveal answer Fill a bubble to check yourself

Question 14

Multiple choice

What is the time complexity of the following recursive function?

Int Do Something (int n) {
return 1;
else
return (Do Something (floor sqrt (n))) + n);

$\Theta$(n²)
$\Theta$(n log₂ n)
$\Theta$(log₂ n)

Reveal answer Fill a bubble to check yourself

Question 15

Multiple choice

Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:

$\Theta$(log₂ log₂ n)
$\Theta$ (n)
$\Theta$(nlog₂ n)

Reveal answer Fill a bubble to check yourself

Data Structures and Algorithms

Data Structures and Algorithms Questions