Computer Science Study Materials for Competitive Exams

Sample Questions, Previous Year Solved Papers, Study Materials For Competitive Examinations Like UGC NET, SET And GATE Computer Science.

Friday, 10 May 2019

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)
Answer: 1
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
Answer: 2
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
Answer: 3
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
Answer: 4
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
Answer: 4
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
Answer: 2
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)
Answer: 4
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
Answer: 3
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
Answer: Marks to all
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
(3) Quadratic
(4) Exponential
Answer: 4
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
Answer: 3
32.    The finite state machine given in figure below recognizes:
(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
Answer: 4
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
Answer: 4
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
Answer: 3
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
Answer: 1
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
Answer: 3
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
Answer: 4
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
Answer: 1
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
Answer: 2
40.    Consider the following statements( ):
S1 : There exists no algorithm for deciding if any two Turing machines M1 and M2 accept the same language.
S2 : The problem of determining whether a Turing machine halts on any input is undecidable.
Which of the following options is correct?
(1) Both S1 and S2 are correct
(2) Both S1 and S2 are not correct
(3) Only S1 is correct
(4) Only S2 is correct
Answer: 1

No comments:

Post a Comment