Nielit Scientist-B 17-12-2017

Question 1
Which of the following statements are not correct?
S1: 3NF decomposition is always lossless join and dependency preserving
S2: 3NF decomposition is always lossless join but may or may not be dependency preserving
S3: BCNF decomposition is always lossless join and dependency preserving
S4: BCNF decomposition is always lossless join but may or may not be dependency preserving
A
Only S1
B
Only S4
C
boh S1 and S4
D
Both S2 and S3
       Database-Management-System
Question 1 Explanation: 
→ Sometimes, BCNF may not be functional dependency preserving.
→ lossless join should be compulsory in any normal form.
Question 2
According to the given language, which among the following expression does it corresponds to? Language L={xɛ{0,1}|x is of length 4 or less}
A
(0+1+0+1+0+1+0+1)4
B
(0+1)4
C
(01)4
D
(0+1+ɛ)4
       Theory-of-Computation
Question 2 Explanation: 
The extended notation would be (0+1)4 but however, we may allow some or all the factors to be ε. Thus ε needs to be included in the given regular expression.
Question 3
Using bisection method, one root of X4-X-1 lies between 1 and 2. After second iteration the root may lie in interval:
A
(1.25,1.5)
B
(1,1.25)
C
(1,1.5)
D
None of the options
       Engineering-Mathematics
Question 3 Explanation: 
Given data.
root= X4-X-1.
Root lies Between 1 and 2,
After second iteration=?
Using bisection method.
f(1)=X4-X-1
=1-1-1
= -1
f(2)=X4-X-1
= 24 -2 -1
=13
Given constraint that “root lies between 1 and 2”
Iteration-1: x1=(a+b)/2
=(1+2)/2
= 1.5
f(1.5) = 2.5625
Iteration-2: x2=(a+b)/2
=(1+1.5)/2
=1.25
f(1.25)=0.19140625 >0
Root may lie in between (1, 1.25)
Algorithm - Bisection Scheme
Given a function f (x) continuous on an interval [a,b] and f (a) * f (b) < 0
Do
c=(a+b)/2
if f(a)*f(c)< 0 then b=c
else a=c
while (none of the convergence criteria C1, C2 or C3 is satisfied)
More info:
Bisection method is the simplest among all the numerical schemes to solve the transcendental equations. This scheme is based on the intermediate value theorem for continuous functions .
Consider a transcendental equation f(x)=0 which has a zero in the interval [a,b] and f(a)*f(b)<0. Bisection scheme computes the zero, say c, by repeatedly halving the interval [a,b]. That is, starting with
c = (a+b) / 2
The interval [a,b] is replaced either with [c,b] or with [a,c] depending on the sign of f (a) * f (c) . This process is continued until the zero is obtained. Since the zero is obtained numerically the value of c may not exactly match with all the decimal places of the analytical solution of f (x) = 0 in the interval [a,b]. Hence any one of the following mechanisms can be used to stop the bisection iterations :
C1. Fixing a priori the total number of bisection iterations N i.e., the length of the interval or the maximum error after N iterations in this case is less than | b-a | / 2N.
C2. By testing the condition | ci - c i-1| (where i are the iteration number) less than some tolerance limit, say epsilon, fixed a priori.
C3. By testing the condition | f (ci ) | less than some tolerance limit alpha again fixed a priori.
http://mat.iitm.ac.in/home/sryedida/public_html/caimna/transcendental/bracketing%20methods/bisection/bisection.html
Question 4
In a cache memory if total number of sets are 's', then the set offset is:
A
28
B
log2s
C
s2
D
s
       Computer-Organization
Question 4 Explanation: 
If S is the number of sets in our cache, then the set index has s=log2 S bits.
→ Note that in a fully-associative cache, there is only 1 set so the set index will not exist. The remaining bits are used for the tag.
→ If ℓ is the length of the address (in bits), then the number of tag bits is t = ℓ − b − s.
Question 5
Which of the following is machine independent optimization?
A
Loop optimization
B
Redundancy Elimination
C
Folding
D
All of the options
       Compiler-Design
Question 5 Explanation: 

Question 6
A stack organized computer has which of the following instructions?
A
Zero address
B
one address
C
two address
D
three address
       Computer-Organization
Question 6 Explanation: 
Zero-Address Instructions:
A stack-organized computer does not use an address field for the instructions ADD and MUL. The PUSH and POP instructions, however, need an address field to specify the operand that communicates with the stack. The following program shows how X=(A+B)*(C+D) will be written for a stack-organized computer. (TOS stands for top of stack).

