## Nielit STA [02-12-2018]

Please wait while the activity loads.

If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

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?

Parallel-in parallel-out | |

Parallel-in Serial-out | |

Serial-in parallel-out | |

Serial-in Serial-out |

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.

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?

Binary search | |

Linear Search | |

Insertion sort | |

Merge Sort |

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.

→ 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?

An array of 50 numbers | |

An array of 100 numbers | |

An array of 500 numbers | |

A dynamically allocated array of 550 numbers |

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.

→ 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:

Determine the test technique to be employed | |

Determine the extent of testing to be carried out | |

Prioritize testing in an attempt to find critical defects as early as possible | |

Determine the cost of the project |

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

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:

Application layer | |

Transport layer | |

Network layer | |

Data link layer |

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.

→ 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:

The data type and the length | |

The NULL value rejection | |

The allowable values, through techniques like constraints or rules | |

Default value |

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

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:

Rotation | |

Scaling | |

Translation | |

Morphism |

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.

→ 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?

Program counter | |

IO status information | |

CPU registers | |

Translation lookaside buffer |

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.

→ 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:

O(nlogd) | |

O(n ^{2} logd) | |

O(nd) | |

O(n ^{2}d) |

Question 9 Explanation:

→ Using insertion sort worst case time complexity is O(n

→ They are asking to find the atmost distance from every element. So, it will take O(n

Note: Using heap sort , time complexity will be O(nlogd) and most effective than insertion sort.

^{2}).→ They are asking to find the atmost distance from every element. So, it will take O(n

^{2}*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:

Triggers | |

Cursors | |

Locks | |

Pointers |

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

→ 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.

Final | |

Static | |

Sealed | |

Fixed |

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.

→ 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:

Instruction register | |

Program counter | |

Accumulator | |

Instruction Decoder |

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.

→ 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:

MSB | |

LSB | |

Bits | |

Nibble |

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

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;

}

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;

}

12244668 | |

11335578 | |

12335578
| |

12343676 |

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:

F(x,y)=mx+b-y | |

F(x,y)=mx-y+b | |

F(x,y)=mx+b | |

F(x,y)=mx-y+b-y |

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

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:

Karnaugh map | |

DeMorgan’s second theorem | |

The commutative law of addition | |

The associative law of multiplication |

Question 16 Explanation:

Question 17 |

A DFD that can be used to plan or record the specific makeup of a system is called:

Level 0 DFD | |

Level 1 DFD | |

Level 2 DFD | |

Level 3 DFD |

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.

→ 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:

Lack of sufficient resources | |

High cost per bit value | |

Lack of speed of operation | |

High cost of raw material |

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?

Efficient implementation of multi user supports is no longer possible | |

The processor cache organization can be made more efficient now | |

Hardware support for memory management is no longer needed | |

CPU scheduling can be made more efficient now |

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.

→ 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?

There exist parsing algorithms for some programming languages whose complexities are less than O(n ^{3}) | |

A programming language which allows recursion can be implemented with static storage allocation | |

L-attributed definition can be evaluated in the framework of bottom-up parsing | |

Code improving transformation can be performed at both source language and intermediate code level. |

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.

→ 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?

Private methods are final | |

Protected members are accessible within a package and inherited classes outside the package | |

Protected methods are final | |

We cannot override private methods |

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.

→ 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?

2 | |

3 | |

4 | |

5 |

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

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:

Layer 2 firewall | |

Layer 3 firewall | |

Layer 4 firewall | |

Layer 7 firewall |

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.

→ 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:

We can process the XML document in a linear fashion from the top to down | |

We are processing a very large XML document whose DOM tree would consume too much memory | |

The problem to be solved involves only part of the XML document | |

When we are parsing HTML documents to read and store the contents written in fields. |

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.

→ 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:

Distance Vector | |

Path Vector | |

Link Vector | |

Multipoint |

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.

→ 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:

!2n / (!n*!(n+1)) | |

C(n,2n) (n+1) | |

!n*C(2n,n) (n+1) | |

C(2n,n)/ !n |

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!

→ 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?

- Does a given ever produce an output?
- If L is a context free language, then is L’ (complement of L) also context free?
- If L is a regular language, then is L’ also regular?
- If L is a recursive language, then is L’ also recursive?

(a), (b), (c), (d) | |

