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

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

Why use sequential search?

  1. If your collection size is relatively small and you would be performing this search relatively a few times, then this might an option.
  2. Another case is when you need to have constant insertion performance (like using a linked list) and the search frequency is less.
  3. In addition, linear search places very few restrictions on the complex data types. All that is needed is a match function of sorts.

Which are the basic steps for performing selection sort?

There are basically two steps perform during selection sort:

  1. Find smallest element in unsorted portion from list or array.
  2. Interchange the smallest element with the one at the front of the unsorted portion

What is truncation method?

This method is used to compute the address of a record. In this method, a part of the numeric key is considered as an offset address of the corresponding record.

Linear search is special case of which search.

Linear search is special case of brute-force search.

How do you define linear search ?

Linear or sequential search is a method for finding a particular value in a list that consists of checking every one of its elements, one at a time and in sequence, until the desired one is found.

How many Comparisons would be Required?

Consider the following lists of partially sorted numbers. The double bars represent the sort marker. For each list state how many comparisons and swaps are needed to sort the next number.

  1. [1 3 4 6 7 || 9 8]
  2. [1 2 4 5 8 || 9]
  3. [1 3 || 4 9 6 8
  4. [|| 9 2 3 8 1 6 4]
  5. [2 3 4 || 9 8 7 6 5]

Answer:

  1. comparisons = 0, swaps = 1
  2. comparisons = 0, swaps = 0
  3. comparisons = 3, swaps = 0
  4. comparisons = 6, swaps = 1
  5. comparisons = 4, swaps = 1

What operations are implemented in a linked list?

Various operations implemented on a linked list are insert, delete, traverse and search.

How can the efficiency of bubble sort algorithm be determined?

The efficiency of bubble sort algorithm can be determined in terms of the number of comparisons.

What is the worst case complexity of binary search?

The worst case complexity of binary search is O(1).

Sort the following array with bubble sort

Index -> 0 1 2 3 4
arr -> 5 2 6 7 3
In Pass 1, following steps are performed:
  1. Compare arr[0] with arr[1]. In the given list, arr[0]>arr[1],therefore, you need to interchange the two values. The resultant list is shown in following fig:
    Index -> 0 1 2 3 4
    arr -> 2 5 6 7 3
  2. Compare arr[1] with arr[2].Here arr[1]<arr[2],therefore, the values remain unchanged.
  3. Compare arr[2] with arr[3].Here arr[2]<arr[3] ,therefore, the values remain unchanged.
  4. Compare arr[3] with arr[4]. In the given list, arr[3]>arr[4],therefore, you need to interchange the two values. The resultant list is shown in following fig:
    Index -> 0 1 2 3 4
    arr -> 2 5 6 3 7
At the end of pass 1,the largest element is placed at the last index position. The preceding process will be repeated in all the subsequent passes. In Pass 2, following steps are performed:
  1. Compare arr[0] with arr[1].Here arr[0]<arr[1],therefore, the values remain unchanged.
  2. Compare arr[1] with arr[2].Here arr[1]<arr[2],therefore, the values remain unchanged.
  3. Compare arr[2] with arr[3]. In the given list, arr[2]>arr[3],therefore, you need to interchange the two values. The resultant list is shown in following fig:
    Index -> 0 1 2 3 4
    arr -> 2 5 3 6 7
At the end of pass 2, the second largest element is placed at its correct position. The preceding process will be repeated in all the subsequent passes. The result after pass 3 would be as follows:
Index -> 0 1 2 3 4
arr -> 2 3 5 6 7
Now the above array is sorted.

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.