GATE CS 2001

Consider the following statements:
S1: The sum of two singular n × n matrices may be non-singular
S2: The sum of two n × n non-singular matrices may be singular.
Which of the following statements is correct?

S1 and S2 are both true

S1 is true, S2 is false

S1 is false, S2 is true

S1 and S2 are both false

Ans .

Explanation :
Singular Matrix: A square matrix is singular if and only if its determinant
value is 0. S1 is True: The sum of two singular n × n matrices may be
non-singular It can be seen be taking following example.
The following two matrices are singular, but their sum is non-singular

Consider the following relations:
R1(a,b) iff (a+b) is even over the set of integers
R2(a,b) iff (a+b) is odd over the set of integers
R3(a,b) iff a.b > 0 over the set of non-zero rational numbers
R4(a,b) iff |a - b| <= 2 over the set of natural numbers
Which of the following statements is correct?

R1 and R2 are equivalence relations, R3 and R4 are not.

R1 and R3 are equivalence relations, R2 and R4 are not.

R1 and R4 are equivalence relations, R2 and R3 are not.

R1, R2, R3 and R4 are all equivalence relations

Ans .

Explanation :
So basically, we have to tell whether these relations are equivalence or not.
R1(a,b)
Reflexive : Yes, because (a+a) is even.
Symmetrix : Yes, (a+b) is even ⟹ (b+a) is even.
Transitive : Yes, because (a+b) is even and (b+c) is even ⟹ (a+c) is even.
So R1 is equivalence relation.
R2(a,b)
Reflexive : No, because (a+a) is even.
So R2 is not equivalence relation.
R3(a,b)
Reflexive : Yes, because a.a > 0.
Symmetrix : Yes, a.b > 0 ⟹ b.a > 0.
Transitive : Yes, because a.b > 0 and b.c > 0 ⟹ a.c > 0.
So R3 is equivalence relation.
R4(a,b)
Reflexive : Yes, because |a-a| ≤ 2.
Symmetrix : Yes, |a-b| ≤ 2 ⟹ |b-a| ≤ 2.
Transitive : No, because |a-b| ≤ 2 and |b-c| ≤ 2 ⇏ (a-c) is even.
So R4 is not equivalence relation.
So option (b) is correct..

Consider two well-formed formulas in prepositional logic
GATE CSE
Which of the following statements is correct?

F1 is satisfiable, F2 is valid %

F1 unsatisfiable, F2 is satisfiable

F1 is unsatisfiable, F2 is valid

F1 and F2 are both satisfiable

Ans .

Explanation :
Explanation: The concept behind this solution is: a) Satisfiable If there is an assignment of truth values which makes that expression true. b) UnSatisfiable If there is no such assignment which makes the expression true c) Valid If the expression is Tautology Here, P => Q is nothing but –P v Q F1: P => -P = -P v –P = -P F1 will be true if P is false and F1 will be false when P is true so F1 is Satisfiable F2: (P => -P) v (-P => P) which is equals to (-P v-P) v (-(-P) v P) = (-P) v (P) = Tautology So, F1 is Satisfiable and F2 is valid Option (a) is correct.

Consider the following two statements:
GATE CSE

Only S1 is correct

Only S2 is correct

Both S1 and S2 are correct

None of S1 and S2 is correct

Ans .

Explanation :
Explanation: We can easily build a DFA for S1. All we need to check is whether input string has even number of 0's. Therefore S1 is regular. We can't make a DFA for S2. For S2, we need a stack. Therefore S2 is not regular.

Which of the following statements is true?

If a language is context free it can always be accepted by a deterministic push-down automaton

The union of two context free languages is context free

The intersection of two context free languages is context free

The complement of a context free language is context free

Ans .

Explanation :
Refer http://en.wikipedia.org/wiki/Context-free_language#Closure_properties

Given an arbitary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least

N²

2 ^N

Ans .

