## Nielit Scentist-B [02-12-2018]

 Question 1
For the given recurrence equation
T(n)=2T(n-1), if n>0.
=1, otherwise
 A O(nlogn) B O(n2) C O(2n) D O(n)
Question 1 Explanation:
T(n) = 2T (n - 1) + 1
= 2 [2T(n - 2) + 1] + 1
= 22 T(n - 2) + 3

= 2kT(n - k) + (2k - 1)
= 2n-1T(1) + (2n-1 - 1)
= 2n-1+ 2n-1 - 1
= 2n - 1
≅ O( 2n )
 Question 2
___ number of leaf nodes in a rooted tree of n nodes, where each node is having 0 or 3 children.
 A n/2 B (2n+1)/3 C (n-1)/n D (n-1)
Question 2 Explanation:
→ Any n-ary tree in which every node has either 0 or n children will take L=(n-1)*I +1
[ Where L is the number of leaf nodes and I is the number of internal nodes]
→ Given data n=3.
L=(3-1)I +1
=2I +1 ------------> 1
→ To find total number of nodes is nothing but sum of leaf nodes and internal nodes
n=L+I ------------> 2
With the help of 1 and 2, we get L =(2n+1)/3/
 Question 3
___ number of gates are required to implement the boolean function (AB+C) with using only 2 input NOR gates.
 A 2 B 3 C 4 D 5
Question 3 Explanation:
NOR is Complement of OR
AB+C
= (A+C)(B+C) ← Distribution of + over
= ((A+C)’+(B+C)’)’
1st NOR- (A+C)’. Let X = (A+C)’
2nd NOR- (B+C)’. Let Y = (B+C)’
3rd NOR- (X+Y)’
 Question 4
Time To Live(TTL) field in the IP datagram is used___
 A To optimize throughput B To prevent packet looping C To reduce delays D To prioritize packets
Question 4 Explanation:
→ Time to Live (TTL) is a limit on the period of time or transmissions in computer and computer network technology that a unit of data (e.g. a packet) can experience before it should be discarded.
→ If the limit is not defined then the packets can go into an indefinite loop.
→ The packet is discarded when the time to live field reaches 0 to prevent looping.
 Question 5
Consider the following finite state automaton. The language accepted by this automaton is given by the regular.
 A ab*b* B a*b* C b*b D b*ab*
Question 5 Explanation:
According to the given state transition diagram, the regular expression is
Step-1: Starting state has loop with symbol ‘b’ . It means, we can get n number of times ‘b’.
Step-2: The symbol ‘a’ between the starting state and end state. It means we can get only one
‘a’ after b*.
Step-3: The final state also having self loop with symbol ‘b’.
 Question 6
 A 255.255.192.192 B 255.255.255.198 C 255.255.255.240 D 255.255.257.240 E None of the above
Question 6 Explanation:

The last octet of given DBA is 0001 1111. So, in Subnet mask address all should be 1’s except last 5 digits, i.e., 27 bit for NID which is 255.255.255.224.
The correct answer would be none of these.
 Question 7
The smallest element that can be found in time___ in a binary max heap
 A O(nlogn) B O(logn) C O(n) D O(n2)
Question 7 Explanation:
We need to traverse all nodes in order to identify smallest element because it is not following binary search tree properties. Searching time for ‘n’ elements will take O(n) in worst case.
 Question 8
The ALU uses ____ to store intermediate result.
 A Cache B Registers C Accumulators D Stack
Question 8 Explanation:
→ An accumulator is a register for short-term, intermediate storage of arithmetic and logic data in a computer's CPU (central processing unit).
→ A processor register (CPU register) is one of a small set of data holding places that are part of the computer processor.
→ Cache memory is a small-sized type of volatile computer memory that provides high-speed data access to a processor and stores frequently used computer programs, applications and data.
 Question 9
___symbol is used to denote derived attribute in ER model
 A Dashed ellipse B Square ellipse C Ellipse with attribute name undIrected D Rectangular box
