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

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

What is worst case space complexity of bubble sort algorithm?

O(1) auxiliary.

What is worst case efficiency of linear search?

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

Write code in java for selection sort algorithm

public void selectionSort(int[] arr)
{

    int i, j, minIndex, tmp;

    int n = arr.length;

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

        minIndex = i;

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

            if (arr[j] < arr[minIndex])
            {

                minIndex = j;

            }

            if (minIndex != i)
            {

                tmp = arr[i];

                arr[i] = arr[minIndex];

                arr[minIndex] = tmp;

            }

        }

    }

}


What is the best case efficiency of binary search?

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

What is the complexity of the bubble sort algorithm?

The complexity is O(n2). The time required to execute the bubble sort algorithm is proportional to (n2), where n is the number of input items.

What is the mathematical definition of selection sort?

We define selection sort mathematically:

Let L be a non-empty set and such that f(L) = L' where:
  1. L' is a permutation of L,
  2. for all and
  3. s is the smallest element of L, and
  4. Ls is the set of elements of L without one instance of the smallest element of L.

Which are the two principle criteria for selecting a hash function?

Two principle criteria for selecting a hash function are:

  1. It should be easy and quick to compute.
  2. It should achieve a uniform distribution of keys in address space.

How can a binary tree be represented as a array?

Consider the binary tree with the nodes labeled from 0 to 6,as shown in the following figure.


In the preceding binary tree, the node labeled x will be stored at index x in the array. Consider the array representation of preceding binary tree, as shown in the following figure.

For any node with index i, n-1>i>0,the following holds true:
  1. Parent of i is at index(i-1)/2
  2. Left child of i is at index 2i+1. If 2i+1>n-1 there is no left child.
  3. Right child of i is at index 2i+2. If 2i+2>n-1 there is no right child

Do bubble sort and selection sort have quadratic order of growth?

Yes, bubble sort and selection sort have quadratic order of growth.

List some techniques that are used to design a hash function?

There are various techniques that can be used to design the hash function:

  1. Truncation Method
  2. Modular Method
  3. Mid Square Method
  4. Folding Method

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.