Explanation :
Refer http://en.wikipedia.org/wiki/Powerset_construction

More than one word are put in one cache block to

exploit the temporal locality of reference in a program

exploit the spatial locality of reference in a program

reduce the miss penalty

none of the above

Ans .

Explanation :
Temporal locality refers to the reuse of specific data and/or resources within relatively small time durations. Spatial locality refers to the use of data elements within relatively close storage locations. To exploit the spatial locality, more than one word are put into cache block.

Which of the following statements is false?

Virtual memory implements the translation of a program‘s address space into physical memory address space

Virtual memory allows each program to exceed the size of the primary memory

Virtual memory increases the degree of multiprogramming

Virtual memory reduces the context switching overhead

Ans .

Explanation :

A low memory can be connected to 8085 by using

INTER

RESET IN

HOLD

READY

Ans .

Explanation :
A low memory can be connected to 8085 by using READY signal, Communication is only possible when READY signal is set .So (D) is correct option

Suppose a processor does not have any stack pointer register. Which of the following statements is true?

It cannot have subroutine call instruction

It can have subroutine call instruction, but no nested subroutine calls

Nested subroutine calls are possible, but interrupts are not

All sequences of subroutine calls and also interrupts are possible

Ans .

Explanation :
Stack pointer register hold the address of top of stack, which is the location of memory at which CPU should resume its execution after servicing some interrupt or subroutine call. So if SP register is not available then no subroutine call instructions are possible. So (A) is correct option.

Given the following Karnaugh map, which one of the following represents the minimal Sum-Of-Products of the map?
GATE CSE

xy + y'z

wx'y' + xy + xz

w'x + y'z + xy

xz + y

Ans .

Explanation :

On solving we get xy+y’z so ans is (A) part

A processor needs software interrupt to

test the interrupt system of the processor

implement co-routines

obtain system services which need execution of privileged instructions

return from subroutine

Ans .

Explanation :
Software interrupts are required by CPU to obtain System services which need execution of privileged instructions. 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. The former is often called a trap or exception and is used for errors or events occurring during program execution that are exceptional enough that they cannot be handled within the program itself.. An interrupt alerts the processor to a high-priority condition requiring the interruption of the current code the processor is executing. The processor responds by suspending its current activities, saving its state, and executing a function called an interrupt handler (or an interrupt service routine, ISR) to deal with the event. This interruption is temporary, and, after the interrupt handler finishes, the processor resumes normal activities. So (C) is correct option

A CPU has two modes-privileged and non-privileged. In order to change the mode from privileged to non-privileged

a hardware interrupt is needed

a software interrupt is needed

a privileged instruction (which does not generate an interrupt) is needed

a non-privileged instruction (which does not generate an interrupt is needed

Ans .

Explanation :
Software interrupt occurs when a program terminates or a program invokes some system calls to request for some services like I/O request etc. This type of interrupt is caused by the program in user mode. Thus, a software interrupt is required to switch from kernel (privilege) mode to user (non-privilege) mode.

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?

O(n)

O(n Log n)

O(n2)

O(n!)

Ans .

Explanation :
Randomized quicksort has expected time complexity as O(nLogn), but worst case time complexity remains same. In worst case the randomized function can pick the index of corner element every time.

Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i <= n), the index of the parent is

i - 1

floor(i/2)

ceiling(i/2)

(i+1)/2

Ans .

Explanation :
Binary heaps can be represented using arrays: storing elements in an array and using their relative positions within the array to represent child-parent relationships. For the binary heap element stored at index i of the array, Parent Node will be at index: floor(i/2) Left Child will be at index: 2i Right child will be at index: 2*i + 1

Let f(n) = n ²Logn and g(n) = n (logn) ¹⁰ be two positive functions of n. Which of the following statements is correct?

f(n) = O(g(n)) and g(n) != O(f(n))

f(n) != O(g(n)) and g(n) = O(f(n))

