Sorting Data Structure Practice Questions

Featured

September 14, 2023 in Data Structure

Sorting Data Structure Practice Questions

  1. Write an algorithm to implement Bubble sort with suitable example.
  2. Explain any two techniques to overcome hash collision.
  3. Write an algorithm to implement insertion sort with suitable example.
  4. Write an algorithm to implement selection sort with suitable example.
  5. Write an algorithm to implement radix sort with suitable example.
  6. Write an algorithm for binary search with suitable example.
  7. Discuss the common collision resolution strategies used in closed hashing system.
  8. Given the input { 4371, 1323, 6173, 4199, 4344, 9679, 1989 } and a hash function of h(X)=X (mod 10) show the resulting:
    a. Separate Chaining hash table
    b. Open addressing hash table using linear probing
  9. Explain Re-hashing and Extendible hashing.
  10. Show the result of inserting the keys 2,3,5,7,11,13,15,6,4 into an initially empty extendible hashing data structure with M=3. (8) (Nov 10)
  11. what are the advantages and disadvantages of various collision resolution strategies? (6)

September 14, 2023 in Data Structure

Define hash function?

Hash function takes an identifier and computes the address of that identifier in the hash table using some function.

September 14, 2023 in Data Structure

What is Binary search?

A binary search, also called a dichotomizing search, is a digital scheme for locating a specific object in a large set. Each object in the set is given a key. The number of keys is always a power of 2. If there are 32 items in a list, for example, they might be numbered 0 through 31 (binary 00000 through 11111). If there are, say, only 29 items, they can be numbered 0 through 28 (binary 00000 through 11100), with the numbers 29 through31 (binary 11101, 11110, and 11111) as dummy keys.

September 14, 2023 in Data Structure

What is linear search?

In Linear Search the list is searched sequentially and the position is returned if the key element to be searched is available in the list, otherwise -1 is returned. The search in Linear Search starts at the beginning of an array and move to the end, testing for a match at each item.

September 14, 2023 in Data Structure

Define Searching.

Searching for data is one of the fundamental fields of computing. Often, the difference between a fast program and a slow one is the use of a good algorithm for the data set. Naturally, the use of a hash table or binary search tree will result in more efficient searching, but more often than not an array or linked list will be used. It is necessary to understand good ways of searching data structures not designed to support efficient search.

September 14, 2023 in Data Structure

Compare quick sort and merge sort.

Quicksort has a best-case linear performance when the input is sorted, or nearly sorted. It has a worst-case quadratic performance when the input is sorted in reverse, or nearly sorted in reverse.

Merge sort performance is much more constrained and predictable than the performance of quicksort. The price for that reliability is that the average case of merge sort is slower than the average case of quicksort because the constant factor of merge sort is larger.

September 14, 2023 in Data Structure

What is divide-and-conquer strategy?

  • Divide a problem into two or more sub problems
  • Solve the sub problems recursively
  • Obtain solution to original problem by combining these solutions

September 14, 2023 in Data Structure

Mention the different ways to select a pivot element.

The different ways to select a pivot element are

  • Pick the first element as pivot
  • Pick the last element as pivot
  • Pick the Middle element as pivot
  • Median-of-three elements
  • Pick three elements, and find the median x of these elements
  • Use that median as the pivot.
  • Randomly pick an element as pivot.