## JNU 2018-2 PhD CS

Question 1 |

If L and ~L (complement of L) are recursive enumerable, then L is

regular | |

context free | |

context sensitive | |

recursive |

Question 1 Explanation:

If L is recursively enumerable that means a TM accepts all strings in L. ~L is recursively enumerable means that a TM accepts all strings in ~L.So we can always decide if a string is in L or not. Since we can always decide so it is recursive.

Question 2 |

If transition is not defined on the current state and the current tape symbol, then the machine

halts | |

does not halt | |

goes into loop forever | |

None of the above |

Question 2 Explanation:

If transition is not defined in any state,then the state may be final or non final state.In both case it is said that the machine halts.If in final state there is no transition then we say machine halts and we say string accepted or if in non-final state there is no transition then we say machine halts and we say string is rejected.

Question 3 |

A language L may not be accepted by a Turing machine if

it is recursively enumerable | |

L can be enumerated by some Turing machine | |

it is recursive | |

None of the above |

Question 3 Explanation:

A language L may not be accepted by a Turing machine if L is not recursively enumerable. But note that if L is recursively enumerable then it will be definitely accepted by TM.

Question 4 |

The variable which produces an epsilon is called

empty | |

terminal | |

non-terminal | |

nullable |

Question 4 Explanation:

The variable which produces an epsilon is called nullable variable.

Question 5 |

The construction time for DFA having m nodes from an equivalent NFA is

O(m ^{2})
| |

O(2 ^{m}) | |

O(m) | |

O(log m) |

Question 5 Explanation:

The construction time for a DFA from an NFA is O(2^m) where m is the number of nodes in NFA because if no. of nodes in NFA is m then DFA can have upto 2^m states.

Question 6 |

Which of the following is true about a file?

It is an abstract data type | |

It is usually non-volatile | |

It is a logical storage unit | |

All of the above |

Question 6 Explanation:

File is logical storage unit with set of physical blocks

Question 7 |

Consider a fully associative cache with 8 cache blocks (numbered 0-7) and the following sequence of memory block requests:

4, 3, 25, 8, 19, 6, 25, 8, 16, 35, 45, 22, 8, 3, 16, 25, 7

If LRU replacement policy is used, which cache block will have memory block 7?

4 | |

5 | |

6 | |

7 |

Question 7 Explanation:

Question 8 |

Which of the following is the address generated by the CPU?

Physical address | |

Absolute address | |

Logical address | |

None of the above |

Question 8 Explanation:

The address generated by the CPU is a logical address, whereas the address actually seen by the memory hardware is a physical address

Question 9 |

What is interprocess communication?

Communication within the process | |

Communication between two processes | |

Communication between two threads of same process | |

None of the mentioned |

Question 9 Explanation:

Inter process communication is a set of programming interface which allow a programmer to coordinate activities among various program processes which can run concurrently in an operating system.

Question 10 |

Which of the following storage units has the highest access time?

Magnetic disk | |

Floppy disk | |

Cache | |

Swapping device |

Question 10 Explanation:

Among the given devices magnetic disk has the highest access time.

Question 11 |

Which of the following is/are the advantage(s) of connection-oriented networking?

Quality of service | |

No priority service | |

Bandwidth utilization | |

All of the above |

Question 12 |

PID is used by the system to identify

a process | |

file name | |

i-node | |

All of the above |

Question 12 Explanation:

A PID (i.e., process identification number) is an identification number that is automatically assigned to each process when it is created on a Unix-like operating system. A process is an executing (i.e., running) instance of a program. Each process is guaranteed a unique PID, which is always a non-negative integer.

Question 13 |

In which switching, multiplexing is used?

Packet switching | |

Circuit switching
| |

Data switching | |

All of the above |

Question 13 Explanation:

points. Circuit switching method is also called a connection oriented network. Two nodes must be physically and logically connected to each other to create a circuit switching network.

Question 14 |

The purpose of subnetting is

it divides one large network into several smaller ones | |

it divides network into network classes | |

it speeds up the speed of network | |

None of the above |

Question 14 Explanation:

Subnetting divides a network into smaller sections. It can have a number of purposes including easier network management and more organized networks, as well as various security and performance gains

Question 15 |

The network mask for a class C network is

255.255.255.1 | |

255.255.255.0 | |

255.255.255.254 | |

255.255.255.255 |

Question 15 Explanation:

In class C network first 24 bit is network id and next 8 bit is host id.

So in network mask of class C first 24 bit will have binary 1’s and next 8 bits will have binary 0’s.

So therefore network mask of class C will be 255.255.255.0

So in network mask of class C first 24 bit will have binary 1’s and next 8 bits will have binary 0’s.

So therefore network mask of class C will be 255.255.255.0

Question 16 |

Which is not true about an AVL tree of n nodes?

Average space complexity is O(n) | |

Average space complexity is O(log (n)) | |

Worst space complexity is O(n ^{2}) | |

Average insert complexity is O(log (n)) |

Question 16 Explanation:

The space complexity of an AVL tree is O(n) in both the average and the worst case because the AVL tree is balanced BST and will require space almost equal to the space required by complete binary tree which is O(n). But the average space complexity can never be O(logn) since no. of elements are n.

Also time complexity for inserting an element in AVL tree is O(logn) since the tree is balanced binary search tree whose height is O(logn).

Also time complexity for inserting an element in AVL tree is O(logn) since the tree is balanced binary search tree whose height is O(logn).

Question 17 |

The logical relationship among data items is defined by

data structure | |

data relationship | |

storage structure | |

data operation |

Question 18 |

One generally uses which of the following data structures to recollect some past happening/event?

Array | |

Queue | |

Stack | |

Link |

Question 19 |

The time complexity of inserting a node in a doubly linked list is

O(n ^{2} log(n)) | |

O(n log (n)) | |

O(log (n)) | |

O(n) |

Question 19 Explanation:

Strictly speaking an insertion is simply O(1). The other answers mostly correctly state that the complexity is O(n) if you need to search for the position in which to insert the new node

Question 20 |

Which of the following is not an application of priority queue?

Huffman code | |