f(n) = O(g(n)) but g(n) = O(f(n))

Ans .

Explanation :
Any constant power of Logn is asymptotically smaller than n. Proof: Given f(n) =n2Logn and g(n) = n (logn)10 In these type of questions, we suggest you to first cancel out the common factor in both the function. After removing these, we are left with f(n) = n and g(n) = (logn)9. Removing a factor of nlogn from both functions. Now n is very very large asymptotically as compared to any constant integral power of (logn) which we can verify by substituting very large value say 2100. f(2100) = 2100 = 1030 and g(2100) = 1009 = 1018. Always remember to substitute very large values of n in order to compare both these functions. Otherwise you will arrive at wrong conclusions because if f(n) is asymptotically larger than g(n) that means after a particular value of n, f(n) will always be greater that g(n)

The process of assigning load addresses to the various parts of the program and adjusting the code and date in the program to reflect the assigned addresses is called

Assembly

Parsing

Relocation

Symbol resolution

Ans .

Explanation :
Relocation of code is the process done by the linker-loader when a program is copied from external storage into main memory. A linker relocates the code by searching files and libraries to replace symbolic references of libraries with actual usable addresses in memory before running a program. Thus, option (C) is the answer.

Which of the following statements is false?

An unambiguous grammar has same leftmost and rightmost derivation

An LL(1) parser is a top-down parser

LALR is more powerful than SLR

An ambiguous grammar can never be LR(k) for any k

Ans .

Explanation :
A grammar is ambiguous if there exists a string s such that the grammar has more than one leftmost derivations for s. We could also come up with more than one rightmost derivations for a string to prove the above proposition, but not both of right and leftmost. An unambiguous grammar can have different rightmost and leftmost derivations. 2. LL parser is top-down by nature. Leftmost derivation is, intuitively, expanding or top-down in fashion, hence such convention. Rightmost derivation, on the other hand, seems like a compressing or bottom-up thing. 3. LALR is more powerful than SLR, even when both have the same LR(0) states, due to the fact that SLR checks for lookaheads by looking at FIRST and FOLLOW from the grammar after constructing its parse table and on the other hand, LALR computes lookaheads from the LR(0) states while constructing the parse table, which is a better method. 4. An ambiguous grammar can never be LR(k) for any k, because LR(k) algorithm aren’t designed to handle ambiguous grammars. It would get stuck into undecidability problem, if employed upon an ambiguous grammar, no matter how large the constant k is

Consider a set of n tasks with known runtimes r1, r2, .... rn to be run on a uniprocessor machine. Which of the following processor scheduling algorithms will result in the maximum throughput?

Round-Robin

Shortest-Job-First

Highest-Response-Ratio-Next

First-Come-First-Served

Ans .

Explanation :
Throughput means total number of tasks executed per unit time i.e. sum of waiting time and burst time. Shortest job first scheduling is a scheduling policy that selects the waiting process with the smallest execution time to execute next. Thus, in shortest job first scheduling, shortest jobs are executed first. This means CPU utilization is maximum. So, maximum number of tasks are completed. Thus, option (B) is correct.

Where does the swap space reside?

RAM

Disk

ROM

On-chip cache

Ans .

Explanation :
Swap space is an area on disk that temporarily holds a process memory image. When memory is full and process needs memory, inactive parts of process are put in swap space of disk.

Consider a virtual memory system with FIFO page replacement policy. For an arbitrary page access pattern, increasing the number of page frames in main memory will

always decrease the number of page faults

always increase the number of page faults

sometimes increase the number of page faults

never affect the number of page faults

Ans .

Explanation :
%

Which of the following requires a device driver?

Cache

Main memory

Disk

Ans .

Explanation :
A disk driver is software which enables communication between internal hard disk (or drive) and computer. It allows a specific disk drive to interact with the remainder of the computer.

Consider a schema R(A,B,C,D) and functional dependencies A->B and C->D. Then the decomposition of R into R1(AB) and R2(CD) is

