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

## 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. 4 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.

## What is the worst case scenario for bubble sort, and why?

The worst situation for bubble sort is when the list's smallest element is in the last position. In this situation, the smallest element will move down one place on each pass through the list, meaning that the sort will need to make the maximum number of passes through the list, namely n - 1.

## What do mean by Linear search optimization?

If the elements you would be searching in a list are NOT uniformly distributed, then you could do certain optimizations that can help you improve the efficiency of your search algorithms. For such improvements to be effective, you do need to know the characteristics of the data being searched, the frequency and also the fact that the underlying collection needs to be modifiable.
1. Most Recently Used pattern: If the likelihood of the current element being searched again is high, then move if from it's current location (say position i) to the front of the collection (say position 0). This does require moving elements from A[0, i-1] to A[1, i] to accommodate the new element at A[0].
2. The disadvantage of the above pattern is that it requires a lot of movement. One quick strategy is to move an element up on success by simply swapping the target element from position x with the first element at position 0. This eventually results in a similar pattern as the frequently searched elements bubble up to the top of the list.
3. On the other end of the spectrum, if an element is unlikely to be search again, then moving it to the end on find improves the chances of the other elements being searched.

## What is best case efficiency of linear search?

The best case efficiency of linear search is O(1).

## Describe Mid Square Method with an example.

In this method, we square the key, and then take some digits from the middle of the number as an address of the corresponding key. Consider the given set of keys:

2636,5657,5869,4756,6079

Key (Keys)²
2636 6948496
5657 32001649
5869 34445161
4756 22619536
6079 36954241

Now, take the 4th and 5th digits from the square of each key. Then we can consider them as the address of the corresponding keys. Therefore, addresses of the given keys will be 84, 01, 45, 19 and 54.

## What is the worst case performance of binary search?

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

## How many comparisons are performed in the second pass of the selection sort algorithm?

n-2 comparisons are performed in the second pass of the selection sort algorithm.

## Write an algorithm for preorder traversing of binary tree.

Algorithm: Preorder(root)

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

## How traversing is done in a binary tree?

Traversing a tree refers to the process of visiting all the nodes of the tree once. There are three ways in which traversing is done such as

1. Inorder
2. Preorder
3. Postorder

## C program for linear search using function

```int linear_search(int*, int, int);

int main()
{

int array[100], search, c, n, position;

printf("Enter the number of elements in array\n");

scanf("%d",&n);

printf("Enter %d numbers\n", n);

for ( c = 0 ; c < n ; c++ )
{

scanf("%d",&array[c]);

}

printf("Enter the number to search\n");

scanf("%d",&search);

position = linear_search(array, n, search);

if ( position == -1 )
{

printf("%d is not present in array.\n", search);

}

else
{

printf(
"%d is present at location %d.\n", search, position+1
);

}

return 0;

}

int linear_search(int *pointer, int n, int find)
{

int c;

for ( c = 0 ; c < n ; c++ )
{

if ( *(pointer+c) == find )
{

return c;

}

}

return -1;

}

```

## Write an algorithm for inserting nodes in doubly-linked list, if the list is empty.

If the list is empty, the following algorithm is used to insert a node in the linked list:

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 NULL.
4. Make the prev field of the new node point to NULL.
5. Make START point to the new node.

## My C/C++ Videos on Youtube

Here is the complete playlist for video lectures and tutorials for the absolute beginners. The language has been kept simple so that anybody can easily understand them. I have avoided complex jargon in these videos.