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
- Q1). Write a note on searching in data structure.
- Q2). Write a algorithm for linear search technique.
- Q3). Write a algorithm for binary search technique.
- Q4). Explain binary search tree.
- Q5). Explain binary search tree and its opearations. 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
- Q6). What are various operations performed in BST?
- Q7). What is binary search tree? Write the important applications of binary search tree. Write algorithm to delete a node from a binary search tree.
- Q8). Explain the m-way search tree.
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
- Q1). What do you mean by hashing in data structure? Write the types of Hashing.
- Q2). Discuss the advantages and disadvantages of hashing over other searching technique.
- Q3). What is collision in Data structure? Explain different types of collision resolution technique.
- Q4). 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
- Q1). Explain insertion sort. Write insertion sort algorithm and program.
- Q2). Explain selection sort. Write selection sort algorithm and program.
- Q3). Explain bubble sort. Write bubble sort algorithm and program.
- Q4). Explain quick sort. Write quick sort algorithm and program.
- Q5). Explain and give heap sort and write its algorithm.
- Q6). Explain and give radix sort and write its algorithm.
- Q7). What is quick sort? Sort the given values using quick sort; present all steps/iterations: 38,81,22,48,13,69,93,14,45,58,79,72.
- Q8). Write an algorithm for merge sorting. Using the algorithm sort in ascending order: 10,25,16,5,35,48,8.
- Q9). Sort the following array manually using non-recursive quick sort method: 40,15,65,35,55,45,75,95,85,05 and 30.
- Q10). Describe two way merge sort method. Explain the complexities of merge sort method.
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
- Q1). Explain binary search tree.
- Q2). Explain binary search tree and its opearations. 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
- Q3). What are various operations performed in BST?
- Q4). What is binary search tree? Write the important applications of binary search tree. Write algorithm to delete a node from a binary search tree.
- Q5). Explain AVL tree. Explain the balancing methods of AVL trees with an example.
- Q6). 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.
- Q7). Describe all rotations in AVL tree. Construct AVL tree from the following nodes: B,C,G,E,F,D,A.
- Q8). Explain B-tree. Write down the steps for insertion operation in B-tree.
- Q9). Write the characteristics of B-tree. Construct a B-tree on following sequence sequence of inputs 10,20,30,40,50,60,70,80,90. Assume that the order of the B-tree is 3.
- Q10). What do you mean by B+ tree?
Latest Uploads on Website
- AVL Tree with explanation
- Radix sort algorithm explanation with example
- Quick Sort Algorithm with explanation
- Bubble sorting algorithm with Bubble sort program in C
- Insertion sort algorithm and program in C
- Selection Sort Algorithm and Program in C
- Linear probing technique explanation with example
- Collision in Hashing and Collision resolution technique
- Hashing in data structure with its types
- Binary search tree operations with Program
- Binary search tree in data structure
- Binary search algorithm in data structure with explanation
- linear search in data structure with Algo and Program