dependency preserving and lossless join

lossless join but not dependency preserving

dependency preserving but not lossless join

not dependency preserving and not lossless join

Ans .

Explanation :
Dependency Preserving Decomposition: Decomposition of R into R1 and R2 is a dependency preserving decomposition if closure of functional dependencies after decomposition is same as closure of of FDs before decomposition. A simple way is to just check whether we can derive all the original FDs from the FDs present after decomposition. In the above question R(A, B, C, D) is decomposed into R1 (A, B) and R2(C, D) and there are only two FDs A -> B and C -> D. So, the decomposition is dependency preserving

Suppose the adjacency relation of vertices in a graph is represented in a table Adj(X,Y). Which of the following queries cannot be expressed by a relational algebra expression of constant length?

List of all vertices adjacent to a given vertex

List all vertices which have self loops

List all vertices which belong to cycles of less than three vertices

List all vertices reachable from a given vertex

Ans .

Explanation :
(A) This is simple query as we need to find (X, Y) for a given X. (B) This is also simple as need to find (X, X) (C) :-> Cycle < 3 . Means cycle of length 1 & 2. Cycle of length 1 is easy., Same as self loop. Cycle of length 2 is is also not too hard to compute. Though it'll be little complex, will need to do like (X,Y) & (Y, X ) both present & X != Y,. We can do this with constant RA query. (D) :-> This is most hard part. Here we need to find closure of vertices. This will need kind of loop. If the graph is like skewed tree, our query must loop for O(N) Times. We can't do with constant length query here. Answer is :-> D

Let r and s be two relations over the relation schemes R and S respectively, and let A be an attribute in R. then the relational
GATE CSE is always equal to

Ans .

Explanation :
The above expression evaluates A = a for tables r and s Option A : is only displaying attributes of table r on the select condition Option B : is only displaying attributes of table r Option C: evaluates A = a by joining tables r and s efficiently , thus correct Therefore, Answer C

How many 4-digit even numbers have all 4 digits distinct?

2240

2296

2620

4536

Ans .

Explanation :
This is a basic permutation combination question. Considering two cases : numbers ending with 0 and not ending with 0: Numbers ending with 0 1{first place: 0} ∗9{fourth place: 9 possibilities, 1-9} ∗8{third place: 8 possibilities left} ∗7{second place: 7 possibilities left} = 504 Numbers ending with non-0 4{first place: 2,4,6,8} ∗8{fourth place: 8 possibilities left, 1-9}∗8{third place: 8 possibilities left b/w 0-9} ∗7{second place: 7 possibilities left b/w 0-9} = 2592 Total = 2296 See https://in.answers.yahoo.com/question/index?qid=20090417083307AA61h9I

Consider the following statements:
S1: There exists infinite sets A, B, C such that A ∩ (B ∪ C) is finite.
S2: There exists two irrational numbers x and y such
that (x+y) is rational.
Which of the following is true about S1 and S2?

Only S1 is correct

Only S2 is correct

Both S1 and S2 are correct

None of S1 and S2 is correct

Ans .

Explanation :
S1: A ∩ (B ∪ C) Here S1 is finite where A, B, C are infinite We’ll prove this by taking an example. Let A = {Set of all even numbers} = {2, 4, 6, 8, 10...} Let B = {Set of all odd numbers} = {1, 3, 5, 7...........} Let C = {Set of all prime numbers} = {2, 3, 5, 7, 11, 13......} B U C = {1, 2, 3, 5, 7, 9, 11, 13......} A ∩ (B ∪ C) Will be equals to: {2} which is finite. I.e. using A, B, C as infinite sets the statement S1 is finite. So, statement S1 is correct. S2: There exists two irrational numbers x, y such that (x+y) is rational To prove this statement as correct, we take an example. Let X = 2-Sqrt (3), Y = 2+Sqrt (3) => X, Y are irrational X+Y = 2+Sqrt (3) + 2-Sqrt (3) = 2+2 = 4 So, statement S2 is also correct. Answer is Option C Both Statements S1, S2 are correct.

