# Questions on various Topics of Data Structures(Randomly Mixed) Set 10

## Interview questions on binary search, bubble sort, linear search, linked lists, selection sort and trees in data structures. These questions have been arranged in random order. The questions are meant for a fresher preparing for a job interview. Please inform us if you find any mistakes. This is subjective type short answers question and answer set no. 10 in this series.

Last Reviewed and Updated on February 7, 2020
Posted by Parveen(Hoven),
Aptitude Trainer and Software Developer

## Interview and Exam Questions and Answers

This set contains a list of commonly asked questions. They are short interview questions aimed at freshers interview, campus placement drives, and also for job interviews. You can use these to have a quick grasp and brush-up of your fundamentals. These questions can be viewed on a mobile phone also because this website is built on responsive web design.

## In binary search algorithm, after every search operation, the search gets reduced by ______?

In binary search algorithm, after every search operation, the search gets reduced by 1/4.

## Write an algorithm for inserting node at the beginning of the doubly-linked list, when list is not empty.

1. Allocate memory for the new node.
2. Assign a value to the data field of the new node.
3. Make the next field of the new point to the first node in the list.
4. Make the prev field of START point to the new node.
5. Make the prev field of the new node point to NULL.
6. Make START point to the new node.

## Write an algorithm for in order traversing of binary tree.

Algorithm:Inorder(root)

1. If(root=NULL): Exit
2. Inorder(left child of root)
3. Visit(root)
4. Inorder(right child of root)

## Write an algorithm to insert a node at the end of the list, when the list is not empty.

The algorithm for inserting a node at the end of the list as follows:

1. Allocate memory for the new node.
2. Assign value to the data field of the new node
3. Make the next field of the new node point to successor of LAST.
4. Make the next field of LAST point to new node.
5. Make LAST point to the new node.

## Write an algorithm to convert a binary tree into heap.

The following algorithm to convert a binary tree into heap:

1. Set i=(n-1)/2
2. Set j=2i+1
3. Let heap=False
4. Compare the value at index j with the value of its sibling at index j+1:
1. If A[j+1]>A[j]:
2. j=j+1
5. If A[j]>A[(j-1)/2]:

6. Swap A[j] with A[(j-1)/2
j=2j+1
Else
heap=True
7. If((n>j) or(heap=False)),repeat step 4,5, and 6
8. Decrement i by 1
9. If(i>=),repeat steps 2 through 8

## What is average case performance of binary search?

The average case performance of binary search is O(log n).

## What do you mean by linked list?

Linked lists are flexible data structure that provide a convenient way to store data. In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.

## Sort an Array with C++

```{

30, 50, 20, 10, 40
}

```
THIS IS A SCHEMATIC SOLUTION
```const int nSize = 5;

int anArray[nSize] = { 30, 50, 20, 10, 40 };

void main()
{

// Step through each element of the array
for (int nStartIndex = 0; nStartIndex < nSize; nStartIndex++)
{

// nSmallestIndex is the index of the smallest element
// we've encountered so far.
int nSmallestIndex = nStartIndex;

// Search through every element starting at nStartIndex+1
for (
int nCurrentIndex = nStartIndex + 1;

nCurrentIndex < nSize;

nCurrentIndex++
)
{

// If the current element is smaller
// than our previously found smallest
if (anArray[nCurrentIndex] < anArray[nSmallestIndex])
// Store the index in nSmallestIndex
{

nSmallestIndex = nCurrentIndex;

}

}

// Swap our start element with our smallest element
swap(anArray[nStartIndex], anArray[nSmallestIndex]);

}

}

```

### Another Variation of the above question: Rewrite the selection sort code above to sort in descending order (largest numbers first).

Simply change:
```If (anArray[nCurrentIndex] < anArray[nSmallestIndex])
```
to
```if (anArray[nCurrentIndex] > anArray[nSmallestIndex])
```
nSmallestIndex should probably be renamed nLargestIndex as well.
```const int nSize = 5;

int anArray[nSize] = { 30, 50, 20, 10, 40 };

void main()
{

// Step through each element of the array
for (int nStartIndex = 0; nStartIndex < nSize; nStartIndex++)
{

// nLargestIndex is the index of the smallest element
// we've encountered so far.
int nLargestIndex = nStartIndex;

// Search through every element starting at nStartIndex+1
for (
int nCurrentIndex = nStartIndex + 1;

nCurrentIndex <

nSize; nCurrentIndex++
)
{

// If the current element is smaller
// than our previously found smallest
if (anArray[nCurrentIndex] < anArray[nLargestIndex])
{

// Store the index in nLargestIndex
nLargestIndex = nCurrentIndex;

}

}

// Swap our start element with our smallest element
swap(anArray[nStartIndex], anArray[nLargestIndex]);

}

}

```

## Write an algorithm for selection sort.

1. Repeat step 2 and 3 varying j from 0 to n-2 //Repeat for n-1 passes
2. Find the index of the minimum value in arr[j] to arr[n-1]
1. Set min_index=j
2. Repeat step c varying i from j+1 to n-1
3. If arr[i]<arr[min_index]: min_index = i
3. swap arr[j] with arr[min_index]

## Write algorithm for binary search for a desired element.

The following algorithm is used for binary search:

1. Accept the element to be searched
2. Set lowerbound=0
3. Set upperbound=n-1
4. Set mid=(lowerbound+upperbound)/2
5. If arr[mid]=desired element:
1. Display "Found"
2. Go to step 10
6. If desired element<arr[mid]:
1. Set upperbound=mid-1
7. If desired element>arr[mid]:
1. Set lowerbound=mid+1
8. If lowerbound ≤upperbound:
1. Go to step 4