## UGC NET CS 2015 Jun- paper-2

Question 1 |

How many strings of 5 digits have the property that the sum of their digits is 7?

66 | |

330 | |

495 | |

99 |

Question 1 Explanation:

→ From the given question, there should be string with 5 digits and sum of that digits should be 7

→ There is no specification about positive,negative digits and also repetition of digits.

→ We are assuming the positive digits which is greater than or equal to 0.

→ The starting digit of the string should not be zero. We will also consider the repetition of digits.

→ Example of such strings are 70000,61000,60100,60010..,

→ The possible number of strings are C((n+r-1),(r-1))

→ From the given data n=7,r=5 then We have to fine C(11,4) which is equal to 330

→ There is no specification about positive,negative digits and also repetition of digits.

→ We are assuming the positive digits which is greater than or equal to 0.

→ The starting digit of the string should not be zero. We will also consider the repetition of digits.

→ Example of such strings are 70000,61000,60100,60010..,

→ The possible number of strings are C((n+r-1),(r-1))

→ From the given data n=7,r=5 then We have to fine C(11,4) which is equal to 330

Question 2 |

Consider an experiment of tossing two fair dice, one black and one red. What is the probability that the number on the black die divides the number on red die?

22 / 36 | |

12 / 36 | |

14 / 36 | |

6 / 36 |

Question 2 Explanation:

→ From the given data, there are two dice and each dice the possible ways are 6. So total possible ways are 6*6=36 ways.

→ The possible ways are 1,2,3,4,5,6

→ The possible ways of one number divides another number are (1,1) (1,2), (1,3), (1,4), (1,5), (1,6), (2,2), (2,4), (2,6), (3,3), (3,6), (4,4), (5,5) and (6,6).

→ The probability is the number of outcomes / total outcomes = 14/36

→ The possible ways are 1,2,3,4,5,6

→ The possible ways of one number divides another number are (1,1) (1,2), (1,3), (1,4), (1,5), (1,6), (2,2), (2,4), (2,6), (3,3), (3,6), (4,4), (5,5) and (6,6).

→ The probability is the number of outcomes / total outcomes = 14/36

Question 3 |

In how many ways can 15 indistinguishable fish be placed into 5 different ponds, so that each pond contains at least one fish ?

1001 | |

3876 | |

775 | |

200 |

Question 3 Explanation:

→ We know that if we have “n” identical items which will be distributed in “r” distinct groups where each must get at least one then the number of way is C(n−1,r−1)

→ From the given question, n=15, r=5 We need to calculate C(14,4) and it’s value is 1001.

→ From the given question, n=15, r=5 We need to calculate C(14,4) and it’s value is 1001.

Question 4 |

Consider the following statements:

(a) Depth first search is used to traverse a rooted tree.

(b) Preorder, Postorder and Inorder are used to list the vertices of an ordered rooted tree.

(c) Huffman’s algorithm is used to find an optimal binary tree with given weights.

(d) Topological sorting provides a labelling such that the parents have larger labels than their children.

Which of the above statements are true?

(a) Depth first search is used to traverse a rooted tree.

(b) Preorder, Postorder and Inorder are used to list the vertices of an ordered rooted tree.

(c) Huffman’s algorithm is used to find an optimal binary tree with given weights.

(d) Topological sorting provides a labelling such that the parents have larger labels than their children.

Which of the above statements are true?

(a) and (b) | |

(c) and (d) | |

(a), (b) and (c) | |

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

Question 4 Explanation:

→ Preorder, Postorder and Inorder are traversing techniques where all the nodes of the tree will be traversed from the root node.

→ Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

→ The optimal binary tree, which has minimum weighted path length when the characters of the alphabet are stored at its n terminal nodes.An optimal binary tree generates what is called a Huffman code

→ A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.

A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.

→ Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

→ The optimal binary tree, which has minimum weighted path length when the characters of the alphabet are stored at its n terminal nodes.An optimal binary tree generates what is called a Huffman code

→ A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.

A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.

Question 5 |

Consider a Hamiltonian Graph (G) with no loops and parallel edges. Which of the following is true with respect to this Graph (G) ?

(a) deg (v) ≥ n / 2 for each vertex of G

(b) |E(G)| ≥ 1 / 2 (n - 1) (n - 2) + 2 edges

(c) deg (v) + deg (w) ≥ n for every n and v not connected by an edge.

(a) deg (v) ≥ n / 2 for each vertex of G

(b) |E(G)| ≥ 1 / 2 (n - 1) (n - 2) + 2 edges

(c) deg (v) + deg (w) ≥ n for every n and v not connected by an edge.

(a) and (b) | |

(b) and (c) | |

(a) and (c) | |

(a), (b) and (c) |

Question 5 Explanation:

→ According to Dirac's theorem on Hamiltonian cycles, the statement that an n-vertex graph in which each vertex has degree at least n/2 must have a Hamiltonian cycle.

→ According to ore’s theorem,Let G be a (finite and simple) graph with n ≥ 3 vertices. We denote by deg v the degree of a vertex v in G, i.e. the number of incident edges in G to v. Then, Ore's theorem states that if deg v + deg w ≥ n for every pair of distinct non adjacent vertices v and w of G, then G is Hamiltonian.

→ A complete graph G of n vertices has n(n−1)/2 edges and a Hamiltonian cycle in G contains n edges. Therefore the number of edge-disjoint Hamiltonian cycles in G cannot exceed (n − 1)/2. When n is odd, we show there are (n − 1)/2 edge-disjoint Hamiltonian cycles.

So the statement(b) is false and statement a and c are true.

→ According to ore’s theorem,Let G be a (finite and simple) graph with n ≥ 3 vertices. We denote by deg v the degree of a vertex v in G, i.e. the number of incident edges in G to v. Then, Ore's theorem states that if deg v + deg w ≥ n for every pair of distinct non adjacent vertices v and w of G, then G is Hamiltonian.