Let f: A→B be a function, and let E and F be subsets of A. Consider the following statements about images. S1: f (E ∪ F) = f (E) ∪ f (F)
S1: f (E ∩ F) = f (E) ∩ f (F)
Which of the following is true about S1 and S2?

Only S1 is correct

Both S1 and S2 are correct

None of S1 and S2 is correct

Ans .

Explanation :
S1 : correct, because both L.H.S. and R.H.S. will contain exactly the images of all elements in E and F. S2 : false, let f is a constant function s.t. range is only {1}. Now let E and F be two partitions of set A, then clearly A ∩ B is φ, and so f (φ) is not defined, but f (E) ∩ f (F) is {1}. So S1 is true, but S2 is false. So option (A) is correct.

Seven (distinct) car accidents occurred in a week. What is the probability that they all occurred on the same day?

1/7 ⁷

1/7 ⁶

1/2 ⁷

7/2 ⁷

Ans .

Explanation :
Prob(all accidents on Monday) = 1/7 ⁷. Similarly for other 6 days. So total probability = 7 * 1/7 ⁷ = 1/7 ⁶. So option (B) is correct

Consider a DFA over ∑ = {a, b} accepting all strings which have number of a’s divisible by 6 and number of b’s divisible by 8. What is the minimum number of states that the DFA will have?

Ans .

Explanation :
We construct a DFA for strings divisible by 6. It requires minimum 6 states as length of string mod 6 = 0, 1, 2, 3, 4, 5 We construct a DFA for strings divisible by 8. It requires minimum 8 states as length of string mod 8 = 0, 1, 2, 3, 4, 5, 6, 7 If first DFA is minimum and second DFA is also minimum then after merging both DFAs resultant DFA will also be minimum. Such DFA is called as compound automata. So, minimum states in the resultant DFA = 6 * 8 = 48 Thus, option (D) is the answer.

Consider the following problem X. Given a Turing machine M over the input alphabet Σ, any state q of M And a word w∈Σ*, does the computation of M on w visit the state q? Which of the following statements about X is correct?

X is decidable

X is undecidable but partially decidable

X is undecidable and not even partially decidable

X is not a decision problem

Ans .

Explanation :
This problem is a State Entry Problem. State entry problem can be reduced to halting problem. We construct a turing machine M with final state ‘q’. We run a turing machine R (for state entry problem) with inputs : M, q, w . We give ‘w’ as input to M. If M halts in the final state ‘q’ then R accepts the input. So, the given problem is partially decidable. If M goes in an infinite loop then M can not output anything. So, R rejects the input. So, the given problem becomes undecidable. Thus, option (B) is the answer.

Consider the following circuit with initial state Q0 = Q1 = 0. The D Flip-flops are positive edged triggered and have set up times 20 nanosecond and hold times 0. GATE CSE
Consider the following timing diagrams of X and C; the clock period of C <= 40 nanosecond. Which one is the correct plot of Y?

Ans .

Explanation :
Q0 = 0 (given) Therefore, Q0' = 1 During the first clock cycle nothing will change since input doesn't come before rising edge of the clock cycle Q0' becomes ’0’ on rising edge of next clock cycle. Therefore, for only one clock cycle D1 will be ‘1’.

Which is the most appropriate match for the items in the first column with the items in the second column X. Indirect Addressing I. Array implementation
Y. Indexed Addressing II. Writing re-locatable code
Z. Base Register Addressing III. Passing array as parameter

(X, III) (Y, I) (Z, II)

(X, II) (Y, III) (Z, I)

(X, III) (Y, II) (Z, I)

(X, I) (Y, III) (Z, II)

Ans .

