JNU 2018-2 PhD CS

 Question 1
If L and ~L (complement of L) are recursive enumerable, then L is
 A regular B context free C context sensitive D 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
 A halts B does not halt C goes into loop forever D 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
 A it is recursively enumerable B L can be enumerated by some Turing machine C it is recursive D 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
 A empty B terminal C non-terminal D 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
 A O(m2) B O(2m) C O(m) D 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?
 A It is an abstract data type B It is usually non-volatile C It is a logical storage unit D 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?
 A 4 B 5 C 6 D 7
Question 7 Explanation:
 Question 8
Which of the following is the address generated by the CPU?
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?
 A Communication within the process B Communication between two processes C Communication between two threads of same process D 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?
 A Magnetic disk B Floppy disk C Cache D 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?
 A Quality of service B No priority service C Bandwidth utilization D All of the above
 Question 12
PID is used by the system to identify
 A a process B file name C i-node D 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?
 A Packet switching B Circuit switching C Data switching D 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
 A it divides one large network into several smaller ones B it divides network into network classes C it speeds up the speed of network D 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
 A 255.255.255.1 B 255.255.255.0 C 255.255.255.254 D 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
 Question 16
Which is not true about an AVL tree of n nodes?
 A Average space complexity is O(n) B Average space complexity is O(log (n)) C Worst space complexity is O(n2) D 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).
 Question 17
The logical relationship among data items is defined by
 A data structure B data relationship C storage structure D data operation
 Question 18
One generally uses which of the following data structures to recollect some past happening/event?
 A Array B Queue C Stack D Link
 Question 19
The time complexity of inserting a node in a doubly linked list is
 A O(n2 log(n)) B O(n log (n)) C O(log (n)) D 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?
 A Huffman code B