19 + Interview Questions in Gate Cs 2001 in Gate Page 1 InterviewSolution

1.	The 2’s complement representation of (−539)10 in hexadecimal is(A) ABE(B) DBC(C) DE5(D) 9E7
Answer» Answer: (C) Explanation: -539₁₀ = 1 010 0001 1011₂( 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.

1.

The 2’s complement representation of (−539)10 in hexadecimal is(A) ABE(B) DBC(C) DE5(D) 9E7

Answer» Answer: (C)
Explanation: -539₁₀ = 1 010 0001 1011₂( 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.

2.	Consider the following statements:S1: The sum of two singular n × n matrices may be non-singularS2: The sum of two n × n non-singular matrices may be singular. Which of the following statements is correct?(A) S1 and S2 are both true(B) S1 is true, S2 is false(C) S1 is false, S2 is true(D) S1 and S2 are both false
Answer» None

Discussion

3.	Which of the following requires a device driver?(A) Register(B) Cache(C) Main memory(D) Disk
Answer»

Discussion

4.	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(A) always decrease the number of page faults(B) always increase the number of page faults(C) sometimes increase the number of page faults(D) never affect the number of page faults
Answer»

Discussion

5.	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) A tuple (z,w) with z > y is deleted(B) A tuple (z,w) with z > x is deleted(C) A tuple (z,w) with w < x is deleted(D) The deletion of (x,y) is prohibited
Answer» None

Discussion

6.	Which of the following does not interrupt a running process?(A) A device(B) Timer(C) Scheduler process(D) Power failure
Answer»

Discussion

7.	Consider the following languagesWhich of the languages are regular?(A) Only L1 and L2(B) Only L2, L3 and L4(C) Only L3 and L4(D) Only L3
Answer»

Discussion

8.	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?(A) 8(B) 14(C) 15(D) 48
Answer»

Discussion

9.	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(A) i – 1(B) floor(i/2)(C) ceiling(i/2)(D) (i+1)/2
Answer»

Discussion

10.	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?(A) O(n)(B) O(n Log n)(C) O(n2)(D) O(n!)
Answer»

Discussion

11.	Let f(n) = n2Logn and g(n) = n (logn)10 be two positive functions of n. Which of the following statements is correct?(A) f(n) = O(g(n)) and g(n) != O(f(n))(B) f(n) != O(g(n)) and g(n) = O(f(n))(C) f(n) = O(g(n)) but g(n) = O(f(n))(D) f(n) != O(g(n)) but g(n) != O(f(n))
Answer» Answer: (B) Explanation: Any constant power of Logn is asymptotically smaller than n. Proof: Given f(n) =n²Logn and g(n) = n (logn)¹⁰ 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)⁹. 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 2¹⁰⁰. f(2¹⁰⁰) = 2¹⁰⁰ = 1030 and g(2¹⁰⁰) =100⁹ = 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).

11.

Let f(n) = n2Logn and g(n) = n (logn)10 be two positive functions of n. Which of the following statements is correct?(A) f(n) = O(g(n)) and g(n) != O(f(n))(B) f(n) != O(g(n)) and g(n) = O(f(n))(C) f(n) = O(g(n)) but g(n) = O(f(n))(D) f(n) != O(g(n)) but g(n) != O(f(n))

Answer» Answer: (B)
Explanation:

Any constant power of Logn is asymptotically smaller than n.

Proof:

Given f(n) =n²Logn and g(n) = n (logn)¹⁰
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)⁹. 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 2¹⁰⁰.

f(2¹⁰⁰) = 2¹⁰⁰ = 1030 and g(2¹⁰⁰) =100⁹ = 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).

Discussion

12.	A CPU has two modes-privileged and non-privileged. In order to change the mode from privileged to non-privileged(A) a hardware interrupt is needed(B) a software interrupt is needed(C) a privileged instruction (which does not generate an interrupt) is needed(D) a non-privileged instruction (which does not generate an interrupt is needed
Answer»

Discussion

13.	Consider the following programProgram P2var n: int:procedure W(var x: int)beginx=x+1;print x;endprocedure Dbeginvar n: int;n=3;W(n);endbegin //beginP2n=10;D;endIf the language has dynamic scoping and parameters are passed by reference, what will be printed by the program?(A) 10(B) 11(C) 3(D) None of the above
Answer»

Discussion

14.	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? (GATE 2001)(A)(B)(C)(D)(A) Only P3(B) Only P1 and P3(C) Only P1 and P2(D) P1, P2 and P3
Answer»

Discussion

15.	What is the minimum number of stacks of size n required to implement a queue of size n?(A) One(B) Two(C) Three(D) Four
Answer» None

Discussion

16.	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;}(A) 10, 3(B) 31, 3(C) 27, 7(D) None of the above
Answer» Answer: (B) 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.

16.

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;}(A) 10, 3(B) 31, 3(C) 27, 7(D) None of the above

Answer» Answer: (B)
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.

Discussion

17.	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?(A) d(r, u) < d(r, v)(B) d(r,u) > d(r,v)(C) d(r,u) <= (r,v)(D) None of the above
Answer»

Discussion

18.	Which of the following statements is false?(A) An unambiguous grammar has same leftmost and rightmost derivation(B) An LL(1) parser is a top-down parser(C) LALR is more powerful than SLR(D) An ambiguous grammar can never be LR(k) for any k
Answer»

Discussion

19.	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?(A) 16 MB(B) 8 MB(C) 2 MB(D) 24 MB
Answer»

Discussion

Explore topic-wise InterviewSolutions in .

The 2’s complement representation of (−539)10 in hexadecimal is(A) ABE(B) DBC(C) DE5(D) 9E7

Which of the following requires a device driver?(A) Register(B) Cache(C) Main memory(D) Disk

Which of the following does not interrupt a running process?(A) A device(B) Timer(C) Scheduler process(D) Power failure

Consider the following languagesWhich of the languages are regular?(A) Only L1 and L2(B) Only L2, L3 and L4(C) Only L3 and L4(D) Only L3

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?(A) 8(B) 14(C) 15(D) 48

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 &lt;= n), the index of the parent is(A) i – 1(B) floor(i/2)(C) ceiling(i/2)(D) (i+1)/2

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?(A) O(n)(B) O(n Log n)(C) O(n2)(D) O(n!)

Let f(n) = n2Logn and g(n) = n (logn)10 be two positive functions of n. Which of the following statements is correct?(A) f(n) = O(g(n)) and g(n) != O(f(n))(B) f(n) != O(g(n)) and g(n) = O(f(n))(C) f(n) = O(g(n)) but g(n) = O(f(n))(D) f(n) != O(g(n)) but g(n) != O(f(n))

What is the minimum number of stacks of size n required to implement a queue of size n?(A) One(B) Two(C) Three(D) Four

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;}(A) 10, 3(B) 31, 3(C) 27, 7(D) None of the above

Which of the following statements is false?(A) An unambiguous grammar has same leftmost and rightmost derivation(B) An LL(1) parser is a top-down parser(C) LALR is more powerful than SLR(D) An ambiguous grammar can never be LR(k) for any k

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?(A) 16 MB(B) 8 MB(C) 2 MB(D) 24 MB

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(A) i – 1(B) floor(i/2)(C) ceiling(i/2)(D) (i+1)/2