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

In binary search algorithm, after every search operation, the search gets reduced by ______?

In binary search algorithm, after every search operation, the search gets reduced by 1/4.

What are steps for "in order" traversing a binary tree?

The steps for in order traversing a binary tree are as follows:

1. Traverse the left subtree
2. Visit the root
3. Traverse the right subtree

How can we rewrite the Selection Sort algorithm so that it sorts numbers from highest to lowest?

To modify the Selection Sort Algorithm so that it sorts from highest to lowest, we need to search for the largest card rather than the smallest. The modifications to the original algorithm are marked in italics.

1. Get a list of unsorted numbers
2. Set a marker for the unsorted section at the front of the list
3. Repeat steps 4 through 7 until one number remains in the unsorted section
4. Compare all unsorted numbers
5. Select the largest unsorted number
6. Swap this number with the first number in the unsorted
7. Advance the marker to the right one position
8. Stop

Is selection sort having same efficiency as bubble sort?

Yes, both have same efficiency order of growth.

How do you define binary search?

A binary search or half-interval search finds the position of a specified value (the input "key") within a sorted array. Binary search is applied only on the list which is sorted and if the list to be searched is not sorted, it needs to be sorted before binary search can be applied to it.

Write an algorithm to delete a node from a binary search tree.

The following algorithm to locate the node to be deleted and its parent:

1. Make a variable/pointer currentNode point to the ROOT node.
2. Make a variable/pointer parent point to NULL.
3. Repeat steps a,b, and c until currentNode becomes NULL or the value of the node to be searched becomes equal to that of currentNode:
   1. Make parent point to currentNode.
   2. If the value to be deleted is less than tht of currentNode:
      1. Make currentNode point to its left child.
   3. If the value to be deleted is greater than that of currentNode:
      1. Make currentNode point to its right child.

What are the various applications of linear search?

Linear search is usually very simple to implement, and is practical when the list has only a few elements, or when performing a single search in an unordered list. When many values have to be searched in the same list, it often pays to pre-process the latter in order to use a faster method.

Bubble sort is used for large or small list.

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

To insert a node at the and 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. If START is NULL,then:
   1. Make START point to the new node.
   2. Go to step 6.
4. Locate the last node in the list, and mark it as currentNode.To locate the last node in the list,execute the following steps:
   1. Mark the first node as currentNode.
   2. Repeat step c until the successor of currentNode becomes NULL.
   3. Make currentNode point to the next node in sequence.
5. Make the next field of currentNode point to the new node.
6. Make the next field of the new node point to NULL.

Write an algorithm to convert a binary tree into heap.

The following algorithm to convert a binary tree into heap:

1. Set i=(n-1)/2
2. Set j=2i+1
3. Let heap=False
4. Compare the value at index j with the value of its sibling at index j+1:
   1. If A[j+1]>A[j]:
   2. j=j+1
5. If A[j]>A[(j-1)/2]:

Swap A[j] with A[(j-1)/2
j=2j+1
Else
heap=True
6. If((n>j) or(heap=False)),repeat step 4,5, and 6
7. Decrement i by 1
8. If(i>=),repeat steps 2 through 8