→ A complete graph G of n vertices has n(n−1)/2 edges and a Hamiltonian cycle in G contains n edges. Therefore the number of edge-disjoint Hamiltonian cycles in G cannot exceed (n − 1)/2. When n is odd, we show there are (n − 1)/2 edge-disjoint Hamiltonian cycles.

So the statement(b) is false and statement a and c are true.

Question 6 |

Consider the following statements :

(a)Boolean expressions and logic networks correspond to labelled acyclic digraphs.

(b)Optimal boolean expressions may not correspond to simplest networks.

(c)Choosing essential blocks first in a Karnaugh map and then greedily choosing the largest remaining blocks to cover may not give an optimal expression.

Which of these statement(s) is/are correct ?

(a)Boolean expressions and logic networks correspond to labelled acyclic digraphs.

(b)Optimal boolean expressions may not correspond to simplest networks.

(c)Choosing essential blocks first in a Karnaugh map and then greedily choosing the largest remaining blocks to cover may not give an optimal expression.

Which of these statement(s) is/are correct ?

(a) only | |

(b) only | |

(a) and (b) | |

(a), (b) and (c) |

Question 6 Explanation:

→ An acyclic digraph is a directed graph containing no directed cycles, also known as a directed acyclic graph or a "DAG.",We can represent the boolean expressions and logic networks by using DAG.

→ Karnaugh maps reduce logic functions more quickly and easily compared to Boolean algebra. By reduce we mean simplify, reducing the number of gates and inputs.

→ Karnaugh maps reduce logic functions more quickly and easily compared to Boolean algebra. By reduce we mean simplify, reducing the number of gates and inputs.

Question 7 |

Consider a full - adder with the following input values:

(a)x = 1, y = 0 and C

(b)x = 0, y = 1 and C

(a)x = 1, y = 0 and C

_{i} (carry input) = 0(b)x = 0, y = 1 and C

_{i} = 1 Compute the values of S(sum) and C_{o} (carry output) for the above input values.S = 1, C _{o} = 0 and S = 0, C_{ o} = 1 | |

S = 1, C _{o} = 0 and S = 1, C_{ o} = 1 | |

S = 1, C _{o} = 1 and S = 1, C_{ o} = 0 | |

S _{0} = 1, C _{o} = 1 and S = 1, C_{ o} = 0 |

Question 7 Explanation:

For the given x and y values, the correct option is A

Question 8 |

“If my computations are correct and I pay the electric bill, then I will run out of money. If I don’t pay the electric bill, the power will be turned off. Therefore, if I don’t run out of money and the power is still on, then my computations are incorrect.”
Convert this argument into logical notations using the variables c, b, r, p for propositions of computations, electric bills, out of money and the power respectively. (Where ¬ means NOT)

if (c Λ b)→r and ¬b→p, then (¬r Λ p)→¬c | |

if (c ∨ b)→r and ¬b→¬p, then (r Λ p)→c | |

if (c Λ b)→r and ¬p→b, then (¬r ∨ p)→¬c | |

if (c ∨ b)→r and ¬b→¬p, then (¬r Λ p)→¬c |

Question 8 Explanation:

We can represent ,

“c” for my computations are correct

“b” for I pay the electric bill.

“r” for I will run out of money

“p” for the power is on.

(c Λ b) means my computations are correct and I pay the electric bill.

(¬r Λ p) means I don’t run out of money and the power is still on.

According to the statement , the option -(A) is correct.

“c” for my computations are correct

“b” for I pay the electric bill.

“r” for I will run out of money

“p” for the power is on.

(c Λ b) means my computations are correct and I pay the electric bill.

(¬r Λ p) means I don’t run out of money and the power is still on.

According to the statement , the option -(A) is correct.

Question 9 |

Match the following:

(a)-(i), (b)-(ii), (c)-(iii), (d)-(iv) | |

(a)-(ii), (b)-(iii), (c)-(i), (d)-(iv) | |

(a)-(iii), (b)-(ii), (c)-(iv), (d)-(i) | |

(a)-(iv), (b)-(ii), (c)-(iii), (d)-(i) |

Question 9 Explanation:

→ In logic, contraposition is an inference that says that a conditional statement is logically equivalent to its contrapositive. The contrapositive of the statement has its antecedent and consequent inverted and flipped: the contrapositive of P → Q is thus as ~Q → ~P.

→ The equivalence relation translates verbally into "if and only if" and is symbolized by a double-lined, double arrow pointing to the left and right (↔). If A and B represent statements, then A ↔ B means "A if and only if B."

→ The exportation rule is a rule in logic which states that "if (P and Q), then R" is equivalent to "if P then (if Q then R)".

→ The exportation rule may be formally stated as: (P ∧ Q) → R is equivalent to P → (Q →R)

→ A mode of argumentation or a form of argument in which a proposition is disproven by following its implications logically to an absurd conclusion. Arguments that use universals such as, “always”, “never”, “everyone”, “nobody”, etc., are prone to being reduced to absurd conclusions. The fallacy is in the argument that could be reduced to absurdity -- so in essence, reductio ad absurdum is a technique to expose the fallacy.

→ The equivalence relation translates verbally into "if and only if" and is symbolized by a double-lined, double arrow pointing to the left and right (↔). If A and B represent statements, then A ↔ B means "A if and only if B."

→ The exportation rule is a rule in logic which states that "if (P and Q), then R" is equivalent to "if P then (if Q then R)".

→ The exportation rule may be formally stated as: (P ∧ Q) → R is equivalent to P → (Q →R)

