## 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)
Algorithms
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)
Data-Structures
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
Digital-Logic-Design
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
Computer-Networks
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*
Theory-of-Computation
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
Computer-Networks
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)
Algorithms
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
Computer-Organization
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
Database-Management-System
Question 9 Explanation:
Derived attributes are depicted by dashed ellipse.
Example: Question 10
Among all given option, ___ must reside in the main memory.
Operating-Systems
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
Computer-Networks
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’
Digital-Logic-Design
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)
Computer-Organization
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
Algorithms
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
Database-Management-System
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
Compiler-Design
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
__number of queues are needed to implement symbol and is acting as permanent database
 A Variable Table B Terminal Table C Keyword Table D Identifier Table
Compiler-Design
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