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

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.

Write an algorithm for inserting node at the beginning of the doubly-linked list, when list is not empty.

1. Allocate memory for the new node.
2. Assign a value to the data field of the new node.
3. Make the next field of the new point to the first node in the list.
4. Make the prev field of START point to the new node.
5. Make the prev field of the new node point to NULL.
6. Make START point to the new node.

Write an algorithm for in order traversing of binary tree.

Algorithm:Inorder(root)

1. If(root=NULL): Exit
2. Inorder(left child of root)
3. Visit(root)
4. Inorder(right child of root)

Write an algorithm to insert a node at the end of the list, when the list is not empty.

The algorithm for inserting a node at the end of the list as follows:

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 successor of LAST.
4. Make the next field of LAST point to new node.
5. Make LAST point to the new node.

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

What is average case performance of binary search?

The average case performance of binary search is O(log n).

What do you mean by linked list?

Linked lists are flexible data structure that provide a convenient way to store data. In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.

Sort an Array with C++

{

    30, 50, 20, 10, 40
}

const int nSize = 5;

int anArray[nSize] = { 30, 50, 20, 10, 40 };

void main()
{

    // Step through each element of the array
    for (int nStartIndex = 0; nStartIndex < nSize; nStartIndex++)
    {

        // nSmallestIndex is the index of the smallest element
        // we've encountered so far.
        int nSmallestIndex = nStartIndex;

        // Search through every element starting at nStartIndex+1
        for (
        int nCurrentIndex = nStartIndex + 1;

        nCurrentIndex < nSize;

        nCurrentIndex++
        )
        {

            // If the current element is smaller
            // than our previously found smallest
            if (anArray[nCurrentIndex] < anArray[nSmallestIndex])
            // Store the index in nSmallestIndex
            {

                nSmallestIndex = nCurrentIndex;

            }

        }

        // Swap our start element with our smallest element
        swap(anArray[nStartIndex], anArray[nSmallestIndex]);

    }

}

Another Variation of the above question: Rewrite the selection sort code above to sort in descending order (largest numbers first).

If (anArray[nCurrentIndex] < anArray[nSmallestIndex])

if (anArray[nCurrentIndex] > anArray[nSmallestIndex])

const int nSize = 5;

int anArray[nSize] = { 30, 50, 20, 10, 40 };

void main()
{

    // Step through each element of the array
    for (int nStartIndex = 0; nStartIndex < nSize; nStartIndex++)
    {

        // nLargestIndex is the index of the smallest element
        // we've encountered so far.
        int nLargestIndex = nStartIndex;

        // Search through every element starting at nStartIndex+1
        for (
        int nCurrentIndex = nStartIndex + 1;

        nCurrentIndex <

        nSize; nCurrentIndex++
        )
        {

            // If the current element is smaller
            // than our previously found smallest
            if (anArray[nCurrentIndex] < anArray[nLargestIndex])
            {

                // Store the index in nLargestIndex
                nLargestIndex = nCurrentIndex;

            }

        }

        // Swap our start element with our smallest element
        swap(anArray[nStartIndex], anArray[nLargestIndex]);

    }

}

Write an algorithm for selection sort.

1. Repeat step 2 and 3 varying j from 0 to n-2 //Repeat for n-1 passes
2. Find the index of the minimum value in arr[j] to arr[n-1]
   1. Set min_index=j
   2. Repeat step c varying i from j+1 to n-1
   3. If arr[i]<arr[min_index]: min_index = i
3. swap arr[j] with arr[min_index]

Write algorithm for binary search for a desired element.

The following algorithm is used for binary search:

1. Accept the element to be searched
2. Set lowerbound=0
3. Set upperbound=n-1
4. Set mid=(lowerbound+upperbound)/2
5. If arr[mid]=desired element:
   1. Display "Found"
   2. Go to step 10
6. If desired element<arr[mid]:
   1. Set upperbound=mid-1
7. If desired element>arr[mid]:
   1. Set lowerbound=mid+1
8. If lowerbound ≤upperbound:
   1. Go to step 4
9. Display "Not Found"
10. Exit