UGC NET Computer Science Data Structures Previous Year Questions (PYQs) – Page 7 of 9
A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations
Study Stuff for MCA Examinations
Showing 83 questions
A double-ended queue (deque) supports adding and removing items from both ends of the queue. The operations supported by deque are AddFront, AddRear, RemoveFront and RemoveRear. You are given only stacks to implement this data structure. You can implement only push and pop operations. What is the time complexity of performing AddFront() and AddRear() assuming $m$ is the size of the stack and $n$ is the number of elements?
1
2
3
4
Solution
Using stack operations, insertion at front can be done directly by push operation.
So, AddFront takes:
$O(1)$
But insertion at rear needs moving elements because stack allows insertion only at top.
So, AddRear may require shifting $n$ elements.
Therefore, AddRear takes:
$O(n)$
So, AddFront takes:
$O(1)$
But insertion at rear needs moving elements because stack allows insertion only at top.
So, AddRear may require shifting $n$ elements.
Therefore, AddRear takes:
$O(n)$
Lower-triangular sparse matrix is one :
1
2
3
4
Solution
A lower triangular matrix is a matrix in which all the elements above the main (leading) diagonal are zero. Therefore, the non-zero elements can appear only on or below the leading diagonal.
Hence the correct statement is that the non-zero elements lie below the leading diagonal.
Match List I with List II
| List I (Hashing Collision Handling Method) | List II (Strategy) |
|---|---|
| A. Chaining | I. Check next slot |
| B. Linear Probing | II. Use second hash function |
| C. Quadratic Probing | III. Linked list at index |
| D. Double Hashing | IV. Skip slots using quadratic step |
1
2
3
4
Solution
Chaining → Linked list at index (III)
Linear probing → Check next slot (I)
Quadratic probing → Skip slots using quadratic step (IV)
Double hashing → Use second hash function (II)
Consider the following graph.
Among the following sequences
I. $a\ b\ e\ g\ h\ f$
II. $a\ b\ f\ e\ h\ g$
III. $a\ b\ f\ h\ g\ e$
IV. $a\ f\ g\ h\ b\ e$
Which are depth first traversals of the above graph?
Among the following sequences
I. $a\ b\ e\ g\ h\ f$
II. $a\ b\ f\ e\ h\ g$
III. $a\ b\ f\ h\ g\ e$
IV. $a\ f\ g\ h\ b\ e$
Which are depth first traversals of the above graph?
1
2
3
4
Solution
In DFS, we keep moving to an unvisited adjacent vertex as deeply as possible.
Check I:
$a\to b\to e\to g\to h\to f$
All consecutive vertices are connected, so I is possible DFS traversal.
Check II:
$a\to b\to f\to e$
Here, $f$ is not directly connected to $e$.
Also, from $f$, unvisited adjacent vertices like $h$ and $g$ are available, so DFS cannot jump to $e$.
So, II is not possible.
Check III:
$a\to b\to f\to h\to g\to e$
All consecutive vertices are connected, so III is possible DFS traversal.
Check IV:
$a\to f\to g\to h\to b\to e$
All consecutive vertices are connected, so IV is possible DFS traversal.
Therefore, valid DFS traversals are I, III, and IV only.
Check I:
$a\to b\to e\to g\to h\to f$
All consecutive vertices are connected, so I is possible DFS traversal.
Check II:
$a\to b\to f\to e$
Here, $f$ is not directly connected to $e$.
Also, from $f$, unvisited adjacent vertices like $h$ and $g$ are available, so DFS cannot jump to $e$.
So, II is not possible.
Check III:
$a\to b\to f\to h\to g\to e$
All consecutive vertices are connected, so III is possible DFS traversal.
Check IV:
$a\to f\to g\to h\to b\to e$
All consecutive vertices are connected, so IV is possible DFS traversal.
Therefore, valid DFS traversals are I, III, and IV only.
Which of the given options provides the increasing order of asymptotic complexity of functions $f_1,\ f_2,\ f_3$ and $f_4$?
A. $f_1(n)=2^n$
B. $f_2(n)=n^{3/2}$
C. $f_3(n)=n\log n$
D. $f_4(n)=n^{\log n}$
Choose the correct answer from the options given below.
A. $f_1(n)=2^n$
B. $f_2(n)=n^{3/2}$
C. $f_3(n)=n\log n$
D. $f_4(n)=n^{\log n}$
Choose the correct answer from the options given below.
1
2
3
4
Solution
Compare the growth rates:
$n\log n$ grows slower than $n^{3/2}$.
So,
$f_3(n)<f_2(n)$
Now, $n^{\log n}$ grows faster than any polynomial like $n^{3/2}$.
But $2^n$ grows faster than $n^{\log n}$.
So, increasing order is:
$f_3,\ f_2,\ f_4,\ f_1$
That is:
C, B, D, A
$n\log n$ grows slower than $n^{3/2}$.
So,
$f_3(n)<f_2(n)$
Now, $n^{\log n}$ grows faster than any polynomial like $n^{3/2}$.
But $2^n$ grows faster than $n^{\log n}$.
So, increasing order is:
$f_3,\ f_2,\ f_4,\ f_1$
That is:
C, B, D, A
A hash function $h$ defined as $h(key)=key\ mod\ 7$, with linear probing, is used to insert the keys $44,45,79,55,91,18,63$ into a table indexed from $0$ to $6$. What will be the location of key $18$?
1
2
3
4
Solution
Hash function is:
$h(key)=key\ mod\ 7$
Insert keys one by one.
$44\ mod\ 7=2$, so $44$ goes to index $2$.
$45\ mod\ 7=3$, so $45$ goes to index $3$.
$79\ mod\ 7=2$, but index $2$ is filled. Using linear probing, index $3$ is also filled, so $79$ goes to index $4$.
$55\ mod\ 7=6$, so $55$ goes to index $6$.
$91\ mod\ 7=0$, so $91$ goes to index $0$.
Now for key $18$:
$18\ mod\ 7=4$
Index $4$ is already filled by $79$.
Using linear probing, next index $5$ is empty.
So, key $18$ is inserted at index $5$.
$h(key)=key\ mod\ 7$
Insert keys one by one.
$44\ mod\ 7=2$, so $44$ goes to index $2$.
$45\ mod\ 7=3$, so $45$ goes to index $3$.
$79\ mod\ 7=2$, but index $2$ is filled. Using linear probing, index $3$ is also filled, so $79$ goes to index $4$.
$55\ mod\ 7=6$, so $55$ goes to index $6$.
$91\ mod\ 7=0$, so $91$ goes to index $0$.
Now for key $18$:
$18\ mod\ 7=4$
Index $4$ is already filled by $79$.
Using linear probing, next index $5$ is empty.
So, key $18$ is inserted at index $5$.
In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Here, $n$ and $m$ are number of vertices and edges, respectively. Match each algorithm with its time complexity.
Choose the correct answer from the options given below:
| List I | List II |
|---|---|
| A. Bellman-Ford algorithm | I. $O(m\log n)$ |
| B. Kruskal's algorithm | II. $O(n^3)$ |
| C. Floyd-Warshall algorithm | III. $O(n*m)$ |
| D. Topological sorting | IV. $O(n+m)$ |
1
2
3
4
Solution
Bellman-Ford algorithm checks all edges repeatedly for shortest path, so its time complexity is $O(n*m)$. Thus, $A-III$.
Kruskal's algorithm sorts edges and then applies union-find, so its time complexity is $O(m\log n)$. Thus, $B-I$.
Floyd-Warshall algorithm uses three nested loops for all pairs shortest path, so its time complexity is $O(n^3)$. Thus, $C-II$.
Topological sorting visits vertices and edges once, so its time complexity is $O(n+m)$. Thus, $D-IV$.
Final matching is $A-III,\ B-I,\ C-II,\ D-IV$.
Kruskal's algorithm sorts edges and then applies union-find, so its time complexity is $O(m\log n)$. Thus, $B-I$.
Floyd-Warshall algorithm uses three nested loops for all pairs shortest path, so its time complexity is $O(n^3)$. Thus, $C-II$.
Topological sorting visits vertices and edges once, so its time complexity is $O(n+m)$. Thus, $D-IV$.
Final matching is $A-III,\ B-I,\ C-II,\ D-IV$.
Which of the following algorithms use the Greedy strategy?
A. Dijkstra’s algorithm
B. Kruskal’s algorithm
C. Huffman coding
D. Bellman-Ford algorithm
1
2
3
4
Solution
Dijkstra’s algorithm ✅ — Uses greedy approach to select the next minimum-distance vertex.
Kruskal’s algorithm ✅ — Uses greedy strategy to build Minimum Spanning Tree (MST).
Huffman coding ✅ — Greedy algorithm for constructing optimal prefix codes.
Bellman-Ford algorithm ❌ — Uses dynamic programming, not greedy.
How many different binary trees are possible with $n$ nodes?
1
2
3
4
Solution
The number of different binary trees possible with $n$ nodes is given by the Catalan number.
Catalan number formula is:
$C_n=\frac{1}{n+1}\binom{2n}{n}$
So, the number of different binary trees possible with $n$ nodes is:
$\frac{1}{n+1}\binom{2n}{n}$
Let $n$ denote a positive integer. Suppose a function $F$ is defined as
$f(n)=
\begin{cases}
0, & n=1 \
f\left(\left\lfloor \frac{n}{2} \right\rfloor\right)+1, & n>1
\end{cases}$
What is $f(25)$? and what does this function find?
1
2
3
4
Solution
Given,
$f(1)=0$
Now find $f(25)$:
$f(25)=f\left(\left\lfloor \frac{25}{2} \right\rfloor\right)+1$
$f(25)=f(12)+1$
$f(12)=f(6)+1$
$f(6)=f(3)+1$
$f(3)=f(1)+1$
$f(1)=0$
Now putting values back:
$f(3)=0+1=1$
$f(6)=1+1=2$
$f(12)=2+1=3$
$f(25)=3+1=4$
So,
$f(25)=4$
This function counts how many times $n$ can be divided by $2$ until it becomes $1$.
So, it finds:
$\left\lfloor \log_2 n \right\rfloor$
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
Ask Your Question or Put Your Review.