To evaluate arithmetic expressions in a stack computer, it is necessary to convert the expression into reverse Polish notation. The name “zero-address” is given to this type of computer because of the absence of an address field in the computational instructions.
Question 7
Let G be a grammar in CFG and Let W 1,W2ɛ L(G) such that |W1|=|W2| then which of the following statement is TRUE?
A
Any derivation of W1 has exactly the same number of steps as any derivation of W2
B
Different derivation have different length
C
Some derivation of W1 may be shorter the derivation of W2
D
None of the options
       Theory-of-Computation
Question 7 Explanation: 
Given data,
W1 and W2 are 2 strings,
|W1|=|W2| means same length
Example CFG grammar:
S→ Cbb | cc
C→ a
W1=cc W2=Cbb
As per the grammar, W1 require only one derivation S→ cc
W2 requires two derivations S→ Cbb→ abb
It means W1 is smaller than W2.
Question 8
Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is________
A
2
B
4
C
3
D
5
       Data-Structures
Question 8 Explanation: 
→ If we apply binary search to find the first occurrence of 1 in the list, it will give us the smallest index i where 1 is stored.
→ As in this array sequence of 0’s is followed by sequence of 1’s, the array is sorted. We can apply binary search directly without sorting it.
→ So number of probes = ⌈(log2 31)⌉
= ⌈4.954196310386876⌉
⇒5
Question 9
Find the smallest number y such that y*162 (y multiplied by 162) is perfect cube:
A
24
B
27
C
36
D
38
       Engineering-Mathematics
Question 9 Explanation: 
Prime factorize: 162
⇒162 =2×3×3×3×3 = 33×(2×3)
For (2×3) to be a perfect cube, it should be multiplied by (22×32)
∴ Required number = y = 22×32 = 36
Question 10
A regular expression is (a+b*c) is equivalent to :
A
Set of strings with either a or one or more occurences of b followed by c.
B
(b*c+a)
C
Set of strings with either a or zero or more occurence of b followed by c
D
Both (B) and (C)
       Theory-of-Computation
Question 10 Explanation: 
Given regular expression is (a+b*c). It means either a or zero or more occurence of b followed by c. But according to option A, they given “one or more occurences of b”. So, it is false.
Question 11
Which of the following are undecidable?
P1: The language generated by some CFG contains any words of length less than some given number n.
P2: Let L1 be CFL and L2 be regular, to determine whether L1 and L2 have common elements
P3: Any given CFG is ambiguous or not
P4: For any given CFG G, to determine whether ɛ belongs to L(G)
A
P2 only
B
P1 and P2 only
C
P2 and P3 only
D
P3 only
       Theory-of-Computation
Question 11 Explanation: 
Decidable Problems
A problem is decidable if we can construct a Turing machine which will halt in finite amount of time for every input and give answer as ‘yes’ or ‘no’. A decidable problem has an algorithm to determine the answer for a given input.
Examples
Equivalence of two regular languages:Given two regular languages, there is an algorithm and Turing machine to decide whether two regular languages are equal or not.
Finiteness of regular language: Given a regular language, there is an algorithm and Turing machine to decide whether regular language is finite or not.
Emptiness of context free language: Given a context free language, there is an algorithm whether CFL is empty or not.

Undecidable Problems
A problem is undecidable if there is no Turing machine which will always halt in finite amount of time to give answer as ‘yes’ or ‘no’. An undecidable problem has no algorithm to determine the answer for a given input.
Examples
Ambiguity of context-free languages: Given a context-free language, there is no Turing machine which will always halt in finite amount of time and give answer whether language is ambiguous or not.
Equivalence of two context-free languages: Given two context-free languages, there is no Turing machine which will always halt in finite amount of time and give answer whether two context free languages are equal or not.
Everything or completeness of CFG: Given a CFG and input alphabet, whether CFG will generate all possible strings of input alphabet (∑*)is undecidable.
Regularity of CFL, CSL, REC and REC: Given a CFL, CSL, REC or REC, determining whether this language is regular is undecidable.
Question 12
Consider the following four processes with their corresponding arrival time and burst time :

What is the average turnaround time (in ms) for these processes using FCFS scheduling algorithm ?
A
15
B
12.8
C
13
D
none of the options
       Operating-Systems
Question 12 Explanation: 
Given, FCFS it means first come first serve. And also it is pure preemptive scheduling.

Average Turnaround Time =(8+13.4+14.2+15.6)/4=(51.2)/4=12.8
Question 13
Consider a non pipelined machine with 6 stages. the length of each stage are 20ns, 10ns, 30ns, 25ns, 40ns, and 15ns respectively. Suppose for implementing the pipelining the machine adds 5ns of overhead to each stage for clock skew and set up. What is the speed up factor of the pipelining system (ignoring any hazard impact) ?
A
7
B
14
C
3.11
D
6.22
       Computer-Organization