Explanation :
Indexed addressing is used for array implementation where each element has indexes. Base register is used to relocatable code which starts from base address and then all local addresses are added to base address. Indirect addressing is done when array is passed as parameter where only name is passed. So (A) is correct option.

The 2’s complement representation of (−539) ₁₀ in hexadecimal is

ABE

DBC

DE5

9E7

Ans .

Explanation :
-53910 = 1 010 0001 10112 ( Leftmost 1 denotes negative ) One's complement = 1 101 1110 0100 Two's complement = 1 101 1110 0101 Converting this two's complement to hexadecimal form, we get DE5. Thus, C is the correct choice.

Consider the circuit shown below. The output of a 2:1 Mux is given by the function (ac' + bc).
GATE CSE
Which of the following is true?

f = x1'+ x1x

f = x1'x2 + x1x2'

f = x1x2 + x1'x2'

f = x1 + x2'

Ans .

Explanation :
g = (a and x1') or (b and x1) g = (1 and x1’) or (0 and x1) g = x1’ f = ac’ + bc f = (a and x2') or (b and x2) f = (g and x2') or (x1 and x2) f = x1’x2’ + x1x2 Thus, option (C) is the answer.

Consider the circuit given below with initial state Q0 =1, Q1 = Q2 = 0. The state of the circuit is given by the value 4Q2 + 2Q1 + Q0
GATE CSE Which one of the following is the correct state sequence of the circuit?

1,3,4,6,7,5,2

1,2,5,3,7,6,4

1,2,7,3,5,6,4

1,6,5,7,2,3,4

Ans .

Explanation :

Consider the following data path of a simple non-pilelined CPU. The registers A, B, A1, A2, MDR, the bus and the ALU are 8-bit wide. SP and MAR are 16-bit registers. The MUX is of size 8 × (2:1) and the DEMUX is of size 8 × (1:2). Each memory operation takes 2 CPU clock cycles and uses MAR (Memory Address Register) and MDR (Memory Date Register). SP can be decremented locally. GATE CSE
The CPU instruction “push r”, where = A or B, has the specification
M [SP]
How many CPU clock cycles are needed to execute the “push r” instruction?

Ans .

Explanation :
Push ‘r’ consist of following operations : M[SP ]!R SP!SP-1 ‘r’ is stored at memory at address stack pointer currently is, this take 2 clock cycles SP is then decremented to point to next top of stack So total cycles=3 So (B) is correct option

Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r,u) and d(r,v) be the lengths of the shortest paths from r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct?

d(r, u) < d(r, v)

d(r,u) > d(r,v)

d(r,u) <= (r,v)

None of the above

Ans .

Explanation :
%

How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {v1, v2, ... vn} of n vertices?

n(n-1)/2

2 ⁿ

2 ^n(n-1)/2

Ans .

Explanation :
There are total n*(n-1)/2 possible edges. For every edge, there are to possible options, either we pick it or don't pick. So total number of possible graphs is 2n(n-1)/2.

What is the minimum number of stacks of size n required to implement a queue of size n?

One

Two

Three

Four

Ans .

Explanation :
A queue can be implemented using two stacks. Let queue to be implemented be q and stacks used to implement q be stack1 and stack2. q can be implemented in two ways: Method 1 (By making enQueue operation costly) This method makes sure that newly entered element is always at the top of stack 1, so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used. enQueue(q, x)
1) While stack1 is not empty, push everything from satck1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.
dnQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it Method 2 (By making deQueue operation costly) In this method, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned. enQueue(q, x) 1) Push x to stack1 (assuming size of stacks is unlimited). deQueue(q) 1) If both stacks are empty then error. 2) If stack2 is empty While stack1 is not empty, push everything from satck1 to stack2. 3) Pop the element from stack2 and return it.

What is printed by the print statements in the program P1 assuming call by reference parameter passing? Program P1()
{
x = 10;
y = 3;
func1(y,x,x);
print x;
print y;
}
func1(x,y,z)
{
y = y+4;
z = x+y+z;
}

