## Introduction

UGC NET Exam is a very popular exam in India for people interested in research. Previous Year Questions are an excellent option to learn about the exam pattern. By solving the PYQs, you will get a basic idea about your preparation.

Refer to July 2018 Paper II Part 1 __here__.

Refer to July 2018 Paper II Part 3 __here__.

Refer to July 2018 Paper II Part 4 __here__.

You can evaluate your weak areas and work on them to perform better in the examination. In this article, we have given the questions of UGC NET July 2018 Paper II. We have also explained every problem adequately to help you learn better.

## July 2018 Paper II Part 2

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**

2(n)-1 where n is the for the leaves nodes. So by that way we have exactly 37 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)

**Answer: 4**

The 8-Queen problem is a Backtracking algorithm.

Single-Source shortest paths is a Greedy approach

STRASSEN’s Matrix multiplication is a Divide and conquer

Optimal binary search trees is Dynamic programming.

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**

Actually radix sort is not a comparison based algorithm. ===> No.of comparissions = 0

So, here comparisons account for the comparisons involved in iterations.

given that, it is 5 digit number ( remember that totally we have 5 iterations due to no. of digits =5 )

29. A 5-ary tree is a 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**

Everyone was given marks for the above question due to an unclear statement of the question regarding the number of leaf nodes.

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**

Given, n Boolean variables.

If there are n Boolean variables, the number of Boolean functions possible is 2^{n}.

Suppose we have 4 Boolean variables, so the number of Boolean functions is = 2^{4} = 16

Here, we have to find the order of the algorithm which determines whether the Boolean function produces an output 1.

For this, we need to check each Boolean function one by one in the worst case.

As there are 2^{n} Boolean functions, we have to check all of these in the worst case.

As it is in exponential form. So, the order of the algorithm is also in exponential form.

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**

Two finite state machines are said to be equivalent if they recognize the same set of tokens.

Having the same number of edges and states doesn’t mean that FA is equivalent.

32. The finite state machine given in the 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**

This finite state machine will accept any string of an odd number of a’s and an odd number of b’s.

33. A pushdown automaton 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**

A pushdown automaton behaves like a Turing machine when the number of auxiliary memory is 2 or more.

PDA with 2 or more auxiliary memory has the same expressive power.

Generally, PDA has one auxiliary memory.

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**

Pushdown __Automata__ can recognize language generated by Context-free grammar or regular 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) n^{2}

**Answer: 1**

The number of productions to be used is 2n-1.

36. Consider the following two Grammar:

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**

A grammar is said to be ambiguous if we can generate more than one parse for a same given string.

Here both Grammar G1 and G2 are ambiguous For G1 we can generate more than one parse tree for the same string “ababa”.

Since G1 is ambiguous and for G2 we can also generate more than one parse for the string ” ab ” since G2 is also 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

**Answer: 4**

Context-sensitive language can be recognized by linear bounded automata.

Context-free languages and regular languages are accepted by pushdown automata.