Question 13 Explanation: 
Given data,
Non pipelined machine with 6 stages,
Length of each stage=20,10,30,25,40,15 ns.
Implementing the pipelining the machine adds each stage=5ns overhead.
Speed up factor of the pipelining system=?

Step-1: Non pipeline for 1 instruction to all stages=20+10+30+25+40+15 ns
=140 ns
Step-2: Per cycle adds 5ns overhead to each stage =25,15,35,30,45,20 ns
= 45 ns
Step-3: Speedup factor= Time non pipelining / Time with pipeline
= 140/45
= 3.11 ns
Question 14
In how many ways 8 girl and 8 boys can sit around a circular table so that no two boys sit together?
A
(7!)2
B
(8!)2
C
7!8!
D
15!
       Engineering-Mathematics
Question 14 Explanation: 
→ First fix one boy and place other 7 in alternative seats so total ways is 7! Because they are seated in circular table. (n-1)!.
→ Now place each girl between a pair of boys. So, total ways of seating arrangement of girls is 8!
→ Finally, 7!8! Possible ways are possible.
Question 15
Which of the following is added to page table in order to track whether a page of cache has been modified since it was read from the memory?
A
Reference bit
B
Dirty bit
C
Tag Bit
D
Valid Bit
       Operating-Systems
Question 15 Explanation: 
A dirty bit (or) modified bit is a bit that is associated with a block of computer memory and indicates whether or not the corresponding block of memory has been modified. The dirty bit is set when the processor writes to (modifies) this memory.
→ The bit indicates that its associated block of memory has been modified and has not been saved to storage yet. When a block of memory is to be replaced, its corresponding dirty bit is checked to see if the block needs to be written back to secondary memory before being replaced or if it can simply be removed.
→ Dirty bits are used by the CPU cache and in the page replacement algorithms of an operating system.
→ Dirty bits can also be used in Incremental computing by marking segments of data that need to be processed or have yet to be processed.
Question 16
The time taken to switch between user and kernel modes of execution be t1 while the time taken to switch between two processes be t2. Which of the following is TRUE?
A
t1>t2
B
t1=t2
C
t1< t2
D
Nothing can be said about the relation between t1 and t2
       Operating-Systems
Question 16 Explanation: 
→ A context switch (also sometimes referred to as a process switch or a task switch) is the switching of the CPU (central processing unit) from one processor thread to another.
→ Context switches can occur only in kernel mode. Kernel mode is a privileged mode of the CPU in which only the kernel runs and which provides access to all memory locations and all other system resource
→ Other programs, including applications, initially operate in user mode, but they can run portions of the kernel code via system calls
→ The existence of these two modes in Unix-like operating systems means that a similar, but simpler, operation is necessary when a system call causes the CPU to shift to kernel mode. This is referred to as a mode switch rather than a context switch, because it does not change the current process.
→ Context switch between the processes involves mode switch also.
Question 17
In conservative two phase locking protocol, a transaction
A
Should release all the locks only at beginning of transaction
B
Should release exclusive locks only after the commit operation
C
Should acquire all the exclusive locks at beginning of transaction
D
Should acquire all the locks at beginning of transaction
       Database-Management-System
Question 17 Explanation: 
Conservative 2PL prevents deadlocks
. The difference between 2PL and C2PL is that C2PL's transactions obtain all the locks they need before the transactions begin. This is to ensure that a transaction that already holds some locks will not block waiting for other locks.
→ In heavy lock contention, C2PL reduces the time locks are held on average, relative to 2PL and Strict 2PL, because transactions that hold locks are never blocked.
→ In light lock contention, C2PL holds more locks than is necessary, because it is hard to tell what locks will be needed in the future, thus leads to higher overhead.
→ Also, a transaction will not even obtain any locks if it cannot obtain all the locks it needs in its initial request. Furthermore, each transaction needs to declare its read and write set (data items to be read/written during transaction), which is not always possible. Because of these limitations, C2PL is not used very frequently.
Question 18
Recursive enumerable language are not closed under___
A
Set difference
B
Complement
C
Both (A) and (B)
D
None of the options
       Theory-of-Computation
Question 18 Explanation: 
→ Recursively enumerable languages are not closed under set difference or complementation.
→ The set difference L-P may or may not be recursively enumerable.
→ If L is recursively enumerable, then the complement of L is recursively enumerable if and only if L is also recursive.
Question 19
Let u and V be two vectors in R 2 whose euclidean norms satisfy |u|=2|v|. What is the value α such that w=u+αv bisects the angle between u and v?
A
2
B
1
C
1/2
D
-1
       Engineering-Mathematics
Question 19 Explanation: 

