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

Let A[1,....n] be an array storing a bit (1 or 0) at each location, and f (m) is a function whose time complexity is è(m). Consider the following program fragment written in a C like language:

The complexity of this program fragment is
  1. $\Omega$(n2)
  2. $\Omega$ (nlogn) and O(n2)
  3. $\theta$(n)

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

Here the fragment of code contains for loop which goes from 1 to n. Since due to given conditions m < n. So complexity of code is $\Theta$ 6(n)

Multiple choice

Consider the following C-function:

The space complexity of the above function is foo O and store the values of foo (i),0 <= i < n, as and when they are computed. With this modification, the time complexity for function fooO is significantly reduced. The space complexity of the modified function would be:

  1. O(1)

  2. O(n)

  3. O(n2)

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

Here we store values in foo(i ) only when they are completed then in every recursion we require space to store 1 double. So overall n calls we require 0(n)

Multiple choice

Match the following. (Choose the most appropriate option) (A) S – Attributed Definition (i) Synthesized attribute (B) L _ Attributed Definition (ii) Inherited attributed

  1. A – i, B – ii

  2. A – ii, B – i

  3. A – i, B – i, B – ii

  4. A – i, B – ii, A – ii
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

In an S – attributed syntax directed translation all attributes are synthesized. In an L – attributed definition attributes may be inherited or synthesized.

Multiple choice

Which one of the following sorting algorithms is using divide and conquer method?

  1. Bubble sort

  2. Selection sort

  3. Quick sort

  4. All of the above
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Quick sort choose one element and divide the list into two. It uses divide and conquer method. A key element is chosen then it is compared and the element is placed in such a way that all smaller elements as compared to key are on one side and larger than key are on other side. Then likewise list is broken into two, again algorithm is applied.

Multiple choice

For height H and root at level 0, how many number of nodes will be there in a binary tree?

  1. 2H+1 - 1

  2. 2H-1

  3. 2H+1 + 1

  4. 2H+1
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

2H+1 - 1, gives total number of nodes present in any binary tree for tree at level 0. 2H gives the total number of nodes at any level. If root is at level zero, 2H+1 will give the same, e.g. at level 3, total no. of nodes will be 8 and total number of nodes at level 2 if root is at level 0, is 7. So this relation works here 2H+1 - 1.

Multiple choice

Insert the following elements as binary search tree, 10, 11, 12, 13, 14, 15, 16, 17 and build AVL tree.

  1. 15

  2. 14

  3. 13

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

While inserting the element make sure the difference of height of  left subtree and right sub tree must be -1, 0 and +1. Insert 10 as a root, then 11 as right child. Here, tree is balanced. Now Insert 12, tree became unbalanced as the height of left sub tree from root and right sub tree is -2, 0 = -2. So do RR rotation on tree. Now 11 is as root and 10 as left child and 12 as right child. Again insert 13 as left child of 12, then 14 right child of 13 again it unbalanced. So do again RR rotation and so on.

Multiple choice

In-order traversal of a tree will yield a sorted list of elements of tree in

  1. binary trees

  2. binary search trees

  3. heaps

  4. None of the above
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Binary search tree has all the small data in left and all big data in right. So, when inorder traversal is made, it gives sorted list. Suppose tree is having data 1, 2, 3, 4 and 5, if 3 is the root element then 4 and 5 will be on right side of the root. 1 and 2 will get place in left side of 3. So, inorder traversel of BST will give sorted elements.

Multiple choice

For height H and root at level 1, how many number of nodes will be there in a binary tree?

  1. 2H - 1

  2. 2H+1

  3. 2H+1 - 1

  4. None of the above
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

2H - 1, gives total number of nodes present in any binary tree. 2H gives the total number of nodes at any level. So for height H, total number of nodes will be one less than next level. For example at level 3, the number of nodes is 8, for height 3 the total number of nodes is 7. This is the way how this expression works.

Multiple choice

Which of the following data structures is used to perform recursion?

  1. Queue

  2. Stack

  3. Tree

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

Stack is used to perform recursion. It stores the function call in stack. then call each function in LIFO order. Let a function is called from its own body then for to track the function call, each call is pushed into stack till the end of counter then one by one each function call is executed. So, stack is a correct answer.