## JT(IT) 2018 PART-B Computer Science

 Question 1

Which of the following numerical values is NOT a valid constant in C language?

 A 12345L B 018CDF C 9.3e12 D 0XBCF
Programming       Data-Type
Question 1 Explanation:
→ 12345L integer long is valid integer
→ 018CDF starts with 0 means octal number but actually we are given decimal and hexa numbers. So it is not a valid constant.
→ 9.3e12 float number
→ 0XBCF is hexa number. Valid constant.
 Question 2

Let P, Q and R be three atomic prepositional assertions, and

X : (P ∨ Q) → R
Y : (P → R) ∨ (Q → R)

Which one of the following is a tautology?

 A X → Y B Y → X C X ≣ Y D ~Y → X
Engineering-Mathematics       Propositional-Logic
Question 2 Explanation:
 Question 3

Which of the following is NOT a symmetric key algorithm?

 A Ellipse Curve Cryptography B Advanced Encryption standard C Data Encryption Standard D Blowfish
Computer-Networks       Network-Security
Question 3 Explanation:
 Question 4

Which of the following statements is FALSE?

 A The long term scheduler controls the degree of multiprogramming B Multiple process of a single program cannot exist C Ready queue of the processes resides in main memory D A process can have multiple sub processes
Operating-Systems       Process-Scheduling
Question 4 Explanation:
→ Long term scheduler controls the degree of multiprogramming.
→ Ready queue of the processes resides in main memory.
→ A process can have multiple sub processes.
→ Multiple process of a single program cannot exist because each program can have only one process.
 Question 5

Which of the following Boolean equations is/are correct?

```X(X'+ Y) = XY'
X + XY = X
X + X'Y = X + Y```
 A only (iii) B only (ii) C only (i) D Both (ii) and (iii)
Digital-Logic-Design       Boolean-Function
Question 5 Explanation:
 Question 6

With respect to compiler design, "recursive descent" is a ____ parsing technique that reads the inputs from ____.

 A top-down, right to left B top-down, left to right C bottom up, right to left D bottom up, left to right
Compiler-Design       Parsers
Question 6 Explanation:
A recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure implements one of the nonterminals of the grammar. Thus the structure of the resulting program closely mirrors that of the grammar it recognizes.
→ Top down parsers reads the input from left to right and bottom up parsers are reads the input from left to right and reverse.
 Question 7

Which of the following statements is/are FALSE?

(i) XML element names are case sensitive
(ii) In XML, empty element can be represented as
(iii) XML element names can contain spaces
 A only (iii) B only (ii) and (iii) C only (i) and (iii) D only (ii)
Web-Technologies       XML
Question 7 Explanation:
An element can contain
1. text
2. attributes
3. other elements or a mix of the above
Note: XML element names cannot contain spaces.
 Question 8

For what values of k, the points(-k+1, 2k),(k, 2-2K) and (-4-k, 6-2k) are collinear?

 A 0, 1 B -1, 1 C -1, 1/2 D 1/2, -1/2
Engineering-Mathematics       Vectors
Question 8 Explanation:
There is a restrictions for 3 points to be colLinear and that is
1/2[X1(Y2 - Y3) + X2(Y3 - Y1) + X3(Y1 - Y2)] = 0
Here, X1 = -k + 1, Y1 = 2k, X2 = k, Y2 = 2 – 2k, X3 = -4 - k, Y3 = 6 – 2k
1/2[-k + 1(2 – 2k - 6 + 2k) + k(6 – 2k - 2k) - 4 -k(2k - 2 + 2k)] = 0
1/2[-k + 1(-4) + k(6 - 4k) -4 - k(4k - 2)] = 0
1/2[4k - 4 + 6k - 4k2 - 16k + 8 - 4k2 + 2k)] = 0
1/2(-8k2 - 4k + 4) = 0
-8k2 - 4k + 4 = 0
-8k2 - 8k + 4k + 4 = 0
-8K(k + 1) + 4(k + 1) = 0
(k + 1) (4 - 8k) = 0
k + 1 = 0
k = -1
4 - 8k = 0
k = 4/8
k = 1/2
So, the value of k is -1 and 1/2 .
 Question 9

If a connected graph G has planar embedding with 4 faces and 4 vertices, then what will be the number of edges in G?

 A 7 B 6 C 4 D 3
Engineering-Mathematics       Graph-Theory
Question 9 Explanation:
Euler's Formula for Planar Graphs:
For any(connected) planar graph with v vertices, e edges and faces, we have
V - E + F = 2
= 4 - E + 4 =2
E = 4 - 2 + 4
E = 6
 Question 10

What is the area bounded by the parabola 2y = x2 and the line x = y - 4?

 A 18 B 36 C 72 D 6
Engineering-Mathematics       Co-ordinate-Geometry
Question 10 Explanation:
Given parabola 2y = x2 --- (1)
and the line x = y – 4 ------ (2)
Then y = x+4
Now, Substitute Y value in Equation-(1)
x2 = 2 ( x + 4 ) ------ (3)
Solving equation-3 we get x = 4, - 2.
Place Values of x in equation (1) and (2) we will get y = 8, 2.
Then the points of intersection are (8, 4), (2, –2).

After solving the integration, we will get 18.
 Question 11

The following circuit represents the function of a 2–input __________ logic gate.

 A Exclusive-OR B Exclusive-NOR C NAND D NOR
Digital-Logic-Design       Logic-Gates
Question 11 Explanation:
Step-1: A⊕B = (A’⊕B’)
Step-2:

Step-3: We have to apply not operation then we are getting Ex-NOR.
 Question 12

What is the possible number of reflexive relations on a set of 5 elements?

 A 225 B 215 C 210 D 220
Engineering-Mathematics       Sets-And Relation
Question 12 Explanation:
Step-1: To find number of reflexive relation we have standard formula is 2(n2-n)
Step-2: The possible number of reflexive relations on a set of 5 elements 2(n2-n) which is 220 for n=5.
 Question 13

XML documents form a ___ structure.

 A Binary tree B Tree C Linear list D Graph
