UGC NET · PAPER 2
UGC NET Paper 2 Computer Science – Unit 7: Data Structures and Algorithms PYQ (December 2022 Shift 2)
Q25. How many different binary trees are possible with n nodes?
- n − 1
- 2n − 1
- 2n
- (1/(n+1)) · C(2n, n)
Q26. Let n denote a positive integer. A function f is defined as
f(n) = 0, if n = 1
f(n) = f(⌊n/2⌋) + 1, if n > 1
What is f(25), and what does this function find?
f(n) = 0, if n = 1
f(n) = f(⌊n/2⌋) + 1, if n > 1
What is f(25), and what does this function find?
- 4, ⌊log2 n⌋
- 14, ⌊log2 n⌋
- 4, ⌊n/2⌋
- 14, ⌊n/2⌋
Q27. Given the FFT, we can have a ______ time procedure for multiplying two polynomials A(x) and B(x) of degree bound n, where input and output representations are in coefficient form, assuming n is a power of 2.
- O(n2)
- O(n log2 n)
- O(2n)
- O(log2 n)
Q56. Circuit satisfiability problem: given a Boolean combinational circuit composed of AND, OR and NOT gates, is it satisfiable? A one-output Boolean combinational circuit is satisfiable if for some input the output is 1.
1. The circuit satisfiability problem belongs to class NP.
2. The circuit satisfiability problem is at least as hard as any language in NP.
3. Circuit satisfiability is NP-complete.
4. The size of the circuit is Θ(k2 + 1).
5. If P ≠ NP, this situation would contradict the NP-completeness of the problem.
Choose the correct answer from the options given below:
1. The circuit satisfiability problem belongs to class NP.
2. The circuit satisfiability problem is at least as hard as any language in NP.
3. Circuit satisfiability is NP-complete.
4. The size of the circuit is Θ(k2 + 1).
5. If P ≠ NP, this situation would contradict the NP-completeness of the problem.
Choose the correct answer from the options given below:
- 1, 3, 4 only
- 2, 4, 5 only
- 1, 2, 3 only
- 2, 3, 4 only
Q57. Given the expression (A + B * D) / (E − F) + G:
1. The prefix notation is + / + A * D B − E F G
2. The prefix expression is the reverse of the postfix expression.
3. The order of operands in the infix expression and postfix expression is the same.
4. The order of operands in the infix, prefix and postfix expressions is the same.
Choose the most appropriate answer from the options given below:
1. The prefix notation is + / + A * D B − E F G
2. The prefix expression is the reverse of the postfix expression.
3. The order of operands in the infix expression and postfix expression is the same.
4. The order of operands in the infix, prefix and postfix expressions is the same.
Choose the most appropriate answer from the options given below:
- 1, 3 and 4 only
- 3 and 4 only
- 1 and 2 only
- 1 and 4 only
Q72. Match List I with List II.
Choose the correct answer from the options given below:
Choose the correct answer from the options given below:
| List I | List II |
|---|---|
| a. Dijkstra's algorithm | I. Calculates path matrix |
| b. Prim's algorithm | II. Stores minimum cost edge |
| c. Warshall's algorithm | III. Stores the total cost from a source node to the current node |
| d. Kruskal's algorithm | IV. Finds minimum spanning tree |
- a-I, b-II, c-III, d-IV
- a-III, b-II, c-I, d-IV
- a-II, b-I, c-IV, d-III
- a-III, b-IV, c-II, d-I
Q82. For the weighted graph below, which of the following orders of adding edges can NOT be produced by a minimum spanning tree algorithm?
Edges (weight): a–b (1), d–f (1), b–f (2), c–d (2), b–c (3), d–e (3), b–d (4), c–e (4), e–f (5), a–c (6), c–f (7)
I. a-b II. d-f III. b-f IV. d-c V. d-e
Choose the correct answer from the options given below:
Edges (weight): a–b (1), d–f (1), b–f (2), c–d (2), b–c (3), d–e (3), b–d (4), c–e (4), e–f (5), a–c (6), c–f (7)
I. a-b II. d-f III. b-f IV. d-c V. d-e
Choose the correct answer from the options given below:
- I, II, III, IV, V
- I, II, IV, III, V
- II, I, III, V, IV
- II, I, IV, III, V
Q89. Statement I: Given a graph G = (V, E) in which each vertex v ∈ V has an associated positive weight w(v), we can use linear programming to find a lower bound on the weight of the minimum-weight vertex cover.
Statement II: The lower bound can be found by maximising Σv∈V w(v)x(v) subject to x(u) + x(v) ≥ 1 for each (u, v) ∈ V, x(v) ≤ 1 and x(v) ≥ 0 for each v ∈ V.
Choose the most appropriate answer.
Statement II: The lower bound can be found by maximising Σv∈V w(v)x(v) subject to x(u) + x(v) ≥ 1 for each (u, v) ∈ V, x(v) ≤ 1 and x(v) ≥ 0 for each v ∈ V.
Choose the most appropriate answer.
- Both Statement I and Statement II are correct
- Both Statement I and Statement II are incorrect
- Statement I is correct but Statement II is incorrect
- Statement I is incorrect but Statement II is correct