DST Unit 3 – Searching and Sorting questions

Topic : Array & Array Representation (Key Note and Questions)

   Key Note:

  • Searching is a process to find a particular element in a set of elements.
  • Linear search is also known as sequential search in which each elements is to be visit until we reach at same match.
  • Binary search is a very efficient searching where set of elements are sorted and we can eliminate half set of elements in one time if item not matched.

Questions

  1. Write a note on searching in data structure.
  2. Write a algorithm for linear search technique.
  3. Write a algorithm for binary search technique.
  4. Explain binary search tree.
  5. Explain binary search tree and its operations. Make a binary search tree for the following sequence of numbers, show all steps: 45,32,90,34,68,72,15,24,30,66,11,50,10
  6. What are various operations performed in BST?

Topic : Hashing And Collision (Key Note and Questions)​

   Key Note:

  • Hashing is a key comparisons search technique  that perform searches in O(n) time in the worst case and in an average case it will be done in O(1) time.
  • Hash Collision is a situation in which two or more  data elements in the data set U, maps to the same location in the has table.
  • Open Hashing and Closed Hashing is a Collision resolution technique.

Questions

  1. What do you mean by hashing in data structure? Write the types of Hashing.
  2. Discuss the advantages and disadvantages of hashing over other searching technique.
  3. What is collision in Data structure? Explain different types of collision resolution technique.
  4. Explain linear probing collision resolution technique with explanation.

Topic : Sorting (Key Note and Questions)​​

   Key Note:

  • Sorting is a technique of arranging elements in a ordered form either in ascending or in descending order.
  • Some List of sorting algorithms are Insertion sort, Selection sort, Quick sort, Merge sort, Heap sort etc.

Questions

  1. Explain insertion sort. Write insertion sort algorithm and program.
  2. Explain selection sort. Write selection sort algorithm and program.
  3. Explain bubble sort. Write bubble sort algorithm and program.
  4. Explain quick sort. Write quick sort algorithm and program.
  5. Explain and give heap sort and write its algorithm.
  6. Explain and give radix sort and write its algorithm.

Topic : Tree (Key Note and Questions)​​​

   Key Note: 

  • Tree is a non-linear data structure that have nodes which is connected using edge.
  • All node are arrange as root node, parent node and child node in hierarchical manner.

Questions

  1. Explain binary search tree.
  2. Explain binary search tree and its operations. Make a binary search tree for the following sequence of numbers, show all steps: 45,32,90,34,68,72,15,24,30,66,11,50,10
  3. What are various operations performed in BST?
  4. Explain AVL tree. Explain the balancing methods and all rotations of AVL trees with an example.
  5. Draw an AVL tree on following inputs, assume that tree is initially empty: 45,55,65,75,80,90,100,110,120,130,140,40,35,25,20,15,10,5.
  6. Explain B-tree. Write down the steps for insertion operation in B-tree.