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

Post order traversal of a given binary search tree, T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29

Which one of the following sequences of keys can be the result of an in order traversal of the tree T?

  1. 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95

  2. 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29

  3. 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95

  4. 95, 50, 60, 40, 27, 23, 22, 25, 10, 0, 15, 29
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

When we are given any no elements & even any order (preorder or post order) & we need to calculate in order, then in order is simply sorted sequence of the elements. Here 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95

Multiple choice

A program P reads in 500 integers in the range (0, 100) representing the scores of 500 students. It then prints the frequency of each score above 50. What be the best way for P to store the frequencies?

  1. An array of 50 numbers

  2. An array of 100 numbers

  3. An array of 500 numbers

  4. A dynamically allocated array of 550 numbers
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Here the no. readable are range 0 to 100 but the output of the program is interested in scores above 50 so there are 50 values (51 to 100) in this range. So only an array 50 integers required as we get any no. we increment the value stored at index.Array [x − 50] by

Multiple choice

Consider a file of 16384 records. Each record is 32 bytes long and its key field is of size 6 bytes. The file is ordered on a non-key field and the file organisation is unspanned. The file is stored in a file system with block size 1024 bytes and the size of a block pointer is 10 bytes. If the secondary index is built on the key field of the file and a multi-level index scheme is used to store the secondary index, then the numbers of first-level and second-level blocks in the multi-level index are respectively

  1. 8 and 0

  2. 128 and 6

  3. 256 and 4

  4. 512 and 5
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Multiple choice

The following key values are inserted into a B+ - tree in which order of the internal nodes is 3, and that of the leaf nodes is 2, in the sequence given below. The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that can be stored in it. The B+ - tree is initially empty. 10, 3, 6, 8, 4, 2, 1 The maximum number of times leaf nodes would get split as a result of these insertions is

  1. 2

  2. 3

  3. 4

  4. 5
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Multiple choice

Which one of the following is a key factor for preferring B+-trees to binary search trees for indexing database relation?

  1. Database relations have a large number of records.

  2. Database relations are sorted on the primary key.

  3. B+-trees require less memory than binary search trees.

  4. Data transfer from disks is in blocks.
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

B+ tree's each node size is kept almost the same to the block size of the system. This causes record data transfer from disk to memory one block at a time.

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

Which of the following is true?

  1. The complement of a recursive language is recursive.

  2. The complement of a recursively enumerable language is recursively enumerable.

  3. The complement of a recursive language is either recursive or recursively enumerable.

  4. The complement of a context-free language is context-free.
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

A recursive language has complement & its complement is also recursive. Whereas complement of others is not recursive

Multiple choice

Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is true?
  1. $\bar L_1$ is recursive and $\bar L_2$ is recursively enumerable
  2. $\bar L_1$ is recursive and $\bar L_2$ is not recursively enumerable
  3. $\bar L_1$ and L2 are recursively enumerable
  4. $\bar L_1$ is recursively enumerable and $\bar L_2$ is recursive
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

The rules here used will be. All those languages which are recursive their complements are also recursive. So option (1) & (2) can be correct. Now languages which are recursively enumerable but not recursive, their complements can't be recursively enumerable. So only option (2) is correct

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)