10,3

31,3

27,7

None of the above

Ans .

Explanation :
Here, we are passing the variables by call by reference. This means that the changes that we will make in the parameter would be reflected in the passed argument. Here, the first variable passed in the function func1 (i.e., y) points to the address of the variable x. Similarly, the second variable passed in the function func1 (i.e., x) points to the address of the variable y and the third variable passed in the function func1 (i.e., x) points to the address of the variable z. So, we have y = y + 4 ⇒ y = 10 + 4 = 14 and z = x + y + z ⇒ z = 14 + 14 + 3 = 31 z will be returned to x. So, x = 31 and y will remain 3. Thus, the correct choice is B.

Consider the following three C functions :
[PI] int * g (void)
{
int x= 10;
return (&x);
}
[P2] int * g (void)
{
int * px;
*px= 10;
return px;
}
[P3] int *g (void)
{
int *px;
px = (int *) malloc (sizeof(int));
*px= 10;
return px;
}
Which of the above three functions are likely to cause problems with pointers?

Only P3

Only P1 and P3

Only P1 and P2

P1, P2 and P3

Ans .

Explanation :
%

Consider the following program
Program P2
var n: int:
procedure W(var x: int)
begin
x=x+1;
print x;
end
procedure D
begin
var n: int;
n=3;
W(n);
end
begin //beginP2
n=10;
D;
end
If the language has dynamic scoping and parameters are passed by reference, what will be printed by the program?

None of the above

Ans .

Explanation :
In static scoping or compile-time scoping the free variables (variables used in a function that are neither local variables nor parameters of that function) are referred as global variables because at compile only global variables are available. In dynamic scoping or run-time scoping the free variables are referred as the variables in the most recent frame of function call stack. In the given code in the function call of procedure W the local variable x is printed i.e 4. Under dynamic scoping if x would have not been there in procedure W then we would refer to x of the function in function call stack i.e procedure D and the main function but since x is a local variable not a free variable we referred to the local variable hence 4 will be printed

Which of the following does not interrupt a running process?

A Device

Timer

Schedular Process

Power Failure

Ans .

Explanation :
Scheduler process doesn’t interrupt any process, it’s Job is to select the processes for following three purposes. Long-term scheduler(or job scheduler) –selects which processes should be brought into the ready queue Short-term scheduler(or CPU scheduler) –selects which process should be executed next and allocates CPU. Mid-term Scheduler (Swapper)- present in all systems with virtual memory, temporarily removes processes from main memory and places them on secondary memory (such as a disk drive) or vice versa. The mid-term scheduler may decide to swap out a process which has not been active for some time, or a process which has a low priority, or a process which is page faulting frequently, or a process which is taking up a large amount of memory in order to free up main memory for other processes, swapping the process back in later when more memory is available, or when the process has been unblocked and is no longer waiting for a resource.

Consider a machine with 64 MB physical memory and a 32-bit virtual address space. If the page size is 4KB, what is the approximate size of the page table?

16MB

8MB

2MB

24MB

Ans .

Explanation :

Consider Peterson’s algorithm for mutual exclusion between two concurrent processes i and j. The program executed by process is shown below. repeat
flag [i] = true;
turn = j;
while ( P ) do no-op;
Enter critical section, perform actions, then exit critical
section
flag [ i ] = false;
Perform other non-critical section actions.
until false;
For the program to guarantee mutual exclusion, the predicate P in the while loop should be.

flag[j] = true and turn = i

flag[j] = true and turn = j

flag[i] = true and turn = j

flag[i] = true and turn = i

Ans .

Explanation :
%

R(A,B,C,D) is a relation. Which of the following does not have a lossless join, dependency preserving BCNF decomposition?

A->B, B->CD

A->B, B->C, C->D

AB->C, C->AD

A ->BCD

