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

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. 12 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.

Write an algorithm for traversing a doubly-linked list.

It enables to traverse a list in forward as well as backward direction.

The algorithm for traversing it in forward directions as follows:
  1. Mark the first node in the list as currentNode.
  2. Repeat steps 3 and 4 until currentNode becomes NULL.
  3. Display the information contained in the node marked as currentNode.
  4. Make currentNode point to the next node in sequence.

The algorithm for traversing it in backward directions as follows:
  1. Mark the last node in the list as currentNode.
  2. Repeat steps 3 and 4 until currentNode becomes NULL.
  3. Display the information contained in the node marked as currentNode.
  4. Make currentNode point to the node preceding it .

How a circular-linked list is traversed and also write algorithm.

For traversing a circular linked-list, we need a variable/pointer to track currentNode, which initially points to the first node in the list.

The algorithm for traversing a circular linked list is as follows:
  1. Make currentNode point to the successor of the node marked as LAST, such that currentNode points to the first node in the list.
  2. Repeat step 3 and 4 until currentNode=LAST.
  3. Display the information contained in the node marked as currentNode.
  4. Make currentNode point to the next node in its sequence.
  5. Display the information contained in the node marked as LAST.

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.

What are steps for preorder traversing a binary tree?

The steps for preorder traversing a binary tree is as follows:

  1. Visit the root
  2. Traverse the left sub-tree
  3. Traverse the right sub-tree

A min heap is used to sort the list in which order?

A min heap is used to sort the list in descending order.

What is the worst case performance of binary search?

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

How is a node searched in binary search tree? Give algorithm for it.

The search operation in binary search tree refers to the process of searching for a specific value in the tree. To perform searching a node in binary search tree following algorithm is used:

  1. Make currentNode point to the root node
  2. If currentNode is null:
    1. Display "Not found"
    2. Exit
  3. Compare the value to be searched with the value of currentNode. Depending on the result of the comparison,there can be three possibilities:
    1. If the value is equal to the value of currentNode:
      1. Display "Found"
      2. Exit
    2. If the value is less than the value of currentNode:
      1. Make currentNode point to its left child
      2. Go to step 2
    3. If the value is greater than the value of currentNode:
      1. Make currentNode point to its right child
      2. Go to step 2

What are the problems in the bubble sort?

The bubble sort have Turtles and rabbits problem. Because big elements (rabbits) go up fast, while small ones (turtles) go down very slow.

How do you define singly-linked list?

Singly linked lists contain nodes which have a data field as well as a next field, which points to the next node in the linked list.

A singly linked list whose nodes contain two fields: an integer value and a link to the next node.

How is selection sort implemented ?

void selectionSort(int numbers[], int array_size)
{

    int i, j;

    int min, temp;

    for (i = 0; i < array_size-1; i++)
    {

        min = i;

        for (j = i+1; j < array_size; j++)
        {

            if (numbers[j] < numbers[min])
            {

                min = j;

            }

        }

        temp = numbers[i];

        numbers[i] = numbers[min];

        numbers[min] = temp;

    }

}


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.