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

While implementing the bubble sort algorithm, how many comparisons will performed in Pass 1?

n - 1 comparisons.

How do you define selection sort?

Selection sort scans through the list iteratively, selecting one item in each scan, and moving the item to its correct position in the list.

NOTE: Iteratively means one by one. It can also be called 'in a loop'.

Write an algorithm to delete a node from the beginning of a circular list.

The algorithm to delete a node from beginning of the list:

1. If the node to be deleted is the only node in the list:
   1. Mark LAST as NULL
   2. Exit
2. Make current point to the successor of LAST.
3. Make the next field of LAST point to the successor of current
4. Release the memory for the node marked as current

Define these Terms.

How do you define terms:

1. Leaf node
2. Subtree
3. Children of a node
4. Degree of a node
5. Edge

1. Leaf Node:Anode with no children is called leaf node. They are also referred as terminal nodes. In the given figure,2,5,11 and 4 are leaf nodes
2. Subtree: A portion of a tree, which can be viewed as tree in itself,is called subtree. In preceding figure the tree starting at node 7, containing nodes 2 and 6.A subtree can also contain just one node called the leaf node. In other words, all the leaf nodes are subtrees but all the subtrees are not leaf nodes
3. Children of a node: The roots of the subtrees of a node are called the children of the node. In figure 7 and 3 are children of node 1.
4. Degree of a node: The number of subtrees of a node is called the degree of a node.in given :
   1. Degree of node 1 is 2
   2. Degree of node 7 is 2
   3. Degree of node 3 is 1
5. Edge: A link from the parent to the child node is referred to as edge. It is also known as a branch. A tree with n nodes has n-1 edges.

Which are the various variants of binary tree?

Various variants of binary tree are:

1. Strictly binary tree: A binary tree is said to be strictly binary if every node, except for the leaf nodes, have non-empty left and right children. A strictly binary tree is shown in following figure:

   
   In the preceding binary tree, every non-leaf node has precisely two children. Therefore, it is strictly binary tree.

2. Full binary tree: A binary tree of depth d is said to be a full binary tree if it has exactly 2^d-1
3. Complete binary tree: A binary tree with n nodes and depth d is complete if and only if its nodes correspond to the nodes numbered from 0 to n-1 in the full binary tree of depth k. A complete binary tree is shown in the following figure:

   

Sort the following array

{

    30, 50, 20, 10, 40
}

Answer:

1. We find the smallest element, starting from index 0:

   { 30, 50, 20, 10 , 40 }

2. We then swap this with the element at index 0:

   { 10 , 50, 20, 30 , 40 }

3. Now that the first element is sorted, we can ignore it. Consequently, we find the smallest element, starting from index 1:

   { 10, 50, 20 , 30, 40 }

4. And swap it with the element in index 1:

   { 10, 20 , 50 , 30, 40 }

5. Find the smallest element starting at index 2:

   { 10, 20, 50, 30 , 40 }

6. And swap it with the element in index 2:

   { 10, 20, 30 , 50 , 40 }

7. Find the smallest element starting at index 3:

   { 10, 20, 30, 50, 40  }

8. And swap it with the element in index 3:

   { 10, 20, 30, 40 , 50  }

9. Finally, find the smallest element starting at index 4:

   { 10, 20, 30, 40, 50  }

10. And swap it with the element in index 4 (which doesn't do anything):

    { 10, 20, 30, 40, 50  }

11. Done!

Write Code for bubble sort in C++

void bubbleSort(int arr[], int n)
{

    bool swapped = true;

    int j = 0;

    int tmp;

    while (swapped)     {
    swapped = false;

    j++;

    for (int i = 0; i < n - j; i++)
    {

        if (arr[i] > arr[i + 1])
        {

            tmp = arr[i];

            arr[i] = arr[i + 1];

            arr[i + 1] = tmp;

            swapped = true;

        }

    }

}

What is the best case performance of selection sort?

The best case performance of selection sort is O(n²).

How can a binary tree be represented as a linked list?

What do you mean by Binary tree?

A binary tree is a specific type of tree in which each node can have a maximum of two children. These child nodes are typically distinguished as the left and the right child. The structure of a binary tree is shown in the following figure: