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

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

## Give an example of modular method.

Consider the following keys:

36475611,47566933,75669353,34547579,46483499
Assume that the size of the table is 43,the addresses of the preceding keys will be calculated as:
36475611 mod 43=1
47566933 mod 43=32
75669353 mod 43=17
34547579 mod 43=3
46483499 mod 43=26

## What operation does the Selection Sort use to move numbers from the unsorted section to the sorted section of the list?

The Selection Sort uses the swap operation since it is ordering numbers within a single list.

## Write an algorithm to insert a node in a binary search tree.

The following is the algorithm to insert a node in a binary search tree:

1. Allocate memory for the new node.
2. Assign value to the data field of new node.
3. Make the left and right child of the new node point to NULL.
4. Locate the node that will be the parent of the node to be inserted. Mark it as parent. Execute the following steps to locate the parent of the new node to be inserted:
1. Mark the root node as currentNode
2. Make parent point to NULL
3. Repeat steps ,e,and f,until currentNode becomes NULL
4. Make parent point to currentNode
5. If the value of the new node is less than that of currentNode:
1. Make currentNode point to its left child
6. If the value of the new node is greater than that of currentNode:
1. Make currentNode point to its right child
5. If parent is NULL(Tree is empty):
1. Mark the new node as ROOT
2. Exit
6. If the value in the data field of the new node is less than that of parent:
1. Make the left child of parent point to the new node
2. Exit
7. If the value in the data field of the new node is greater than that of the parent:
1. Make the right child of parent point to the new node
2. Exit

## What main properties are considered in bubble sort?

1. Stable
2. O(1) extra space
3. O(n2) comparisons and swaps
4. Adaptive: O(n) when nearly sorted

## What is the difference between a singly linked list and circular linked list?

In a singly linked list, the last node points to Null. However, in a circular linked list, the last node point to the first node of the the list, forming the circular structure.

## In which traversal method, the root is processed before traversing the left and right subtrees.

In Preorder traversal method, the root is processed before traversing the left and right sub-trees.

## What are the various steps while performing Binary Search?

To perform binary search following steps are performed: Suppose in given list we have to search element 13

1. Divide the list into two equal halves.To divide the list,you need to obtain the index of the middlemost element in the list.The index of the middlemost element is determine with the help of the following formula:
Mid=(Lower bound+Upper bound)/2
Here,lower bound(LB) is the index of the first element in the list and the Upper bound(UB) is the index of the last element in the list.
In the given list,LB is 0 and UB is 8.

Therefore,
Mid=(LB+UB)/2
Mid=(0+8)/2
Mid=4
After dividing the list,there can be three possible condition:
1. Element to be searched=middle element:If this condition holds true,the desired element is found at arr[mid]
2. Element to be searched<middle element:If this condition holds true,search the item towards the left of the middle element.
3. Element to be searched>middle element:If this condition holds true,search the element towards the right of the middle element.
In the given example,the middle element is at index 4,as shown in the following figure.
2. The element at index 4 is 25,which is greater than 13.Therefore,search the element towards the left of the middle element,that is,in the lsit arr[0] to arr[3].Here LB is 0 and the UB is equal to mid-1,as shown in the following figure.
3. Again divide the list into two halves by determining the value of Mid.
Here,
Mid=(LB+UB)/2
Mid=(0+3)/2
Mid=1
Therefore,the middle element will be at index 1,as shown in the following figure.

The element at index 1 is 13,which is the desired element.

## Write algorithm for inserting node at the beginning of Singly-Linked list, if list is not empty .

To insert a node at the beginning of the linked list algorithm is:

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 the first node in the list.
4. Make START point to the new node.

## What is the worst case space complexity of selection sort?

The worst case space complexity of selection sort is O(n) total, O(1) auxiliary.

## Give an example of Rabbit problem in bubble sort.

Array {6, 1, 2, 3, 4, 5} is almost sorted, but it takes O(n) iterations to sort it. Element {6} is a rabbit.

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