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

21.       The solution of the recurrence relation
T(m) = T(3m/4) + 1 is:
(1) θ (lg m)
(2) θ (m)
(3) θ (mlg m)
(4) θ (lglg m)
22.       Consider the array A=<4, 1, 3, 2, 16, 9, 10, 14, 8, 7>. After building heap from the array A, the depth of the heap and the right child of max-heap are .............. and ..................
respectively. (Root is at level 0).
(1) 3, 14
(2) 3, 10
(3) 4, 14
(4) 4, 10
23.       A hash function h defined 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) 3
(2) 4
(3) 5
(4) 6
24.       Which of the following algorithms solves the single-source shortest paths?
(1) Prim’s algorithm
(2) Floyd - Warshall algorithm
(3) Johnson’s algorithm
(4) Dijkstra’s algorithm
25.       A text is made up of the characters A, B, C, D, E each occurring with the probability 0.08, 0.40, 0.25, 0.15 and 0.12 respectively. The optimal coding technique will have the average length of:
(1) 2.4
(2) 1.87
(3) 3.0
(4) 2.15
26.       A binary search tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 19 leaves:
(1) cannot have more than 37 nodes
(2) has exactly 37 nodes
(3) has exactly 35 nodes
(4) cannot have more than 35 nodes
27.       Match the following with respect to algorithm paradigms :
List - I
(a) The 8-Queen’s problem
(b) Single-Source shortest paths
(c) STRASSEN’s Matrix multiplication
(d) Optimal binary search trees
List - II
(i) Dynamic programming
(ii) Divide and conquer
(iii) Greedy approach
(iv) Backtracking
Code:
(a)  (b)  (c)  (d)
(1) (iv)  (i)   (iii)  (ii)
(2) (iv)  (iii)  (i)   (ii)
(3) (iii)  (iv)  (ii)  (i)
(4) (iv)  (iii)  (ii)  (i)
28.       The maximum number of comparisons needed to sort 9 items using radix sort is (assume each item is 5 digit octal number):
(1) 45
(2) 72
(3) 360
(4) 450
29.       A 5-ary tree is tree in which every internal node has exactly 5 children. The number of left nodes in such a tree with 8 internal nodes will be:
(1) 30
(2) 33
(3) 45
(4) 125
30.    Consider a Boolean function of ‘n’ variables. The order of an algorithm that determines whether the Boolean function produces a output 1 is:
(1) Logarithmic
(2) Linear
(4) Exponential
31.    Two finite state machines are said to be equivalent if they:
(1) Have the same number of edges
(2) Have the same number of states
(3) Recognize the same set of tokens
(4) Have the same number of states and edges
(1) any string of odd number of a’s
(2) any string of odd number of b’s
(3) any string of even number of a’s and odd number of b’s
(4) any string of odd number of a’s and odd number of b’s
33.    A pushdown automata behaves like a Turing machine when the number of auxiliary memory is:
(1) 0
(2) 1
(3) 1 or more
(4) 2 or more
34.    Pushdown automata can recognize language generated by ................
(1) Only context free grammar
(2) Only regular grammar
(3) Context free grammar or regular grammar
(4) Only context sensitive grammar
35.    To obtain a string of n Terminals from a given Chomsky normal form grammar, the number of productions to be used is:
(1) 2n−1
(2) 2n
(3) n+1
(4) n2
36.    Consider the following two Grammars:
G1 : S → SbS | a
G2 : S → aB | ab, A→GAB | a, B→ABb | b
Which of the following option is correct?
(1) Only G1 is ambiguous
(2) Only G2 is ambiguous
(3) Both G1 and G2 are ambiguous
(4) Both G1 and G2 are not ambiguous
37.    Context sensitive language can be recognized by a:
(1) Finite state machine
(2) Deterministic finite automata
(3) Non-deterministic finite automata
(4) Linear bounded automata
38.    The set A={ 0n 1n 2n | n=1, 2, 3, ......... } is an example of a grammar that is:
(1) Context sensitive
(2) Context free
(3) Regular
(4) None of the above
39.    A bottom-up parser generates:
(1) Left-most derivation in reverse
(2) Right-most derivation in reverse
(3) Left-most derivation
(4) Right-most derivation