Let u, v be vectors in R2, increasing at a point, with an angle θ.
A vector bisecting the angle should split θ into θ/2,θ/2
Means ‘w’ should have the same angle with u, v and it should be half of the angle between u and v.
Assume that the angle between u, v be 2θ (thus angle between u,w=θ and v,w=θ) Cosθ=(u∙w)/(∥u∥ ∥w∥) ⇾①
Cosθ=(v∙w)/(∥v∥ ∥w∥) ⇾②
①/②⇒1/1=((u∙w)/(∥u∥ ∥w∥))/((v∙w)/(∥v∥ ∥w∥))⇒1=((u∙w)/(∥u∥))/((v∙w)/(∥v∥))
⇒(u∙w)/(v∙w)=(∥u∥)/(∥v∥) which is given that ∥u∥=2 ∥v∥
⇒(u∙w)/(v∙w)=(2∥v∥)/(∥v∥)=2 ⇾③
Given ∥u∥=2∥v∥
u∙v=∥u∥ ∥v∥Cosθ
=2∙∥v∥2 Cosθ
w=u+αv
(u∙w)/(v∙w)=2
(u∙(u+αv))/(v∙(u+αv))=2
(u∙u+α∙u∙v)/(u∙v+α∙v∙v)=2a∙a=∥a∥2
4∥v∥2+α∙2∙∥v∥2 Cosθ=2(2∥v∥2 Cosθ+α∙∥v∥2/sup>)
4+2αCosθ=2(2Cosθ+α)

4+2αCosθ=4Cosθ+2α⇒Cosθ(u-v)+2α-4=0
4-2α=Cosθ(4-2α)
(4-2α)(Cosθ-1)=0 4-2α=0

Question 20
A system has 3 processes sharing 4 resources. If each process needs a maximum of 2 units then, deadlock.
A
Can never occur
B
Has to occur
C
May occur
D
None of the options
       Operating-Systems
Question 20 Explanation: 
If the system is deadlocked, it implies that each process is holding one resource and is waiting for one more. Since there are 3 processes and 4 resources, one process must be able to obtain two resources. This process requires no more resources and therefore it will return its resources when done
Question 21
What is the meaning of regular expression  * 001 *?
A
Any string containing '1' as substring
B
Any string containing '01' as substring
C
Any string containing '011' as substring
D
All string containing '001' as substring
       Theory-of-Computation
Question 21 Explanation: 
∑* means it may be zero or any string. The above regular expression should contain 001.
Question 22
Let G be a complete undirected graph on 8 vertices of G are labelled, then the number of distinct cycles of length 5 in G is equal to:
A
15
B
30
C
56
D
60
E
None of the above
       Engineering-Mathematics
Question 22 Explanation: 
Given data,
8 vertices and distinct cycles length=5
Step-1: To find number of distinct cycles
C(n,r)=C(8,5)
=8! / (5!(8−5)!)
=56
Total number of distinct cycles we can get n-1= 5-1 = 4
= 56*4
= 224
Question 23
Which of the following is TRUE?
A
Every relation in 3NF is also in BCNF
B
A relation R is in 3NF if every non prime attributes of R is fully functionally dependent on every key of R
C
Every relation in BCNF is also in 3NF
D
No relation can be in both BCNF and 3NF
       Database-Management-System
Question 23 Explanation: 
BCNF is a stronger version 3NF. So straight from definition of BCNF every relation in BCNF will also be in 3NF.
Question 24
Consider the relation scheme R(A,B,C,D) with following FD set   F={A → CE, B → D, AE → D}, Identify the highest normal form satisfied by the relation R
A
2NF
B
BCNF
C
3NF
D
1NF
       Database-Management-System
Question 24 Explanation: 
FD set F={ A→CE, B→D, AE→D }
AB+={A,B,C,D,E} it clearly shows that right side, there is no B. So, definitely candidate key require B.
→ The functional dependency B→D violates 2NF requirement. It is a partial dependency, D is partially dependent on B, where B is a proper subset of a candidate key.
Question 25
The grammar S→ aSb | bSa | SS | ɛ is :
A
Unambiguous CFG
B
Ambiguous CFG
C
Not a CFG
D
Deterministic CFG
       Theory-of-Computation
Question 25 Explanation: 

Question 26
If any string of a language L can be effectively enumerator in a lexicographic by an enumerator in a lexicographic order then language L is___
A
Regular
B
Context free but not regular
C
Recursive but not necessarily context free
D
Recursively enumerable but not necessarily recursive
       Theory-of-Computation
Question 26 Explanation: 
The given language L is to be recursively enumerable. The TM which accepts the language which is in lexicographic order. If the language is not in lexicographic order which is not accepted by TM. The give 'L' is recursive but not necessarily context free.
Question 27
Which of the following is not a deliverable of the structured system analysis?
A
Data flow diagram
B
Prototype model
C
Entity Relationship diagram
D
Data dictionary
       Software-Engineering
