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

Which of the following is not correct about quicksort algorithm?

  1. The partition method returns the position of pivot element as it should be in the final sorted array.

  2. The average running time of quicksort is O(nlogn).

  3. Quicksort is faster than insertion sort and bubble sort.

  4. Best case running time of quicksort is O(nlogn).

  5. Worst case running time of quicksort is O(nlogn).
Reveal answer Fill a bubble to check yourself
E Correct answer
Explanation

This is incorrect, the worst case running time of quicksort is quadratic.

Multiple choice

What would come in place of two in the above algorithm?

Here is an algorithm to insert a key k in a binary search tree T.
insert(T,k)
{
int flag = 0;
node x = root[T]; i
if(x == null)
{
root = new node(k);
}
while(x != null)
{
if(x > k)
{
y = x;
x = left[x];
flag = 1;
}
else
{
y = x;
x = right[x];
flag = 2;
}
}
if(flag ==1)
{
k = ?;
}
else
{
k = ?;
}
}

  1. right[x] and left[x] respectively

  2. right[y] and left[y] respectively

  3. left[x] and right[x] respectively

  4. left[y] and right[y] respectively

  5. left[x] and left[y] respectively
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

This is correct,  since y is the parent node to null value, this will designate the new key to correct place.

Multiple choice

Given a sequence of numbers 8, 4, 9, 3, 2, 0, 11, 10 to be inserted in the tree. Which key will be visited last in the inorder traversal of the inserted keys?

Here is an algorithm to insert a key k in a binary search tree T.
insert(T,k)
{
int flag = 0;
node x = root[T];
if(x == null)
{
root = new node(k);
}
while(x != null)
{
if(x > k)
{
Y = x;
X = left[x];
flag = 1;
}
else
{
Y = x;
X = right[x];
flag = 2;
}
}
if(flag ==1)
{
K = left[y];
}
else
{
K = right[y];
}
}

  1. 10

  2. 9

  3. 11

  4. 8

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

This is correct. since with insertion and inorder traversal the rightmost key will be referred last. During insertion since 11 comes second last and only 10 comes after that which will be the left key of 11 so inorder traversal will visit 11 key only at the end.

Multiple choice

What should come in place of ? in the above algorithm?

An algorithm to delete the node/key k from a tree T is given below:
delete(T, k)
{
if(left[k] == null && right[k] == null)
{
K = null;
}
else if(left[k] != null && right[k] == null)
{
if(k == left[parent[k]]) left[parent[k]] == left[k];
else right[parent[k]] = left[k];
 }
else if(left[k] == null && right[k] != null)
{
if(k == left[parent[k]]) left[parent[k]] == right[k];
else right[parent[k]] = right[k];
 }
else Y = ?;
X = y;
Right[x] = left[y];
 }
}

  1. Treemax(T)

  2. Successor(T, k)

  3. Predecessor(T, k)

  4. Treemin(T)

  5. Root[T]
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

This is the correct answer since when both right and left child node of the node to be deleted is not null, then the predecessor of the current node should be connected to the parent node

Multiple choice

A _______ locates an item by repeatedly dividing a list in half and examining the middle element until the target value is found.

  1. bubble sort

  2. binary search

  3. sequential search

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

Binary search works by repeatedly dividing the sorted list in half and examining the middle element. If the middle element is the target, the search ends. Otherwise, the search continues in the half where the target must exist. This makes binary search extremely efficient for large datasets.

Multiple choice

A bubble sort compares _______ elements.

  1. contrasting

  2. first and last

  3. even numbered

  4. adjacent
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

Bubble sort is named because it works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they're in the wrong order. This process causes smaller values to 'bubble up' to the top of the list like bubbles rising in water, hence the algorithm's name.

Multiple choice

Which of the following statements best explains the processing of a sequential search?

  1. It searches an array by starting at the middle and working out in both the directions.

  2. It compares adjacent array elements, exchanging them if they are out of order.

  3. It searches an array from beginning to the end, until the specified element is located.

  4. It combines two sorted arrays into a single sorted array.
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Sequential search, also called linear search, examines each element in order from the beginning until it finds the target or reaches the end. It's simple but relatively slow for large lists. Unlike binary search, it doesn't require the list to be sorted beforehand.

Multiple choice

Sublists sorted independently of each other is a characteristic of a _______.

  1. bubble sort

  2. shell sort

  3. binary search

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

Shell sort improves on bubble sort by comparing elements that are far apart, then gradually reducing the gap between compared elements. This creates independent sublists that are sorted separately. The gap sequence determines how these sublists are formed and is key to the algorithm's efficiency.

Multiple choice

In a shell sort, the second gap is _______ .

  1. 1/2 the length of the array

  2. 1/2 of the first gap

  3. 1/2 of the third gap

  4. 1/2 of itself
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Shell sort uses a sequence of diminishing gaps to compare and sort elements. A common gap sequence starts with N/2, then N/4, N/8, and so on. Each successive gap is typically half the previous one, eventually reaching gap=1 which is equivalent to a final bubble sort pass.

Multiple choice

One of the conditions used to control the DO WHILE...LOOP in a binary search is that

  1. the target value should match the middle value

  2. the last element of the array should have been reached

  3. the size of the gap should be zero

  4. the size of the gap should be greater than zero
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

In a binary search algorithm implemented with a loop, the search continues as long as the search space or gap between the low and high pointers is greater than zero, meaning there are still elements to examine.

Multiple choice

Refer to the exhibit. Two routers are unable to establish an adjacency. What is the possible cause for this?

  1. The two routers are connected on a multiaccess network.

  2. The hello and dead intervals are different on the two routers.

  3. They have different OSPF router IDs.

  4. They have different process IDs.
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

OSPF routers must have matching hello and dead intervals to form an adjacency. Different intervals prevent routers from recognizing each other as valid neighbors. Process IDs are locally significant and can differ, different router IDs are expected and necessary, and multiaccess networks work fine with proper DR/BDR election.