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

Give an example of modular method.

Consider the following keys:

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(n²) 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.