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 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

Multiple choice

If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?

  1. L is necessarily finite

  2. L is regular but not necessarily finite

  3. L is context free but not necessarily regular

  4. L is recursive but not necessarily context free
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Since L can be effectively enumerated so L has to be regular, but is doesn't mean that the decisions are finite.

Multiple choice

Nobody knows yet if P = NP. Consider the language L defined as follows.

$$L = \begin{cases} (0 +1)^* \text { if } (P = NP) \in E \\ \phi \text{ otherwise} \end{cases}$$

Which of the following statements is true?

  1. L is recursive

  2. L is recursively enumerable but not recursive

  3. L is not recursively enumerable

  4. Whether L is recursive or not will be known after we find out if P = NP
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

A language L is said to be recursive if there exists any rule to determine whether an element belong to language or not, if language can be accepted by turning machine. So there exist the rules so L is recursive.

Multiple choice

Given two arrays of numbers a1,..........., an and b1,............, bn where each number is 0 or 1, the fastest algorithm to find the largest span (i, j ) such that ai + ai+1 + .........+ aj = bi + bi + 1 +...........+ bj or report that there is not such span,
  1. Takes O (3n) and $\Omega$(2n) time if hashing is permitted
  2. Takes O (n3) and $\Omega$ (n2.5) time in the key comparison model
  3. Takes $\odot$ (n3) time and space
  4. Takes O ($\sqrt{n}$) time only if the sum of the 2n elements is an even number
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Multiple choice

Consider two cache organizations: The first one is 32 KB 2-way set associative with 32- byte block size. The second one is of the same size but direct mapped. The size of an address is 32 bits in both cases. A 2-to-1 multiplexer has a latency of 0.6 ns while a k - bit comparator has a latency of k /10 ns. The hit latency of the set associative organization is h1 while that of the direct mapped one is h2.

The value of h1 is:

  1. 2.4 ns

  2. 2.3 ns

  3. 1.8 ns

  4. 1.7 ns
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Multiple choice

Consider two cache organizations: The first one is 32 KB 2-way set associative with 32- byte block size. The second one is of the same size but direct mapped. The size of an address is 32 bits in both cases. A 2-to-1 multiplexer has a latency of 0.6 ns while a k - bit comparator has a latency of k /10 ns. The hit latency of the set associative organization is h1 while that of the direct mapped one is h2.

The value of h2 is:

  1. 2.4 ns

  2. 2.3 ns

  3. 1.8 ns

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

Multiple choice

A CPU has a 32 KB direct mapped cache with 128-byte block size. Suppose A is a two dimensional array of size 512×512 with elements that occupy 8-bytes each. Consider the following two C code segments, P1 and P2. P1: for (i=0; i<512; i++) { for (j=0; j<512; j++) { x +=A[i] [j]; } } P2: for (i=0; i<512; i++) { for (j=0; j<512; j++) { x +=A[j] [i]; } } P1 and P2 are executed independently with the same initial state, namely, the array A is not in the cache and i, j, x are in registers. Let the number of cache misses experienced by P1 be M1 and that for P2 be M2 .

The value of the ratio $\dfrac{M_1}{M_2}$

  1. 0
  2. $\dfrac{1}{16}$
  3. $\dfrac{1}{8}$

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

Multiple choice

Consider the following C-function in which a [n] and b [m] are two sorted integer arrays and c [n + m ] be another integer array.

void xyz (int a[ ], int b [ ], int c [ ]) {
  int i, j, k;
  i=j=k=0;
  while ((i &lt; n) &amp;&amp; (j &lt; m))
     if (a[i] &lt; b[j]) c[k++] = a[i++];
     else c[k++] = b[j++];
}

Which of the following condition(s) hold(s) after the termination of the while loop?

  1. only (i)

  2. only (ii)

  3. either (i) or (ii) but not both

  4. neither (i) nor (ii)
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

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