→ A mode of argumentation or a form of argument in which a proposition is disproven by following its implications logically to an absurd conclusion. Arguments that use universals such as, “always”, “never”, “everyone”, “nobody”, etc., are prone to being reduced to absurd conclusions. The fallacy is in the argument that could be reduced to absurdity -- so in essence, reductio ad absurdum is a technique to expose the fallacy.

Question 10 |

Consider a proposition given as :

“ x ≥ 6, if x

If x ≥ 6, then x 2 = x.x ≥ 6.6 = 36 ≥ 25

Which of the following is correct w.r.to the given proposition and its proof?

(a)The proof shows the converse of what is to be proved.

(b)The proof starts by assuming what is to be shown.

(c)The proof is correct and there is nothing wrong.

“ x ≥ 6, if x

^{2} ≥ 5 and its proof as:If x ≥ 6, then x 2 = x.x ≥ 6.6 = 36 ≥ 25

Which of the following is correct w.r.to the given proposition and its proof?

(a)The proof shows the converse of what is to be proved.

(b)The proof starts by assuming what is to be shown.

(c)The proof is correct and there is nothing wrong.

(a) only | |

(c) only | |

(a) and (b) | |

(b) only |

Question 10 Explanation:

The proof which is described in the question is wrong because for a given “x” value , x

^{2}>=5 but in the proof they mentioned 36>=25 which is wrong.Question 11 |

What is the output of the following program?

(Assume that the appropriate preprocessor directives are included and there is no syntax error)

main( )

{

char S[ ] = "ABCDEFGH";

printf ("%C", *(&S[3]));

printf ("%s", S+4);

printf ("%u", S);

/* Base address of S is 1000 */

}

(Assume that the appropriate preprocessor directives are included and there is no syntax error)

main( )

{

char S[ ] = "ABCDEFGH";

printf ("%C", *(&S[3]));

printf ("%s", S+4);

printf ("%u", S);

/* Base address of S is 1000 */

}

ABCDEFGH1000 | |

CDEFGH1000 | |

DDEFGHH1000 | |

DEFGH1000 |

Question 11 Explanation:

Step-1: String is stored in appropriate location is

Step-2: printf ("%C", *(&S[3]));

This statement will print character ‘D’

(&S[3]) → Will print address of index 3

*(&S[3]) → will print value in index 3. The value is nothing but ‘D’.

Step-3: printf ("%s", S+4); /* will print characters ‘EFGH’ */

Because previous S value index position is 3. Now we are performing +4 operations. It will print EFGH. we are given escape sequence is String.

Step-4: printf ("%u", S); → It will print address of S. The base address given as S is 1000.

Step-2: printf ("%C", *(&S[3]));

This statement will print character ‘D’

(&S[3]) → Will print address of index 3

*(&S[3]) → will print value in index 3. The value is nothing but ‘D’.

Step-3: printf ("%s", S+4); /* will print characters ‘EFGH’ */

Because previous S value index position is 3. Now we are performing +4 operations. It will print EFGH. we are given escape sequence is String.

Step-4: printf ("%u", S); → It will print address of S. The base address given as S is 1000.

Question 12 |

Which of the following, in C++, is inherited in a derived class from base class ?

constructor | |

destructor | |

data members | |

virtual methods |

Question 12 Explanation:

Data members in C++, is inherited in a derived class from base class.

→ When creating a class, instead of writing completely new data members and member functions, the programmer can designate that the new class should inherit the members of an existing class. This existing class is called the base class, and the new class is referred to as the derived class.

→ A derived class can access all the non-private members of its base class. Thus base-class members that should not be accessible to the member functions of derived classes should be declared private in the base class.

→ When creating a class, instead of writing completely new data members and member functions, the programmer can designate that the new class should inherit the members of an existing class. This existing class is called the base class, and the new class is referred to as the derived class.

→ A derived class can access all the non-private members of its base class. Thus base-class members that should not be accessible to the member functions of derived classes should be declared private in the base class.

Question 13 |

Given that x = 7.5, j = -1.0, n = 1.0, m = 2.0

the value of --x + j == x>n>=m is:

the value of --x + j == x>n>=m is:

0 | |

1 | |

2 | |

3 |

Question 13 Explanation:

Step-1: Given data, x = 7.5, j = -1.0, n = 1.0, m = 2.0

given condition is --x + j == x > n >= m

(6.5 + (-1.0)) == ((6.5 > 1.0) >= 2.0)

Here, 6.5 is greater than 1.0. so, it will print TRUE value is 1

Step-2: (5.5 == (1 >= 2.0))

Here, 1 is less than 2.0. So, it will print FALSE value is 0

Step-3: 5.5 == 0

5.5 is not equal to 0. So, it will print FALSE value is 0.

given condition is --x + j == x > n >= m

(6.5 + (-1.0)) == ((6.5 > 1.0) >= 2.0)

Here, 6.5 is greater than 1.0. so, it will print TRUE value is 1

Step-2: (5.5 == (1 >= 2.0))

Here, 1 is less than 2.0. So, it will print FALSE value is 0

Step-3: 5.5 == 0

5.5 is not equal to 0. So, it will print FALSE value is 0.

Question 14 |

Which of the following is incorrect in C++ ?

When we write overloaded function we must code the function for each usage. | |

When we write function template we code the function only once. | |

It is difficult to debug macros | |

Templates are more efficient than macros | |

None of These |

Question 14 Explanation:

TRUE: When we write overloaded function we must code thevfunction for each usage.

TRUE: When we write function template we code the function only once.

TRUE: It is difficult to debug macros

TRUE: Templates are more efficient than macros

1. Macros are a primitive form, without much compiler enforcement

2. Templates are more advanced, and have a lot better compiler type-checking, error messages, etc.

3. Templates can only generate dynamic class types

4. Macros can generate almost any code you want (other than another macro definition).

