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

What is the worst case scenario for bubble sort, and why?

What do mean by Linear search optimization?

1. Most Recently Used pattern: If the likelihood of the current element being searched again is high, then move if from it's current location (say position i) to the front of the collection (say position 0). This does require moving elements from A[0, i-1] to A[1, i] to accommodate the new element at A[0].
   
2. The disadvantage of the above pattern is that it requires a lot of movement. One quick strategy is to move an element up on success by simply swapping the target element from position x with the first element at position 0. This eventually results in a similar pattern as the frequently searched elements bubble up to the top of the list.
   
3. On the other end of the spectrum, if an element is unlikely to be search again, then moving it to the end on find improves the chances of the other elements being searched.

What is best case efficiency of linear search?

The best case efficiency of linear search is O(1).

Describe Mid Square Method with an example.

In this method, we square the key, and then take some digits from the middle of the number as an address of the corresponding key. Consider the given set of keys:

What is the worst case performance of binary search?

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

How many comparisons are performed in the second pass of the selection sort algorithm?

n-2 comparisons are performed in the second pass of the selection sort algorithm.

Write an algorithm for preorder traversing of binary tree.

Algorithm: Preorder(root)

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

How traversing is done in a binary tree?

Traversing a tree refers to the process of visiting all the nodes of the tree once. There are three ways in which traversing is done such as

1. Inorder
2. Preorder
3. Postorder

C program for linear search using function

int linear_search(int*, int, int);

int main()
{

    int array[100], search, c, n, position;

    printf("Enter the number of elements in array\n");

    scanf("%d",&n);

    printf("Enter %d numbers\n", n);

    for ( c = 0 ; c < n ; c++ )
    {

        scanf("%d",&array[c]);

    }

    printf("Enter the number to search\n");

    scanf("%d",&search);

    position = linear_search(array, n, search);

    if ( position == -1 )
    {

        printf("%d is not present in array.\n", search);

    }

    else
    {

        printf(
        "%d is present at location %d.\n", search, position+1
        );

    }

    return 0;

}

int linear_search(int *pointer, int n, int find)
{

    int c;

    for ( c = 0 ; c < n ; c++ )
    {

        if ( *(pointer+c) == find )
        {

            return c;

        }

    }

    return -1;

}

Write an algorithm for inserting nodes in doubly-linked list, if the list is empty.

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

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 NULL.
4. Make the prev field of the new node point to NULL.
5. Make START point to the new node.