Computer Knowledge

Data Structures and Algorithms

1,256 Questions

Data Structures and Algorithms form the core of computer science, focusing on arrays, linked lists, trees, and sorting mechanisms. These concepts are essential for solving complex computational problems efficiently. Test takers preparing for technical and administrative IT exams will find these questions highly relevant.

Array OperationsLinked List ApplicationsSorting AlgorithmsTree Data StructuresMultilevel IndexingAlgorithm Time Complexity

Data Structures and Algorithms Questions

Multiple choice

The following key values are inserted into a B+ - tree in which order of the internal nodes is 3, and that of the leaf nodes is 2, in the sequence given below. The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that can be stored in it. The B+ - tree is initially empty. 10, 3, 6, 8, 4, 2, 1 The maximum number of times leaf nodes would get split as a result of these insertions is

  1. 2

  2. 3

  3. 4

  4. 5
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Multiple choice

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

0
1
2 42
3 23
4 34
5 52
6 46
7 33
8
9

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

  1. 46, 42, 34, 52, 23, 33

  2. 34, 42, 23, 52, 33, 46

  3. 46, 34, 42, 23, 52, 33

  4. 42, 46, 33, 23, 34, 52
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Multiple choice

An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array $A[0:n-1]$ is given below.

Let $L_i$, denote the length of the longest monotonically increasing sequence starting at index $i$ in the array.

Initialize $L_{n-1} = 1$.

For all $i$ such that $0 \leq i \leq n-2$

$ L_i = \begin{cases} 1+ L_{i+1} & \quad\text{if A[i] < A[i+1]} \\ 1 & \quad\text{Otherwise}\end{cases} $

Finally the the length of the longest monotonically increasing sequence is $\text{Max} :(L_0, L_1, \dots , L_{n-1}).$

Which of the following statements is TRUE?

  1. The algorithm uses dynamic programming paradigm.

  2. The algorithm has a linear complexity and uses branch and bound paradigm.

  3. The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm.

  4. The algorithm uses divide and conquer paradigm.
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

This algorithm uses dynamic programming because it solves the problem by breaking it into smaller subproblems (L_i depends on L_{i+1]) and stores the results. It builds the solution bottom-up from the base case L[n-1] = 1. The complexity is O(n) linear time. It does not use branch and bound (which prunes search trees) or divide and conquer (which recursively splits problems).

Multiple choice

We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

  1. 0

  2. 1

  3. n!
  4. $\frac{1} {n+1} .^{2n}C_n$
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

The number of distinct BSTs with n distinct keys is the nth Catalan number: C(n) = (1/(n+1)) * (2nCn) = (2n)!/((n+1)!n!). This is a fundamental result in combinatorics - the structure of a BST is determined solely by the relative ordering of elements. With n distinct elements and n nodes, there are exactly C(n) ways to build a BST.

Multiple choice

Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables a, b, c, d and e are initially stored in memory. The binary operators used in this expression tree can be evaluated by the machine only when the operands are in registers. The instructions produce result only in a register. If no intermediate results can be stored in memory, what is the minimum number of registers needed to evaluate this expression?

  1. 2

  2. 9

  3. 5

  4. 3
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

Load R1,a ; R1 $\leftarrow$M[a] Load R2,b ; R2 $\leftarrow$M[b] Sub R1,R ; R1 $\leftarrow$R1 – R2 Load R2 ,c ; R2 $\leftarrow$M[c] Load R3 ,d ; R3 $\leftarrow$Md] Add R2 , R3 ; R2 $\leftarrow$R2 R3 Load R3 ,e ; R3 $\leftarrow$M[e] Sub R3, R2 : R3$\leftarrow$R3 – R2 Add R1 ,R3 ; R1 $\leftarrow$R1 R3 Minimum 3 Registers are required.