5. Macros can be very useful to embed static tables of structured data into your code.

Note: Excluded for evaluation. Given all options are correct.

TRUE: When we write function template we code the function only once.

TRUE: It is difficult to debug macros

TRUE: Templates are more efficient than macros

1. Macros are a primitive form, without much compiler enforcement

2. Templates are more advanced, and have a lot better compiler type-checking, error messages, etc.

3. Templates can only generate dynamic class types

4. Macros can generate almost any code you want (other than another macro definition).

5. Macros can be very useful to embed static tables of structured data into your code.

Note: Excluded for evaluation. Given all options are correct.

Question 15 |

When the inheritance is private, the private methods in base class are __________ in the derived class (in C++).

inaccessible | |

accessible | |

protected | |

public |

Question 15 Explanation:

When the inheritance is private, the private methods in base class are inaccessible in the derived class.

Question 16 |

An Assertion is a predicate expressing a condition we wish database to always satisfy.

The correct syntax for Assertion is :

The correct syntax for Assertion is :

CREATE ASSERTION ‘ASSERTION Name’ CHECK ‘Predicate’ | |

CREATE ASSERTION ‘ASSERTION Name’ | |

CREATE ASSERTION, CHECK Predicate | |

SELECT ASSERTION |

Question 16 Explanation:

An Assertion is a condition that we wish the database to always satisfy. Domain constraints, functional dependency and referential integrity are special forms of assertion.

The syntax of Assertion in SQL is:

create assertion assertion-name check predicate

The syntax of Assertion in SQL is:

create assertion assertion-name check predicate

Question 17 |

Which of the following concurrency protocol ensures both conflict serializability and freedom from deadlock?

(a) Z-Phase Locking

(b) Timestamp ordering

(a) Z-Phase Locking

(b) Timestamp ordering

Both (a) and (b) | |

(a) only | |

(b) only | |

Neither (a) nor (b) |

Question 17 Explanation:

Timestamp ordering provides a schedule which is conflict serializable and free from deadlock but Z-phase locking provides a schedule which is conflict serializable only.

Question 18 |

Drop Table cannot be used to drop a Table referenced by __________ constraint.

(a)Primary key

(b)Sub key

(c)Super key

(d)Foreign key

(a)Primary key

(b)Sub key

(c)Super key

(d)Foreign key

(a) | |

(a), (b) and (c) | |

(d) | |

(a) and (d) |

Question 18 Explanation:

Drop Table cannot be used to drop a Table referenced by Foreign Key because deleting a table referenced by a foreign key will violate the referenced key constraint.

Question 19 |

Database applications were built directly on top of file system to overcome the following drawbacks of using file-systems:

(a) Data redundancy and inconsistency

(b) Difficulty in accessing Data

(c) Data isolation

(d) Integrity problems

(a) Data redundancy and inconsistency

(b) Difficulty in accessing Data

(c) Data isolation

(d) Integrity problems

(a) | |

(a) and (d) | |

(a), (b) and (c) | |

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

Question 19 Explanation:

Drawbacks of using a file system are data redundancy, data inconsistency, difficulty in accessing data, data isolation and data integrity. So to overcome all these disadvantages Database management system are used because it involves specifying the data types, structures and constraints of the data to be stored in the database. Constraints that helps in overcoming the disadvantages of file system are

1. Entity constraint: No primary key should have NULL values.

2. Key constraint: No two rows in a table should be same.

3. Domain constraint: A column in a table should not be multi valued or composite

4. Referential integrity constraint: A foreign key should contain the subset values of primary key.

1. Entity constraint: No primary key should have NULL values.

2. Key constraint: No two rows in a table should be same.

3. Domain constraint: A column in a table should not be multi valued or composite

4. Referential integrity constraint: A foreign key should contain the subset values of primary key.

Question 20 |

For a weak entity set to be meaningful, it must be associated with another entity set in combination with some of their attribute values, is called as:

Neighbour Set | |

Strong Entity Set | |

Owner Entity Set | |

Weak Set |

Question 20 Explanation:

A weak entity set do not have any primary key using which we can identify it uniquely. So to uniquely identify a weak entity set it must be associated with its owner entity set and must have total participation in relationship with its owner entity set.

In above figure "Employee" can have many dependents and a dependent can belongs to only one employee. Now two dependents can have same names. So "Dependent" table don't have any primary key to uniquely identify each dependent uniquely. So, it is a weak entity set and "Employee" entity is having "Emp No" as its primary key. Now using "Emp No. along with Name" in "dependent" relation each dependent can be uniquely identify. So we associated "Dependent" set with "Employee" set.

In above figure "Employee" can have many dependents and a dependent can belongs to only one employee. Now two dependents can have same names. So "Dependent" table don't have any primary key to uniquely identify each dependent uniquely. So, it is a weak entity set and "Employee" entity is having "Emp No" as its primary key. Now using "Emp No. along with Name" in "dependent" relation each dependent can be uniquely identify. So we associated "Dependent" set with "Employee" set.

Question 21 |

Question 21 Explanation:

To find minimum cost spanning tree, we are using either prim’s algorithm (or) kruskal’s algorithm.

According to kruskal’s algorithm, first we have sort an elements.

Elements are: 10,12,14,16,18,22,24,25,28

According to kruskal’s algorithm, first we have sort an elements.

Elements are: 10,12,14,16,18,22,24,25,28

Question 22 |

The inorder and preorder Traversal of binary Tree are dbeafcg and abdecfg respectively. The post-order Traversal is __________.

dbefacg | |

debfagc | |

dbefcga | |

debfgca |

Question 22 Explanation:

Inorder: Left root Right

Pre order: Root Left Right

Post order: Left Right Root

Inorder: d b e a f c g

Pre order: a b d e c f g

Post order: d e b f g c a