Question 27 Explanation: 
→ Prototype model is used when the customers do not know the exact project requirements beforehand. In this model, a prototype of the end product is first developed, tested and refined as per customer feedback repeatedly till a final acceptable prototype is achieved which forms the basis for developing the final product.
Question 28
If for a given binary search tree(BST) the pre order traversal is 41,23,11,31,62,50,73. then which of the following is its postorder traversal?
A
11,31,23,50,73,62,41
B
31,11,23,50,41,62,73
C
11,31,50,23,73,62,41
D
11,31,23,50,62,73,41
       Data-Structures
Question 28 Explanation: 
Option B is wrong, because pre order first element is root element and post order last element is root element.
According to pre order we will get below graph based on Inorder is 11,23,31,41,50,62,73.

Question 29
Consider a complete binary tree where the left and the right subtrees of the root are max heaps. The lower bound for the number of operations to convert the tree to a heap is:
A
Ω(logn)
B
Ω(nlogn)
C
Ω(n)
D
Ω(n2)
       Algorithms
Question 29 Explanation: 
→ We can apply Heapify (node) which take log n time. The lower bound for the number of operations to convert the tree to a heap is log n.
Question 30
The collection of turing recognizable languages are closed under:
i.Union
ii.Intersection
iii.complement
iv.Concatenation
v.star closure
A
i only
B
Both i,iv
C
i,ii,iv and v
D
All of the options
       Theory-of-Computation
Question 30 Explanation: 
The collection of turing recognizable languages are closed under
1)Union
2)Intersection
3)Concatenation
4)Star closure
Question 31
Which of the following statements is/ are false?
S1: LR(0) grammar and SLR(1) grammar are equivalent
S2: LR(1) grammar are subset of LALR(1) grammars
A
S1 only
B
S1 and S2 both
C
S2 only
D
None of the options
       Compiler-Design
Question 31 Explanation: 
The space of grammars:
FALSE: S1: LR(0) grammar and SLR(1) grammar are equivalent
FALSE: S2: LR(1) grammar are subset of LALR(1) grammars
Question 32
The condition for total participation of entity in a relationship is__
A
Maximum cardinality should be one
B
Minimum cardinality should be one
C
Minimum cardinality should be zero
D
None of the options
       Database-Management-System
Question 32 Explanation: 

Question 33
Which of the following regular expression is equal to (r1+r2)*?
A
r1*r2*
B
(r1r2)*
C
r1*r2*+r1r2
D
(r1*r2*)*
       Theory-of-Computation
Question 33 Explanation: 
→ We can also get many number of r1 and many number of r2.
→ Given in regular expression to get together also many number of occurrences. So, correct answer is option D.
Question 34
If the number of networks and number of hosts in class B are 2m, (2n -2) respectively. Then the relation between m,n is:
A
3m=2n
B
7m=8n
C
8m=7n
D
2m=3n
       Computer-Networks
Question 34 Explanation: 
Total number of networks in class-B network is 214
Total number of hosts per network is 216-2
Substitute 8m and 7n
⇒ 14*8=16*7
112=112
Question 35
Which of the following is true?
S1: The power of a multi tape Turing machine is greater than the power of a single tape turing machine
S2: Every non deterministic Turing machine has an equivalent deterministic Turing machine
A
S1
B
S2
C
Both S1 and S2
D
None of the options
       Theory-of-Computation
Question 35 Explanation: 
S1:In turing machine if we increase the number of tape then also language accepted by that machine is same as single tape turing machine.so there expressing power is same
S2:Non-Deterministic TM is equivalent to DTM
Question 36
Which of the following is TRUE?
A
mealy and moore machine are language acceptors
B
Finite state automata is language translator
C
NPDA is more powerful than DPDA
D
mealy machine is more powerful than moore machine
       Theory-of-Computation
Question 36 Explanation: 
→ NPDA(Non deterministic Pushdown Automata) and DPDA(Deterministic Pushdown Automata) are not equivalent in power.
→ NPDA is more powerful than DPDA which means for every language for which a dpda exist, there exist an NPDA but there are some languages that are accepted by NPDA but are not accepted by DPDA.
→ In case of DFA and NFA they are equivalent in power. So for every language accepted by DFA there exists an NFA and vice versa.
Hence,we can’t convert NPDA to DPDA always and we can convert NFA to an equivalent DFA always.
Question 37
Which of the following is/are not features of RISC processor?
i.Large number of addressing modes
ii.Uniform instruction set
A
i only
B
ii only
C
Both i and ii
D
None of the options
       Computer-Organization
