CS301 - Data Structures
Course Page
Q & A
Short Question & Answers
Q1: In the array representation of union what represents -1?
This shows that this node has no parent. Moreover, this node will be a root that may be a parent of some other node.
Q2: For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply." Justify why?
Since for smaller lists number of comparisons and interchange (if needed) decreases radically in insertion sort than quick sort. For larger lists, opposite occurs in both sorting techniques.
Q3: If we want to delete the node from BST which has left and right child then which rotation is applied?
After deleting the node we traverse up the tree from the deleted node checking the balance of each node at each level up to the root.
Q4: Collision in hashing definition?
Collision takes place when two or more keys (data items) produce the same index.
Q5: Algorithm union by weight?
root1 = find(i); root2 = find(j);
if (root1 != root2) if (parent[root1] <= parent[root2]){ // first tree has more nodes
parent[root1] += parent[root2]; parent[root2] = root1;
 } else { // second tree has more nodes
parent[root2] += parent[root1]; parent[root1] = root2; }
Q6: Which data structure is best for priority queue?
The use of priority queue with the help of heap is a major application. The priority queue is itself a major data structure, much-used in operating systems. Similarly priority queue data structure is used in network devices especially in routers. Heap data structure is also employed in sorting algorithms.
Q7: Name of two divide and conquer algorithm
Merge Sort, Quick Sort, Heap Sort
Q8: How heap sort works to set a set of data?
When we construct the heap or complete binary tree of the list, the smallest name (considering alphabet ‘a’ as the smallest) in the list will take the root node place in the tree. The remaining names will take their places in the nodes below the root node according to their order. Remember, we are not constructing binary search tree but a min-heap to sort the data. After the construction of the min-heap from all the names in the list, we start taking the elements out (deleting) from the heap in order to retrieve the sorted data. The first element that is taken out would be the smallest name in the heap. The remaining heap after taking out the deleted node will be reduced by one element in size and the next name will be at the root position. It is taken out to further reduce the tree size by one. This way, the continuation of the process of taking out the elements from the heap will ultimately lead to a situation when there is no more nodes left in the tree.
Q9: What is an Equivalent relation?
Two cells are equivalent if they can be reached from each other.
Q10: Give the operation names that we can perform on Table abstract data type?
Insert: As the name shows this method is used to insert (add) a record in a table. For its execution, a field is designated as key. To insert a record (entry) in the table, there is need to know the key and the entry. The insert method puts the key and the other related fields in a table. Thus we add records in a table. Find: Suppose we have data in the table and want to find some particular information. The find method is given a key and it finds the entry associated with the key. In other words, it finds the whole record that has the same key value as provided to it. For example, in employees table if employee id is the key, we can find the record of an employee whose employee id is, say, 15466. Remove: Then there is the remove method that is given a value of the key to find and remove the entry associated with that key from the table.
Q11:. Heapify the elements of the following array (reading from left to right) into a Min Heap and show that Min Heap contents in the form of array as shown below,
Original Array: 6 5 3 9 1 2 10 8 -
Q12: Suppose the hash table of height 7 (index 0 to 6), hash function H (key) = (2 *key + 5) Mode 7 and pass these numbers [5, 23, 17, 14, 44] from the hash function to resolve the collision by the linear probing.
H (key) = (2 *key + 5) Mode 7
Mode = 15mode7= 7(2) + 1, in which 1 is the remainder. And this reminder is mode.
H(23)= (2*23+5)mode7=2
 ….so on
Q13: Why binary search not use with link list?
Because it store sorted data.
Course Instructor

Dr. Sohail Aslam
Ph.D in Computer Science
University of Illinois,
at Urbana-Champaign

Data Structures and Algorithm Analysis in C++ by Mark Allen