Computer Knowledge

Data Structures and Algorithms

1,518 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

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.

Multiple choice

Suppose a circular queue of capacity (n - 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are

  1. full: (REAR+l) mod n == FRONT empty: REAR ==FRONT

  2. full:(REAR+l)mod n == FRONT empty: (FRONT+l)mod n==REAR

  3. full: REAR == FRONT empty: (REAR+l) mod n == FRONT

  4. full:(FRONT+ l)mod n == REAR empty: REAR == FRONT
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Multiple choice

A list of n stings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is

  1. O(nlogn)

  2. O(n2 logn)

  3. O(n2 +logn)

  4. O(n2)
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

The height of the recursion tree using merge sort is logn and n2 comparisons are done at each level, where at most n pairs of strings are compared at each level and n comparisons are required to compare any two strings, So the worst case running time is O(n2 logn)

Multiple choice

The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root. int height (treeptr n) The appropriate expressions for the two boxes B1 and B2 are
  1. B1: (1 + height (n$\rightarrow$right)) B2: (1 - max (h1, h2))
  2. B1: (height (n$\rightarrow$right)) B2: (1 - max (h1, h2))
  3. B1: height (n$\rightarrow$right) B2: max (h1, h2)
  4. B1: (1 + height (n$\rightarrow$right)) B2: max (h1, h2)
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Multiple choice

In a k-way set associative cache, the cache is divided into v sets, each of which consists of k lines. The lines of a set are placed in sequence one after another. The lines in set s are sequenced before the lines in set (s+1). The main memory blocks are numbered from 0 onwards. The main memory block numbered j must be mapped to any one of the cache lines from

  1. (j mod v) *k to (j mod v) * k + (k - 1)

  2. (j mod v) to (j mod v) + (k - 1)

  3. (j mod k) to (j mod k) + (v - 1)

  4. (j mod k) * v to (j mod k) * v + (v - 1)
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Set number in the cache = (main memory block number) MOD number of sets in the cache As the lines in the set are placed in sequence, we can have the lines from 0 to K – 1 in the set. Number of sets = v Main memory block number = j First line = (j mod v); last line = (j mod v) + (k – 1)