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

1.	Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge weighted directed graph with vertex P as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?(A) P, Q, R, S, T, U(B) P, Q, R, U, S, T(C) P, Q, R, U, T, S(D) P, Q, T, R, U, S
Answer»

Discussion

2.	A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 nanoseconds respectively. Registers that are used between the stages have a delay of 5 nanoseconds each. Assuming constant clocking rate, the total time taken to process 1000 data items on this pipeline will be(A) 120.4 microseconds(B) 160.5 microseconds(C) 165.5 microseconds(D) 590.0 microseconds
Answer» None

Discussion

3.	Which of the following grammar rules violate the requirements of an operator grammar ? P, Q, R are nonterminals, and r, s, t are terminals.1. P → Q R 2. P → Q s R3. P → ε 4. P → Q t R r (A) 1 only(B) 1 and 3 only(C) 2 and 3 only(D) 3 and 4 only
Answer»

Discussion

4.	Let A = 1111 1010 arid B = 0000 1010 be two 8-bit 2’s complement numbers. Their product in 2’s complement is(A) 1100 0100(B) 1001 1100(C) 1010 0101(D) 1101 0101
Answer» Answer: (A) Explanation: Here, we have A = 1111 1010 = – 6₁₀ (A is a 2’s complement number) B = 0000 1010 = 10₁₀ (B is a 2’s complement number) A x B = – 60₁₀ = 1 011 1100₂ = 1 100 0011 (1’s complement) = 1 100 0100 (2’s complement)

4.

Let A = 1111 1010 arid B = 0000 1010 be two 8-bit 2’s complement numbers. Their product in 2’s complement is(A) 1100 0100(B) 1001 1100(C) 1010 0101(D) 1101 0101

Answer» Answer: (A)
Explanation: Here, we have

A = 1111 1010 = – 6₁₀ (A is a 2’s complement number)

B = 0000 1010 = 10₁₀ (B is a 2’s complement number)

A x B = – 60₁₀ = 1 011 1100₂ = 1 100 0011 (1’s complement) = 1 100 0100 (2’s complement)

Discussion

5.	A 4-bit carry lookahead adder, which adds two 4-bit numbers, is designed using AND, OR, NOT, NAND, NOR gates only. Assuming that all the inputs are available in both complemented and uncomplemented forms and the delay of each gate is one time unit, what is the overall propagation delay of the adder? Assume that the carry network has been implemented using two-level AND-OR logic.(A) 4 time units(B) 6 time units(C) 10 time units(D) 12 time units
Answer»

Discussion

6.	Let A, B, C, D be n × n matrices, each with non-zero determinant. If ABCD = 1, then B-1 is(A) D-1C-1A-1(B) CDA(C) ADC(D) Does not necessarily exist
Answer»

Discussion

7.	The number of different n × n symmetric matrices with each element being either 0 or 1 is: (Note: power(2, x) is same as 2x)(A) power(2, n)(B) power(2, n2)(C) power(2, (n2 + n)/2)(D) power(2, (n2 – n)/2)
Answer»

Discussion

8.	The inclusion of which of the following sets intoS = {{1, 2}, {1, 2, 3}, {1, 3, 5}, (1, 2, 4), (1, 2, 3, 4, 5}}is necessary and sufficient to make S a complete lattice under the partial order defined by set containment ?(A) {1}(B) {1}, {2, 3}(C) {1}, {1, 3}(D) {1}, {1, 3}, (1, 2, 3, 4}, {1, 2, 3, 5)
Answer»

Discussion

9.	An examination paper has 150 multiple-choice questions of one mark each, with each question having four choices. Each incorrect answer fetches -0.25 mark. Suppose 1000 students choose all their answers randomly with uniform probability. The sum total of the expected marks obtained by all these students is:(A) 0(B) 2550(C) 7525(D) 9375
Answer» None

Discussion

10.	Two n bit binary strings, S1 and S2, are chosen randomly with uniform probability. The probability that the Hamming distance between these strings (the number of bit positions where the two strings differ) is equal to d is(A) nCd /2n(B) nCd / d(C) d/2n(D) 1/2d
Answer»

Discussion

11.	A point is randomly selected with uniform probability in the X-Y plane within the rectangle with corners at (0,0), (1,0), (1,2) and (0,2). If p is the length of the position vector of the point, the expected value of p2 is(A) 2/3(B) 1(C) 4/3(D) 5/3
Answer»

Discussion

12.	The employee information in a company is stored in the relationEmployee (name, sex, salary, deptName)Consider the following SQL queryselect deptName from Employee where sex = 'M' group by deptName having avg (salary) > (select avg (salary) from Employee)It returns the names of the department in which(A) the average salary is more than the average salary in the company(B) the average salary of male employees is more than the average salary of all male employees in the company(C) the average salary of male employees is more than the average salary of employees in the same department(D) the average salary of male employees is more than the average salary in the company
Answer» Answer: (D) Explanation: In this SQL query, we have select deptName --------------- Select the department namefrom Employee ---------------- From the database of employeeswhere sex = 'M' --------------- Where sex is male (M)group by deptName ------------- Group by the name of the departmenthaving avg (salary) > (select avg (salary) from Employee) ----- Having the average salary greater than the average salary of all employees in the organization. So, this query would return the name of all departments in which the average salary of male employees is greater than the average salary of all employees in the company. Hence, D is the correct choice.

12.

The employee information in a company is stored in the relationEmployee (name, sex, salary, deptName)Consider the following SQL queryselect deptName from Employee where sex = 'M' group by deptName having avg (salary) > (select avg (salary) from Employee)It returns the names of the department in which(A) the average salary is more than the average salary in the company(B) the average salary of male employees is more than the average salary of all male employees in the company(C) the average salary of male employees is more than the average salary of employees in the same department(D) the average salary of male employees is more than the average salary in the company