Web-Technologies       XML
Question 13 Explanation:
→ The document entity serves as the root of the entity tree and a starting-point for an XML processor.
→ This specification does not specify how the document entity is to be located by an XML processor; unlike other entities, the document entity has no name and might well appear on a processor input stream without any identification at all.
 Question 14

Banker’s algorithm is used for:

Question 14 Explanation:
Banker’s algorithm is used for Deadlock avoidance.
 Question 15

Which one of the following is most affected by the presence of outliers in sample data?

 A Variance B Mean C Median D Mode
Engineering-Mathematics       Probability
Question 15 Explanation:
Let's examine what can happen to a data set with outliers.
For the sample data set:
1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4
We find the following mean, median, mode, and standard deviation:
Mean = 2.58
Median = 2.5
Mode = 2
Standard Deviation = 1.08
If we add an outlier to the data set:
1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 400
The new values of our statistics are:
Mean = 35.38
Median = 2.5
Mode = 2
Standard Deviation = 114.74
Note: Outliers often has a significant effect on your mean and standard deviation.
 Question 16

Consider the matrix A defined as follows:

What is the eigenvalue of 3A+ 5A- 6A + 21, where I is an identity matrix?

 A 4, 110, 10 B 1, 27, -8 C 1, 9, 4 D 4, 27, 9
Engineering-Mathematics       Linear-Algebra
Question 16 Explanation:
The eigenvalues of A are 1, 3, –2 ( ∵ The given matrix is upper triangular)
Eigenvalues of A3 are 1, 27 and –8.
Eigenvalues of A2 are 1, 9 and 4.
Eigenvalues of A are 1, 3 and –2.
Eigenvalues of I are 1, 1 and 1.
∴ The eigenvalues of 3A3 + 5A2 – 6A + 2I.
First eigenvalue = 3(1) + 5(1) – 6(1) + 2(1) = 4
Second eigenvalue = 3(27) + 5(9) – 6(3) + 2(1) = 110
Third eigenvalue = 3(–8) + 5(4) – 6(–2) + 2(1) = 10
∴ The required eigenvalues are 4, 110, and 10.
 Question 17

If A and B are sets and AUB = A∩B, then which of the following is correct?

 A A=B B A=∅ C B=∅ D A⊂B
Engineering-Mathematics       Sets-And Relation
Question 17 Explanation:
For this let x belongs to A implies x belongs to A U B
= x belongs to A intersection B
= x belongs to A and x Belongs to B
= x belongs to B
so A subset of B --- (2)
Now we will let y belong to B which implies y belongs to A U B
= y belongs to A intersection B
= y belongs to A and y belongs to B
= y belongs to A
Therefore, B subset of A --- (3) from (2) and (3) we get A=B.
 Question 18

What is the total number of spanning trees of a complete graph of 4 vertices (K4)?

 A 16 B 8 C 4 D 15
Algorithms       Greedy-approach
Question 18 Explanation:
To find total number of spanning trees for complete graph using standard formula
nn-2 = 42 = 16
 Question 19

Considering 0-address instructions machine, what will be the top of the stack after executing the following sequence of instructions?

PUSH 15, PUSH 4, PUSH 6, MULT, PUSH 30, ADD, ADD

 A 30 B 69 C 54 D 10
Data-Structures       Queues-and-Stacks
Question 19 Explanation:
Initially stack is empty. We are using last in first out strategy.
Step-1: PUSH 15,PUSH 4 and PUSH 6 from bottom to top. Now top of the stack value is 6.
Step-2: Perform MULT operation. 6*4=24. Now present stack values are from bottom is 15 and 24.
Step-3: Next again PUSH 30. Now top of the stack is 30.
Step-4: Perform ADD operation. 30+24=54
Step-5: Now present stack values are from bottom is 15 and 54. Perform ADD operation.
Step-6: 15+54=69
 Question 20

The maximum number of boolean functions that can be formed using 3 boolean variable is ____.

 A 512 B 256 C 128 D 1024
Digital-Logic-Design       Boolean-Function
Question 20 Explanation:
→ The set of all Boolean functions of a finite number of Boolean variables. This function assigns a unique integer between 0 and 22n - 1 to each Boolean function of n Boolean variables.
→ For three Boolean variables (n = 3), there are 23 = 8 different cases, giving us a total of 28
= 256 Boolean functions of 3 variables.
 Question 21

Which of the following statements is/are correct?

(i) If the rank of the matrix of given vectors is equal to the number of vectors, then the vectors are linearly independent.
(ii) If the rank of the matrix of given vectors is less than the number of vectors, then the vectors are linearly dependent.
 A Both (i) and (ii) B Only (ii) C Only (i) D Neither (i) nor (ii)
Engineering-Mathematics       Linear-Algebra
Question 21 Explanation:
The Rank of a Matrix
→ You can think of an r x c matrix as a set of r row vectors, each having c elements; or you can think of it as a set of c column vectors, each having r elements.
→ The rank of a matrix is defined as (a) the maximum number of linearly independent column vectors in the matrix or (b) the maximum number of linearly independent row vectors in the matrix. Both definitions are equivalent.
For an r x c matrix,
1. If r is less than c, then the maximum rank of the matrix is r.
2. If r is greater than c, then the maximum rank of the matrix is c.
→ The rank of a matrix would be zero only if the matrix had no elements. If a matrix had even one element, its minimum rank would be one.
 Question 22

Which of the following is NOT a bottom up, shift reduce parser?

 A LR parser B LL parser C SLR parser D LALR parser
Compiler-Design       Parsers
Question 22 Explanation:
Bottom Up SR Parsers are:
1. SLR
2. LALR
3. CLR
4. LR(0)
Top Down parser:
1. Recursive descent
2. Non Recursive descent(LL(1))
 Question 23

Which of the following does NOT represent the Exclusive NOR operation over the binary variables A and B?

 A A’ ⊕ B’ B A ⊕ B’ C A’ ⊕ B D AB + A’B’
Digital-Logic-Design       Boolean-Algebra
Question 23 Explanation:
A’ ⊕ B’ = Ex-NOR
 Question 24