38. The set A={ 0^{n} 1^{n} 2^{n} | 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**

The given grammar is context-sensitive.

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**

This corresponds to starting at the leaves of the parse tree also known as shift-reduce parsing.

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**

There exists no algorithm for deciding if any two Turing machines M 1 and M 2 accept the same language. True

The problem of determining whether a Turing machine halts on any input is undecidable.True

Both statements are correct.

41. A slotted ALOHA network transmits 200-bit frames using a shared channel with a 200 Kbps bandwidth. Find the throughput of the system, if the system (all stations put together) produces 250 frames per second:

(1) 49

(2) 368

(3) 149

(4) 151

**Answer: 1**

The frame transmission time=200/200 kbps=1ms

G=1/4

So S=Ge^{-G} = 0.195= 19.5%

This means that the throughput is 250 * 0.195=49 frames.

Only 49 out of 250 frames will survive.

42. The period of a signal is 100 ms. Its frequency is .............

(1) 100^{3} Hertz

(2) 10^{−2} kHz

(3) 10^{−3} kHz

(4) 10^{5} Hertz

**Answer: 2**

We know that:

frequency(f) = 1 / Timeperiod(T)

Given timeperiod(T) = 100 ms

f = 1 / 100ms

f = 1000 / 100000 ms

We know that 1000 ms = 1 sec and we can write 1000 as 1 k

i.e. f = 1k / 100s

f = 10-2 kHz (1 / s = Hz)

43. The dotted-decimal notation of the following IPV4 address in binary notation is ...................

10000001 00001011 00001011 11101111

(1) 111.56.45.239

(2) 129.11.10.238

(3) 129.11.11.239

(4) 111.56.11.239

**Answer: 3**

IPV4 address = 10000001 00001011 00001011 11101111

10000001 = 129

00001011 = 11

00001011 = 11

11101111 = 239

IPV4 address 10000001 00001011 00001011 11101111 is equivalent to 129.11.11.239

44. Which of the following statements are true?

(a) Advanced Mobile Phone System (AMPS) is a second-generation cellular phone system.

(b) IS - 95 is a second-generation cellular phone system based on CDMA and DSSS.

(c) The Third generation cellular phone system will provide universal personnel communication.

Code:

(1) (a) and (b) only

(2) (b) and (c) only

(3) (a), (b) and (c)

(4) (a) and (c) only

**Answer: 2**

Advanced Mobile Phone System (AMPS) is a First generation cellular phone system.

IS – 95 is a second-generation cellular phone system based on CDMA and DSSS.True

The Third generation cellular phone system will provide universal personnel communication. True

45. Match the following symmetric block ciphers with corresponding block and key sizes:

List - I

(a) DES

(b) IDEA

(c) BLOW FISH

(d) AES

List - II

(i) block size 64 and key size ranges between 32 and 448

(ii) block size 64 and key size 64

(iii) block size 128 and key sizes 128, 192, 256

(iv) block size 64 and key size 128

Code:

(a) (b) (c) (d)

(1) (iv) (ii) (i) (iii)

(2) (ii) (iv) (i) (iii)

(3) (ii) (iv) (iii) (i)

(4) (iv) (ii) (iii) (i)

**Answer: 2**

In DES 64 Bit is Block Size and 64 Bit Key initially, later key gets converted in 56 bits.

46. Which of the following statements are true?

(a) Three broad categories of Networks are

(i) Circuit Switched Networks

(ii) Packet Switched Networks

(iii) Message Switched Networks

(b) Circuit Switched Network resources need not be reserved during the set-up phase.

(c) In packet switching there is no resource allocation for packets.

Code:

(1) (a) and (b) only

(2) (b) and (c) only

(3) (a) and (c) only

(4) (a), (b) and (c)

**Answer: 3**

Three broad categories of Networks are

(i) Circuit Switched Networks

(ii) Packet Switched Networks

(iii) Message Switched Networks True

Circuit Switched Network resources need not be reserved during the set-up phase. False because resources need to be reserved

In packet switching, there is no resource allocation for packets. True

47. In Challenge-Response authentication the claimant ...............

(1) Proves that she knows the secret without revealing it

(2) Proves that she doesn’t know the secret

(3) Reveals the secret

(4) Gives a challenge

**Answer: 1**

Challenge-Response authentication is a computer security protocol in which one party ask a question and another party must provide a valid answer. I.e. she knows the secret without revealing it or will provide the secret when it is asked.

48. Decrypt the message “WTAAD” using the Caesar Cipher with key=15.

(1) LIPPS

(2) HELLO

(3) OLLEH

(4) DAATW

**Answer: 2**

In the Ceaser cypher algorithm encryption and decryption takes place.

During encryption right shift takes place depending upon the key and in decryption left shift takes place depending on the key.

In the given question key value is 15 and decryption is asked:

The given message is WTAAD

Left shift 15 on W is H

Left shift 15 on T is E

Left shift 15 on A is L

Left shift 15 on A is L

Left shift 15 on D is O

The decrypted message will HELLO.

49. To guarantee the correction of up to t errors, the minimum Hamming distance dmin is a block code must be ................

(1) t+1

(2) t−2

(3) 2t−1

(4) 2t+1

**Answer: 4**

To guarantee correction of up to t errors in all cases, the minimum Hamming distance in a block code must be dmin = 2t + 1.

50. Encrypt the Message “HELLO MY DEARZ” using Transposition Cipher with

(1) HLLEO YM AEDRZ

(2) EHOLL ZYM RAED

(3) ELHL MDOY AZER

(4) ELHL DOMY ZAER

**Answer: 3**

Given message is “HELLO MY DEARZ” Now arrange thenm in group of 4

I.e. HELL OMYD EARZ

i.e. replace second character in abobe format to the first place and fourth character to the first place, first character to the third place and third character to the

fourth place.

Encrypted message will be ELHL MDOY AZER.