Pre order: Root Left Right

Post order: Left Right Root

Inorder: d b e a f c g

Pre order: a b d e c f g

Post order: d e b f g c a

Question 23 |

Level order Traversal of a rooted Tree can be done by starting from root and performing:

Breadth First Search | |

Depth First Search | |

Root Search | |

Deep Search |

Question 23 Explanation:

Breadth first search:

It is an algorithm for traversing (or) searching tree (or) graph data structures. It starts at the root and explores all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level.

It is an algorithm for traversing (or) searching tree (or) graph data structures. It starts at the root and explores all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level.

Question 24 |

The average case occurs in the linear search algorithm when:

The item to be searched is in somewhere middle of the array | |

The item to be searched is not in the array | |

The item to be searched is in the last of the array | |

The item to be searched is either in the last or not in the array |

Question 24 Explanation:

→ A linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched.

→ A linear search runs in at worst linear time and makes at most n comparisons, where ‘n’ is the length of the list. If each element is equally likely to be searched, then linear search has an average case of n/2 comparisons, but the average case can be affected if the search probabilities for each element vary. → Linear search is rarely practical because other search algorithms and schemes, such as the binary search algorithm and hash tables, allow significantly faster searching for all but short lists.

→ A linear search runs in at worst linear time and makes at most n comparisons, where ‘n’ is the length of the list. If each element is equally likely to be searched, then linear search has an average case of n/2 comparisons, but the average case can be affected if the search probabilities for each element vary. → Linear search is rarely practical because other search algorithms and schemes, such as the binary search algorithm and hash tables, allow significantly faster searching for all but short lists.

Question 25 |

To determine the efficiency of an algorithm the time factor is measured by:

Counting microseconds | |

Counting number of key operations | |

Counting number of statements | |

Counting kilobytes of algorithm |

Question 25 Explanation:

To determine the efficiency of an algorithm the time factor is measured by counting number of key operations.

Question 26 |

Which of the following protocols is an application layer protocol that establishes, manages and terminates multimedia sessions ?

Session Maintenance Protocol | |

Real time Streaming Protocol | |

Real time Transport Control Protocol | |

Session Initiation Protocol |

Question 26 Explanation:

The Session Initiation Protocol (SIP) is a signaling protocol used for initiating, maintaining, and terminating real-time sessions that include voice, video and messaging applications.

→ SIP is used for signaling and controlling multimedia communication sessions in applications of Internet telephony for voice and video calls, in private IP telephone systems, in instant messaging over Internet Protocol (IP) networks as well as mobile phone calling over LTE (VoLTE).

→ SIP is used for signaling and controlling multimedia communication sessions in applications of Internet telephony for voice and video calls, in private IP telephone systems, in instant messaging over Internet Protocol (IP) networks as well as mobile phone calling over LTE (VoLTE).

Question 27 |

Match the following port numbers with their uses:

(a)-(iv), (b)-(i), (c)-(ii), (d)-(iii) | |

(a)-(ii), (b)-(i), (c)-(iv), (d)-(iii) | |

(a)-(ii), (b)-(iv), (c)-(iii), (d)-(i) | |

(a)-(ii), (b)-(iv), (c)-(i), (d)-(iii) |

Question 27 Explanation:

Question 28 |

Which of the following is not associated with the session layer ?

Dialog control | |

Token management | |

Semantics of the information transmitted | |

Synchronization |

Question 28 Explanation:

Session Layer responsibilities:

1. Session checkpointing and recovery

2. Dialog control

3. Token management

4. Synchronization

1. Session checkpointing and recovery

2. Dialog control

3. Token management

4. Synchronization

Question 29 |

What is the size of the ‘total length’ field in IPv4 datagram?

4 bit | |

8 bit | |

16 bit | |

32 bit |

Question 29 Explanation:

Question 30 |

Which of the following is/are restriction(s) in classless addressing?

The number of addresses needs to be a power of 2. | |

The mask needs to be included in the address to define the block. | |

The starting address must be divisible by the number of addresses in the block. | |

All of the above |

Question 30 Explanation:

Classless addressing rules:

1. The number of addresses needs to be a power of 2.

2. The mask needs to be included in the address to define the block.

3. The starting address must be divisible by the number of addresses in the block.

1. The number of addresses needs to be a power of 2.

2. The mask needs to be included in the address to define the block.

3. The starting address must be divisible by the number of addresses in the block.

Question 31 |

Match the following:

(a)-(ii), (b)-(iii), (c)-(iv), (d)-(i) | |

(a)-(iii), (b)-(iv), (c)-(ii), (d)-(i) | |

(a)-(iv), (b)-(i), (c)-(iii), (d)-(ii) | |

(a)-(iv), (b)-(iii), (c)-(ii), (d)-(i) |

Question 31 Explanation:

Forward Reference Table → Uses linked list data structure

Mnemonic Table → Contains machine OP code

Segment Register Table → Uses array data structure

EQU → Assembler directive.

The EQU directive gives a symbolic name to a numeric constant, a register-relative value or a PC-relative value.

Mnemonic Table → Contains machine OP code

Segment Register Table → Uses array data structure

EQU → Assembler directive.

The EQU directive gives a symbolic name to a numeric constant, a register-relative value or a PC-relative value.

Question 32 |

The translator which performs macro calls expansion is called:

Macro processor | |

Micro preprocessor | |

Macro preprocessor | |

Dynamic Linker |

Question 32 Explanation:

→ The C preprocessor is a macro preprocessor (allows you to define macros) that transforms your program before it is compiled. These transformations can be inclusion of header file, macro expansions,etc,...

→ All preprocessing directives begins with a # symbol. For example,

#define PI 3.14

→ All preprocessing directives begins with a # symbol. For example,

#define PI 3.14