Ans .

Explanation :
Background : Lossless-Join Decomposition: Decomposition of R into R1 and R2 is a lossless-join decomposition if at least one of the following functional dependencies are in F+ (Closure of functional dependencies)
R1 ∩ R2 → R1
OR
R1 ∩ R2 → R2
dependency preserving :
Decomposition of R into R1 and R2 is a dependency preserving decomposition if closure of functional dependencies after decomposition is same as closure of of FDs before decomposition. A simple way is to just check whether we can derive all the original FDs from the FDs present after decomposition. Question : We know that for lossless decomposition common attribute should be candidate key in one of the relation. A) A->B, B->CD R1(AB) and R2(BCD) B is the key of second and hence decomposition is lossless. B) A->B, B->C, C->D R1(AB) , R2(BC), R3(CD) B is the key of second and C is the key of third, hence lossless. C) AB->C, C->AD R1(ABC), R2(CD) C is key of second, but C->A violates BCNF condition in ABC as C is not a key. We cannot decompose ABC further as AB->C dependency would be lost. D) A ->BCD Already in BCNF. Therefore, Option C AB->C, C->AD is the answer.

Which of the following relational calculus expressions is not safe?
GATE CSE

Ans .

Explanation :
A tuple relational calculus expression may at times generate an infinite relation. It may also contain values that do not even appear in the database. Such expressions are said to be unsafe. A safe tuple relational calculus expression is the one which surely generates finite results. To pose a restriction over the unsafety of expressions in tuple relational calculus there is a concept of domain of a tuple relational formula denoted by dom (P) is the set of values referenced by P i.e. values there in P or values in tuple of a relation mentioned in P. Eg: The expression {t | ¬ (t € R)} is not safe because there are infinitely many tuples that do not occur in R relation . In the above question Options (A), (B) and option (D) produce finite set of tuples as each gives out tuples restricted from a particular relation and hence are safe. Option (C) produces infinite number of tuples as it generates all the tuples not in R1 i.e. it can have tuples from any other relation other than R1.Hence it is not safe.

Consider a relation geq which represents “greater than or equal to”, that is, (x,y) ∈ geq only if y >= x. create table geq
(
ib integer not null
ub integer not null
primary key 1b
foreign key (ub) references geq on delete cascade
)
Which of the following is possible if a tuple (x,y) is deleted?

A tuple (z,w) with z > y is deleted

A tuple (z,w) with z > x is deleted

A tuple (z,w) with w < x is deleted

The deletion of (x,y) is prohibited

Ans .

Explanation :
In the above question, the relation schema is ( lb , ub ), where lb is the primary key, and ub is the foreign key which is referencing the primary key of its own relation. Hence the table geq is both the master ( which has the referenced key ) as well as the child table (which has the referencing key). The table has two constraint, one is that if there is a tuple ( x, y ), then y is greater than or equal to x, And the other is referential integrity constraint, which is on-cascade-delete on the foreign key. On-cascade-delete says, that "When the referenced row is deleted from the other table (master table), then delete also from the child table". Suppose the instance in the given relation is the following:
x y
-----
5 6
4 5
3 4
6 6
Now if we delete tuple (5,6) then tuple ( 4,5 ) should also be deleted ( as 5 in the tuple (4, 5) was referencing to 5 in the tuple(5,6) which no longer exist, hence the referencing tuple should also be deleted), and as (4,5) got deleted hence tuple (3,4) should also be deleted for the same reason. Therefore in total 3 rows have to be deleted if tuple ( 5,6 ) is deleted. Now from the above instance we can say that if (x,y), i.e. ( 5,6 ) gets deleted then a tuple ( z, w) i.e, ( 3, 4) is also deleted. And we can see here that w < x. Hence option C

upscfever.com

Journey of a Thousand Miles begins with One Click!!!

UPSCFEVER - POPULAR PAGES

Join The Movement

Discussions and Comments