Answer» Answer: (D)
Explanation: In this SQL query, we have

select deptName --------------- Select the department namefrom Employee ---------------- From the database of employeeswhere sex = 'M' --------------- Where sex is male (M)group by deptName ------------- Group by the name of the departmenthaving avg (salary) > (select avg (salary) from Employee) ----- Having the average salary greater than the average salary of all employees in the organization.

So, this query would return the name of all departments in which the average salary of male employees is greater than the average salary of all employees in the company.

Hence, D is the correct choice.

Discussion

13.	The following propositional statement is(P → (Q v R)) → ((P ^ Q) → R)(A) satisfiable but not valid(B) valid(C) a contradiction(D) none of the above
Answer»

Discussion

14.	Consider a system with a two-level paging scheme in which a regular memory access takes 150 nanoseconds, and servicing a page fault takes 8 milliseconds. An average instruction takes 100 nanoseconds of CPU time, and two memory accesses. The TLB hit ratio is 90%, and the page fault rate is one in every 10,000 instructions. What is the effective average instruction execution time?(A) 645 nanoseconds(B) 1050 nanoseconds(C) 1215 nanoseconds(D) 1230 nanoseconds
Answer»

Discussion

15.	The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined by(A) the instruction set architecture(B) page size(C) physical memory size(D) number of processes in memory
Answer»

Discussion

16.	It is desired to design an object-oriented employee record system for a company. Each employee has a name, unique id and salary. Employees belong to different categories and their salary is determined by their category. The functions to get Name, getld and compute salary are required. Given the class hierarchy below, possible locations for these functions are:i. getld is implemented in the superclassii. getld is implemented in the subclassiii. getName is an abstract function in the superclassiv. getName is implemented in the superclassv. getName is implemented in the subclassvi. getSalary is an abstract function in the superclassvii. getSalary is implemented in the superclassviii. getSalary is implemented in the subclassChoose the best design(A) (i), (iv), (vi), (viii)(B) (i), (iv), (vii)(C) (i), (iii), (v), (vi), (viii)(D) (ii), (v), (viii)
Answer»

Discussion

17.	Let R1 (A, B, C) and R2 (D, E) be two relation schema, where the primary keys are shown underlined, and let C be a foreign key in R1 referring to R2. Suppose there is no violation of the above referential integrity constraint in the corresponding relation instances r1 and r2. Which one of the following relational algebra expressions would necessarily produce an empty relation ?(A) 1(B) 2(C) 3(D) 4
Answer»

Discussion

18.	Consider two processes P1 and P2 accessing the shared variables X and Y protected by two binary semaphores SX and SY respectively, both initialized to 1. P and V denote the usual semaphone operators, where P decrements the semaphore value, and V increments the semaphore value. The pseudo-code of P1 and P2 is as follows : P1 : While true do { L1 : ................ L2 : ................ X = X + 1; Y = Y - 1; V(SX); V(SY); }P2 : While true do { L3 : ................ L4 : ................ Y = Y + 1; X = Y - 1; V(SY); V(SX); }In order to avoid deadlock, the correct operators at L1, L2, L3 and L4 are respectively(A) P(SY), P(SX); P(SX), P(SY)(B) P(SX), P(SY); P(SY), P(SX)(C) P(SX), P(SX); P(SY), P(SY)(D) P(SX), P(SY); P(SX), P(SY)
Answer» None

Discussion

19.	Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely ? (i) preorder and postorder(ii) inorder and postorder(iii) preorder and inorder(iv) level order and postorder(A) (i) only(B) (ii), (iii)(C) (iii) only(D) (iv) only
Answer»

Discussion

Explore topic-wise InterviewSolutions in .

Which of the following grammar rules violate the requirements of an operator grammar ? P, Q, R are nonterminals, and r, s, t are terminals.1. P → Q R 2. P → Q s R3. P → ε 4. P → Q t R r (A) 1 only(B) 1 and 3 only(C) 2 and 3 only(D) 3 and 4 only

Let A = 1111 1010 arid B = 0000 1010 be two 8-bit 2’s complement numbers. Their product in 2’s complement is(A) 1100 0100(B) 1001 1100(C) 1010 0101(D) 1101 0101

Let A, B, C, D be n × n matrices, each with non-­zero determinant. If ABCD = 1, then B-1 is(A) D-1C-1A-1(B) CDA(C) ADC(D) Does not necessarily exist

The number of different n × n symmetric matrices with each element being either 0 or 1 is: (Note: power(2, x) is same as 2x)(A) power(2, n)(B) power(2, n2)(C) power(2, (n2 + n)/2)(D) power(2, (n2 – n)/2)

Two n bit binary strings, S1 and S2, are chosen randomly with uniform probability. The probability that the Hamming distance between these strings (the number of bit positions where the two strings differ) is equal to d is(A) nCd /2n(B) nCd / d(C) d/2n(D) 1/2d

A point is randomly selected with uniform probability in the X-Y plane within the rectangle with corners at (0,0), (1,0), (1,2) and (0,2). If p is the length of the position vector of the point, the expected value of p2 is(A) 2/3(B) 1(C) 4/3(D) 5/3

The following propositional statement is(P → (Q v R)) → ((P ^ Q) → R)(A) satisfiable but not valid(B) valid(C) a contradiction(D) none of the above

The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined by(A) the instruction set architecture(B) page size(C) physical memory size(D) number of processes in memory

Let A, B, C, D be n × n matrices, each with non-zero determinant. If ABCD = 1, then B-1 is(A) D-1C-1A-1(B) CDA(C) ADC(D) Does not necessarily exist