Question 33 |

If all the production rules have single non-terminal symbol on the left side, the grammar defined is:

context free grammar | |

context sensitive grammar | |

unrestricted grammar | |

phrase grammar |

Question 33 Explanation:

If all the production rules have single non-terminal symbol on the left side, the grammar defined is context free grammar.

Context-free grammar (CFG) is a certain type of formal grammar: a set of production rules that describe all possible strings in a given formal language. Production rules are simple replacements. For example, the rule

A → α replaces A with α . There can be multiple replacement rules for any given value. For example,

A → α

A → β

means that A can be replaced with either α or β.

→ In context-free grammars, all rules are one-to-one, one-to-many, or one-to-none. These rules can be applied regardless of context. The left-hand side of the production rule is always a nonterminal symbol. This means that the symbol does not appear in the resulting formal language. So in our case, our language contains the letters α and β but not A.

Context-free grammar (CFG) is a certain type of formal grammar: a set of production rules that describe all possible strings in a given formal language. Production rules are simple replacements. For example, the rule

A → α replaces A with α . There can be multiple replacement rules for any given value. For example,

A → α

A → β

means that A can be replaced with either α or β.

→ In context-free grammars, all rules are one-to-one, one-to-many, or one-to-none. These rules can be applied regardless of context. The left-hand side of the production rule is always a nonterminal symbol. This means that the symbol does not appear in the resulting formal language. So in our case, our language contains the letters α and β but not A.

Question 34 |

Which one from the following is false?

LALR parser is Bottom up parser | |

A parsing algorithm which performs a left to right scanning and a right most deviation is RL (1) | |

LR parser is Bottom up parser. | |

In LL(1), the 1 indicates that there is a one - symbol look - ahead. |

Question 34 Explanation:

TRUE: LALR parser is Bottom up parsers.

TRUE: LR parser is Bottom up parser. It has SLR, LALR and SLR.

TRUE: In LL(1), the 1 indicates that there is a one - symbol look - ahead.

FALSE: A parsing algorithms scans right to left and reverse order.

TRUE: LR parser is Bottom up parser. It has SLR, LALR and SLR.

TRUE: In LL(1), the 1 indicates that there is a one - symbol look - ahead.

FALSE: A parsing algorithms scans right to left and reverse order.

Question 35 |

Which phase of compiler generates stream of atoms?

Syntax Analysis | |

Lexical Analysis | |

Code Generation | |

Code Optimization |

Question 35 Explanation:

Syntax analysis: understanding the structure of the source code

1. Tokenizing: creating a stream of “atoms”

2. Parsing: matching the atom stream with the language grammar

XML output = one way to demonstrate that the syntax analyzer works

1. Tokenizing: creating a stream of “atoms”

2. Parsing: matching the atom stream with the language grammar

XML output = one way to demonstrate that the syntax analyzer works

Question 36 |

A disk drive has 100 cyclinders, numbered 0 to 99. Disk requests come to the disk driver for cyclinders 12, 26, 24, 4, 42, 8 and 50 in that order. The driver is currently serving a request at cyclinder 24. A seek takes 6 msec per cyclinder moved. How much seek time is needed for shortest seek time first (SSTF) algorithm?

0.984 sec | |

0.396 sec | |

0.738 sec | |

0.42 sec |

Question 36 Explanation:

Step-1:

Step-2: Total seek time= 420 msec.

Step-3: =420/1000

=0.42

Note: 1000 msec = 1 sec

Step-2: Total seek time= 420 msec.

Step-3: =420/1000

=0.42

Note: 1000 msec = 1 sec

Question 37 |

Let P

_{i} and P_{ j} be two processes, R be the set of variables read from memory, and W be the set of variables written to memory. For the concurrent execution of two processes P_{ i} and P_{ j} which of the following conditions is not true?R(P _{i} ) ∩ W(P _{j} ) = Ф | |

W(P _{ i} ) ∩ R(P_{ j} ) = Ф | |

R(P _{ i} ) ∩ R(P_{ j} ) = Ф | |

W(P _{ i} ) ∩ W(P_{ j} ) = Ф |

Question 37 Explanation:

Option-A: It performs Read and Write. So, it violates concurrent execution of two processes P

Option-B: It performs write and Read. So, it violates concurrent execution of two processes P

Option-C: It performs Read and Write. So, it is not violates concurrent execution of two processes P

Option-D: It performs Write and Write. So, it violates concurrent execution of two processes P

_{i}and P_{j}Option-B: It performs write and Read. So, it violates concurrent execution of two processes P

_{i}and P_{j}Option-C: It performs Read and Write. So, it is not violates concurrent execution of two processes P

_{i}and P_{j}Option-D: It performs Write and Write. So, it violates concurrent execution of two processes P

_{i}and P_{j}Question 38 |

A LRU page replacement is used with four page frames and eight pages. How many page faults will occur with the reference string 0172327103 if the four frames are initially empty?

6 | |

7 | |

8 | |

5 |

Question 38 Explanation:

Question 39 |

What does the following command do?

grep -vn “abc” x

grep -vn “abc” x

It will print all of the lines in the file x that match the search string “abc”. | |

It will print all of the lines in file x that do not match the search string “abc”. | |

It will print the total number of lines in the file x that match the string “abc”. | |

It will print the specific line numbers of the file x in which there is a match for string “abc”. |

Question 39 Explanation:

The grep filter searches a file for a particular pattern of characters, and displays all lines that contain that pattern. The pattern that is searched in the file is referred to as the regular expression (grep stands for globally search for regular expression and print out).

Syntax: grep [options] pattern [files]

Step-1: grep -vn → This prints out all the lines that do not matches the pattern.

Step-2: grep -vn “abc” → “abc” is pattern

Step-3: grep -vn “abc” x → x is a file name