Which of the following provides a method to avoid element name conflicts in XML?
 A Namespaces B DTD C CSS D DOM
Web-Technologies       Web-Technologies
Question 24 Explanation:
 Question 25

Suppose x and y are floating point variables that have been assigned the values x = 8.8 and y = 3.5. What will be the value of the following arithmetic expression?

2 * x / 3 * y

 A 20.3333 B 24.4545 C 16.3535 D 20.5333
Digital-Logic-Design       Number-Systems
Question 25 Explanation:
x = 8.8 y=3.5
= 1 (equal priority
Associativity (left to Right)
(((2 * x)/3) * y)
((2 x *) / 3) * y)
(2x * 31) * y
2x * 31) y*
(2x * 31 y*
Put the 2 * 8.8 * 3 / 3.5 *
= 20.53333
 Question 26

State whether TRUE or FALSE

(i) In NDFA, the transition function δ: Q × Σ → 2Q
(ii) NDFA does not permit empty string transitions
 A (i) False (ii) False B (i) True (ii) False C (i) False (ii) True D (i) True (ii) True
Theory-of-Computation       DFA
Question 26 Explanation:
Formal Definition of an NDFA
An NDFA can be represented by a 5-tuple (Q, ∑, δ, q0, F) where
Q is a finite set of states.
is a finite set of symbols called the alphabets.
δ is the transition function where δ: Q × ∑ → 2Q
(Here the power set of Q (2Q) has been taken because in case of NDFA, from a state, transition can occur to any combination of Q states)
q0 is the initial state from where any input is processed (q0 ∈ Q).
F is a set of final state/states of Q (F ⊆ Q).
DFA: Empty string transitions are not seen in DFA.
NDFA: permits empty string transitions.
 Question 27

Which of the following data structures is used in level order traversal of a binary tree?

 A Skip list B Stack C Array D Queue
Data-Structures       Binary-Trees
Question 27 Explanation:
Queue data structures is used in level order traversal of a binary tree.
Example:
Level order traversal of binary tree.
For each node, first the node is visited and then it’s child nodes are put in a FIFO queue.
printLevelorder(tree)
1) Create an empty queue q
2) temp_node = root /*start from root*/
3) Loop while temp_node is not NULL
a) print temp_node->data
b) Enqueue temp_node’s children (first left then right children) to q
c) Dequeue a node from q and assign it’s value to temp_node
Note:
Level order traversal of binary tree is time Complexity is O(n) where n is number of nodes in the binary tree.
 Question 28

The boolean function X’Y’ + XY + X’Y, where X’ represents the complement of X, is equivalent to ____

 A X + Y’ B X’ + Y’ C X’ + Y D X + Y
Digital-Logic-Design       Boolean-Function
Question 28 Explanation:
 Question 29

Which of the following is a white box testing technique?

 A Data flow testing B Equivalence class testing C Cause effect graphing D State based testing
Software-Engineering       Software-testing
Question 29 Explanation:
White box testing techniques analyze the internal structures the used data structures, internal design, code structure and the working of the software rather than just the functionality as in black box testing. It is also called glass box testing or clear box testing or structural testing.
White box testing techniques
1. Statement coverage
2. Branch CoverAge
3. Condition Coverage
4. Multiple Condition Coverage
5. Basis Path Testing
6. Flow graph notation
7. Loop Testing
 Question 30

In a Big-Endian machine, a 32 bit word is stored at address 0 in a memory that is byte addressable. What byte of the word will be stored at address 0?

 A Byte 3 B Byte 2 C Byte 1 D Byte 0
Computer-Organization       Memory-Interfacing
Question 30 Explanation:
→ A load word or store word instruction uses only one memory address. The lowest address of the four bytes is used for the address of a block of four contiguous bytes.
→ How is a 32-bit pattern held in the four bytes of memory?
There are 32 bits in the four bytes and 32 bits in the pattern, but a choice has to be made about which byte of memory gets what part of the pattern. There are two ways that computers commonly do this:
Big Endian Byte Order: The most significant byte (the "big end") of the data is placed at the byte with the lowest address. The rest of the data is placed in order in the next three bytes in memory.
Little Endian Byte Order: The least significant byte (the "little end") of the data is placed at the byte with the lowest address. The rest of the data is placed in order in the next three bytes in memory.
→ In these definitions, the data, a 32-bit pattern, is regarded as a 32-bit unsigned integer.
→ The "most significant" byte is the one for the largest powers of two: 231, ..., 224. The "least significant" byte is the one for the smallest powers of two: 27, ..., 20.
→ For example, say that the 32-bit pattern 0x12345678 is stored at address 0x00400000. The most significant byte is 0x12; the least significant is 0x78.
Within a byte the order of the bits is the same for all computers (no matter how the bytes themselves are arranged).
 Question 31

Which of the following relation schemas is definitely in BCNF?

 A R1(A,B) B R4(A,B,C,D,E) C R3(A,B,C,D) D R2(A,B,C)
Database-Management-System       Normalization
Question 31 Explanation:
BCNF properties
1. BCNF is free from redundancy.
2. If a relation is in BCNF, then 3NF is also also satisfied.
3. Every Binary Relation ( a Relation with only 2 attributes ) is always in BCNF.
4. Sometimes going for BCNF form may not preserve functional dependency.
 Question 32

Suppose a network using CSMA/CD has a bandwidth of 10 Mbps. If the maximum propagation time is 25 microsec, that what will be the minimum frame size?

 A 500 bits B 50 bits C 500 bytes D 4*1011 bits
Computer-Networks       Ethernet
Question 32 Explanation:
→ The minimum frame transmission time is Tfr = 2 × Tp = 50 μs.
→ This means, in the worst case, a station needs to transmit for a period of 50 μs to detect the collision.
→ The minimum size of the frame is 10 Mbps × 50 μs = 500 bits or 62.5 bytes.
→ This is actually the minimum size of the frame for Standard Ethernet.
 Question 33

If 100 users are making 10 request/sec to a slotted ALOHA channel and each slot is of 50 m sec, then what will be the channel load?

 A 10 B 20 C 2 D 50
