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

Consider the following algorithm for searching for a given number x in an unsorted array A[1.....n] having n distinct values : (1) Choose an i uniformly at random from 1....n If A[i] = x then stop else Goto 1;

Assuming that x is present A, What is the expected number of comparisons made by the algorithm before it terminates?

  1. n

  2. n -1

  3. 2n
  4. $\dfrac{n}{2}$
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Given array A[1.....n], an element A[i] is chosen randomly from 1 to n.This would require n selections & comparisons to find x in array

Multiple choice

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely?

  1. preorder and postorder
  2. inorder and postorder
  3. preorder and inorder
  4. level order and postorder

  1. 1 only

  2. 2 and 3

  3. 3 only

  4. 4 only
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

For a tree we not only require in order & preorder but also post order traversal. Preorder & post order help to determine the roots of binary subtrees, inorder arranges those roots in order.

Multiple choice

Two matrices M1 and M2 are to be stored in arrays A and B respectively. Each array can be stored either in row-major or column major order in contiguous memory locations. The time complexity of an algorithm to compute M1x M2 x will be

  1. best if A is in row-major, and B is in column-major order

  2. best if both are in row-major order

  3. best if both are in column-major order

  4. independent of the storage scheme
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

Since the matrices are stored in array, there is no dependence of time complexity on row major or column major. Here only the starting address is known & on the basis of indexes the next memory locations are calculated.

Multiple choice

Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest?

  1. union only

  2. intersection, membership

  3. membership, cardinality

  4. union, intersection
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

Membership & cardinality functions takes constt. time i.e. 0(1), but union & intersection require emparison of 1 element with all the other elements so these two would be slowest.

Multiple choice

A program takes as input a balanced binary search tree with n leaf modes and computes the value of a function g(x) for each node x . If the cost of computing g(x) is min (number of leaf-nodes in learsubtree of x , number of leaf-nodes in right-subtree of x) then the worst case time complexity of the program is
  1. $\theta$(n)

  2. O(nlogn)

  3. O(n)2

  4. O(2n)
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

The function g(x) calculates for a node x min no. of leaf noes whether in left subtree or right subtree. The for balanced BST. The no. of inner nodes = leaf nodes−1. So this loop will sun for max n-times so complexity is  $\Theta$(n)