Syntax: grep [options] pattern [files]

Step-1: grep -vn → This prints out all the lines that do not matches the pattern.

Step-2: grep -vn “abc” → “abc” is pattern

Step-3: grep -vn “abc” x → x is a file name

Question 40 |

The Unix Kernel maintains two key data structures related to processes, the process table and the user structure. Which of the following information is not the part of user structure?

File descriptor table | |

System call state | |

Scheduling parameters | |

Kernel stack |

Question 40 Explanation:

The Unix Kernel maintains two key data structures related to processes, the process table and the user structure.

1. File descriptor table

2. System call state

3. Kernel stack

Scheduling parameters: Process priority, amount of CPU time consumed recently, amount of time spent sleeping recently. Together, these are used to determine which process to run next.

1. File descriptor table

2. System call state

3. Kernel stack

Scheduling parameters: Process priority, amount of CPU time consumed recently, amount of time spent sleeping recently. Together, these are used to determine which process to run next.

Question 41 |

Match the following:

(a)-(iii), (b)-(iv), (c)-(i), (d)-(ii) | |

(a)-(ii), (b)-(i), (c)-(iv), (d)-(iii) | |

(a)-(iv), (b)-(ii), (c)-(iii), (d)-(i) | |

(a)-(iii), (b)-(i), (c)-(iv), (d)-(ii) |

Question 41 Explanation:

Size-oriented metrics → derived by normalizing quality and/or productivity measures by considering the size of the software.

Function-oriented metrics → uses number of external interfaces as one of the measurement parameter

Extended Function Point metrics → uses algorithm characteristics as one of the measurement parameter

Function point → originally designed to be applied to business information systems.

Function-oriented metrics → uses number of external interfaces as one of the measurement parameter

Extended Function Point metrics → uses algorithm characteristics as one of the measurement parameter

Function point → originally designed to be applied to business information systems.

Question 42 |

In which testing strategy requirements established during requirements analysis are validated against developed software?

Validation testing | |

Integration testing | |

Regression testing | |

System testing |

Question 42 Explanation:

Validation Testing ensures that the product actually meets the client's needs. It can also be defined as to demonstrate that the product fulfills its intended use when deployed on appropriate environment.

It answers to the question, Are we building the right product?

It answers to the question, Are we building the right product?

Question 43 |

Which process model is also called as classic life cycle model?

Waterfall model | |

RAD model | |

Prototyping model | |

Incremental model |

Question 43 Explanation:

→ The classical waterfall model is intuitively the most obvious way to develop software. Though the classical waterfall model is elegant and intuitively obvious, it is not a practical model in the sense that it can not be used in actual software development projects.

→ This model can be considered to be a theoretical way of developing software. But all other life cycle models are essentially derived from the classical waterfall model. So, in order to be able to appreciate other life cycle models it is necessary to learn the classical waterfall model.

→ This model can be considered to be a theoretical way of developing software. But all other life cycle models are essentially derived from the classical waterfall model. So, in order to be able to appreciate other life cycle models it is necessary to learn the classical waterfall model.

Question 44 |

Cohesion is an extension of:

Abstraction concept | |

Refinement concept | |

Information hiding concept | |

Modularity |

Question 44 Explanation:

→ Cohesion refers to the degree to which the elements inside a module belong together.

→ Cohesion is an extension of Information hiding concept.

→ Cohesion is an extension of Information hiding concept.

Question 45 |

Which one from the following is highly associated activity of project planning?

Keep track of the project progress. | |

Compare actual and planned progress and costs. | |

Identify the activities, milestones and deliverables produced by a project. | |

Both (2) and (3). |

Question 45 Explanation:

Project planning activities(High priority):

1. Compare actual and planned progress and costs.

2. Identify the activities, milestones and deliverables produced by a project.

1. Compare actual and planned progress and costs.

2. Identify the activities, milestones and deliverables produced by a project.

Question 46 |

In the case of parallelization, Amdahl’s law states that if P is the proportion of a program that can be made parallel and (1 -P) is the proportion that cannot be parallelized, then the maximum speed-up that can be achieved by using N processors is:

1/((1−p)+ N .P) | |

1/((N −1)P +P) | |

1/((1−P )+ P /N) | |

1/((P)+(1-P)/N) |

Question 46 Explanation:

Amdahl’s law can be formulated in the following way:

where

● S latency is the theoretical speedup of the execution of the whole task;

● s is the speedup of the part of the task that benefits from improved system resources;

● p is the proportion of execution time that the part benefiting from improved resources originally occupied.

Furthermore,

shows that the theoretical speedup of the execution of the whole task increases with the improvement of the resources of the system and that regardless of the magnitude of the improvement, the theoretical speedup is always limited by the part of the task that cannot benefit from the improvement.

→ Amdahl's law applies only to the cases where the problem size is fixed. In practice, as more computing resources become available, they tend to get used on larger problems (larger datasets), and the time spent in the parallelizable part often grows much faster than the inherently serial work. In this case, Gustafson's law gives a less pessimistic and more realistic assessment of the parallel performance.

where

● S latency is the theoretical speedup of the execution of the whole task;

● s is the speedup of the part of the task that benefits from improved system resources;

● p is the proportion of execution time that the part benefiting from improved resources originally occupied.

Furthermore,

shows that the theoretical speedup of the execution of the whole task increases with the improvement of the resources of the system and that regardless of the magnitude of the improvement, the theoretical speedup is always limited by the part of the task that cannot benefit from the improvement.

→ Amdahl's law applies only to the cases where the problem size is fixed. In practice, as more computing resources become available, they tend to get used on larger problems (larger datasets), and the time spent in the parallelizable part often grows much faster than the inherently serial work. In this case, Gustafson's law gives a less pessimistic and more realistic assessment of the parallel performance.

Question 47 |

Which of the following statements is incorrect for Parallel Virtual Machine (PVM) ?

The PVM communication model provides asynchronous blocking send, asynchronous blocking receive, and non-blocking receive function. | |

Message buffers are allocated dynamically. | |

The PVM communication model assumes that any task can send a message to any other PVM task and that there is no limit to the size or number of such messages. | |

In PVM model, the message order is not preserved. |

Question 47 Explanation:

PVM (Parallel Virtual Machine) is a software package that permits a heterogeneous collection of Unix and/or Windows computers hooked together by a network to be used as a single large parallel computer. Thus large computational problems can be solved more cost effectively by using the aggregate power and memory of many computers. The software is very portable. The source, which is available free thru netlib, has been compiled on everything from laptops to CRAYs.

→ PVM enables users to exploit their existing computer hardware to solve much larger problems at minimal additional cost. Hundreds of sites around the world are using PVM to solve important scientific, industrial, and medical problems in addition to PVM's use as an educational tool to teach parallel programming. With tens of thousands of users, PVM has become the de facto standard for distributed computing world-wide.

→ PVM enables users to exploit their existing computer hardware to solve much larger problems at minimal additional cost. Hundreds of sites around the world are using PVM to solve important scientific, industrial, and medical problems in addition to PVM's use as an educational tool to teach parallel programming. With tens of thousands of users, PVM has become the de facto standard for distributed computing world-wide.

Question 48 |

Which of the following algorithms sort n integers, having the range 0 to (n

^{2} - 1), in ascending order in O(n) time ?Selection sort | |

Bubble sort | |

Radix sort | |

Insertion sort |

Question 48 Explanation:

Consider sorting n integers in the range 0 to n

Phase 1:

1. We use n bins, one for each of the integers 0,1,.., n-1. We place each integer i on the list to be sorted into the bin numbered (i mod n) each bin will then contain a list of integers leaving the same remainder when divided by n.

At the end, we concatenate the bins in order to obtain a list L.

Phase 2:

1. The integers on the list L are redistributed into bins, but using the bin selection

function: ⌊i/n⌋

2. Now append integers to the ends of lists. Finally, concatenate the lists to get the final sorted sequence.

^{2} - 1. We do it in two phases.Phase 1:

1. We use n bins, one for each of the integers 0,1,.., n-1. We place each integer i on the list to be sorted into the bin numbered (i mod n) each bin will then contain a list of integers leaving the same remainder when divided by n.

At the end, we concatenate the bins in order to obtain a list L.

Phase 2:

1. The integers on the list L are redistributed into bins, but using the bin selection

function: ⌊i/n⌋

2. Now append integers to the ends of lists. Finally, concatenate the lists to get the final sorted sequence.

Question 49 |

Which of the following statements is FALSE about weak entity set?

Weak entities can be deleted automatically when their strong entity is deleted. | |

Weak entity set avoids the data duplication and consequent possible inconsistencies caused by duplicating the key of the strong entity. | |

A weak entity set has no primary keys unless attributes of the strong entity set on which it depends are included | |

Tuples in a weak entity set are not partitioned according to their relationship with tuples in a strong entity set. |

Question 49 Explanation:

A weak entity always have total participation relationship with strong entity. It means that every entry in weak entity set will participate in relationship with strong entity and if a strong entity on which weak entity depends is deleted then total participation condition is exploited. So to avoid this Weak entities are deleted automatically when their strong entity is deleted. So option (A) is correct.

Option (B) is correct. A weak entity is an entity which do not have any primary key to uniquely identify its each entry and this leads to data duplication and data inconsistency in the weak entity. So to avoid this problem the key of a strong entity is duplicated into weak entity to uniquely identify each entry of a weak entity. So option (B) is correct.

Option (C) is also correct. Because until the key attributes of a owner strong entity of a weak entity are not included each entry of weak entity can't be uniquely identified.

Option (D) is false because tuples in a weak entity set are partitioned according to their relationship with tuples in a strong entity set.

In above example the key attribute of "Employee" (which is a strong entity) is partitioning the the tuples of "Dependent" (which is a weak entity) based on the tuples belongs to Emp No. "1" and tuples belongs to Emp No. "2".

So option(D) is false

Option (B) is correct. A weak entity is an entity which do not have any primary key to uniquely identify its each entry and this leads to data duplication and data inconsistency in the weak entity. So to avoid this problem the key of a strong entity is duplicated into weak entity to uniquely identify each entry of a weak entity. So option (B) is correct.

Option (C) is also correct. Because until the key attributes of a owner strong entity of a weak entity are not included each entry of weak entity can't be uniquely identified.

Option (D) is false because tuples in a weak entity set are partitioned according to their relationship with tuples in a strong entity set.

In above example the key attribute of "Employee" (which is a strong entity) is partitioning the the tuples of "Dependent" (which is a weak entity) based on the tuples belongs to Emp No. "1" and tuples belongs to Emp No. "2".

So option(D) is false

Question 50 |

Which of the following is not valid with reference to Message Passing Interface (MPI) ?

MPI can run on any hardware platform. | |

The programming model is a distributed memory model. | |

All parallelism is implicit. | |

MPI - Comm - Size returns the total number of MPI processes in specified communication. |

Question 50 Explanation:

→ MPI primarily addresses the message-passing parallel programming model: data is moved from the address space of one process to that of another process through cooperative operations on each process.

→ 1.The goal of the Message Passing Interface is to provide a widely used standard for writing message passing programs. The interface attempts to be:

Practical

Portable

Efficient

Flexible

→ 1.The goal of the Message Passing Interface is to provide a widely used standard for writing message passing programs. The interface attempts to be:

Practical

Portable

Efficient

Flexible

There are 50 questions to complete.