Data Structures unit-3 Questions with the solution – AKTU

This is Btech, MCA, and BCA’s common subject, “data structures.” Providing Unit -3 SEARCHING & SORTING important questions, Last year’s question paper with solutions, and many more study materials that will help students or bachelor’s exam

Dudes 🤔.. You want more useful details regarding this subject. Please keep in mind this as well.

Important Questions For Data Structures: 
*Unit-01     *Unit-02    
*Unit-03    *Unit-04 
*Unit-05    *Short-Q/Ans
*Question-Paper with solution 21-22 

Q1. What is collision? Discuss collision resolution techniques. 

Ans. Collision:

• 1. Collision is a situation which occur when we want to add a new record R with key k to our file F, but the memory location address HA) is already occupied.
• 2. A collision occurs when more than one keys map to same hash value in the hash table.

Collision resolution technique:

Hashing with open addressing:

• 1. In open addressing, all elements are stored in the hash table itself.
• 2. While searching for an element, we systematically examine table slots until the desired element is found or it is clear that the element is not in the table.
• 3. Thus, in open addressing, the load factor à can never exceed 1.
• 4. The process of examining the locations in the hash table is called probing.
• 5 Following are techniques of collision resolution by open addressing:

c. Double hashing:

i. Double hashing is one of the best methods available for open addressing because the permutations produced have many of the characteristics of randomly chosen permutations.

Hashing with separate chaining:

• 1. This method maintains the chain of elements which have same hash address.
• 2. We can take the hash table as an array of pointers.
• 3. Size of hash table can be number of records.
• 4. Here each pointer will point to one linked list and the elements which have same hash address will be maintained in the linked list.
• 5. We can maintain the linked list in sorted order and each elements of linked list will contain the whole record with key.
• 6. For inserting one element, first we have to get the hash value through hash function which will map in the hash table, then that element will be inserted in the linked list.
• 7. Searching a key is also same, first we will get the hash key value in hash table through hash function, then we will search the element in corresponding linked list.
• 8. Deletion of a key contains first search operation then same as delete operation of linked list.

Q2. Write shorts notes on garbage collection.

Ans.

• 1. When some memory space becomes reusable due to the deletion of a node from a list or due to deletion of entire list from a program then we want the space to be available for future use.
• 2. One method to do this is to immediately reinsert the space into the free-storage list. This is implemented in the linked list.
• 3. This method may be too time consuming for the operating system of a computer.
• 4. In another method, the operating system of a computer may periodically collect all the deleted space onto the free storage list. This type of technique is called garbage collection.
• 5. Garbage collection usually takes place in two steps. First the computer runs through all lists, tagging those cells which are currently in use and then the computer runs through the memory, collecting all untagged space onto the free storage list.
• 6. The garbage collection may take place when there is only some minimum amount of space or no space at all left in the free storage list or when the CPU is idle and has time to do the collection.

Q3. Write a short note on insertion sort.

Ans.1. In insertion sort, we pick up a particular value and then insert it at the appropriate place in the sorted sublist, ie., during kth iteration the element a[k] is inserted in its proper place in the sorted sub-array a [1], a[2],a[3]……..a[k- 1].

Q4. Write algorithm for quick sort. Trace your algorithm on the following data to sort the list: 2, 13,4,21, 7, 56, 51, 85, 59,1,9,10. How the choice of pivot elements affects the efficiency of algorithm.

Ans.

Q5. Write a short note on heap sort.

Ans. 1. Heap sort finds the largest element and puts it at the end of array, then the second largest item is found and this process is repeated for all other elements.

2. The general approach of heap sort is as follows:

a. From the given array, build the initial max heap.

b. Interchange the root (maximum) element with the last element.

c. Use repetitive downward operation from root node to rebuild the heap of size one less than the starting.

d. Repeat step (a) and (b) until there are no more elements.

Q6.Write a short note on radix sort.

Ans. 1. Radix sort is a small method that many people uses when alphabetizing a large list of names (here Radix is 26, 26 letters of alphabet).

2. Specifically, the list of name is first sorted according to the first letter of each name, i.e., the names are arranged in 26 classes.

3. Intuitively, one might want to sort numbers on their most significant digit.

Cracking AKTU B.Tech: Quantum Data Structures – Last Year’s Short Questions Paper

AKTU Important Links | Btech Syllabus

Important Links-Btech (AKTU)| Data Structures Syllabus