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

## 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. 5 in this series.

Last Reviewed and Updated on February 7, 2020

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

## Write an algorithm for bubble sort.

1. Set pass=1
2. Repeat step 3 varying j from 0 to (n - 1 - pass).
3. If the element at index j is greater than the element at index j+1, swap the two elements.
4. Increment pass by 1.
5. If (pass <= n="" -="" 1)="" go="" to="" step="">

## What is worst case and average case of bubble sort algorithm?

Worst case = O(n2) and average case = O(n2).

## How do we define bubble sort?

Bubble sort repeatedly scan the list, comparing adjacent elements swapping them if they are in wrong order. ## Write an algorithm to search for an employee ID in an array(Hint: use linear search)

1. Read the employee ID to be searched
2. Set i=0
3. Repeat step d until i>n or arr[i]=employee ID
4. Increment i by 1
5. If i>n : Display "Not found"
Else Display "Found"

## Write an algorithm fo deleting a node between two nodes in the doubly-linked list.

The algorithm to delete a node between two nodes in the list is as follows:

1. Make the node to be deleted as current and its predecessor as previous. To locate previous and current, execute the following steps:
1. Make previous point to NULL.
2. Make current point to the first node in the linked list.
3. Repeat steps d and e until either the node is found or current becomes NULL.
4. Make previous point to current.
5. Make current point to the next node in sequence.
2. Make the next field of previous point to the successor of current
3. Make the prev field of the successor of current point to previous
4. Release the memory of the node marked as current.

## Write an algorithm to delete a node from the end of the circular -linked list.

The algorithm to delete a node from the end of the circular -linked list:

1. Make current point to LAST.
2. mark the predecessor of LAST as previous. To locate the predecessor of LAST execute the following steps:
1. Make previous point to the successor of LAST.
2. Repeat step c until the successor of previous becomes LAST.
3. Make previous point to the next node in sequence.
3. Make the next field of previous point to successor of LAST.
4. Mark previous as LAST.
5. Release the memory of node marked as current.

## What is best case performance of bubble sort algorithm?

The best case performance of bubble sort algorithm is O(n).

## Write an algorithm to insert a node between two nodes in the list, when the list is not empty.

If the list is not empty, the following algorithm is used to insert a node between two nodes in the linked list.

1. Identify the nodes between which th new node is to be inserted. Mark them as previous and current. To locate previous and current, execute the following steps:
1. Make current point to the first node.
2. Make previous point to NULL.
3. Repeat step d and e until current.info>newnode.info or previous=LAST
4. Make previous point to current.
5. Make current point to the next node in sequence.
2. Allocate a memory fo new node.
3. Assign a value to the data field of the new node.
4. Make the next field of new node point to current.
5. Make the next field of previous point to the new node.

## Write Code for bubble sort in java

```public void bubbleSort(int[] arr)
{

boolean swapped = true;

int j = 0;

int tmp;

while (swapped)
{

swapped = false;

j++;

for (int i = 0; i < arr.length - j; i++)
{

if (arr[i] > arr[i + 1])
{

tmp = arr[i];

arr[i] = arr[i + 1];

arr[i + 1] = tmp;

swapped = true;

}

}

}

}

```

## Draw the structure of a linked list. first part represent data and second part represent address of next 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.