Question 37 Explanation: 
The standard features of RISC processors are listed below:
1. RISC processors use a small and limited number of instructions.
RISC processors only support a small number of primitive and essential instructions. This puts emphasis on software and compiler design due to the relatively simple instruction set.
2. RISC machines mostly uses hardwired control unit.
Most of the RISC processors are based on the hardwired control unit design approach. In hardwired control unit, the control units use fixed logic circuits to interpret instructions and generate control signals from them. It is significantly faster than its counterpart but are rather inflexible.
3. RISC processors consume less power and have high performance.
RISC processors have been known to be heavily pipelined this ensures that the hardware resources of the processor are utilized to a maximum giving higher throughput and also consuming less power.
4. Each instruction is very simple and consistent.
Most instructions in a RISC instruction set are very simple that get executed in one clock cycle. 5. RISC processors use simple addressing modes.
RISC processors don’t have as many addressing modes and the addressing modes these processors have are rather very simple. Most of the addressing modes are for register operations and do not refer memory.
6. RISC instruction is of uniform fixed length.
The decision of RISC processor designers to provide simple addressing modes leads to uniform length instructions. For example, instruction length increases if an operand is in memory as opposed to in a register. a. This is because we have to specify the memory address as part of instruction encoding, which takes many more bits. This complicates instruction decoding and scheduling.
7. Large Number of Registers.
The RISC design philosophy generally incorporates a larger number of registers to prevent in large amounts of interactions with memory
Question 38
The optimization phase in a compiler gererally:
A
Reduces the space of the code
B
Optimization the code to reduce execution time
C
Both (A) and (B)
D
Neither (A) nor (B)
       Compiler-Design
Question 38 Explanation: 
→ An optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program.
→ The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the amount of memory occupied.
→ The growth of portable computers has created a market for minimizing the power consumed by a program
Question 39
Which one is the correct translation of the following statement into mathematical logic?
"None of my friends are perfect"
A
~∃x(p(x) ⋀ q(x))
B
∃x(~p(x) ⋀ q(x))
C
∃x(~p(x) ⋀ ~q(x))
D
∃x(p(x) ⋀ ~q(x))
       Engineering-Mathematics
Question 39 Explanation: 
F(x) ⇒ x is my friend
P(x) ⇒ x is perfect
There doesn't exist any person who is my friend and perfect
Question 40
If x is a one dimensional array, then:
A
*(x+i) is same as *(&x[i])
B
&x[i] is same as x+i-1
C
*(x+i) is same as *x[i]
D
*(x+i) is same as *x+i
       Data-Structures
Question 40 Explanation: 
⇒The statement *(x+i) means Value at “i” location of “ x address”.
⇒* is nothing but Value at address location
⇒&x[i] means address of ith element
⇒*(&x[i]) means Value at “i” location of “ x address”.
We can also write it into *(X+i) = X[i] =*(&x[i])
Question 41
The string 1101 does not belong to the set represented by:
A
(00+(11)*0)
B
1(0+1)*101
C
(10)*(01)*(00+11)*
D
110*(0+1)
E
Option-1 and 3
       Theory-of-Computation
Question 41 Explanation: 
Every 11 followed by 0 and no single occurrence of 1 is possible. So it cannot generate 1101 (or) 11011
Question 42
The number of integers between 1 and 500(both inclusive) that are divisible by 3 or 5 or 7 is__
A
269
B
20
C
271
D
272
       Engineering-Mathematics
Question 42 Explanation: 

Let A = number divisible by 3
B = numbers divisible by 5
C = number divisible by 7
We need to find “The number of integers between 1 and 500 that are divisible by 3 or 5 or 7" i.e.,|A∪B∪C|
We know,
|A∪B∪C|=|A|+|B|+C-|A∩B|-|A∩C|-|B∩C|+|A∩B|
|A|=number of integers divisible by 3
[500/3=166.6≈166=166]
|B|=100
[500/5=100]
|C|=71
[500/7=71.42]
|A∩B|=number of integers divisible by both 3 and 5 we need to compute with LCM (15)
i.e.,⌊500/15⌋≈33
|A∩B|=33
|A∩C|=500/LCM(3,7) 500/21=23.8≈28
|B∩C|=500/LCM(5,3) =500/35=14.48≈14
|A∩B∩C|=500/LCM(3,5,7) =500/163=4.76≈4
|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|
=166+100+71-33-28-14+4
=271
Question 43
INCA(Increase register A by 1) is an example of which of the following addressing mode?
A
Immediate addressing
B
Indirect addressing
C
Implied addressing
D
Relative addressing
       Computer-Organization
