CS301 Final Term Solved Subjective 2013

CS301 All Current · Final Term Paper Subjective 2013 · Solved with refernces · Pattren: · Total Questions: 52 · Total MCQs: 40 (Each of 1 Mark) · Total Short Questions: 4 (Each of 2 Mark) · Total Short Questions: 4 (Each of 3 Mark) · Total Long Questions: 4 (Each of 5 Mark) · Subjective questions:

Note: Try to Prepare Mcqz and subjective files of Moaaz brother.

Q1. In the array representation of union what represents -1?

Answer: Page no 392 Chapter no 34 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?

Answer: 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?

Answer: 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?

Answer: page no 464 chapter no 42

Question of 3 marks:

Q1. Algorithm union by weight?

Answer: Page no 408 //union(i,j):

1. root1 = find(i);
2. root2 = find(j);
3. if (root1 != root2)
4. if (parent[root1] <= parent[root2])
5. {
6. // first tree has more nodes
7. parent[root1] += parent[root2];
8. parent[root2] = root1;
9. }
10. else
11. {
12. // second tree has more nodes
13. parent[root2] += parent[root1];
14. parent[root1] = root2;
15. }

2. One tree is given question is it heap or not if it is heap then write its type

Answer: Consult Page no 333-335 Ch:29 Due to the violation, the value of child is less than that of the parent it is not a heap

Q3. Which data structure is best for priority queue?

Answer: Page no 334 Ch: 29 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.

Q1. Some numbers are given and using those make BST?

Page no: 128

Q2. One array is given we require to sort it using bubble sort and write only 2 iterations?

Page no: 486

Q3. One tree is given which not the heap but after minimum changes it becomes max heap make it?

Chapter no 29 page no 335

1. name of two divide and conquer algorithm

Answer: Merge Sort Quick Sort Heap Sort

2. Height of a tree is 5 find sum of heights

Answer: Total number of nodes N = 2h +1 – 1=25 +1 – 1=26– 1=63

Q3. What is a skip List?

Answer: Page no 444 Chapter: 39

What is an Equivalent relation?

Answer: Page no 424 Chapter : 37