Computer-Networks       Network-Access-Methods
Question 33 Explanation:
→ Slotted aloha throughput S = Ge−G
→Total user = 100 making 10 request/sec, Then total number of requests are 1000
Each slot time is 50 ms, so the number of slots in one second = 1/(50 X 10-3) = 20 slots/sec
Requests per second = 1000
Time slots per second = 20
Channel load = Number of Requests / Number of Slots = 1000 / 20 = 50
 Question 34

Every cut set of a connected euler graph has____

 A An odd number of edges B At least three edges C An even number of edges D A single edge
Engineering-Mathematics       Graph-Theory
Question 34 Explanation:
If every minimal cut has an even number of edges, then in particular the degree of each vertex is even. Since the graph is connected, that means it is Eulerian.
 Question 35

A fair coin is tossed 6 times. What is the probability that exactly two heads will occur?

 A 11/32 B 1/64 C 15/64 D 63/64
Engineering-Mathematics       Probability
Question 35 Explanation:
Step-1: We want to calculate the probability of getting exactly k "success" results using Bernoulli's Scheme.

The probability can be calculated as:
n is a total number of experiments
k is an expected number of successes
p is the probability of a success
Step-2: The first task can be simply solved by calculating the probability of 2 successes:
A "success" is "tossing heads in a single toss".
A "failure" is "tossing tails in a single toss".
Step-3: The probability of a success is ½
The number of all experiments is n=6.
The number of successes is k=2
 Question 36

Which of the following data structures is most suitable for radix sort?

 A Stack B Binary search tree C Tree D Linked list
Algorithms       Sorting
Question 36 Explanation:
→ Forming the circularly linked list requires more memory but allows the keys to be visited more directly in either ascending or descending order via a linear traversal of the linked list rather than a depth-first traversal of the entire trie.
→ This concept of a circularly linked trie structure is similar to the concept of a threaded binary tree. This structure will be called a circularly threaded trie.
 Question 37

How many solutions does the equation x + y - z = 11 have, where x, y and z are non negative integers?

 A 120 B 78 C 156 D 130
Engineering-Mathematics       Linear-Algebra
Question 37 Explanation:
→ For any pair of natural numbers n and k, the number of distinct n-tuples of non-negative integers whose sum is k is given by the binomial coefficient.

Here, n=3 and k=11, giving you
 Question 38

Which of the following is the first module of a language processing system?

 A Preprocessor B Loader C Compiler D Linker
Question 38 Explanation:
→ Preprocessor is a program that processes its input data to produce output that is used as input to another program.
→ The output is said to be a preprocessed form of the input data, which is often used by some subsequent programs like compilers.
→ The amount and kind of processing done depends on the nature of the preprocessor.
→ Preprocessor is the first module of a language processing system.
 Question 39

Which of the following is the correct syntax to insert an image in HTML documents?

 A < a href=”flower.jpg”? > B < image href=”flower.jpg” width=”500” height=”600” > C < img src=”flower.jpg” > D < img href=”flower.jpg” >
Web-Technologies       HTML
Question 39 Explanation:
→ In HTML, images are defined with the < img > tag.
→ The < img > tag is empty, it contains attributes only, and does not have a closing tag.
→ The src attribute specifies the URL (web address) of the image: < img src="url" >
 Question 40

A graph G is dual if and only if G is a ___

 A Euler graph B Regular graph C Complete graph D Planar graph
Engineering-Mathematics       Graph-Theory
Question 40 Explanation:
Deﬁnition Given a plane graph G, the dual graph G* is the plane graph whose vtcs are the faces of G.
→ The correspondence between edges of G and those of G* is as follows:
if e∈E(G) lies on the boundaries of faces X and Y, then the endpts of the dual edge e*∈(G*) are the vertices x and y that represent faces X and Y of G.
 Question 41
Which of the following correctly defines kleene closure?
 A It is the infinite set of all possible strings of all possible lengths over Σ(input set) excluding ʎ(empty string) B It is the finite set of all possible strings of all possible lengths over Σ(input set) excluding ʎ(empty string) C It is the finite set of all possible strings of all possible lengths over Σ(input set) D It is the infinite set of all possible strings of all possible lengths over Σ(input set)
Theory-of-Computation       Languages-and-Grammars
Question 41 Explanation:
Kleene closure
It is the infinite set of all possible strings of all possible lengths over Σ(input set) excluding ʎ(empty string).
 Question 42

Which of the given options is the logical translation of the following statement, where F(x) and P(x) express the terms friend and perfect, respectively?

“None of my friends are perfect”?

 A ∃x(~F(x)∧P(x)) B ∃x(F(x)∧ ~P(x)) C ~∃x(F(x)∧P(x)) D ∃x(~F(x)∧~P(x))
Engineering-Mathematics       Propositional-Logic
Question 42 Explanation:
F(x) represents x is friend.
P(x) represents x is perfect.
Given statement is “None of my friends are perfect”.
F(x)∧P(x) ---> X is both Friend and perfect.
~∃x ----> There is exist no one.
We can also write the above statement as follows
∀x[F(x) ⟹ ¬P(x)]
≡ ∀x[¬F(x) ∨ ¬P(x)]
≡∀x¬[F(x) ∧ P(x)]
≡¬∃x[F(x) ∧ P(x)]
 Question 43

Consider the following algorithm:

```Algorithm Anand(n)
{
sum=0;
For i=1 to n do
{
For j=1 to i do
{
sum=sum+i;
}
}
}```

What will be the output of this algorithm for n=10?

 A 370 B 385 C 380 D 55
Programming       Control Flow
Question 43 Explanation:

Step-1: if i=1, j is also will execute 1 time because it is purely dependent to the variable i.
Sep-2: The sum variable is perform addition how many time jth loop executes with the difference of i value.
 Question 44

In C language ______ is a process in which a function calls itself repeatedly until some specified condition has been satisfied

 A Infinite loop B Call by value C Call by reference D Recursion
Programming       Functions
Question 44 Explanation:
Recursion is a process in which a function calls itself repeatedly until some specified condition has been satisfied.
 Question 45