Question 9 Explanation:
Derived attributes are depicted by dashed ellipse.
Example:
 Question 10
Among all given option, ___ must reside in the main memory.
Question 10 Explanation:
→ A loader is the part of an operating system that is responsible for loading programs and libraries.
→ It is one of the essential stages in the process of starting a program, as it places programs into memory and prepares them for execution.
→ Loading a program involves reading the contents of the executable file containing the program instructions into memory, and then carrying out other required preparatory tasks to prepare the executable for running.
→ Once loading is complete, the operating system starts the program by passing control to the loaded program code.
Note: The loader is a program that loads the object program from the secondary memory into the main memory for execution of the program
 Question 11
If the period of a signal is 100 ms. Then its frequency in Hertz is___
 A 10 B 100 C 1000 D 10000
Question 11 Explanation:
Given data,
Frequency = 1/Period.
Frequency = 1/100 x 10-3 Hz
= 10 Hz
 Question 12
(A+C’)(B’+C’) simplifies to ______
 A AC’ +B’ B C(A’+B’) C BC’+A D AB’+C’
Question 12 Explanation:
Distributive law:
x + ( y. z) = (x + y) . (x + z)
Proof:
 Question 13
Identify the true statement from the given statements. Program relocation at run time:
1. Requires transfer complete block to some memory locations
 A (1) B (1) and (2) C (1),(2) and (3) D (1) and (3)
Question 13 Explanation:
→ Program relocation at run time transfer complete block to some memory locations.
 Question 14
___ is the worst case time complexity for all operations(i.e. Search,update and delete) in a general binary search tree
 A O(n) B O(nlogn) C O(logn) for search and insert, and O(n) for delete D None of these
Question 14 Explanation:
→ Suppose the elements are not in sorted order, it will take O(n) time for worst case time complexity.
→ In question, they are not mentioned about elements are sorted or unsorted. So, worst case we have to consider unsorted elements.
→ All operations(i.e. Search,update and delete) will take O(n).
 Question 15
Maximum number of superkeys for the relation schema R(X,Y,Z,W) with X as the key is:
 A 6 B 8 C 9 D 12
Question 15 Explanation:
→ Maximum no. of possible super keys for a relation with n attributes with one candidate key
(only one attribute) = 2n-1
Here, n = 4.
→ So, the possible super keys = 24-1 = 8
→ The super keys are: X, XY, XZ, YZ, XYZ, XYW, YZW, XYZW.
 Question 16
Identify the correct nodes and edges in the given intermediate code:
(1) i=1
(2) t1=5*I
(3) t2=4*t1
(4) t3=t2
(5) a[t3]=0
(6) i=i+1;
(7) if i<15 goto(2)
 A 33 B 44 C 43 D 34
Question 16 Explanation:
Step-1: Initialization we are taking one node
Step-2: From 2nd statement to 6th statement we are performing some tasks.
Step-3: It indicate if condition, so it’s another statement. And the back loop indicates goto statement.
Here, total 3 nodes and 3 edges using control flow graph.

In options they have to give like this
3 and 3
4 and 4
4 and 3
3 and 4
But they combines the node value and edge value. It seems different value.
 Question 17
__ is holding an entry for each terminal symbol and is acting as permanent database
 A Variable Table B Terminal Table C Keyword Table D Identifier Table
Question 17 Explanation:
Symbol Table is an important data structure created and maintained by the compiler in order to keep track of semantics of variable i.e. it stores information about scope and binding information about names, information about instances of various entities such as variable and function names, classes, objects, etc.
Symbol Table entries: Each entry in symbol table is associated with attributes that support
→ compiler in different phases.
→ Items stored in Symbol table:
→ Variable names and constants
→ Procedure and function names
→ Literal constants and strings
→ Compiler generated temporaries
→ Labels in source languages
There are 17 questions to complete.

Register Now