UGC NET Computer Science Data Structures Previous Year Questions (PYQs) – Page 2 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
Which of the followings are true for a complete binary tree?
A. It always has odd number of vertices.
B. With $n$ internal vertices, it has $n+1$ leaves.
C. With $l$ leaves it has $l-1$ internal vertices.
D. With $2n-1$ vertices, it has $n$ leaves.
A. It always has odd number of vertices.
B. With $n$ internal vertices, it has $n+1$ leaves.
C. With $l$ leaves it has $l-1$ internal vertices.
D. With $2n-1$ vertices, it has $n$ leaves.
1
2
3
4
Solution
Properties of complete/full binary tree:
• If internal nodes = $n$ → leaves = $n+1$ ✔
• If leaves = $l$ → internal nodes = $l-1$ ✔
• Total vertices = $2n-1$ when leaves = $n$ ✔
• Such trees always have odd number of vertices ✔
Thus all statements are correct.
Consider the following statements about heap sort algorithm:
A. The MAX-HEAPIFY procedure which runs in $O(\lg n)$ time, is the key to maintaining the max heap property
B. The BUILD-MAX-HEAP procedure, which runs in $O(\lg n)$ time, produces max-heap from an unordered input array
C. The MAX-HEAP-INSERT, which runs in $O(\lg n)$ time, implements the insertion operation
D. The HEAP-INCREASE-KEY procedure runs in $O(n \lg n)$ time, to set the key of new node of its correct value
Choose the correct answer from the options given below:
1
2
3
4
Solution
A is true because MAX-HEAPIFY takes $O(\lg n)$ time.
B is false because BUILD-MAX-HEAP takes $O(n)$ time, not $O(\lg n)$.
C is true because MAX-HEAP-INSERT takes $O(\lg n)$ time.
D is false because HEAP-INCREASE-KEY takes $O(\lg n)$ time, not $O(n \lg n)$.
Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R.
Assertion A: The AVL trees are more balanced as compared to Red Black trees, but they may cause more rotations during insertion and deletion.
Reason R: A Red Black tree with n nodes has height that is greater than $2\log_2(n+1)$ and the AVL tree with n nodes has height less than $\log_\phi(\sqrt{5}(n+2))-2$ where $\phi$ is golden ratio.
In the light of the above statements, choose the correct answer from the options given below.
1
2
3
4
Solution
Assertion A is true because AVL trees are more strictly balanced than Red Black trees.
Reason R is false because the height of a Red Black tree is at most $2\log_2(n+1)$, not greater than it.
Consider the undirected graph below.
Using Prim's algorithm to construct a minimum spanning tree starting with node $a$, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?
Using Prim's algorithm to construct a minimum spanning tree starting with node $a$, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?
1
2
3
4
Solution
Using Prim's algorithm, we always select the minimum weight edge that connects the current tree with a new vertex.
Start from vertex $a$.
From $a$, possible edges are:
$(a,b)=4$
$(a,h)=8$
Minimum edge is:
$(a,b)=4$
So, first edge is $(a,b)$.
Now current tree is:
$\{a,b\}$
Possible crossing edges are:
$(a,h)=8$
$(b,c)=8$
$(b,h)=11$
Here, $(a,h)$ and $(b,c)$ both have the same minimum weight $8$.
So, there is a tie.
If we choose $(a,h)$, then the sequence can be:
$(a,b),(a,h),(g,h),(f,g),(c,f),(c,i),(c,d),(d,e)$
This matches option (A).
Now check option (A):
After adding $(a,h)$, minimum edge from tree to outside is:
$(h,g)=1$
Then,
$(g,f)=2$
Then,
$(f,c)=4$
Then,
$(c,i)=2$
Then,
$(c,d)=7$
Then,
$(d,e)=9$
So, option (A) is a valid possible order.
But because of the tie at weight $8$, we may also choose $(b,c)$ instead of $(a,h)$.
If we choose $(b,c)$, then the sequence can be:
$(a,b),(b,c),(c,i),(c,f),(f,g),(g,h),(c,d),(d,e)$
This matches option (C).
So, option (C) is also a valid possible order.
Option (B) is not correct because after $(a,b)$, edge $(b,h)=11$ cannot be selected since edges of weight $8$ are available.
Option (D) is not correct because $(g,h)$ cannot be selected immediately after $(a,b)$ as it does not connect the current tree to a new vertex.
Therefore, both options (A) and (C) are possible due to tie in Prim's algorithm.
Correct Answer: (A) and (C) both are possible
Note: If the question expects only one answer, then it is ambiguous because Prim's algorithm can give different valid edge orders when equal weight edges are present.
Let $G$ be a simple undirected graph, $T_D$ be a DFS tree on $G$, and $T_B$ be the BFS tree on $G$.
Consider the following statements.
Statement I: No edge of $G$ is a cross with respect to $T_D$.
Statement II: For every edge $(u,v)$ of $G$, if $u$ is at depth $i$ and $v$ is at depth $j$ in $T_B$, then $|i-j|=1$.
In the light of the above statements, choose the correct answer from the options given below:
Consider the following statements.
Statement I: No edge of $G$ is a cross with respect to $T_D$.
Statement II: For every edge $(u,v)$ of $G$, if $u$ is at depth $i$ and $v$ is at depth $j$ in $T_B$, then $|i-j|=1$.
In the light of the above statements, choose the correct answer from the options given below:
1
2
3
4
Solution
Statement I is true.
In DFS of an undirected graph, there are no cross edges.
Edges are generally tree edges or back edges.
So, no edge of $G$ is a cross edge with respect to DFS tree $T_D$.
Statement II is false.
In BFS tree, for every edge $(u,v)$, the depths of $u$ and $v$ differ by at most $1$.
So, the correct condition is:
$|i-j|\le 1$
But the statement says:
$|i-j|=1$
This is not always true because two adjacent vertices can also be at the same level in a BFS tree.
Therefore, Statement I is true and Statement II is false.
In DFS of an undirected graph, there are no cross edges.
Edges are generally tree edges or back edges.
So, no edge of $G$ is a cross edge with respect to DFS tree $T_D$.
Statement II is false.
In BFS tree, for every edge $(u,v)$, the depths of $u$ and $v$ differ by at most $1$.
So, the correct condition is:
$|i-j|\le 1$
But the statement says:
$|i-j|=1$
This is not always true because two adjacent vertices can also be at the same level in a BFS tree.
Therefore, Statement I is true and Statement II is false.
The weight of minimum spanning tree in graph $G$, calculated using Kruskal's algorithm is:
1
2
3
4
Solution
Using Kruskal’s algorithm, arrange all edges in increasing order of weight:
$2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8$
Now select the minimum weight edges without forming a cycle.
Selected edges are:
$2,\ 3,\ 4,\ 6$
Here, edge $5$ is skipped because it forms a cycle.
So, total weight of minimum spanning tree is:
$2+3+4+6=15$
Assume that $f(n)$ and $g(n)$ are asymptotically positive. Which of the following is correct?
1
2
3
4
Solution
If $f(n)=O(g(n))$ and $g(n)=O(h(n))$, then by transitivity:
$f(n)=O(h(n))$
But option says:
$f(n)=\omega(h(n))$
So, option (a) is incorrect.
Check option (b):
If $f(n)=\Omega(g(n))$ and $g(n)=\Omega(h(n))$, then:
$f(n)=\Omega(h(n))$
But option says:
$f(n)=O(h(n))$
So, option (b) is incorrect.
Check option (c):
If $f(n)=o(g(n))$, then $f(n)$ grows strictly slower than $g(n)$.
If $g(n)=o(h(n))$, then $g(n)$ grows strictly slower than $h(n)$.
Therefore, $f(n)$ also grows strictly slower than $h(n)$.
So,
$f(n)=o(h(n))$
Thus, option (c) is correct.
Check option (d):
If $f(n)=\omega(g(n))$ and $g(n)=\omega(h(n))$, then:
$f(n)=\omega(h(n))$
Since $\omega(h(n))$ is stronger than $\Omega(h(n))$, option (d) is also mathematically correct.
Therefore, mathematically both option (c) and option (d) are correct.
If the exam expects only one answer, then the question has ambiguity.
$f(n)=O(h(n))$
But option says:
$f(n)=\omega(h(n))$
So, option (a) is incorrect.
Check option (b):
If $f(n)=\Omega(g(n))$ and $g(n)=\Omega(h(n))$, then:
$f(n)=\Omega(h(n))$
But option says:
$f(n)=O(h(n))$
So, option (b) is incorrect.
Check option (c):
If $f(n)=o(g(n))$, then $f(n)$ grows strictly slower than $g(n)$.
If $g(n)=o(h(n))$, then $g(n)$ grows strictly slower than $h(n)$.
Therefore, $f(n)$ also grows strictly slower than $h(n)$.
So,
$f(n)=o(h(n))$
Thus, option (c) is correct.
Check option (d):
If $f(n)=\omega(g(n))$ and $g(n)=\omega(h(n))$, then:
$f(n)=\omega(h(n))$
Since $\omega(h(n))$ is stronger than $\Omega(h(n))$, option (d) is also mathematically correct.
Therefore, mathematically both option (c) and option (d) are correct.
If the exam expects only one answer, then the question has ambiguity.
The solution of the recurrence relation $T(n)=3T\left(\frac{n}{4}\right)+n\log n$ is
1
2
3
4
Solution
Given recurrence is:
$T(n)=3T\left(\frac{n}{4}\right)+n\log n$
Compare with Master Theorem:
$T(n)=aT\left(\frac{n}{b}\right)+f(n)$
Here,
$a=3,\ b=4,\ f(n)=n\log n$
Now,
$n^{\log_b a}=n^{\log_4 3}$
Since,
$\log_4 3<1$
So,
$n^{\log_4 3}<n$
But,
$f(n)=n\log n$
Clearly,
$n\log n$ grows faster than $n^{\log_4 3}$.
So, by Master Theorem Case 3,
$T(n)=\theta(n\log n)$
$T(n)=3T\left(\frac{n}{4}\right)+n\log n$
Compare with Master Theorem:
$T(n)=aT\left(\frac{n}{b}\right)+f(n)$
Here,
$a=3,\ b=4,\ f(n)=n\log n$
Now,
$n^{\log_b a}=n^{\log_4 3}$
Since,
$\log_4 3<1$
So,
$n^{\log_4 3}<n$
But,
$f(n)=n\log n$
Clearly,
$n\log n$ grows faster than $n^{\log_4 3}$.
So, by Master Theorem Case 3,
$T(n)=\theta(n\log n)$
The number of nodes of height $h$ in any $n$-element heap is atmost:
1
2
3
4
Solution
In a heap, height of a node means the number of edges on the longest downward path from that node to a leaf.
Leaves have height $0$.
In an $n$-element heap, the number of nodes at height $h$ decreases as $h$ increases.
Standard result:
Number of nodes of height $h$ in an $n$-element heap is at most
$\left\lceil \frac{n}{2^{h+1}}\right\rceil$
Ignoring the ceiling value, it is written as:
$\frac{n}{2^{h+1}}$
So, the required expression is:
$\frac{n}{2^{h+1}}$
Leaves have height $0$.
In an $n$-element heap, the number of nodes at height $h$ decreases as $h$ increases.
Standard result:
Number of nodes of height $h$ in an $n$-element heap is at most
$\left\lceil \frac{n}{2^{h+1}}\right\rceil$
Ignoring the ceiling value, it is written as:
$\frac{n}{2^{h+1}}$
So, the required expression is:
$\frac{n}{2^{h+1}}$
Consider a B-tree of height $h$ minimum degree $t\ge 2$ that contains any $n$-key, where $n\ge 1$. Which of the following is correct?
1
2
3
4
Solution
For a B-tree with minimum degree $t$, every internal node except root has at least $t$ children.
Also, every node except root has at least $t-1$ keys.
For a B-tree of height $h$, the minimum number of keys is:
$n\ge 2t^h-1$
Now solve this inequality for $h$.
$n+1\ge 2t^h$
$\frac{n+1}{2}\ge t^h$
Taking logarithm base $t$ on both sides:
$\log_t\frac{n+1}{2}\ge h$
So,
$h\le \log_t\frac{n+1}{2}$
Also, every node except root has at least $t-1$ keys.
For a B-tree of height $h$, the minimum number of keys is:
$n\ge 2t^h-1$
Now solve this inequality for $h$.
$n+1\ge 2t^h$
$\frac{n+1}{2}\ge t^h$
Taking logarithm base $t$ on both sides:
$\log_t\frac{n+1}{2}\ge h$
So,
$h\le \log_t\frac{n+1}{2}$
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.