(a), (b) | |

(b), (c), (d) | |

(c), (d) |

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.

→ 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?

Every minimum spanning tree of G must contain e _{min} and e_{max} | |

If e _{max} is in a minimum spanning tree, then its removal must disconnect G | |

No minimum spanning tree contains e _{max} | |

G has a multiple minimum spanning trees |

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:

nlog(n/2) | |

nlogn | |

(nlogn)/2 | |

logn |

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:

Method declaration | |

Method overriding | |

Method overloading | |

Method Invoking |

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

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:

1,2,3 | |

2,3,4 | |

2,4,5 | |

1,3,5 |

Question 31 Explanation:

→ Suppose a graph has n vertices with degrees d

→ 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, D

→ 1+2+3=6

_{1},d_{2},d_{3},...,d_{n}. Add together all degrees to get a new number d_{1}+ d_{2}+ d_{3}+ ...+ d_{n}= D_{v}. Then D_{v}=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, D

_{v}=2e says that D_{v}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?

3 and 4 | |

2 and 5 | |

2 and 4 | |

3 and 5 |

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.

→ 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:

Composite keys | |

Foreign keys | |

Candidate keys | |

Alternate keys |

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.

→ 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?

Map | |

Array | |

Arraylist | |

Vector |

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:

O(m*n) | |

O(m+n) | |

O(m ^{2}) | |

O(m ^{n}) |

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 graph drawn in a plane in such a way that any pair of edges meet only at their end vertices | |

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. | |

A simple graph which is Isomorphism to Hamiltonian graph. | |

A function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices |

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.

→ 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:

Translation | |

Rotation | |

Scaling | |

Reflection |

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?

IC 74154 | |

IC 74155 | |

IC 74139 | |

IC 74138 |

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.

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?

If a language is context free it can always be accepted by a deterministic pushdown automaton | |

The union of two context free language is context free | |

The intersection of two context free language is context free | |

The complement of a context free language is context free |

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:

Data transfer | |

Enhancing signal strength | |

Interference between signals | |

Connection establishment |

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.

→ 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:

5,4,10,8,6,49,31,43,19,17,11 | |

4,5,6,8,10,11,19,17,43,31,49 | |

4,5,8,10,6,17,31,49,43,19,11 | |

5,4,10,8,6,17,31,49,43,19,11 |

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:

Row lock | |

Page lock | |

Table lock | |

Attribute lock |

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.

→ 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 K

_{ni}>=K_{cn}where K_{n}is n^{th}node value and K_{c}be the value of its child node is called:B+ tree | |

Threaded binary tree | |

Heap | |

AVL tree |

Question 43 Explanation:

A complete binary tree with the property K

_{ni}>=K_{cn}where K_{n}is n^{th}node value and K_{c}be the value of its child node is called heapQuestion 44 |

The name of parser generator that is used for SQL query parsing is:

Lexer parser generator | |

Syntactic parser generator | |

Tokenizer parser generator | |

SQL DML parser generator |

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.

→ 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:

O(1) and θ(logn) | |

θ(1) and θ(logn) | |

O(logn) and θ(logn) | |

θ(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)

→ 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:

Languages for palindrome and prime | |

Languages for palindrome and Even-Even | |

Language for prime and Even-Even | |

Language for palindrome and factorial |

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:

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?

70 | |

280 | |

120 | |

45 |

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 =

Total number of cycles of length ‘3’ out of 16 vertices = 560 × 1/8 = 70

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 =

^{16}C_{3}= 560Total 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?

Pass by value | |

Pass by name | |

Pass by reference | |

Pass by pointer |

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+i*N*S | |

A+(i*N+j)*S | |

A+(i*N+j*M)*S | |

A+(i*M+j*N)*S |

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.

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:

Member function | |

Object | |

Class | |

Class template |

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.

→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:

32 bits | |

64 bits | |

128 bits | |

256 bits |

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)}d^{n}b^{m}| m,n>=0}. Find the best appropriate match to recognize L.Finite automata | |

Pushdown automata | |

Non deterministic turing machine | |

Non deterministic PDA |

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:

1.471 | |

1.517 | |

1.638 | |

1.567 |

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?

Given problems is computable | |

Given problem is non computable | |

Given problem has finite state solution | |

Given problem is solved in polynomial time. |

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.

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.