The average rate of convergence of the bisection method is ____.

 A 1/2 B 3 C 2 D 1
Engineering-Mathematics       Sets-And Relation
Question 45 Explanation:
The average rate of convergence of the bisection method is 1/2.
 Question 46

What is the return value of the C library function fmod(d1,d2), where d1 and d2 are integer numbers?

 A It returns the remainder of d2/d1, with the same sign as d1 B It returns the remainder of d2/d1, with the same sign as d2 C It returns the remainder of d1/d2, with the same sign as d1 D It returns the remainder of d1/d2, with the same sign as d2
Programming       Control Flow
Question 46 Explanation:
Mod operations: fmod(d1,d2)
Take d1 = 10 and d2 = 20
d1/d2 = 10/20 = 10
So, option C is correct.
 Question 47

What is the chromatic number of an n-vertex simple connected graph, which does NOT contain any odd-length cycle?

 A N B N-1 C 2 D 3
Engineering-Mathematics       Graph-Theory
Question 47 Explanation:
→ If n ≥ 2 and there are no odd length cycles, Then it is bipartite graph.
→ A bipartite graph has the chromatic number 2.
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
 Question 48

Chose the option which matches each element of LIST-1 with exactly one element of LIST-2:

 A (i)-(d), (ii)-(c), (iii)-(b), (iv)-(a) B (i)-(b), (ii)-(a), (iii)-(d), (iv)-(c) C (i)-(a), (ii)-(d), (iii)-(c), (iv)-(b) D (i)-(d), (ii)-(b), (iii)-(c), (iv)-(a)
Computer-Networks       OSI-TCP-layers
Question 48 Explanation:
1. Repeater→ Physical layer: Its job is to regenerate the signal over the same network before the signal becomes too weak or corrupted so as to extend the length to which the signal can be transmitted over the same network.
2. Gateway→ All seven layers: A gateway, as the name suggests, is a passage to connect two networks together that may work upon different networking models. They basically works as the messenger agents that take data from one system, interpret it, and transfer it to another system. Gateways are also called protocol converters and can operate at any network layer. Gateways are generally more complex than switch or router.
3. Router→ Network layer: A router is a device like a switch that routes data packets based on their IP addresses. Router is mainly a Network Layer device. Routers normally connect LANs and WANs together and have a dynamically updating routing table based on which they make decisions on routing the data packets. Router divide broadcast domains of hosts connected through it.
Bridge→ Data link layer: A bridge is a repeater, with add on functionality of filtering content by reading the MAC addresses of source and destination. It is also used for interconnecting two LANs working on the same protocol. It has a single input and single output port, thus making it a 2 port device.
 Question 49

How many different headings tags are available in HTML?

 A 6 B 8 C 3 D 5
Web-Technologies       HTML
Question 49 Explanation:
→ HTML defines six levels of headings.
→ A heading element implies all the font changes, paragraph breaks before and after, and any white space necessary to render the heading.
→ The heading elements are H1, H2, H3, H4, H5, and H6 with H1 being the highest (or most important) level and H6 the least.
 Question 50

Considering an undirected graph, which of the following statements is/are true?

(i) Number of vertices of odd degree is always even
(ii) Sum of degrees of all the vertices is always even
 A Neither (i) nor (ii) B Both (i) and (ii) C Only (ii) D Only (i)
Engineering-Mathematics       Graph-Theory
Question 50 Explanation:
True: Number of vertices of odd degree is always even.
True: Sum of degrees of all the vertices is always even.
 Question 51

In a full binary tree of height 10, the number of nodes with degree 0,1, and 2 will be ____,____ and ____ respectively.

Note: Consider height of a tree as the number of nodes in the longest path from root to any leaf node

 A 512, 0, 511 B 512, 1, 510 C 511, 0, 512 D 511, 1, 511
Data-Structures       Binary-Trees
Question 51 Explanation:
→ Height of the full binary tree 2h -1.
Full binary tree consists of either 0 or 2 childs . So one child to the node is not possible.
The number of nodes with the degree of 1 is 0.
The nodes with degree 0 are leaf nodes, 2h-1 = 29 = 512.
The nodes with degree 2 are internal nodes 2h-1 - 1 = 511.
 Question 52

Which of the following greedy strategies gives the optimal solution for the following 0-1 knapsack problem?

w=30, w1=10, p1=11, w2=15, p2=12, w3=20, p3=24, w4=25, p4=25

 A Largest profit per unit weight first B Largest profit first C Lightest item first D Heaviest item first
Algorithms       0/1-Knapsack-and-fractional-knapsack
Question 52 Explanation:

Note: Even though they are asking 0/1 knapsack. We are always takes first profit/weight first.
→ W=30, we can exceed weight and we can’t take fractions of weight.
→ According to profit/weight, W3 having more profit. And W1 having more profit.
→ 0/1 knapsack optimal solution = 24+11 = 35
 Question 53

Select the option that best describes the relationship between the following graphs:

 A G and H are directed B G and H are isomorphic C G and H are homomorphic D G and H are not isomorphic
Engineering-Mathematics       Graph-Theory
Question 53 Explanation:
If G1 ≡ G2 then
1. |V(G1)| = |V(G2)|
2. |E(G1)| = |E(G2)|
3. Degree sequences of G1 and G2 are same.
4. If the vertices {V1, V2, ... Vk} form a cycle of length K in G1, then the vertices {f(V1), f(V2), … f(Vk)} should form a cycle of length K in G2.
→ Graph G and H are having same number of vertices and edges. So, it satisfied first rule.
→ u1 degree 2, u2 degree 3, u3 degree 3, u4 degree 2, u5 degree 3, u6 degree 3.
→ V1 degree 2, V2 degree 3, V3 degree 3, V4 degree 2, V5 degree 3, V6 degree 3.
→ But it violates the property of number of cycles. The number of cycles are not same.
 Question 54

Which of the following is the time complexity to find the determinant of an upper triangular matrix of order n*n?

 A Θ(n2.5) B Θ(n) C Θ(n2) D Θ(n)
Algorithms       Time-Complexity
Question 54 Explanation:
According to Cayley-Hamilton method, the determinant of a triangular matrix can indeed be computed in O(n) time, if multiplication of two numbers is assumed to be doable in constant time.
 Question 55

State whether TRUE or FALSE

(i) Shortest remaining time (SRT) algorithm is the preemptive version of the shortest job next(SJN) CPU scheduling algorithm
(ii) A “context switch” is the mechanism to store and restore the state or context of a CPU in PCB
 A (i) True, (ii) True B (i) False, (ii) False C (i) False, (ii) True D (i) True, (ii) False
Operating-Systems       Process-Scheduling
Question 55 Explanation:
TRUE: Shortest remaining time (SRT) algorithm is the preemptive version of the shortest job next(SJN) CPU scheduling algorithm.
TRUE: A “context switch” is the mechanism to store and restore the state or context of a CPU in PCB.
 Question 56

A language is a subset of Σ* for some alphabet Σ. If a language takes all possible strings of length 2 over Σ = {a,b}, then, which of the below is correct?

 A L = {ab,bb,ba} B L = {aa,ab,ba,bb} C L = {ab,bb,aa} D L = {ab,ba,aa}
Theory-of-Computation       Languages-and-Grammars
Question 56 Explanation:
→ All possible strings of length 2 over Σ = {a,b} = 4(aa,ab,ba,bb}.
→ We are computing all possible strings using 2n formula. Where n is number of strings.
 Question 57

Which of the following protocols is used to map IP address to MAC address?

 A ARP B IP C DHCP D RARP
Computer-Networks       IPv4-and-Fragmentation
Question 57 Explanation:
→ IP address to MAC address using Address resolution protocol(ARP).
→ MAC address to IP address using Reverse Address resolution protocol(RARP).
 Question 58

Consider the following statements. Which one is/are correct?

(i) The LU decomposition method fails if any of the diagonal elements of the matrix is zero.
(ii) The LU decomposition is guaranteed when the coefficient matrix is positive definite.
 A Both (i) and (ii) B Only (i) C Neither (i) nor (ii) D Only (ii)
Engineering-Mathematics       Linear-Algebra
Question 58 Explanation:
Lower–Upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix. The product sometimes includes a permutation matrix as well. LU decomposition can be viewed as the matrix form of Gaussian elimination. Computers usually solve square systems of linear equations using LU decomposition, and it is also a key step when inverting a matrix or computing the determinant of a matrix.
1. The LU decomposition method fails if any of the diagonal elements of the matrix is zero.
2. The LU decomposition is guaranteed when the coefficient matrix is positive definite.
 Question 59

What is the base(radix) of the number system whose numbers 312, 20 and 13.1 satisfy the following equation?

312/20 = 13.1
 A 8 B 4 C 5 D 6
Digital-Logic-Design       Number-Systems
Question 59 Explanation:
Let base of the number system is r.
(3r2 + r + 2) / 2r = (r + 3 + 1/r)
(3r2 + r + 2) / 2r = (r2 + 3r + 1) / r
(3r2 + r + 2) = (2r2 + 6r + 2)
r2 - 5r = 0
Therefore, r = 5
 Question 60

Which of the following DFD levels depicts the entire information system as one diagram concealing all the underlying details?

 A Level 0 B Level 1 C Level 3 D Level 2
Software-Engineering       DFD
Question 60 Explanation:
DFD level 0:
→ It Highest abstraction level DFD is known as Level 0 DFD, which depicts the entire information system as one diagram concealing all the underlying details.
→ Level 0 DFDs are also known as context level DFDs.
→ It shows a data system as a whole and emphasizes the way it interacts with external entities.
→ This DFD level 0 example shows how such a system might function within a typical retail business.
DFD level 1:
→ DFD depicts basic modules in the system and flow of data among various modules.
→ Level 1 DFD also mentions basic processes and sources of information.
→ It breaks down the main processes in to subprocesses that can then be analyzed and improved on a more intimate level.
DFD level 2:
A level 2 data flow diagram (DFD) offers a more detailed look at the processes that make up an information system than a level 1 DFD does it. Higher level DFDs can be transformed into more specific lower level DFDs with deeper level of understanding unless the desired level of specification is achieved.
 Question 61

Which of the following phases of the compilation process is also known as parsing?

 A Lexical analysis B Code optimization C Syntax analysis D Semantic analysis
Compiler-Design       Parsers
Question 61 Explanation:
Parsing, syntax analysis, or syntactic analysis is the process of analysing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. The term parsing comes from Latin pars (orationis), meaning part (of speech).
 Question 62

Consider an AVL tree constructed by inserting the elements 18, 10, 5, 3, 27, 7, 35, 43, 32 one by one. Which of the following options give the number of comparisons to search the key value 45 in this AVL tree?

 A 5 B 4 C 3 D 2
Data-Structures       Binary-Trees
Question 62 Explanation:
 Question 63

Which of the following Hasse diagrams is are lattice(s)?

 A Only (a), (b) and (c) B Only (a) and (b) C Only (b) and (c) D Only (a) and (c)
Engineering-Mathematics       Sets-And Relation
Question 63 Explanation:
A Hasse diagram is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction.
 Question 64

The DELETE/FROM/WHERE command is used for removing one or more ___.

 A Attributes from a table(relation) B Tables from a database C Databases D Tuples from a table(relation)
Database-Management-System       Relational-databases
Question 64 Explanation:
DELETE/FROM/WHERE command is used for removing one or more tuples from a table(relation).
DROP command is used for dropping entire table.
 Question 65

What is the hexadecimal representation of the decimal number 8537?

 A (2059)16 B (2159)16 C (2195)16 D (2157)16
Digital-Logic-Design       Number-Systems
Question 65 Explanation:
Step-1: First convert decimal number into binary number
Step-2: (8537)10 = (0010000101011001)2
Step-3: Divide binary number into 4 segments (0010 0001 0101 1001)2
Step-4: Write equivalent number of hexadecimal (2159)16
 Question 66

Which of the following is a recursive algorithm to convert a positive decimal integers into equivalent binary integers?

 A B C D
Digital-Logic-Design       Number-Systems
Question 66 Explanation:
Algorithm:
Take decimal number is 12.
Step-1 → 12%2 which is equal to 0+10*(⌊12/2⌋)%2
Step-2 → 6%2 which is equal to 0+10*(⌊6/2⌋)%2
Step-3 → 3%2 which is equal to 1+10*(⌊3/2⌋)%2
Step-4 → 1%2 which is equal to 1+10*(⌊1/2⌋)%2
 Question 67

Referential integrity constraints works on the concept of:

 A Secondary key B Super key C Foreign key D Primary key
Database-Management-System       Constraints
Question 67 Explanation:
Referential integrity constraints works on the concept of foreign key.
Referential Integrity Rules
→ A referential integrity rule is a rule defined on a key (a column or set of columns) in one table that guarantees that the values in that key match the values in a key in a related table (the referenced value).
→ Referential integrity also includes the rules that dictate what types of data manipulation are allowed on referenced values and how these actions affect dependent values.
The rules associated with referential integrity are:
1. Restrict: Disallows the update or deletion of referenced data.
2. Set to Null: When referenced data is updated or deleted, all associated dependent data is set to NULL.
3. Set to Default: When referenced data is updated or deleted, all associated dependent data is set to a default value.
4. Cascade: When referenced data is updated, all associated dependent data is correspondingly updated. When a referenced row is deleted, all associated dependent rows are deleted.
5. No Action: Disallows the update or deletion of referenced data. This differs from RESTRICT in that it is checked at the end of the statement, or at the end of the transaction if the constraint is deferred.
 Question 68

Which of the following is NOT a goal of the software testing?

 A Failure detection B Fault detection C Size reduction D Error detection
Software-Engineering       Software-testing
Question 68 Explanation:
Size reduction is not goal of software testing because their intention is to find bugs and detection of bugs.
 Question 69

Choose the option that correctly matches each element of LIST-1 with exactly one element of LIST-2:

```        LIST-1				LIST-2
(i)  Newton-Raphson method	(a) Solving nonlinear equation
(ii) Simpson’s rule		(b) Solving ordinary differential equations
(iii)Runge-Kutta method		(c) Numerical integration
(iv) Gauss elimination		(d) Interpolation```
 A (i)-(b), (ii)-(d), (iii)-(a), (iv)-(c) B (i)-(a), (ii)-(b), (iii)-(c), (iv)-(d) C (i)-(a), (ii)-(c), (iii)-(d), (iv)-(b) D (i)-(d), (ii)-(c), (iii)-(b), (iv)-(a)
Engineering-Mathematics       Newton-Raphson-Method
Question 69 Explanation:
Newton-Raphson method→ Interpolation
Simpson’s rule→ Numerical integration
Runge-Kutta method→ Solving ordinary differential equations
Gauss elimination→ Solving nonlinear equation
 Question 70

How many ways are there to arrange the nine letters of the word ALLAHABAD?

 A 4560 B 4000 C 7560 D 7500
Engineering-Mathematics       Combinatorics
Question 70 Explanation:
Step-1: There are 4A, 2L, 1H, 1B and 1D.
Step-2: Total number of alphabets! / alphabets are repeating using formula (n!) / (r1! r2!..).
Step-3: Repeating letters are 4A's and 2L's
= 9! / (4!2!)
= 7560
 Question 71

Consider an array with n elements. Which of the following options gives the maximum number of swap(aj, aj+1) operations to sort the array elements using efficient bubble sort algorithm?

 A n2 /2 B n(n-1)/2 C n2 D n(n+1)/2
Algorithms       Sorting
Question 71 Explanation:
→ The worst case is if the array is already sorted but in descending order.
→ This means that in the first iteration it would have to look at n elements, then after that it would look n - 1 elements (since the biggest integer is at the end) and so on and so forth till 1 comparison occurs.
→ For n number of numbers, total number of comparisons done will be (n-1)+ ... + 2 + 1.
= (n*(n-1))/2
= O(n2)
 Question 72

A DFA can be expressed as a 5 tuple(Q, Σ, δ, q0, F), where δ is the transition function defined as ___?

 A δ: Σ → Q B δ: Q x Q → Σ C δ: Q → Q D δ: Q x Σ → Q
Theory-of-Computation       Finite-Automata
Question 72 Explanation:
Deterministic Finite Automata (DFA)
DFA consists of 5 tuples {Q, ∑, q, F, δ}.
Q : set of all states.
∑ : set of input symbols. (Symbols which machine takes as input)
q : Initial state. (Starting state of a machine)
F : set of final state.
δ : Transition Function, defined as δ: QX∑ → Q.
 Question 73

How many bit strings of length eight (either start with a 1 bit or end with the two bits 00) can be formed?

 A 64 B 255 C 160 D 128
Engineering-Mathematics       Combinatorics
Question 73 Explanation:
Use the subtraction rule.
1. Number of bit strings of length eight that start with a 1 bit: 27 = 128
2. Number of bit strings of length eight that end with bits 00: 26 = 64
3. Number of bit strings of length eight that start with a 1 bit and end with bits 00: 25 = 32
The number is 128+64+32 = 160
 Question 74

Which of the following statements are logically equivalent?

(i) ∀x(P(x))
(ii) ~∃x(P(x))
(iii) ~∃x(~P(x))
(iv) ∃x(~P(x))
 A Only (ii) and (iv) B Only (ii) and (iii) C Only (i) and (iv) D Only (i) and (ii)
Engineering-Mathematics       Propositional-Logic
Question 74 Explanation:
∀x(P(x)) = ~∃x(~P(x))
 Question 75

State whether TRUE or FALSE

(i) Secondary index cannot be defined on key attribute values
(ii) In B+ tree indexing the non-leaf nodes contain the actual data pointers
 A (i)-False, (ii)-True B (i)-True, (ii)-True C (i)-False, (ii)-False D (i)-True, (ii)-False
Database-Management-System       B-and-B+-Trees
Question 75 Explanation:
→ Secondary Index does not have any impact on how the rows are actually organized in data blocks. They can be in any order. The only ordering is w.r.t the index key in index blocks.
→ Indexing can be of the following types −
1. Primary Index − Primary index is defined on an ordered data file. The data file is ordered on a key field. The key field is generally the primary key of the relation.
2. Secondary Index − Secondary index may be generated from a field which is a candidate key and has a unique value in every record, or a non-key with duplicate values.
3. Clustering Index − Clustering index is defined on an ordered data file. The data file is ordered on a non-key field.
B+ tree
The structure of leaf nodes of a B+ tree is quite different from the structure of internal nodes of the B+ tree. Since data pointers are present only at the leaf nodes, the leaf nodes must necessarily store all the key values along with their corresponding data pointers to the disk file block, in order to access them. Moreover, the leaf nodes are linked to provide ordered access to the records.
 Question 76

What is the solution of the recurrence relation an = 6an-1 - 9an-2 with initial conditions a0=1 and a1=6?

 A an = 3n + 3n2 B an = 3n + n3n C an = 3n + 3nn D an = n3 + n3n
Engineering-Mathematics       Combinatorics
Question 76 Explanation:
→ Let c1, c2, ..., ck be real numbers.
→ Suppose that the characteristic equation rk −c1rk−1 −···−ck = 0 has k distinct roots r1, r2, ..., rk.
→ Then, a sequence {an} is a solution of the recurrence relation: an = c1an−1 + c2an−2 + ··· + ckan−k
→ if and only if an = α1rn1 + α2rn2 + ··· + αk rnk for n = 0,1,2,..., where α1, α2, ..., αk are constants.
→ r2 − 6r + 9 = 0 has only 3 as a root.
→ So the format of the solution is an = α13n + α2n3n.
→ Need to determine α1 and α2 from initial conditions:
a0 = 1 = α1
a1 = 6 = α13 + α23
Solving these equations we get α1=1 and α2=1
Therefore, an = 3n + n3n.
 Question 77

What is the Cyclomatic Complexity of the following flow-graph of a software code?

 A 10 B 4 C 8 D 2
Software-Engineering       Software-testing
Question 77 Explanation:
Step-1: To find cyclomatic complexity we have 3 formulas.
Number of regions(R) + 1
Predicates(P) + 1
Edges(E) - Vertex(V) + 2
Step-2: We can apply any formula to find cyclomatic complexity.
Step-3: 8 vertex and 10 edges.
10 - 8 + 2 = 4
 Question 78

Which of the following ‘C’ language operators has the right to left associativity?

 A Relational operators B Conditional operators C Logical AND and OR operators D Arithmetic multiply and divide operators
Programming       Operator
Question 78 Explanation:
Logical AND and OR operators are having right to left associativity.
 Question 79

What is the minimum number of 2 input NOR gates to implement the Boolean function (XY+Z)?

 A 8 B 5 C 3 D 7
Digital-Logic-Design       Boolean-Function
Question 79 Explanation:
XY+Z
= (X+Z)(Y+Z)( Distribute + over .)
= ((X+Z)' +(Y+Z)' )'
 Question 80

If R(A,B,C,D) is a relation schema, which is decomposed into R1(A,B,C) and R2(C,D), which of the following ensures that the given decomposition is non additive(or lossless)?

 A R1 → R2 B R2 → R1 C R1 ∩ R2 → R1 or R1 ∩ R2 → R2 D R1 U R2 → R1 R1 U R2 → R2
Database-Management-System       Functional-Dependency
Question 80 Explanation:
Option (C) is the correct option because a decomposition can be lossless if and only if there exists a common attribute between the decomposed relations which is either a candidate key or a key attribute in any of the decomposed tables.
For lossless decomposition:
R1 ∩ R2 → R1 (OR) R1 ∩ R2 → R1 - R2
R1 ∩ R2 → R2 (OR) R1 ∩ R2 → R2 - R1
 Question 81

If r and s are regular expression representing the languages L(r) and L(s), respectively, then which of the following is FALSE?

 A (r)|(s) is a regular expression representing L(r)UL(s) B (r)|(s) is a regular expression representing (L(r))* or (L(s))* C (r)* is a regular expression representing (L(r))* D (r)(s) is regular expression representing L(r)L(s)
Theory-of-Computation       Regular-Expression
Question 81 Explanation:
If r and s are regular expressions denoting the languages L(r) and L(s), then
1. Union : (r)|(s) is a regular expression denoting L(r) U L(s)
2. Concatenation : (r)(s) is a regular expression denoting L(r)L(s)
3. Kleene closure : (r)* is a regular expression denoting (L(r))*
(r) is a regular expression denoting L(r).
 Question 82

Which of the following statements about the Newton-Raphson method is/are correct?

(i) It is quadratic convergent
(ii) If f'(x) is zero, it fails
(iii) It is also used to obtain complex root
 A (i), (ii) and (iii) B only (i) and (iii) C only (i) and (ii) D only (i)
Engineering-Mathematics       Calculus
Question 82 Explanation:
Above all statements are true for Newton-Raphson method.
Note: Newton-Raphson method is mainly used for Interpolation.
 Question 83

What is the minimum number of students in a class to be sure that three of them are born in the same month?

 A 24 B 12 C 25 D 13
Engineering-Mathematics       Combinatorics
Question 83 Explanation:
With the help of Pigeonhole principle we can get the solution. The idea is that if you n items and m possible containers. If n > m, then at least one container must have two items in it. So, total 15 minimum number of students.
 Question 84

Considering every instruction and address as one word long, how many memory access are required for the following instruction, where R1, R2 and R3 are registers, and (R3) represents that R3 contains a memory address where some value (operand) is stored?

ADD R1, R2, (R3)

 A 4 B 1 C 3 D 2
Computer-Organization       Machine-Instructions
Question 84 Explanation:
We need one memory access to load the actual instruction from memory. Then R2 contains an operand value, so it doesn't require a memory access. Whereas R3 has a value which is the address of the operand, so taking that address we need to make one memory access to load the actual operand. So, this will be second memory access. The result of the addition is stored into R1. This doesn't require a memory access. So, in total there are 2 memory accesses.
There are 84 questions to complete.