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

In a bottom-up evaluation of a syntax directed definition, inherited attributes can

  1. always be evaluated

  2. be evaluated only if the definition is L-attributed

  3. be evaluated only if the definition has synthesized attributes

  4. never be evaluated
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Every S (synthesized) -attributed definitions is L- attributed. So in a bottom-up evaluation of SDD inherited attributes can be evaluated only if the definition has synthesized attributes.

Multiple choice

In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time

  1. O(n log n)

  2. O(n)

  3. O(log n)

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

Here we can follow simple procedure, we can rum heap sort for 7 iterations. In each iteration the top most element is smallest, we note & then replace it with the last element, then we run min heapify algorithm, which brings next smallest element on top. This procedure take 0 (log n) time. We need to run it for 7 times. So tight bound O(7 log n) = O(log n)

Multiple choice

Consider the syntax directed definition shown below, S $\rightarrow$ id : = E {gen (id.place = E.place;);} E $\rightarrow$ E1 + E2 {t = newtemp( ); gen(t = E1.place + E2.place;); E.place = t;} E $\rightarrow$ id {E.place = id.place;}

Here, gen is a function that generates the output code, and newtemp is a function that returns the name of a new temporary variable on every call. Assume that ti's are the temporary variable names generated by newtemp. For the statement 'X : = Y + Z', the 3-address code sequence generated by this definition is

  1. X = Y + Z

  2. t1 = Y + Z; X = t1

  3. t1 = Y; t2 = t1 + Z; X = t2

  4. t1 = Y; t2 = Z; t3 = t1 + t2; X = t3
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

In 3-address code we use temporary variables to reduce complex instructions so here $$ t_1 = Y \\ t_2 = Z \\ t_3 = t_1 + t_2 \\ x = t_3 \\ $$

Multiple choice

In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time

  1. O(n log n)

  2. O(n)

  3. O(log n)

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

Here we can follow simple procedure, we can rum heap sort for 7 iterations. In each iteration the top most element is smallest, we note & then replace it with the last element, then we run min heapify algorithm, which brings next smallest element on top. This procedure take 0 (log n) time. We need to run it for 7 times. So tight bound O(7 log n) = O(log n)

Multiple choice

The usual O(n2) implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will

  1. remain O (n2)

  2. become O (n (log n)2)

  3. become O (n log n)

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

Binary search is efficient when the sorted sequence is there, but the worst case scenario for insertion sort would not be sorted sequence so even using binary search instead of linear search the complexity of comparisons will remain O (n2)

Multiple choice

The following program fragment is written in a programming language that allows global variables and does not allow nested declarations of functions. global int i = 100, j = 5; void P(x) { int i = 10; print(x + 10); i = 200; j = 20; print (x); } main() {P(i + j);}

If the programming language uses static scoping and call by need parameter passing mechanism, the values printed by the above program are

  1. 115, 220

  2. 25, 220

  3. 25, 15

  4. 115, 105
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

In static scoping the variables are initialized at compile time only So i =100 & j =5 P(i + j) = P(100 + 5) = P(105)

So x =105 x + 10 = 105 + 10 = 115 So 115 and 105 will be printed

Multiple choice

A data structure is required for storing a set of integers such that each of the following operations can be done in O (log n) time, where n is the number of elements in the set. I. Deletion of the smallest element II. Insertion of an element if it is not already present in the set Which of the following data structures can be used for this purpose?

  1. A heap can be used but not a balanced binary search tree

  2. A balanced binary search tree can be used but not a heap

  3. Both balanced binary search tree and heap can be used

  4. Neither balanced binary search tree nor heap can be used
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Both the tasks can be performed by both the data structures but heap is a data structure where to perform these function every element has to be checked so  O (n) complexity. But the balance binary search tree is efficient data structure since at every decision it selects one of its sub tree to no. of elements to be checked are reduced by a factor of / 1 2 every time. $\dfrac{n}{2!} = x$ x = log n

Multiple choice

Let S be a stack of size n $\ge$1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations Assume that Push and Pop operations take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m $\ge$1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is

  1. n(X + Y)

  2. 3Y + 2X

  3. n(X + Y) - X

  4. Y + 2X
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

Multiple choice

Consider the function f defined below. struct item { int data; struct item * next; }; int f(struct item *p) { return ((p == NULL) || (p ->next == NULL) || ((p->data <= p -> next -> data) && f(p-> next))); } For a given linked list p, the function f returns 1 if and only if

  1. the list is empty or has exactly one element

  2. the elements in the list are sorted in non-decreasing order of data value

  3. the elements in the list are sorted in non-increasing order of data value

  4. not all elements in the list have the same data value
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation