UGC NET Computer Science Data Structures Previous Year Questions (PYQs) – Page 3 of 9
Study Stuff for MCA Examinations
Solution
In Quick sort, first we choose a pivot element.
Then the array is divided into two parts:
Elements smaller than pivot
Elements greater than pivot
After partitioning, Quick sort is applied recursively on both parts.
So, the problem is divided into smaller subproblems and then solved recursively.
This is exactly the divide and conquer approach.
Solution
| List-I | List-II |
|---|---|
| (a) Prim's algorithm | (i) $O(V^3\log V)$ |
| (b) Dijkstra's algorithm | (ii) $O(VE^2)$ |
| (c) Faster all-pairs shortest path | (iii) $O(E\log V)$ |
| (d) Edmonds-Karp algorithm | (iv) $O(V^2)$ |
Solution
Prim's algorithm has time complexity:
$O(E\log V)$
So,
$(a)\rightarrow(iii)$
Dijkstra's algorithm has time complexity:
$O(V^2)$
So,
$(b)\rightarrow(iv)$
Faster all-pairs shortest path algorithm has time complexity:
$O(V^3\log V)$
So,
$(c)\rightarrow(i)$
Edmonds-Karp algorithm has time complexity:
$O(VE^2)$
So,
$(d)\rightarrow(ii)$
Therefore, the correct matching is
$(a)-(iii);\ (b)-(iv);\ (c)-(i);\ (d)-(ii)$
Preorder $\to ABCEIFJDGHKL$
Inorder $\to EICFJBGDKHLA$
Which of the following is correct post order traversal?
Solution
Preorder traversal:
$ABCEIFJDGHKL$
Inorder traversal:
$EICFJBGDKHLA$
In preorder traversal, the first element is always the root.
So, root is:
$A$
In inorder traversal, $A$ is at the end.
So, all remaining nodes are in the left subtree of $A$.
Now, after $A$, the next root in preorder is:
$B$
In inorder traversal:
$EICFJBGDKHL$
Here, nodes before $B$ are in left subtree of $B$:
$EICFJ$
Nodes after $B$ are in right subtree of $B$:
$GDKHL$
Now solve left subtree of $B$.
Preorder part is:
$CEIFJ$
Root is $C$.
Inorder part is:
$EICFJ$
Left of $C$ is $EI$ and right of $C$ is $FJ$.
For $EI$, root is $E$, so postorder is:
$IE$
For $FJ$, root is $F$, so postorder is:
$JF$
So, postorder of subtree rooted at $C$ is:
$IEJFC$
Now solve right subtree of $B$.
Preorder part is:
$DGHKL$
Root is $D$.
Inorder part is:
$GDKHL$
Left of $D$ is $G$ and right of $D$ is $KHL$.
So, left postorder is:
$G$
For right part $KHL$, root is $H$.
Left of $H$ is $K$ and right of $H$ is $L$.
So, postorder of subtree rooted at $H$ is:
$KLH$
Thus, postorder of subtree rooted at $D$ is:
$GKLHD$
Now, postorder of subtree rooted at $B$ is:
$IEJFCGKLHDB$
Finally, root $A$ comes at the end.
So, final postorder traversal is:
$IEJFCGKLHDBA$
Solution
Heapsort is an in-place sorting algorithm.
Insertion sort is also an in-place sorting algorithm.
But merge sort is not considered in-place because it requires extra memory for merging.
So, heapsort sorts in place like insertion sort, but unlike merge sort.
Therefore,
$(P,Q)=(Insertion\ sort,\ Merge\ sort)$
Solution
Using Master Theorem / recurrence expansion:
(A)
$T(n) = T(n/2) + 1$
Complexity → $O(\log n)$
(E)
$T(n) = T(n-1) + 1$
Complexity → $O(n)$
(D)
$T(n) = 2T(n/2) + \sqrt{n}$
$n^{\log_2 2} = n$
Since $\sqrt{n} < n$
→ $O(n)$
(B)
$T(n) = 2T(n/2) + n$
$n^{\log_2 2} = n$
→ $O(n \log n)$
(C)
$T(n) = 3T(n/3) + n$
$n^{\log_3 3} = n$
→ $O(n \log n)$
Increasing order
$O(\log n) < O(n) < O(n) < O(n\log n) < O(n\log n)$
$35,50,40,25,30,60,78,20,28$
Solution
Insert $35$:
Tree is balanced. No rotation.
Insert $50$:
$50$ becomes right child of $35$.
Tree is balanced. No rotation.
Insert $40$:
$40$ goes to left of $50$.
This creates Right-Left imbalance at $35$.
For Right-Left case, we do:
Right rotation at $50$
Left rotation at $35$
So far:
Left rotations $=1$
Right rotations $=1$
Insert $25$:
$25$ goes to left side.
Tree remains balanced. No rotation.
Insert $30$:
$30$ goes to right of $25$.
This creates Left-Right imbalance at $35$.
For Left-Right case, we do:
Left rotation at $25$
Right rotation at $35$
Now total:
Left rotations $=2$
Right rotations $=2$
Insert $60$:
$60$ goes to right side.
Tree remains balanced. No rotation.
Insert $78$:
$78$ goes to right of $60$.
This creates Right-Right imbalance at $50$.
For Right-Right case, we do:
Left rotation at $50$
Now total:
Left rotations $=3$
Right rotations $=2$
Insert $20$:
$20$ goes to left side.
Tree remains balanced. No rotation.
Insert $28$:
$28$ goes to right of $25$.
Tree still remains balanced. No rotation.
Therefore, total rotations are:
$3$ left rotations and $2$ right rotations.
Solution
The numbers are in the range
$0$ to $n^2-1$
Using radix sort with base $n$, each number can be represented using $2$ digits.
Radix sort takes
$O(d(n+b))$
Here,
$d=2$ and $b=n$
So,
$O(2(n+n))=O(n)$
Hence, the best running time is $O(n)$.
Which of the following is application of depth-first search?
Solution
Depth-first search is used in topological sorting of directed acyclic graphs.
DFS is also used in finding strongly connected components, such as in Kosaraju's algorithm and Tarjan's algorithm.
So, both topological sort and strongly connected components are applications of DFS.
Consider double hashing of the form
$h(k,i)=(h_1(k)+ih_2(k))\ \text{mod}\ m$
where
$h_1(k)=k\ \text{mod}\ m$
$h_2(k)=1+(k\ \text{mod}\ n)$
where $n=m-1$ and $m=701$.
For $k=123456$, what is the difference between first and second probes in terms of slots?
Solution
In double hashing, the difference between the first and second probe is decided by $h_2(k)$.
Here,
$m=701$
So,
$n=m-1=700$
Now,
$h_2(k)=1+($remainder when $123456$ is divided by $700)$
$123456=700\times 176+256$
So, remainder is $256$.
Therefore,
$h_2(k)=1+256=257$
UGC NET Computer Science
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
UGC NET Computer Science
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
