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 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4]location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.

Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?

  1. 1, 3, 5, 6, 8, 9

  2. 9, 6, 3, 1, 8, 5

  3. 9, 3, 6, 8, 5, 1

  4. 9, 5, 6, 8, 3, 1
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

the all its children

Multiple choice

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4]location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.

Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3- ary max heap found in the above question, Q.76. Which one of the following is the sequence of items in the array representing the resultant heap?

  1. 10, 7, 9, 8, 3, 1, 5, 2, 6, 4

  2. 10, 9, 8, 7, 6, 5, 4, 3, 2, 1

  3. 10, 9, 4, 5, 7, 6, 8, 2, 1, 3

  4. 10, 8, 6, 9, 7, 2, 3, 4, 1, 5
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Multiple choice

Consider the following C program segment where CellNode represents a node in a binary tree: 

Struct Cell Node {
  Struct Cell Node * left child;
  Int element;
  Struct Cell Node * right Child;
};
Int Get Value(struct Cell Node * ptr) {
  Int Value = 0;
  if (ptr! = NULL)
    if ((ptr - > left child == NULL) &&
      (ptr - > right Child == NULL))
      Value = 1;
    else
      Value = value + GetValue(ptr - > left Child) + Get Value(ptr - > right child);
}
return (value);
}

The value returned by GetValue when a pointer to the root of a binary tree is passed as its argument is:

  1. the number of nodes in the tree

  2. the number of internal nodes in the tree

  3. the number of leaf nodes in the tree

  4. the height of the tree
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Multiple choice

An implementation of a queue Q, using two stacks S1 and S2, is given below:

void insert(Q, x) {
  push(S1, x);
}
void delete(Q) {
  if (stack - empty(S2)) then
  if (stack - empty(S1)) then {
    print(“Q is empty”);
    return;
  } else
    while (!(stack - empty(S1))) {
      x = pop(S1);
      push(S2, x);
    }
  x = pop(S2);
}

Let n insert and m ($\le$ n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?
  1. n + m $\le$ x < 2n and 2m $\le$ y $\le$ n + m
  2. n + m $\le$ x < 2n and 2m $\le$ y $\le$ 2n
  3. 2m $\le$ x < 2n and 2m $\le$ y $\le$ n + m
  4. 2m $\le$ x < 2n and 2m $\le$ y $\le$ 2n
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

The order in which insert and delete operations are performed matters here. The best case: Insert and delete operations are performed alternatively. In every delete operation, 2 pop and 1 push operations are performed. So, total m+ n push (n push for insert() and m push for delete()) operations and 2m pop operations are performed. The worst case: First n elements are inserted and then m elements are deleted. In first delete operation, n + 1 pop operations and n push operation are performed. Other than first, in all delete operations, 1 pop operation is performed. So, total m + n pop operations and 2n push operations are performed (n push for insert() and n push for delete())

Multiple choice

The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What will be the contents of the list after the function completes execution?

struct node {
  int value;
  struct node * next;
};
Void rearrange struct node * list {
  struct node * p, * q;
  int temp;
  if (!list || !!list - &gt; ; next) return;
  p = list; | q = list - &gt; ;
  next;
  while q {
    temp = p - &gt; ;
    value;
    p - &gt; ;
    value = q - &gt; ;
    value;
    q - &gt; ;
    value = temp;
    p = q - &gt; ;
    next;
    q = p ? p - &gt; ;
    next: 0;
  }
}

  1. 1,2,3, 4,5, 6, 7

  2. 2,1, 4,3, 6,5, 7

  3. 1,3, 2,5, 4, 7, 6

  4. 2, 3, 4,5, 6, 7,1
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Multiple choice

The best data structure to check whether an arithmetic expression has balanced parenthesis is a

  1. queue

  2. stack

  3. tree

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

Balanced parenthesis in an equation is such that the no. of opening and closing parenthesis and in correct order should be there. We can check balancing using stack. When we get any opening parenthesis then we push that in the stack & if we get a closing one then we pop the stack. After the complete scanning of input string if stack is found empty then the arithmetic expression is balanced

Multiple choice

Consider the following program fragment for reversing the digits in a given integer to obtain a new integer.

Let n = d1 d2 ………… dm

int n, rev;
rev = 0;
while (n &lt; 0) {
  rev = rev * 10 + n % 10;
  n = n / 10;
}

The loop invariant condition at the end of the ith iteration is

  1. n = d1d2......dm−i and rev = dm dm−1......dm−i+1

  2. n = dm−i+1.....dm−1 dm or rev = dm−i .....d2d1
  3. n $\ne$ rev

  4. n = d1d2....dm or rev = dm......d2d1
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Multiple choice

A single array A [1........MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top 1 and top 2 (top 1<top 2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is

  1. (top 1= MAXSIZE/2) and (top 2 = MAXSIZE/.2+1)

  2. top 1+ top2=MAXSIZE

  3. (top 1= MAXSIZE/2) or (top2 = MAXSIZE)

  4. top 1= top 2−1

Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation