Nielit STA [02-12-2018]

Question 1
Which register that shift complete binary number in one bit at a time and shift all the stored bits out at a time?
A
Parallel-in parallel-out
B
Parallel-in Serial-out
C
Serial-in parallel-out
D
Serial-in Serial-out
       Computer-Networks
Question 1 Explanation: 
SIPO is the register is loaded with serial data, one bit at a time, with the stored data being available at the output in parallel form.
SIPO:
A serial-in, parallel-out shift register is similar to the serial-in, serial-out shift register in that it shifts data into internal storage elements and shifts data out at the serial-out, data-out, pin. It is different in that it makes all the internal stages available as outputs. Therefore, a serial-in, parallel-out shift register converts data from serial format to parallel format.
More Information
Serial-in to Serial-out (SISO) - the data is shifted serially “IN” and “OUT” of the register, one bit at a time in either a left or right direction under clock control.
Parallel-in to Serial-out (PISO) - the parallel data is loaded into the register simultaneously and is shifted out of the register serially one bit at a time under clock control.
Parallel-in to Parallel-out (PIPO) - the parallel data is loaded simultaneously into the register, and transferred together to their respective outputs by the same clock pulse.
Question 2
Which among the following algorithm can’t be used with linked list?
A
Binary search
B
Linear Search
C
Insertion sort
D
Merge Sort
       Data-Structures
Question 2 Explanation: 
→ Binary search increases the traversal steps per element in linked list just to find the middle element. This makes it slow and inefficient. Whereas the binary search on an array is fast and efficient because of its ability to access any element in the array in constant time.
→ Merge sort is often preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.
→ Insertion sort & Linear search can use linked list. Note:But Binary search also can implement using linked list but it takes O(n) time complexity.
Question 3
A program P reads in 1000 integers in the range [0, 100] representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?
A
An array of 50 numbers
B
An array of 100 numbers
C
An array of 500 numbers
D
A dynamically allocated array of 550 numbers
       Data-Structures
Question 3 Explanation: 
→ Here we are storing values above 50 and we are ignoring the scores which is less than 50.
→ Then using array of 50 numbers is the best way to store the frequencies.
Question 4
In a risk based approach the risks identified mayn’t be used to:
A
Determine the test technique to be employed
B
Determine the extent of testing to be carried out
C
Prioritize testing in an attempt to find critical defects as early as possible
D
Determine the cost of the project
       Software-Engineering
Question 4 Explanation: 
Risk identification is the process of determining risks that could potentially prevent the program, enterprise, or investment from achieving its objectives. It includes documenting and communicating the concern.
Tasks of risk identification:
1. Determine the test technique to be employed
2. Determine the extent of testing to be carried out
3. Prioritize testing in an attempt to find critical defects as early as possible
Question 5
Simple network management protocol(SNMP) is a protocol that runs on:
A
Application layer
B
Transport layer
C
Network layer
D
Data link layer
       Computer-Networks
Question 5 Explanation: 
→ Simple Network Management Protocol (SNMP) is an Internet Standard protocol for collecting and organizing information about managed devices on IP networks and for modifying that information to change device behavior. Devices that typically support SNMP include cable modems, routers, switches, servers, workstations, printers, and more.
→ SNMP is a component of the Internet Protocol Suite as defined by the Internet Engineering Task Force (IETF). It consists of a set of standards for network management, including an application layer protocol, a database schema, and a set of data objects.
Question 6
In a database system, the domain integrity is not defined by:
A
The data type and the length
B
The NULL value rejection
C
The allowable values, through techniques like constraints or rules
D
Default value
       Database-Management-System
Question 6 Explanation: 
A domain defines the possible values of an attribute. Domain Integrity rules govern these values.
In a database system, the domain integrity is defined by:
1.The data type and the length
2.The NULL value acceptance
3.The allowable values, through techniques like constraints or rules
4.The default value
Question 7
Transformation that moves objects without deformation is called:
A
Rotation
B
Scaling
C
Translation
D
Morphism
       Software-Engineering
Question 7 Explanation: 
→ A translation process moves every point a constant distance in a specified direction. It can be described as a rigid motion.
→ A translation can also be interpreted as the addition of a constant vector to every point, or as shifting the origin of the coordinate system.
Question 8
Which of the following need not necessarily be saved on a context switch between processes?
A
Program counter
B
IO status information
C
CPU registers
D
Translation lookaside buffer
       Computer-Organization
Question 8 Explanation: 
→ Actually TLB (or) Cache memory to ensure correct program resumption.
→ With TLB (or) Cache memory we can get better performance but not mandatory.
→ Program counter, stack, I/O status information and registers must be saved on a context switch between processes.
Question 9
Given an random unsorted array ‘A’ in which every element is at most ‘d’ distance from is position in sorted array where d<Size(A). If we applied the insertion sort over this array, then the time complexity of algorithm is:
A
O(nlogd)
B
O(n2 logd)
C
O(nd)
D
O(n2d)
       Algorithms
Question 9 Explanation: 
→ Using insertion sort worst case time complexity is O(n2).
→ They are asking to find the atmost distance from every element. So, it will take O(n2*d) from every node.
Note: Using heap sort , time complexity will be O(nlogd) and most effective than insertion sort.
Question 10
To maintain transactional integrity and database consistency DBMS will use:
A
Triggers
B
Cursors
C
Locks
D
Pointers
       Database-Management-System
Question 10 Explanation: 
→ Locks are used to maintain transactional integrity and database consistency.
→ Concurrency control protocols can be broadly divided into two categories:
1.Lock based protocols
2.Timestamp based protocols
Question 11
The design of a class in C++ which can’t be inherited is achieved using ___ keyword before class declaration.
A
Final
B
Static
C
Sealed
D
Fixed
       C++
Question 11 Explanation: 
→ Final is a non-access modifier applicable only to a variable, a method or a class.
→ Final variable are used to create constant variables
→ Final methods are used to prevent method overriding
→ Final Classes are prevent inheritance
→ We make the Final class non-inheritable. When a class Derived tries to inherit from it, we get compilation error.
Question 12
CPU register to perform storage of arithmetic and logic results is called:
A
Instruction register
B
Program counter
C
Accumulator
D
Instruction Decoder
       Computer-Organization
Question 12 Explanation: 
→ An accumulator is a register in which intermediate arithmetic and logic results are stored.
→ In a computer's central processing unit (CPU), the accumulator is a register in which intermediate arithmetic and logic results are stored. Without a register like an accumulator, it would be necessary to write the result of each calculation (addition, multiplication, shift, etc.) to main memory, perhaps only to be read right back again for use in the next operation.
→ Access to main memory is slower than access to a register like the accumulator because the technology used for the large main memory is slower (but cheaper) than that used for a register. Early electronic computer systems were often split into two groups, those with accumulators and those without.
Question 13
The nature of any number i.e., positive or negative is recognized by its:
A
MSB
B
LSB
C
Bits
D
Nibble
       Digital-Logic-Design
Question 13 Explanation: 
This standard offers a way to code a number using 32 bits, and defines three components:
1.The plus/minus sign is represented by one bit, the highest-weighted bit (furthest to the left or MSB)
2.The exponent is encoded using 8 bits immediately after the sign
3.The mantissa (the bits after the decimal point) with the remaining 23 bits
Question 14
The output of the following code is:
int main()
{
static int x[ ]={1,2,3,4,5,6,7,8}
int i;
for(i=2;i<6;++i)
x[x[i]]=x[i];
for(i=0;i<8;++i)
printf(“%d”,x[i]);
Return 0;
}
A
12244668
B
11335578
C
12335578
D
12343676
       Programming-for-Output-Problems
Question 14 Explanation: 


Question 15
Using Mid Point algorithm, the new coordinates of the point P(x,y) having slope ‘m’ and constant and ‘b’ is calculated using:
A
F(x,y)=mx+b-y
B
F(x,y)=mx-y+b
C
F(x,y)=mx+b
D
F(x,y)=mx-y+b-y
       Engineering-Mathematics
Question 15 Explanation: 
In order to check this, we need to consider the implicit equation:
F(x,y) = mx + b - y
For positive m at any given X,
If y is on the line, then F(x, y) = 0
If y is above the line, then F(x, y) < 0
If y is below the line, then F(x, y) > 0
Question 16
The theory of bubbled input OR gate is interchangeable with a bubbled output AND gate is demonstrated and proved by:
A
Karnaugh map
B
DeMorgan’s second theorem
C
The commutative law of addition
D
The associative law of multiplication
       Digital-Logic-Design
Question 16 Explanation: 
Question 17
A DFD that can be used to plan or record the specific makeup of a system is called:
A
Level 0 DFD
B
Level 1 DFD
C
Level 2 DFD
D
Level 3 DFD
       Software-Engineering
Question 17 Explanation: 
→ A level 2 data flow diagram (DFD) offers a more detailed look at the processes that make up an information system than a level 1 DFD does It.
→ Higher level DFDs can be transformed into more specific lower level DFDs with deeper level of understanding unless the desired level of specification is achieved.
Question 18
For Providing large storage space the semiconductor based storage is not permitted now a days due to their:
A
Lack of sufficient resources
B
High cost per bit value
C
Lack of speed of operation
D
High cost of raw material
       Operating-Systems
Question 18 Explanation: 
→ In the case of semiconductor based memory technology, we get speed but the increase in the integration of various devices the cost is high.
Question 19
Let the next generation computer systems of 64 bit has virtual address space is of the same size as the physical address space. In such a case, if we remove the virtual space completely in new systems then which one of the following is true in this scenario?
A
Efficient implementation of multi user supports is no longer possible
B
The processor cache organization can be made more efficient now
C
Hardware support for memory management is no longer needed
D
CPU scheduling can be made more efficient now
       Operating-Systems
Question 19 Explanation: 
→ When designer decides to get rid of virtual memory entirely then hardware support is no longer needed.
→ Because special hardware support needed only for virtual memory.
→ Virtual memory is an integral part of a modern computer architecture. Implementations usually require hardware support, typically in the form of a memory management unit built into the CPU.
→ While not necessary, emulators and virtual machines can employ hardware support to increase performance of their virtual memory implementations.
Question 20
Which of the following statements is false?
A
There exist parsing algorithms for some programming languages whose complexities are less than O(n3)
B
A programming language which allows recursion can be implemented with static storage allocation
C
L-attributed definition can be evaluated in the framework of bottom-up parsing
D
Code improving transformation can be performed at both source language and intermediate code level.
       Compiler-Design
Question 20 Explanation: 
→ Statement I is true, as the bottom up and top down parser take O(n) time to parse the string , i.e. only one scan of input is required.
→ Statement II is false, as a programming language which allows recursion requires dynamic storage allocation.
→ Statement III is True, as L-attributed definition (assume for instance the L-attributed definition has synthesized attribute only) can be evaluated in bottom up framework.
→ Statement IV is true,Code improving transformations can be performed at both source language and intermediate code level. For example implicit type casting is also a kind of code improvement which is done during semantic analysis phase and intermediate code optimization is a topic itself which uses various techniques to improve the code such as loop unrolling, loop invariant.
Question 21
Which of the following is FALSE about inheritance in Java?
A
Private methods are final
B
Protected members are accessible within a package and inherited classes outside the package
C
Protected methods are final
D
We cannot override private methods
       Java
Question 21 Explanation: 
→ Methods declared public in a superclass must also be public in all subclasses (this, by the way, is the reason most of the applet methods are public).
→ Methods declared protected in a superclass must either be protected or public in subclasses; they cannot be private.
→ Methods declared private are not inherited and therefore this rule doesn't apply.
→ Methods declared without protection at all (the implicit package protection) can be declared more private in subclasses.
Question 22
Given a mask, M=255.255.255.248. How many subnet bits are required for given mask M?
A
2
B
3
C
4
D
5
       Computer-Networks
Question 22 Explanation: 
Converting the subnet mask 255.255.255.248 into binary is:
11111111.11111111.11111111.11111000
255.255.255.248/29 mask.
→ It is 32 bit address and number of bits in the Network ID is 29
→ Number of bits in host ID=32-29= 3
Question 23
Transparent mode firewall is a:
A
Layer 2 firewall
B
Layer 3 firewall
C
Layer 4 firewall
D
Layer 7 firewall
       Computer-Networks
Question 23 Explanation: 
→ Transparent mode firewall (or routed firewall) is a routed hop and acts as a default gateway for hosts that connect to one of its screened subnets.
→ A transparent firewall, on the other hand, is a Layer 2 firewall that acts like a "bump in the wire," or a "stealth firewall," and is not seen as a router hop to connected devices.
Question 24
The situation when we can’t use a SAX parser is:
A
We can process the XML document in a linear fashion from the top to down
B
We are processing a very large XML document whose DOM tree would consume too much memory
C
The problem to be solved involves only part of the XML document
D
When we are parsing HTML documents to read and store the contents written in fields.
       XML
Question 24 Explanation: 
We should use a SAX parser when:
→ You can process the XML document in a linear fashion from top to down.
→ The document is not deeply nested.
→ You are processing a very large XML document whose DOM tree would consume too much memory. Typical DOM implementations use ten bytes of memory to represent one byte of XML.
→ The problem to be solved involves only a part of the XML document.
→ Data is available as soon as it is seen by the parser, so SAX works well for an XML document that arrives over a stream.
Question 25
A routing protocol that was used for trail information that gets updated dynamically is:
A
Distance Vector
B
Path Vector
C
Link Vector
D
Multipoint
       Computer-Networks
Question 25 Explanation: 
→ In the context of routers, neighbors always means routers sharing a common data link.
→ A distance vector routing protocol sends its updates to neighboring routers and depends on them to pass the update information along to their neighbors.
→ For this reason, distance vector routing is said to use hop-by-hop updates.
Question 26
The catalan number for generating different binary trees is given by:
A
!2n / (!n*!(n+1))
B
C(n,2n) (n+1)
C
!n*C(2n,n) (n+1)
D
C(2n,n)/ !n
       Data-Structures
Question 26 Explanation: 
→ In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects. They are named after the Belgian mathematician Eugène Charles Catalan (1814–1894).
→ Total number of possible Binary Search Trees with n different keys
BST(n)=Cn=(2n)!/(n+1)!*n!
For n = 0, 1, 2, 3, … values of Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ….
So are numbers of Binary Search Trees.
→ Total number of possible Binary Trees with n different keys BT(n)=BST(n)*n!
Question 27
Which of the following problems are decidable?
  1. Does a given ever produce an output?
  2. If L is a context free language, then is L’ (complement of L) also context free?
  3. If L is a regular language, then is L’ also regular?
  4. If L is a recursive language, then is L’ also recursive?
A
(a), (b), (c), (d)
B
(a), (b)
C
(b), (c), (d)
D
(c), (d)
       Theory-of-Computation
Question 27 Explanation: 
→ The statement “Does a given program ever produce an output?” is same as the statement “Does a Turing Machine will halt for any arbitrary string?”, which is nothing but the “halting problem of Turing Machine”, hence statement 1 is undecidable.
→ Context free languages are not closed under complement operation, so complement of CFL may or may not be CFL. Hence statement 2 is also undecidable.
→ Complement of Regular languages is also regular. Since a DFA that accepts the complement of L, i.e. ∑* – L, can be obtained by swapping its final states with its non-final states and vice-versa. Hence it is decidable and if L is a regular language, then, L must also be regular.
→ Recursive languages are closed under complement, so if L is a recursive language then L must also be recursive, hence it is decidable.
Question 28
If G be an undirected connected graphs with distinct edge weight such that maximum weight and minimum weight of edge is given by emax and emin respectively. Then, Which of the following statements is TRUE?
A
Every minimum spanning tree of G must contain emin and emax
B
If emax is in a minimum spanning tree, then its removal must disconnect G
C
No minimum spanning tree contains emax
D
G has a multiple minimum spanning trees
       Algorithms
Question 28 Explanation: 

If they mentioned distinct weights then we will get only one MST. So, Option-C is most appropriate solution.
Question 29
Consider bottom up merge sort working on ‘n’ elements such that n=2i. The minimum number of comparisons in order to get sorted list is:
A
nlog(n/2)
B
nlogn
C
(nlogn)/2
D
logn
       Algorithms
Question 29 Explanation: 
Minimum comparison is only possible when first and last element of either array are smaller then first element of another. so in such as case at each level we will have n/2 comparisons In general= n/2 * number of levels = (nlogn)/2
Question 30
The best example of compile time polymorphism is:
A
Method declaration
B
Method overriding
C
Method overloading
D
Method Invoking
       Java
Question 30 Explanation: 
There are two types of polymorphism in java:
1) Static Polymorphism also known as compile time polymorphism
2) Dynamic Polymorphism also known as runtime polymorphism
→ Method Overloading allows us to have more than one method having the same name, if the parameters of methods are different in number, sequence and data types of parameters.
→ Dynamic polymorphism is a process in which a call to an overridden method is resolved at runtime, that's why it is called runtime polymorphism
Question 31
The correct order of the degrees of vertices that would form the connected graph as eulerian is:
A
1,2,3
B
2,3,4
C
2,4,5
D
1,3,5
       Engineering-Mathematics
Question 31 Explanation: 
→ Suppose a graph has n vertices with degrees d1,d2,d3,...,dn. Add together all degrees to get a new number d1 + d2 + d3 + ...+ dn = Dv. Then Dv =2e.
→ In words, for any graph the sum of the degrees of the vertices equals twice the number of edges. Stated in a slightly different way, Dv =2e says that Dv is ALWAYS an even number
→ 1+2+3=6
Question 32
Consider a B+ tree in which the maximum number of child nodes is 6. What is the minimum and maximum number of keys in such a tree?
A
3 and 4
B
2 and 5
C
2 and 4
D
3 and 5
       Database-Management-System
Question 32 Explanation: 
→ B+ tree in which the maximum number of child nodes is 6. Maximum number of keys 5.
→ Order is Key(5)+1=6.
→ Minimum children that a node can have would be ⌈6/2⌉ =3.
→ Minimum number of keys that a node can have becomes 3-1=2.
Question 33
The primary key of any table is selected from the:
A
Composite keys
B
Foreign keys
C
Candidate keys
D
Alternate keys
       Database-Management-System
Question 33 Explanation: 
→ In the relational model of databases, a primary key is a specific choice of a minimal set of attributes (columns) that uniquely specify a tuple (row) in a relation (table).
→ Informally, a primary key is "which attributes identify a record", and in simple cases are simply a single attribute: a unique id.
→ More formally, a primary key is a choice of candidate key (a minimal superkey); any other candidate key is an alternate key.
Question 34
Which of these classes is not part of Java’s collection framework?
A
Map
B
Array
C
Arraylist
D
Vector
       Java
Question 34 Explanation: 
The java.util.Map interface represents a mapping between a key and a value. The Map interface is not a subtype of the Collection interface. Therefore it behaves a bit different from the rest of the collection types.
Question 35
The time complexity of the Tarjan’s algorithm for finding the strongly connected components of a graph having m vertices and n edges is:
A
O(m*n)
B
O(m+n)
C
O(m2)
D
O(mn)
       Algorithms
Question 35 Explanation: 
Tarjan Algorithm
1. DFS search produces a DFS tree/forest
2. Strongly Connected Components form subtrees of the DFS tree.
3. If we can find head of such subtrees, we can print/store all the nodes in that subtree (including head) and that will be one SCC.
4. There is no back edge from one SCC to another (There can be cross edges, but cross edges will not be used while processing the graph).
Note: Time complexity for Tarjan’s algorithm is O(V+E)


Kosaraju’s algorithm
1) Create an empty stack ‘S’ and do DFS traversal of a graph. In DFS traversal, after calling recursive DFS for adjacent vertices of a vertex, push the vertex to stack. In the above graph, if we start DFS from vertex 0, we get vertices in stack as 1, 2, 4, 3, 0.
2) Reverse directions of all arcs to obtain the transpose graph.
3) One by one pop a vertex from S while S is not empty. Let the popped vertex be ‘v’. Take v as source and do DFS (call DFSUtil(v)). The DFS starting from v prints strongly connected component of v. In the above example, we process vertices in order 0, 3, 4, 2, 1 (One by one popped from stack).
Note: Time complexity for kosaraju’s algorithm is O(V+E)
Question 36
A planar graph is defined as:
A
A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices
B
A graph drawn in a plane in such a way that if the vertex set of graph can be partitioned into two non-empty disjoint subset X and Y in such a way that each edge of G has one end in X and one end in Y.
C
A simple graph which is Isomorphism to Hamiltonian graph.
D
A function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices
       Engineering-Mathematics
Question 36 Explanation: 
→ In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.
→ In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph.
→ A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.
Question 37
The process of rotating the image by 1800 without changing its size is called:
A
Translation
B
Rotation
C
Scaling
D
Reflection
       Graphics
Question 37 Explanation: 
The process of rotating the image by 1800 without changing its size is called Rotation
Question 38
Which IC is used for the implementation of 1 to 16 DEMUX?
A
IC 74154
B
IC 74155
C
IC 74139
D
IC 74138
       Digital-Logic-Design
Question 38 Explanation: 
Demultiplexer IC packages available are the TTL 74LS138 1 to 8-output demultiplexer, the TTL 74LS139 Dual 1-to-4 output demultiplexer or the CMOS CD4514 1-to-16 output demultiplexer.
Another type of demultiplexer is the 24-pin, 74LS154 which is a 4-bit to 16-line demultiplexer/decoder.
Question 39
Which of the following statements is true?
A
If a language is context free it can always be accepted by a deterministic pushdown automaton
B
The union of two context free language is context free
C
The intersection of two context free language is context free
D
The complement of a context free language is context free
       Theory-of-Computation
Question 39 Explanation: 
Context free languages closed under Union, concatenation and kleene star. But not close under intersection and complementation.
Question 40
Frequency hopping spread spectrum can be utilized to solve the problem of:
A
Data transfer
B
Enhancing signal strength
C
Interference between signals
D
Connection establishment
       Communication
Question 40 Explanation: 
→ Frequency-hopping spread spectrum (FHSS) transmission is the repeated switching of frequencies during radio transmission to reduce interference and avoid interception.
→ It is useful to counter eavesdropping, or to obstruct jamming of telecommunications. And it can minimize the effects of unintentional interference.
Question 41
Given the sequence of nodes {11,6,8,19,4,10,5,17,43,49,31} not necessarily in correct order for generating binary search tree. The corresponding postorder traversal of the BST is:
A
5,4,10,8,6,49,31,43,19,17,11
B
4,5,6,8,10,11,19,17,43,31,49
C
4,5,8,10,6,17,31,49,43,19,11
D
5,4,10,8,6,17,31,49,43,19,11
       Data-Structures
Question 41 Explanation: 

Post order: 5,4,10,8,6,17,31,49,43,19,11
Question 42
A lock which required is not acquired by database engine is:
A
Row lock
B
Page lock
C
Table lock
D
Attribute lock
       Database-Management-System
Question 42 Explanation: 
→ Each transaction requests locks of different types on the resources, such as rows, pages, or tables, on which the transaction is dependent.
→ The locks block other transactions from modifying the resources in a way that would cause problems for the transaction requesting the lock.
→ Each transaction frees its locks when it no longer has a dependency on the locked resources.
Question 43
A complete binary tree with the property Kni>=Kcn where Kn is nthnode value and Kc be the value of its child node is called:
A
B+ tree
B
Threaded binary tree
C
Heap
D
AVL tree
       Data-Structures
Question 43 Explanation: 
A complete binary tree with the property Kni>=Kcn where Kn is nthnode value and Kc be the value of its child node is called heap
Question 44
The name of parser generator that is used for SQL query parsing is:
A
Lexer parser generator
B
Syntactic parser generator
C
Tokenizer parser generator
D
SQL DML parser generator
       Database-Management-System
Question 44 Explanation: 
→ The parser takes SQL DML statements as input and creates instances of SQL Query Model classes if the SQL is syntactically valid. In addition to the syntactic validation, the parser can also perform a semantic validation.
→ The parser is extensible to support vendor specific dialects and custom source generation.
Question 45
In the Merge sort algorithm, the time taken by the algorithm to divide an array of size n into two equal halves and many times that divide is called in overall sorting procedure is:
A
O(1) and θ(logn)
B
θ(1) and θ(logn)
C
O(logn) and θ(logn)
D
θ(logn) and O(1)
Question 45 Explanation: 
→ In the Merge sort algorithm, the time taken by the algorithm to divide an array of size n into two equal halves is O(logn)
→ many times that divide is called in overall sorting procedure is O(logn)
Question 46
The best example of language for defining the non regular languages is:
A
Languages for palindrome and prime
B
Languages for palindrome and Even-Even
C
Language for prime and Even-Even
D
Language for palindrome and factorial
       Theory-of-Computation
Question 46 Explanation: 
Using the pumping lemma to show that a language is non-regular:
To show that L is not regular we need to do the following:
Question 47
Consider an undirected random graph of 16 vertices. The probability that there is an edge between a pair of vertices is ½. What is the expected number of unordered cycles of length three?
A
70
B
280
C
120
D
45
       Engineering-Mathematics
Question 47 Explanation: 
Among available ‘16’ vertices, we need to identify the cycles of length ‘3’.

So, the total probability that all three edges of the above exists
= 1/2 × 1/2 × 1/2 (as they are independent events)
= 1/8
Total number of ways in which we can select ‘3’ such vertices among ‘16’ vertices = 16C3 = 560
Total number of cycles of length ‘3’ out of 16 vertices = 560 × 1/8 = 70
Question 48
___ is a parameter passing method that waits to evaluate the parameter value until it is used?
A
Pass by value
B
Pass by name
C
Pass by reference
D
Pass by pointer
       Data-Structures
Question 48 Explanation: 
Pass by value: The method parameter values are copied to another variable and then the copied object is passed, that’s why it’s called pass by value.
Pass by reference: An alias or reference to the actual parameter is passed to the method.Passing a pointer to the actual parameter, and indirect through the pointer
Pass by name: re-evaluate the actual parameter on every use. For actual parameters that are simple variables, this is the same as call by reference. For actual parameters that are expressions, the expression is re-evaluated on each access.
There is no parameter passing method with the name “ Pass by pointer”
Question 49
Suppose that we have an MxN array ‘A’ in row major order, where the size of the elements is S. Then the location of A[i,j] elements is given by:
A
A+i*N*S
B
A+(i*N+j)*S
C
A+(i*N+j*M)*S
D
A+(i*M+j*N)*S
       Data-Structures
Question 49 Explanation: 
“A” is the base address,
M is number of the rows and N is number of Columns and S is size of the element.
The elements are storing row major order. So the elements are in the following order.
A[1,1],A[1,2],A[1,3] ….. A[1,N]
A[2,1],A[2,2],A[2,3]........A[2,N]
……
….
A[M,1],A[M,2],A[M,3]........A[M,N]
We will get the location of A[i,j] by using formula A+(i*N+j)*S where “i” is the index of the row and “j” index of the column and “N” is number of columns.
Question 50
A friend function in C++ can’t be used with:
A
Member function
B
Object
C
Class
D
Class template
       C++
Question 50 Explanation: 
→A C++ friend functions are special functions which can access the private members of a class.
→A friend function is declared by the class that is granting access, so friend functions are part of the class interface, like methods.
→Friend functions allow alternative syntax to use objects, for instance f(x) instead of x.f(), or g(x,y) instead of x.g(y). Friend functions have the same implications on encapsulation as methods.
→Friend of the class can be member of some other class.
→Friend of one class can be friend of another class or all the classes in one program, such a friend is known as GLOBAL FRIEND.
→Friend can access the private or protected members of the class in which they are declared to be friend, but they can use the members for a specific object.
→Friends are non-members hence do not get “this” pointer.
→Friends, can be friend of more than one class, hence they can be used for message passing between the classes.
→Friend can be declared anywhere (in public, protected or private section) in the class.
Question 51
The quantity of very long word is:
A
32 bits
B
64 bits
C
128 bits
D
256 bits
       Computer-Organization
Question 51 Explanation: 
A double word is a single unit of data expressing two adjacent words (a word is a standard unit of data for a certain processor architecture). For instance, if a single word is 16-bits in size, a double word would be 32-bits. A double word can doubled a second time, which turns it into a very long word that is 64-bits.
Question 52
Given language L={a(2*m)c(4*n)dnbm | m,n>=0}. Find the best appropriate match to recognize L.
A
Finite automata
B
Pushdown automata
C
Non deterministic turing machine
D
Non deterministic PDA
       Theory-of-Computation
Question 52 Explanation: 
It generate the string is L={ aaccccdb, aaaaccccccccddbb….,}. So, it is push down automata. It require one stack memory.
Question 53
Suppose the pipelined stages take {15,8,25,4,8} nanoseconds(ns) respectively. With a buffering delay of 5ns. Two pipelined implementation of the processor are used? (i) A naive pipeline implementation(NP) and (ii) An efficient pipeline(EP) where the third stage is splitted into {12ns, 5ns and 8ns} respectively. The speedup achieved by EP over NP in executing 100 independent instructions with no hazards is:
A
1.471
B
1.517
C
1.638
D
1.567
       Computer-Organization
Question 53 Explanation: 
Naive Pipeline implementation: The stage delays are {15,8,25,4,8}. And buffer delay = 5ns
So clock cycle time = max of stage delays + buffer delay = max{15,8,25,4,8}+5 = 25+5 = 30ns
Execution time for n-instructions in a pipeline with k-stages = (k+n-1) clock cycles = (k+n-1)* clock cycle time
In this case execution time for 100 instructions in the pipeline with 5-stages
= (5+100-1)*30ns = 104*30 = 3120ns
Efficient Pipeline implementation: The 3rd phase is split into 3 stages with execution times of 12ns, 5ns and 8ns
New stage delays in this case = {15, 8, 12, 5, 8, 4, 8}
Buffer delay is the same 5ns.
So clock cycle time = max of stage delays + buffer delay = max{15, 8, 12, 5, 8, 4, 8}+5 = 15+5 = 20ns
Execution time = (k+n-1) clock cycles = (k+n-1)* clock cycle time
In this case no. of pipeline stages, k = 7
No. of instructions = 100
Execution time = (7+100-1)*20 = 106*20 = 2120ns
Speed up of Efficient pipeline over naive pipeline = Naive pipeline execution time / efficient pipeline execution time
= 3120 / 2120
~= 1.471
Question 54
Consider the problem of determining string ‘w’ is given some turing machine ‘M’ will it enter into some state ‘q’, where q belongs to set of all states in Turing machine M and sting w is not equal to empty string. Which among the following is correct for above statement?
A
Given problems is computable
B
Given problem is non computable
C
Given problem has finite state solution
D
Given problem is solved in polynomial time.
       Theory-of-Computation
Question 54 Explanation: 
The given problem is undecidable. Whether a TM visit state q is undecidable, it is equivalent to halting problem of TM. So,the correct answer is B , it is non-computable.
If a problem is undecidable then it means we don't have any algorithm to solve this problem and hence solving in polynomial time is also not possible.
There are 54 questions to complete.