# NTA UGC NET Computer Science Paper II December 2018 - Part 2

21.       The solution of recurrence relation:
T(n) = 2T(sqrt(n)) + lg (n)
is
(1) O(lg (n))
(2) O(n lg (n))
(3) O(lg (n) lg (n))
(4) O(lg (n) lg (lg (n)))
22.       The elements 42,25,30,40,22,35,26 are inserted one by one in the given order into a max-heap. The resultant max-heap is sorted in an array implementation as
(1) <42,40,35,25,22,30,26>
(2) <42,35,40,22,25,30,26>
(3) <42,40,35,25,22,26,30>
(4) <42,35,40,22,25,26,30>
23.       Consider two sequences X and Y:
X = <0,1,2,1,3,0,1>
Y = <1,3,2,0,1,0>
The length of longest common subsequence between X and Y is
(1) 2
(2) 3
(3) 4
(4) 5
24.       Consider the following postfix expression with single digit operands:
623/42+68
The top two elements of the stack after the second is evaluated, are:
(1) 8,2
(2) 8,1
(3) 6,2
(4) 6,3
25.       A binary search tree is constructed by inserting the following numbers in order:
60, 25, 72, 15, 30, 68, 101, 13, 18, 47, 70, 34
The number of nodes in the left subtree is
(1) 5
(2) 6
(3) 7
(4) 3
26.       In a ternary tree, the number of internal nodes of degree 1, 2, and 3 is 4, 3, and 3 respectively. The number of leaf nodes in the ternary tree is
(1) 9
(2) 10
(3) 11
(4) 12
27.       Match List-I with List-II and choose the correct answer from the code given below:
List I (Graph Algorithm)        List II (Time Complexity)
(a) Dijkstra’s algorithm            (i) O(E lg E)
(b) Kruskal’s algorithm           (ii) Θ(V3)
(c) Floyd-Warshall algorithm (iii) O(V2)
(d) Topological sorting                        (iv) Θ(V+E)
where V and E are the number of vertices and edges in graph respectively.
Code:
(1) (a)-(i), (b)-(iii), (c)-(ii), (d)-(iv)
(2) (a)-(iii), (b)-(i), (c)-(ii), (d)-(iv)
(3) (a)-(i), (b)-(iii), (c)-(iv), (d)-(ii)
(4) (a)-(iii), (b)-(i), (c)-(iv), (d)-(ii)
28.       In K-coloring of an undirected graph G=(V,E) is a function. c:V→{0,1,…,K−1} such that c(u)≠c(v) for every edge (u,v)E.
Which of the following is not correct?
(1) G is bipartite
(2) G is 2-colorable
(3) G has cycles of odd length
(4) G has no cycles of odd length
29.       Consider a singly linked list. What is the worst case time complexity of the best-known algorithm to delete the node a, pointer to this node is q, from the list?
(1) O(n lg n)
(2) O(n)
(3) O(lg n)
(4) O(1)
30.    The second smallest of n elements can be found with ............... comparisons in the worst case.
(1) n−1
(2) lg n
(3) n+ceil(lg n) - 2
(4) 3n/2
31.    Let r = a(a + b)*, s = aa*b and t = a*b be three regular expressions.
Consider the following:
(i) L(s) L(r) and L(s) L(t)
(ii) L(r) L(s) and L(s) L(t)
Choose the correct answer from the code given below:
Code:
(1) Only (i) is correct
(2) Only (ii) is correct
(3) Both (i) and (ii) are correct
(4) Neither (i) nor (ii) is correct
32.    Consider the language L given by
L = {2nkk>0, and n is non-negative integer number}
The minimum number of states of finite automaton which accepts the language L is
(1) n
(2) n+1
(3) n(n+1)/2
(4) 2n
33.    The number of substrings that can be formed from string given by
a d e f b g h n m p
is
(1) 10
(2) 45
(3) 55
(4) 56
34.    Consider the following two languages:
L1 = {x for some y with y= 2x,xy L and L is regular language}
L2 = {x for some y such that x= y, xy L and L is regular language}
Which one of the following is correct?
Code:
(1) Only L1 is regular language
(2) Only L2 is regular language
(3) Both L1 and L2 are regular languages
(4) Both L1 and L2 are not regular languages
35.    Consider the following languages:
L1 = {an+m bn am n,m ≥ 0}
L2 = {an+m bn+m an+mn,m ≥ 0}
Which of the following is correct?
Code:
(1) Only L1 is context-free language
(2) Only L2 is context-free language
(3) Both L1 and L2 are context free languages
(4) Both L1 and L2 are not context free languages
36.    Consider R to be any regular language and L1, L2 be any two context-free languages. Which of the following is correct?
(1) L1’ is context free
(2) (L1L2)’ – R is context free
(3) L1 ∩ L2 is context free
(4) L1 – R is context free
37.    Consider the following problems:
(i) Whether a finite state automaton halts on all inputs?
(ii) Whether a given context free language is regular?
(iii) Whether a Turing machine computes the product of two numbers?
Which one of the following is correct?
Code:
(1) Only (i) and (iii) are undecidable problems
(2) Only (ii) and (iii) are undecidable problems
(3) Only (i) and (ii) are undecidable problems
(4) (i), (ii) and (iii) are undecidable problems
38.    Which of the following problems is decidable for recursive languages (L)?
(1) Is L = ϕ?
(2) Is w L, where w is a string?
(3) Is L = Σ*?
(4) Is L = R, where R is a given regular set?
39.    Consider the following grammar G:
S → A B
A → a c
B → b c
where {S, A, B} is the set of non-terminals, {a, b, c,} is the set of terminals.
Which of the following statement(s) is/are correct?
S1:          LR(1) can parse all strings that are generated using grammar G.
S2:          LL(1) can parse all strings that are generated using grammar G.
Choose the correct answer from the code given below:
Code:
(1) Only S1
(2) Only S2
(3) Both S1 and S2
(4) Neither S1 nor S2