UGC NET Computer Science Data Structures Previous Year Questions (PYQs) – Page 5 of 9
Study Stuff for MCA Examinations
| List I | List II |
|---|---|
| (A) Breadth First Search | (I) $\theta(V+E)$ |
| (B) Rabin-Karp Algorithm | (II) $O(V+E)$ |
| (C) Depth-First Search | (III) $\theta((n-m+1)m)$ |
| (D) Heap sort (worst case) | (IV) $O(n^2)$ |
| (E) Quick sort (worst case) | (V) $O(n\log n)$ |
Solution
So, its time complexity is:
$O(V+E)$
Therefore,
$(A)-(II)$
Rabin-Karp Algorithm compares the pattern of length $m$ with possible positions in the text.
In the worst case, it may take:
$\theta((n-m+1)m)$
Therefore,
$(B)-(III)$
Depth-First Search also visits every vertex and every edge.
So, its running time is:
$\theta(V+E)$
Therefore,
$(C)-(I)$
Heap sort has worst case time complexity:
$O(n\log n)$
Therefore,
$(D)-(V)$
Quick sort has worst case time complexity:
$O(n^2)$
This happens when partitioning is highly unbalanced.
Therefore,
$(E)-(IV)$
Final matching is:
$(A)-(II), (B)-(III), (C)-(I), (D)-(V), (E)-(IV)$
Solution
Dijkstra's algorithm finds the shortest path based on minimum total weight.
It does not necessarily choose the path with the least number of vertices.
A path with more vertices can have smaller total weight than a path with fewer vertices.
Dijkstra's algorithm also requires all edge weights to be non-negative.
So, the statement “Shortest path always passes through least number of vertices” is not true.
Solution
Using the Fast Fourier Transform $($FFT$)$ method, polynomial multiplication can be done faster than the normal multiplication method.
Normal polynomial multiplication takes:
$\theta(n^2)$
But FFT based polynomial multiplication takes:
$\theta(n\lg n)$
Statement I: Vertex-cover is a polynomial time 2-approximation algorithm.
Statement II: TSP-tour is a polynomial time 3-approximation algorithm for travelling salesman problem with the triangle inequality.
Which of the following is correct?
Solution
For the Vertex Cover problem, there is a standard polynomial time approximation algorithm.
It repeatedly chooses an edge and includes both endpoints in the vertex cover.
This gives a solution whose size is at most $2$ times the optimal solution.
So, Vertex-cover has a polynomial time $2$-approximation algorithm.
Therefore, Statement I is true.
Statement II:
For Travelling Salesman Problem with triangle inequality, the standard MST based TSP-tour approximation algorithm gives a $2$-approximation.
It does not give a $3$-approximation as the standard result.
So, the statement saying it is a polynomial time $3$-approximation algorithm is not correct in the standard form.
Therefore, Statement II is false.
- A. Binary Search Tree
- B. AVL Tree
- C. Red-Black Tree
- D. B-Tree
Choose the correct answer from the options below:
- A and D only
- A, B and D only
- C and D only
- B and C only
Solution
Answer: 4) B and C only
- Binary Search Tree (BST): Not necessarily balanced; height can degrade to O(n).
- AVL Tree: Height-balanced by definition (balance factor −1, 0, +1); height is O(log n).
- Red-Black Tree: Enforces black-height properties that keep height O(log n); treated as a height-balanced binary tree.
- B-Tree: Balanced (all leaves at the same level) but not a binary tree; the term “height-balanced tree” typically refers to binary trees. Hence excluded here.
When developing a dynamic programming algorithm, the sequence of steps followed is:
- A. Construct an optimal solution from computed information.
- B. Recursively define the value of an optimal solution.
- C. Characterize the structure of an optimal solution.
- D. Compute the value of an optimal solution, typically in a bottom-up fashion.
Choose the correct answer from the options given below:
- B, C, A, D
- B, A, C, D
- C, B, A, D
- C, B, D, A
Solution
Answer: (4) C, B, D, A
Explanation:
The standard steps for designing a dynamic programming algorithm are:
- (C) Characterize the structure of an optimal solution.
- (B) Recursively define the value of an optimal solution.
- (D) Compute the value of an optimal solution (usually bottom-up).
- (A) Construct the optimal solution from the computed information.
Hence, the correct order is C → B → D → A.
Select the Sorting Algorithms that are stable.
(A) Quick Sort
(B) Bubble Sort
(C) Insertion Sort
(D) Merge Sort
(E) Shell Sort
Choose the correct answer from the options given below :
Solution
Quick Sort → Not stable ✘
Bubble Sort → Stable ✔
Insertion Sort → Stable ✔
Merge Sort → Stable ✔
Shell Sort → Not stable ✘
Thus stable algorithms:
Bubble Sort, Insertion Sort, Merge Sort
But among given options, only
(B) and (C)
appear together correctly.
In the context of a Hamiltonian problem, which of the following are correct?
A. Hamiltonian cycle problem is NP-Complete
B. If $G$ is an undirected Bipartite graph with an odd number of vertices, then $G$ is Hamiltonian.
C. Hamiltonian path problem cannot be solved in polynomial time on directed acyclic graph
D. If $G$ is a connected undirected graph with at least three vertices and $G^3$ is the graph obtained by connecting all pairs of vertices that are connected by a path in $G$ of length at most $3$.
E. If any NP complete problem is polynomial time solvable the $(P=NP)$.
Choose the most appropriate answer from the options given below:
Solution
Statement A is true.
Hamiltonian cycle problem is NP-Complete.
Statement B is false.
A bipartite graph with odd number of vertices cannot have a Hamiltonian cycle.
Statement C is false.
Hamiltonian path problem can be solved in polynomial time for directed acyclic graph.
Statement D is true.
In graph power concept, $G^3$ connects vertices having distance at most $3$ in $G$.
Statement E is true.
If any NP-Complete problem is solved in polynomial time, then $P=NP$.
So, correct statements are A, D and E.
Correct option is:
$\boxed{(c)\ \text{A, D, E only}}$
Match List - I with List - II.
| List - I (Recurrence Relations) | List - II (Complexity) |
| (A) $T(n)=2T(n/2)+n$ | (I) $T(n)=\theta(n\log n)$ [exact solution] |
| (B) $T(n)=T(n/2)+1$ | (II) $O(n^2)$ |
| (C) $T(n)=2T(n/2)+1$ | (III) $T(n)=\theta(n)$ [exact solution] |
| (D) $T(n)=T(n-1)+1$ | (IV) $O(\log n)$ |
Choose the correct answer from the options given below :
Solution
(A) $T(n)=2T(n/2)+n$
Master theorem
$a=2,; b=2,; f(n)=n$
$\Rightarrow T(n)=\theta(n\log n)$
So (A) → (I)
(B) $T(n)=T(n/2)+1$
Divide size halves each step
$\Rightarrow T(n)=O(\log n)$
So (B) → (IV)
(C) $T(n)=2T(n/2)+1$
Master theorem
$\Rightarrow T(n)=\theta(n)$
So (C) → (III)
(D) $T(n)=T(n-1)+1$
Linear recurrence
$\Rightarrow T(n)=O(n)$
Closest option given:
(D) → (II)
Thus matching:
(A)-(I), (B)-(IV), (C)-(III), (D)-(II)
Solution
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
