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

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 an algorithm for inserting a node at the beginning of the circular-linked list, when the list is not empty.

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

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

To represent an arithmetic expression binary tree uses three notations which are those notations?

To represent an arithmetic expression binary tree uses three notations those are:

1. Infix notation
2. Prefix notation
3. Postfix notation

What are the various application fields where binary search trees are used?

Some of them are as follows:

1. Indexing
2. Encoding messages using Huffman tree
3. Arithmetic expression evaluation
4. Sorting data by using Heap tree

Write an algorithm to delete a node between two nodes in the circular-linked list.

The algorithm to delete a node between two nodes in the circular-linked list:

1. Locate the node to be deleted. Mark the node to deleted as current, and its predecessor as previous. To locate current and previous, execute the following steps:
   1. Make previous point to the successor of LAST
   2. Make current point to the successor of LAST
   3. Repeat steps d and e until either the node is found, or previous=LAST
   4. Make previous point to current
   5. Make current point to the next node in sequence
2. If previous=LAST:
   1. Display "Node not found"
   2. Go to Step 5
3. Make the next field of previous point to the successor of current
4. Release the memory for the node marked as current
5. Exit

Write algorithm for inserting node between two nodes in Singly-Linked list, if list is not empty .

The algorithm for inserting node between two nodes in the list is as follows:

1. Identify the nodes between which the 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 becomes greater than new node.info or current becomes equal to NULL.
   4. Make previous point to current.
   5. Make current point to the next node in sequence.
2. Allocate memory for the new node.
3. Assign value to the data field of the new node.
4. Make the next field of the new node point to current.
5. Make the next field of previous point to the new node.

Describe recursive version of linear search

Linear search can also be described as a recursive algorithm:

Write an algorithm to insert a node at the end of the doubly-linked list.

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 node marked as LAST point to the new node.
4. Make the prev field of new node point to node marked LAST.
5. Make the next field of the new node point to NULL.
6. Mark the new node as LAST.

What is the order of growth of the bubble sort algorithm?

The bubble sort algorithm has a quadratic order of growth.

What is Modular Method?

In this method, modulus operation is applied on each key. This involves dividing the key value by the size of the hash table to obtain the remainder of the division. The remainder is considered as the address of the record corresponding to the key value.