Question 43 Explanation: 
→ Implied addressing refers to instructions that comprise only an opcode without an operand; for example, the INCA (“increment accumulator”) instruction.
→ An implied sequence commences when the PC reaches the opcode for an implied instruction
(a). loads that opcode into the IR
(b). Increments the PC (c). Recognizing that this is an implied instruction, the CPU executes it and continues on to the next instruction.
→ Instructions that use implied addressing are: CLRIM, DECA, DECX, HALT, INCA, INCX, NOP, POPA, POPSR, PUSHA, PUSHSR, ROLC, RORC, RTI, RTS, SETIM, SHL, and SHR.
Question 44
Let n is the length of string to test for membership, then the number of table entry in CYK algorithm is:
A
n(n+1)
B
n2 +1
C
n2 -1
D
n(n+1)/2
       Theory-of-Computation
Question 44 Explanation: 
→ CYK algorithm takes O(n) time to compute any one entry of the table by a method.
→ There are total n(n+1)/2 table entries, the whole table construction process takes O(n3) time in worst case.
Question 45
The total number of page faults for the reference string 1,2,3,4,5,6,7,8,9,10 using FIFO page replacement policy for a process m if 3 frames are allocated to its are:
A
9
B
10
C
8
D
11
       Operating-Systems
Question 45 Explanation: 

Total number of page faults are 10.
Question 46
When the sum of all possible two digit numbers formed from three different one digit natural numbers are divided by sum of the original three numbers, the result is:
A
26
B
24
C
20
D
22
       Engineering-Mathematics
Question 46 Explanation: 
Let a,b,c be 3 different digits, the sum of the different 2 digit numbers formed with them is
=(a*10+b)+(b*10+a)+(a*10+c)+(c*10+a)+(b*10+c)+(c*10+b)
=2(a+b+c)(10+1)
=22
Question 47
Which of the following statement(S) is/are true in the context of interpreters? S1: Interpreters process program according to the logical flow of control through the program S2: Interpreter translates and executes the error free instruction before it goes to the second S3: Interpreter processing time is less compared with compiler S4. LISP and Prolog are interpreted languages
A
Only S1
B
Only S3
C
Only S1,S2 and S3
D
Only S1, S2 and S4
       Computer-Organization
Question 47 Explanation: 
S1: TRUE: Interpreters process program according to the logical flow of control through the program
S2: FALSE: Interpreter translates and executes the instruction before it goes to the second line but not doing error free operations.
S3: FALSE: Compiler more faster than interpreter
S4: FALSE:LISP and Prolog are interpreted rather than compiler based
Question 48
Consider the relation schema R(A,B,C,D) with following functional dependency set F={A→ BC, C→ D}; The relation R is in ___
A
2NF
B
BCNF
C
3NF
D
1NF
       Database-Management-System
Question 48 Explanation: 
Given, functional dependencies are F={A→ BC, C→ D}
Finding candidate key of given relation is relation is
A+={A,B,C} because we don’t have an A element in right hand side.
A→ BC dependency A is the candidate key and also part of FD. So, it is lossless.
C→ D is following Transitive dependency. So, it never become 3NF.
According to given choices, A is the correct choice.
Question 49
Which of the following statement is true?
A
Deterministic Context free language are closed under complement
B
Deterministic Context free language are not closed under union
C
Deterministic Context free language are closed under intersection with regular set
D
All of the options
       Theory-of-Computation
Question 49 Explanation: 
→ Deterministic Context free language are closed under complement
→ Deterministic Context free language are not closed under union
→ Deterministic Context free language are closed under intersection with regular set
Question 50
Which machine is equally powerful in both deterministic and non deterministic form?
A
PDA
B
TM
C
LBA
D
None of the options
       Theory-of-Computation
Question 50 Explanation: 
→ NPDA is more powerful than DPDA because
1)DPDA accept only a proper subset of CFL's ie. LL grammars.
2)NPDA can accept any CFL, which makes them more powerful over DPDA
→ Deterministic TM is equal power to Non deterministic TM
Question 51
Which of the following is a correct hierarchical relationships of the following where
L1: Set of languages accepted by NFA
L2: Set of languages accepted by DFA
L3: Set of languages accepted by DPDA
L4: Set of languages accepted by NPDA
L5: Set of recursive languages
L6. Set of recursively enumerable languages?
A
L1,L2⊂ L3⊂ L4⊂ L5⊂ L6
B
L1⊂L2⊂ L3 ⊂L4⊂ L5 ⊂L6
C
L2⊂L1⊂ L3 ⊂L4⊂ L5⊂ L6
D
L1⊂L2⊂ L3⊂ L4⊂ L6⊂ L5
       Theory-of-Computation
Question 51 Explanation: 
Question 52
Consider two matrices M1 and M2 with M1*M2 =0 and M1 is non singular. Then which of the following is true?
A
M2 is non singular
B
M2 is null Matrix
C
M2 is the identity matrix
D
M2 is transpose of M1
       Engineering-Mathematics
Question 52 Explanation: 
M2 is null Matrix
The easiest way we can prove this is by looking at the determinant, since det(AB)=det(A)det(B)
and a matrix A is singular iff det(A)=0
Question 53
Which machine is equally powerful in both deterministic and nondeterministic form?
A
Pushdown automata
B
Turing machine
C
Linear Bounded Automata
D
None of the options
       Theory-of-Computation
Question 53 Explanation: 
→ Deterministic turing machine and nondeterministic turing machine are same in terms of power.
→ NPDA is more powerful than DPDA.
Question 54
Let G be a simple undirected graph on n=3x vertices (x>=1) with chromatic number 3, then maximum number of edges in G is:
A
n(n-1)/2
B
nn-2
C
nx
D
n
       Engineering-Mathematics
Question 54 Explanation: 
Given undirected graph on n=3x vertices (x>=1) with chromatic number 3.
→ Maximum number of edges are=n.

Question 55
Which of the following is false?
A
Interrupts which are initially by an instruction are software interrupts
B
When a subordinate is called, the address of the instruction following the CALL instruction is stored in the stack pointer
C
A micro program which is written as 0's and 1's is a binary micro program
D
None of the options
       Computer-Organization
Question 55 Explanation: 
→ An interrupt is a signal to the processor emitted by hardware or software indicating an event that needs immediate attention
→ Hardware interrupts are used by devices to communicate that they require attention from the operating system.
→ A software interrupt is caused either by an exceptional condition in the processor itself, or a special instruction in the instruction set which causes an interrupt when it is executed.
Question 56
We have 10 stage pipeline, where the branch target conditions are resolved at stage 5. How many stalls are there for an incorrect predicted branch?
A
5
B
6
C
7
D
4
       Computer-Organization
Question 56 Explanation: 
→ A branch predictor is a digital circuit that tries to guess which way a branch (e.g. an if–then–else structure) will go before this is known definitively.
→ The purpose of the branch predictor is to improve the flow in the instruction pipeline.
→ The technique involves only executing certain instructions if certain predicates are true.
→ Branch prediction is typically implemented in hardware using a branch predictor.
→ Branch target conditions resolved at stage 5 means upto 4 stages there are incorrect branch target conditions are there.
→ So Branch condition is resolved at nth stage means, the number of stalls are (n-1)
Question 57
A RAM chip has 7 address lines, 8 data lines and 2 chips select lines. Then the number of memory locations is___
A
212
B
210
C
219
D
213
       Computer-Organization
Question 57 Explanation: 
Given data,
address line=7
Data lines=8
Chip selected lines=2
Step-1: Total address lines are 27 and chips select lines
Step-2: The chips select lines are 22
Step-3: Total address and chip selected lines are 27 * 22 = 29
Step-4: Number of memory locations for 8 data lines =29 * 23
= 212
Question 58
Which of the following is equivalent regular expressions?
i.((01)*(10)*)*
ii.(10+01)*
iii.(01)*+(11)*
iv.(0*+(11)*+0*)*
A
i and ii
B
ii and iii
C
iii and iv
D
iv and i
       Theory-of-Computation
Question 58 Explanation: 
→ The set of strings generated by the expression ((01)*(10)*)* are
{ε,01,10,0110,0101,1010,010110,01011010, ……}
→ The set of strings generated by the expression (10+01)* are
{ε,10,01,1010,0101,0110,101010,010101….}
→ The set of strings generated by the expression (01)*+(11)* are
{ε,01,11,0101,1111,010101,111111…}
→ The set of strings generated by the expression (0*+(11)*+0*)*are
{ε,0,11,00,000,011,110,0110,00110,01100,.....}
Compare the strings which are generated by option-1 and option-2.
Question 59
On a set A={a,b,c,d} a binary operation * is defined as given in the following table.

The relation is:
 
A
Commutative but not associative
B
neither commutative nor associative
C
Both commutative and associative
D
Associative but not commutative
       Data-Structures
Question 60
A two word instruction is stored in a location A. The operand part of instruction holds B. if the addressing mode is relative, the operand is available in location
A
A+B+2
B
A+B+1
C
B+1
D
A+B
       Computer-Organization
Question 60 Explanation: 
It is given that instruction size is 2 words, and it’s starting address is A.
When executing the present instruction program counter gets incremented to the address of the next instruction.
So, latest value in PC=A+2.
In the instruction operand value is B, which is used as a offset for the effective address calculation.
So, Effective address= Program counter + Offset.
Here Program counter= A+2, Offset = B
Effective address= A+2+B
There are 60 questions to complete.