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

Interview questions on binary search, bubble sort, linear search, linked lists, selection sort and trees in data structures. These questions have been arranged in random order. The questions are meant for a fresher preparing for a job interview. Please inform us if you find any mistakes. This is subjective type short answers question and answer set no. 14 in this series.

Last Reviewed and Updated on February 7, 2020
Posted by Parveen(Hoven),
Aptitude Trainer and Software Developer

Interview and Exam Questions and Answers

This set contains a list of commonly asked questions. They are short interview questions aimed at freshers interview, campus placement drives, and also for job interviews. You can use these to have a quick grasp and brush-up of your fundamentals. These questions can be viewed on a mobile phone also because this website is built on responsive web design.

Give some examples where binary search could be used?

The examples of binary search are:

  1. Number guessing game
  2. Word lists
  3. Applications to complexity theory

Is this code for bubble sort or not ?

void DoBubbleSort ()
{

    int s,t, numItems = 10;

    for(s=(numItems - 1); s >=0; s--)
    {

        for(t=1;t<=s;t++)
        {

            if(arr[t-1]>arr[t])
            {

                temp=arr[t-1];

                arr[t-1]=arr[t];

                arr[t]=temp;

            }

        }

    }

}

Yes, the code is for bubble sort.

Write pseudo code to search the array in the reverse order, returning 0 when the element is not found.

  1. Set i to n.
  2. Repeat this loop
    1. If i <= 0,="" then="" exit="" the="">
    2. If A[i] = x, then exit the loop.
    3. Set i to i - 1.
  3. Return i

How singly-linked list is represented in a program?

A linked list is represented in a program by defining two classes:

a) Node class: A node is the basic building block in a linked list.The Node class represents a node in a linked list

b) List class: This class consists of a set of operations implemented on a linked list. These operations are insertion, deletion, search, and traversal.

What is the average case performance of selection sort?

The average case performance of selection sort is O(n2).

Write an algorithm for deleting a node from the beginning of the doubly linked list.

The algorithm to delete a node from the beginning of the list is as follows:
  1. Mark the first node in the list as current.
  2. Make START point to the next node in its sequence.
  3. If START is not NULL:
    1. Assign NULL to the prev field of the node marked as START.
  4. Release the memory of the node marked as current.

What simple modification could be made to the bubble sort algorithm that would make it perform more efficiently on the case described above?

The algorithm could be made to start at the end of the list and move towards the front, swapping elements only if the first is greater than the second. In this way, the smallest numbers would bubble down instead of the large numbers bubbling up. Note however that this algorithm has its own worst case scenario that is just as bad as the worst case for the normal bubble sort. It occurs when the list's largest element is in the first position.

Give an example of Turtle problem in bubble sort.

Though, array {2, 3, 4, 5, 1} is almost sorted, it takes O(n2) iterations to sort an array. Element {1} is a turtle.

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

Write an algorithm for traversing a singly-linked list

The algorithm for traversing a singly-linked list is as follows:

  1. Make currentNode point to the first node in the list.
  2. Repeat step 3 and 4 until currentNode becomes NULL.
  3. Display the information contained in the node marked as currentNode.
  4. Make currentNode point to thr next node in sequence.

My C/C++ Videos on Youtube

Here is the complete playlist for video lectures and tutorials for the absolute beginners. The language has been kept simple so that anybody can easily understand them. I have avoided complex jargon in these videos.