GATE 2015 COMPUTER SCIENCE (CSE) QUESTIONS AND ANSWER KEY

Hello reader,

Here I am posting the questions asked in GATE 2015  COMPUTER SCIENCE (CSE)  Exam and the answer key. I am thankful to all my friends who have shared these questions. If you also want to share any question other than posted here feel free to comment that here.

Do you know any question other than posted here? Feel free to comment  here.   :)

  All Answers were collected from various forums. Check it and suggest  corrections  if  required.

Here we go.!!

 

 

 

1. Which of the following is not correct about HTTP cookies ?

a.A cookie is a piece of code that has a potential to compromise the security of an Internet user.

b. A cookie gains entry to the user's work area through an HTTP Header.

c. It has expiry date and time.

d. It can be used to track the browsing pattern of a user at a particular site.

a. Any personal information that you give to a Web site, including credit card information, will most likely be stored in a cookie unless you have turned off the cookie feature in your browser. 

b.  

c. The Expires directive in cookie  tells the browser the exact/absolute date and time  to delete the cookie

d  If the user requests a page of the site for first time the server creates a random string and sends it as a cookie back to the browser together with the requested page;this cookie will automatically be sent by the browser to the server every time a new page from the site is requested;the server stores the URL of the requested page, the date/time of the request, and the cookie in a log file. By analyzing the log file collected in the process it is possible to plot browsing pattern. 

Ans: a

2.If a binary tree has 20 leaves, then how many nodes will have two children nodes?

If there are n leaves, there will be (n-1) nodes having two child nodes. 

Answer is 20-1=19

 

3. In a typical server in which order the operations-  accept, bind, listen and recv - will be executing?
a)listen,bind,accept,recv
b)bind,listen,accept,recv
c)listen,accept,bind,recv
d)accept,listen,bind,recv

bind( )  :to associate the socket with a port on server machine

listen( ) :wait for incoming connections

accept( ):accept the connection request and returns new socket file descriptor

recv( ) : accepts the data from the client.

The order is as in (b):

 

4. Assume that for a certain processor, a read request takes 50 nanoseconds on a cache miss and 5 nanoseconds in a cache hit. Suppose while running a program, it was observed that 80% of the processor's read requests result in a cache hit. The average read access time in nanoseconds is :

Ans:  effective memory access time = (hit rate * cache access time) + (miss rate * access time for cache miss),

(50x20+5x80)/100=14 ns

 
5. Find the number of divisors for 2100?

To find the number of positive integral divisors, write the number as a product of prime numbers. Add one to exponent value of each prime number and multiply them together .

Read the method in detail here.

Given number 2100 can be represented as 2100=2*3*5*7*2*5=2^2 * 3 * 5^2* 7

Total number of divisors= (2+1)*(1+1)*(2+1)*(1+1)= 3*2*3*2= 36

 
6. Let R be the relation on the set of positive integers such that aRb if and only if a and b are distinct and have a common divisor other than 1. Which one of the following statements about R is true?

a) Reflexive and symmetric but not transitive
b) Neither Reflexive nor symmetric but transitive
c) Symmetric but not reflexive, not transitive
d) Reflexive but not symmetric, not transitive

Ans c

#Given relation is symmetric for all integers. eg: 7R21  means 21R7

#Given relation cannot be reflexive as a and b should be distinct numbers.

#Given relation may not be transitive Eg: 7R21 and 21 R 3 are true but 7R3 is false.

7. What will the following code print if input is given as ABCD EFGH
void foo(char *a)
{
    if(*a && *a != ' ')
       foo(a+1);
putchar(*a);
}

a. ABCD EFGH
b. ABCD
c. EFGH
d. DCBA 

 Ans d

8. Match the following

A. Lexical analysis                                       i. Graph coloring
B. Parsing                                                    ii. DFA minimization
C. Register allocation                               iii. Post order traversal
D. Expression evaluation                           iv. production tree

Solution:

A -ii   B- iv    C-i    D-iii

9. In a bank transaction scenario, read(x); x:=x-50; write(x); ready(y); y:=y+50; write(y);. The restriction such that the sum of x and y should always be a constant will come under which property?
a. Atomicity
b. Consistency
c. Isolation
d. Durability

Ans: b

10. In an unordered list of numbers find the complexity of an algorithm to search for an element which is neither maximum nor minimum.
a. Θ(n logn) 

b. Θ( n)
c. Θ(log n)
d. Θ(1)

Ans: d 

We only need to consider any 3 elements and compare them. So the number of comparisons is constants, that makes time complexity as Θ(1)

Let us take an array {10, 20, 15, 7, 90}. Output can be 10 or 15 or 20
Pick any three elements from given liar. Let the three elements be 10, 20 and 7.
Using 3 comparisons, we can find that the middle element is 10

11. Consider the statements:
S1: If a candidate is corrupted, he will not be elected.
S2: If a candidate is kind, he will be elected.
Which of the conclusions is TRUE?

a. If a candidate is corrupted he will be kind.
b. If a candidate is not corrupted he is not kind.
c. If a candidate is kind, he is not corrupted.
d. If a candidate is not kind he is not corrupted.

Ans : c

12. Find the largest Eigen value for the matrix
 [4 5
 2 1]

Ans: (4-x)(1-x)-5*2=0

x^2-5x-6=0

Possible value of x are 3,-2,6, and -1.

Thus  Maximum value is 6

13. Which among the following should not be discussed in SRS?
a. User Interface issues.
b. Non functional requirements.
c. Design specifications.
d. Interface with third party software.

Ans : c
14. A system has 6 resources and N processes . Each process can demand for 2 resources n maximum. For what value of n deadlock will definitely occur?
a. 1
b. 2
c. 3
d. 4

Ans: Wrong question

15. Which of the following statements are true about Abstract Syntax Tree(AST) and Control Flow graph(CFG)?
a. If N2 is a successor of N1 in AST and CFG the code implementing N2 will always be after the code implementing N1.
b. Neither AST nor CFG will carry a cycle.
c. The maximum number of successors in AST and CFG depends on input program.
d. In AST and CFG each node represents one  statement in code.

Ans: c

16. If left and right subtrees of a tree are max heaps, then find the time complexity to convert the tree into heap?
a.Ω(logn)
b. Ω(n)
c.Ω(nlogn)
d. Ω(n^2)

Ans: a

17.  A link has a transmission speed of 10^6 bits/sec. It uses data packets of size 1000 bytes each. Assume that the acknowledgment has negligible transmission delay, and that its propagation delay is the same as the data propagation delay. Also assume that the processing delays at nodes are negligible. The efficiency of the stop-and-wait protocol in this setup is exactly 25%. The value of the one-way propagation delay (in milliseconds) is :

Ans: 12

18. Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to Q2. Then which one of the following is consistent with the above statement?
(A) Q1 is in NP, Q2 is NP hard.

 (B) Q2 is in NP, Q1 is NP hard.

 (C) Both Q1 and Q2 are in NP

 (D) Both Q1 and Q2 are NP hard. 

Ans: a

19. Consider the function:
int f(n)
{
int x=1,k;
           if(n==1)
         return x;
for(k=1;k<n;k++)
    x=x+f(k)*f(n-k);
return x;
}
What will be the return value for f(5)?

f(1) = 1

f(2)= 1+ 1*1 =2

f(3)=1+1*2=3 ;

       3+2*1=5

f(4)= 1+1*5=6

         6+2*2=10

         10+5*1=15

f(5)= 1+1*15=16

         16+2*5=26

         26+5*2=36

         36+15*1=51 

Ans: 51

 

20.Equation to find duration for software development using COCOMO Model where a,b,c,d
are usual constants:

a. E=a(KLOC)exp(b) D=c(E)exp(d)
b. E=a(KLOC)exp(b) D=c(KLOC)exp(d)
c. E=a exp(b) D=c exp(d)
d. E=c exp(d) D=a exp(b)

Ans:a

21. Find the cardinality of power set of {0 , 1 , 2 , ...., 10}

Ans: Cardinality= 2^(number of elements) =2^11=2048

22. A graph is self complementary if it is isomorphic to its complementary graph. For a self complementary graph of n vertices which of the following is correct?
a. n is a multiple of 4
b. n is odd
c. n is even
d. n is congruent to 0 mod 4 or 1 mod 4

Ans : d

23. Which of the following is correct?
a.  Code inspection is done after unit testing is completed.
b. Code walk through and Code inspection are synonymous.
c. Coding standards are evaluated during code inspection
d. Code walk through is done by an independent team.

Ans: a. 

Unit testing should be done before Code inspection. 

Code inspection and code walk through have many differences. For example,  Code inspection is formal, initiated by project team and planned one while walk through is informal, initiated by the author and unplanned.

Code Inspection is done to find and fix mistakes

Code walk throgh is done by the author only

24 Consider a simple check-pointing protocol and the following set of operations in the log. 

(start, T4); (write, T4, y, 2, 3); (start, T1); (commit, T4); (write, T1, z, 5, 7);

 (checkpoint);

 (start, T2); (write, T2, x, 1, 9); (commit, T2); (start, T3), (write, T3, z, 7, 2); 

If a crash happens now and the system tries to recover using both undo and redo operations, what are the contents of the undo list and the redo list?

(A) Undo: T3, T1; Redo: T2 

(B) Undo: T3, T1; Redo: T2, T4 

(C) Undo: none; Redo: T2, T4, T3, T1 

(D) Undo: T3, T1, T4; Redo: T2 

Ans: A

In recovery stage, we need not  take care of transactions committed before checkpoint. 

T2 is committed after checkpoint. Thus redo it.

T1 and T3 are not committed after checkpoint. Thus abort them by undoing

25. If there are ten buckets numbered from 0 to 9 and input values can be in between 0 and 2020, which of the following function can fairly distribute values among buckets?
a. h(i)= i^2 mod 10
b. h(i) = i^3 mod 10
c. h(i) = 11. i^2 mod 10
d. h(i)= 12. i^2 mod 10

Ans: B

26. A grammar is given as :
X0=1X1
X1:= 0X1+ 1X1
X2 := 0X1+ λ

Which of the following regular expressions can correctly represent the grammar?
a. 10(0*+ (10)*)1
b. 10(0*1(10)*)*1
c. 1 (0+10)*1
d. 10(0+10)*1 + 110(0+10)*1

Ans: C

27. Host A sends a UDP datagram containing 8880 bytes of user data to host B over an Ethernet LAN. Ethernet frames may carry data up to 1500 bytes (i.e. MTU1500 bytes). Size of UDP header is 8 bytes and size of IP header is 20 bytes. There is no option field in 111 header. How many total number of IP fragments will be transmitted and what will be the contents of offset field in the last fragment?

 (A) 6 and 925

 (B) 6 and 7400

 (C) 7 and 1110
(D) 7 and 8880

Ans: C

28. If a connection has speed of 104560 bits per second and works in TCP connection. If 'α' is the RTT before TCP scaling and 'β'  is the window size after TCP scaling then value of α and β will be:
a. 63 ms ,  65535 x 2^14
b. 63 ms ,  65535 x 2^16
c. 500 ms ,  65535 x 2^14
d. 500 ms ,  65535 x 2^16

Ans: C

29. The edge which causes graph disconnected on deleting it is called bridge. Which of the following is true about bridge?
a. There will be no bridge in a tree.
b. Bridge can never be a part of a simple cycle.
c. Every edge in  a clique having more than 3 nodes is a bridge.
d. If a graph has bridge there will be no cycle in it.

Ans: B

30. A system has memory segments of size 200, 400, 600, 500, 300 and 250
respectively. If the processes of size 357, 210, 468, and 491 are allocated in segments using best fit algorithm, what segments will be left unused?
a. 200 & 300
b. 250 & 300
c. 200 & 400
d. 200 & 250

Ans : A

 
31. Two operations are performed on given matrix

3    4    45
7    9    105
13    2    195

I . Add third row to second row
II . Subtract third column from first column
then Determinant is:

(I) 

3         4       45

20       11     300
 

13        2       195

(II)

3       4    42

20    11    280

13    2     182

 

Do the row transform as C3--> C3/14

3    4    3

20  11  20

13  2   13

As C1=C3  Determinant =0

32. Consider a processor with byte-addressable memory. Assume that all registers, including Program Counter (PC) and Program Status Word (PSW), are of size 2 bytes. A stack in the main memory is implemented from memory location (0100)16 and it grows upward. The stack pointer (SP) points to the top element of the stack. The current value of SP is (016E) 16. The CALL instruction is of two words, the first word is the op-code and the second word is the starting address of the subroutine (one word = 2 bytes). The CALL instruction is implemented as follows:
• Store the current value of PC in the stack 

• Store the value of PSW register in the stack

 • Load the starting address of the subroutine m PC 

The content of PC just before the fetch of a CALL instruction is (5FAO) 16. After execution of the CALL instruction, the value of the stack pointer is

 (A) (016A) 16 (B) (016C)16 (C) (0170)16 (D) (0172)16 

Current value of SP: 016E

PC (2 bytes) will be stored in: 016F and 0170

PSW(2bytes) will be stored in: 0171 and 0172

So after execution of CALL instruction the value of stack pointer is 0172

33.Given two relations: R1(A,B)= {(1,5), (3,7)} and R2(A, C) = {(1 , 7),(4,9)}. R is a relation obtained the doing FULL NATURAL OUTER JOIN between R1 and R2. Find the tuples that cannot be a member of R

 a = (1,5,NULL) b = (1,5,9) c = (1,3,7) d = (4,3,9) e = (1,5,7) f= (3,7,NULL) g = (4,NULL,9)

a. a,b,c,d,e not f,g

b. a,b,c,d,e,f,g
c. e,f,g not a,b
d. e

Full natiral outer join of R1 and R2::(1,5,7), (3,7,NULL), (4,NULL,9)

Ans: c

34. Find the minimal number of gates required to implement the function
[D' +AB' +A'C + AC'D +A'C'D]'

Ans: 1

35. Find the minimum number of states in DFA required to represent the regular expression (0+1)*10

Minimal no of states=3 

36 )A  computer system implements 8 kilobyte pages and a 32-bit physical address space. Each page table entry contains a valid bit, a dirty bit, three permission bits, and the translation. If the maximum size of the page table of a process is 24 megabytes, the length of the virtual address supported by the system is bits. 

 Ans: 36

37. The number of onto functions (surjective functions) from set X = {1, 2, 3, 4} to set
Y = {a, b, c} is

A function f from X to Y is surjective if every element y in Y has a corresponding element x in X such that f(x) = y. 

.In given problem  n = 4 and m = 3.

Count the number of partitions of A into m blocks.

The no of partitions of elements 1, 2,3 and 4 of X into 3 blocks is Stirling value S{4,3}=6

 Each partition the first block can map to any of the m elements of Y, Total number of mappings will be m!=3!=6

Total number of onto functions= S{n,m}*m!=S{4,3}*3!=6*6=36

38. All possible functions are made between set having 2 and 20 distinct elements respectively. Find the probability of selecting an one to one function:

 

39. Four branches of a company are located at M,N,O and P.  M is north of N at a distance of 4 Km, N is 1 km south east to O, and P is 2 km south to O. what is distance between M to P ? 

a. 5.34

b. 6.74

c. 28.5

d. 45.49 

Ans: a

  40. Which of following statements can be used to find the total weight of 10 poles using following statements. 

S1: 1/4th weight of one pole is 5
S2: The total weight of these poles is 160 kg more than the total weight of two poles

 a. S1 alone

b. S2 alone

c. either S1 or S2

d. Neither S1 nor S2

Ans C

S1: Total weight= 5/0.25 *10 =200

S2: Total weight=160/8*10 =200

41.Consider a function f(x) = 1 – |x| on –1 ≤ x ≤1. The value of x at which the function
attains a maximum and the maximum value of the function are:
(a) 0, –1 

(b) –1, 0

(c) 0, 1

(d) –1, 2 

Ans c

42. Let f(x) = x^–(1/3) and A denote the area of the region bounded by f(x) and the X-axis,
when x varies from –1 to 1. Which of the following statements is/are True?

1. f is continuous in [–1, 1]

 2. f is not bounded in [–1, 1]

3. A is nonzero and finite

(a) 2 only

 (b) 3 only
(c) 2 and 3 only 

(d) 1, 2 and 3

 

The graph for given function is plotted as above.

f is not defined for x<0. Hence it is not continuous in [-1,1]

f is not bounded in [-1,1]

A is nonzero and finite

hence c is answer

43. Consider the three languages given:

L1 :  {wxwR| where w R is reversal of w}

L2: {a^m b^n | m≠n where m,n >0}

L3: {a^p  b^q  c^r | where p,q,r >0}

Which of these is/are regular?

a. L1
b. L3
c. L1 & L3
d. L1 , L2 & L3

44. Which one of the following underline word is correct with reference to sentence
a) Industrialist owns a personnel jet.
b) I daily write my personnel diary.
c) All personnel are given day off.
d) Being religious is a personnel aspect.

Ans c: personnel means "people employed in an organization"

  45. Which one of the following word is related to clothes like pair of jeans,shirt,etc

a) fabric
b) textile
c) fiber
d) apparel

a: fabric: cloth produced by weaving

b. textile: a type of cloth

c. Fiber: a thread from which cloth is formed.   

d  Apparel: clothing

46. Consider the sequence of machine instructions given below::

MUL       R5, R0, R1
DIV        R6, R2, R3
ADD      R7, R5, R6
SUB       R8, R7, R4

In the above sequence, R0 to R8 are general purpose registers. In the instructions
shown, the first register stores the result of the operation performed on the second
and the third registers. This sequence of instructions is to be executed in a pipelined
instruction processor with the following 4 stages: 

(1) Instruction Fetch and Decode(IF),

 (2) Operand Fetch (OF), 

(3) Perform Operation (PO) 

(4) Write back theResult (WB). 

The IF, OF and WB stages take 1 clock cycle each for any instruction.The PO stage takes 1 clock cycle for ADD or SUB instruction, 3 clock cycles for MUL instruction and 5 clock cycles for DIV instruction. The pipelined processor uses operand forwarding from the PO stage to the OF stage. The number of clock cycles taken for the execution of the above sequence of instructions is ___________

Cycle no          Operations

========||================

1                  IF1      --         --         --

2                  IF2      OF1     --           --

3,4,5            IF3      OF2     PO1     --

6,7,8,9,10   IF4       OF3    PO2     WB1

11                --          OF4     PO3     WB2

12               --          ---         PO4      WB3

13              --           --            --          WB4

Ans: 13

47. Fill the blanks
we _________ our friend's birthday and we ________ how to make up
a) completely forgot, don't just know
b) forgot completely, don't just know
c) completely forgot, just don't know
d) forgot completely, just don't know

Ans c

48. Calculate distance between S and P
M is 4km north of N
P is 2 km south of O
N is 1km south East of O
a) 5.34
b) 4
c) 28.5
d)6.something

47. If p,q,r,s,t is the arithmetic sequence then which of the following is also an arithmetic sequence
I 2p,2q,2r,2s,2t
II p^2,q^2,r^2,s^2,t^2
III p-3,q-3,r-3,s-3,t-3
a) I & II
b) I & III
c) I only
d) III only

Ans b)

48. In a function integer i,j,k,l
f(i,j,k,l)=max(i,j,k,l)
g(i,j,k,l)=Min(i,j,k,l)
h(i,j,k,l)= remainder of (i*j/k*l) if i*j>k*l or  (k*l/i*j) if k*l>i*j

Also a function fgh(i,j,k,l)=f(i,j,k,l) x g(i,j,k,l) x h(i,j,k,l)
compute the value of fg(h(2,5,3,7),4,6,8)

Ans:

fg(h(2,5,3,7),4,6,8)=fg(1,4,6,8)= f(1,4,6,8) * (g(1,4,6,8) =8x1=8

49.The secant method is used to find the root of an equation f(x) = 0. It is started from
two distinct estimates xa and xb for the root. It is an iterative procedure involving
linear interpolation to a root. The iteration stops if f(xb) is very small and then xb
is the solution. The procedure is given below. Observe that there is an expression
which is missing and is marked by? Which is the suitable expression that is to be
put in place of? So that it follows all steps of the secant method?

Secant
Initialize: xa, xb, ε, N // ε = convergence indicator
fb= f(xb)
i = 0
while (i < N and | fb | > ε) do
i = i + 1 // update counter
xt= ? // missing expression for
// intermediate value
xa= xb// reset xa
xb= xt// reset xb
fb= f(xb) // function value at new xb
end while
if |fb| > εthen // loop is terminated with i = N
write “Non-convergence”
else
write “return xb”
end if

(a) xb– (fb– f(xa)) fb/ (xb– xa)

 (b) xa– (fa– f(xa)) fa/ (xb– xa)
(c) xb– (fb– xa) fb / (xb – fb(xa)

 (d) xa– (xb– xa) fa/ (fb– f (xa))

50.For a given B+ tree of order 1 ,minimum number of nodes to be fetched for a given query
"X greater than or equal to 5 and less than 15"

51. Consider a typical disk that rotates at 15000 rotations per minute (RPM) and has a transfer rate of 50x 10^6 bytes/sec. If the average seek time of the disk is twice the average rotational delay and the controller's transfer time is 10 times the disk transfer time, the average time (in milliseconds) to read or write a 512-byte sector of the disk is  :

Ans : 6.1

52. The minimum number of JK flipflops required to construct a synchronous  counter with the counting sequence (0,0,1,1,2,2,3,3,0,0,......) is:

Ans : 2

53. Out of the following four sentences, select the most suitable sentence with respect to grammar and usage:

a. Since the report lacked needed information, it was of no use to them.

b. The report was useless to them because there were no needed information in it.

c.Since the report did not contain the needed information , it was not real useful to them.

d. Since the report lacked needed information, it would not have been useful to them.

Ans : a

54 

 

 

 

 

 

 

Ans b

55)  . A computer system implements a 40-bit virtual address, page size of 8 kilobytes, and a 128-entry translation look-aside buffer (TLB) organized into 32 sets each having four ways. Assume that the TLB tag does not store any process id. The minimum length of the TLB tag in bits is_________:

 

 Size of a page = 8KB = 2^13
Total number of bits needed to address a page frame = 40 – 13 =  27

If there are ‘n’ cache lines in a set, the cache placement is called n-way set associative. Since T.L.B is 4 way set associative and can hold total 128  page table entries, number of sets in cache = 2^7/4 = 2^5. 

So 5 bits are consumed to address a set.

Hence number of bits needed for tag= 27 -5 =22

56) Consider the following statements. 

I. The complement of every Turing decidable language is Turing decidable 

II.There exists some language which is in NP but is not Turing decidable 

III. If L is a language in NP, L is Turing decidable 

Which of the above statements is/are true? 

(A) Only II

(B) Only I

(C) Only I and II 

(D) Only I and III

  Ans: D

57 With reference to the B+ tree index of order 1 shown below the minimum number of nodes , including root node, that must be fetched in order to satisfy the following query : "Get all records with search key greater than or equal to 7 and less than 15" is______

Ans : 5

58   Consider the following routing table at an IP router: 

Network No.                     Net Mask                      Next Hop 

128.96.170.0                    255255.254.0             Interface 0 

128.96.168 0                    255.255.254.0            Interface 1 

128.96.166.0                    255.255.254.0            R2

128.96.164.0                   255.255.252_0            R3

 0.0.0.0                                   Default                      R4 

For each IP address in Group I identify the correct choice of the next hop from Group II using the entries from the routing table above.
Group I

  A) 128.96.171.92 

  B)128.96.167.151 

C) 128.96.163.151

  D) 128.96.165.121 

Group II

  1) Interface 0

  2) Interface 1 

3)R2

  4) R3

  5) R4

A-1   B-3  C-5   D-4

59.Which of the following well formed formulae is a tautology?

  Ans C 

60.  Given below are some algorithms, and some algorithm design paradigms.
1. Dijkstra's Shortest Path 

2. Floyd-Warshall algorithm to compute pairs shortest path

 3. Binary search on a sorted array 

4. Backtracking search on a graph 

i. Divide and Conquer all

 ii. Dynamic Programming

iii. Greedy design

 iv. Depth-first search

 v. Breadth-first search

Match the above algorithms 

(A) 1-i,2-iii, 3-i, 4-v. 

(B)1-iii, 2-iii, 3-i, 4-v. 

(C) 1-iii,2-ii, 3-i, 4-iv.

 (D)1-iii, 2-ii, 3-i, 4-v. 

Ans: C

61)   A Young tableau is a 2D array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with ∞, and hence there cannot be any entry to the right of, or below a ∞. The following Young tableau consists of unique entries. 

1        2    5     14 

3       4     6      23 

10    12   18   25 

31   ∞    ∞    ∞

When an element is removed from a Young tableau. other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled in with a ∞). The minimum number of entries (other than 1) to be shifted, to remove 1 from the given Young tableau is :

 

After removing 1,

a. Move 2 to position (0,0) 

b. Move 3 to position (0,1)

c. Shift 4, 6 and 23 to one cell left

Minimum 5 numbers have to be shifted.

62)   A half adder is implemented with XOR and AND gates. A full adder is implemented with two half adders and one OR gate. The propagation delay of an XOR gate is twice that of an AND/OR gate. The propagation delay of an AND/OR gate is 1.2 microseconds. A 4-bit ripple-carry binary adder is implemented by using four full adders. The total propagation time of this 4-bit binary adder in microseconds is :

Ans: 12

 

63  )  Suppose you are provided with the following function declaration in the C programming language.
int partition(int a[]), int n);
The function treats the first element of a [ ] as a pivot, and rearranges the array so that all elements less than or equal to the pivot is in the left part of the array, and all elements greater than the pivot is in the right part. In addition, it moves the pivot so that the pivot is the last element of the left part. The return value is the number of elements in the left part. The following partially given function in the C programming language is used to find the kth smallest element in an array a [ ] of size n using the partition function. We assume k <=5 .

 int kth_smallest(int a[], int n, int k)

 {

int left_end = partition(a,n);

 if ( left_end+1 == k)

{

return a[left_end]; 

}
if ( left_end+1 > k )

( return kth_smallest(  ____________ ); 

else ( return kth_smallest(___________   ); 

}

The missing argument lists are respectively
(A) (a, left_end, k) and (a+left_end+1, n-left_end-1, k-left_end-1)

 (B) (a, left_end, k) and (a, n-left_end-1, k-left_end-1) 

(C) (a+left_end+1, n-left_end-1, k-left_end-1) and (a, left_end, k) 

(D) (a, n-left end-1, k-left end-1) and (a, left end, k) 

Ans :A

64) Consider the C program below. 

#include <stdio.h>

int *A, stkTop;
int stkFunc(int opcode, int val) 

{
static int size=0, stkTop=0;

 switch (opcode)

 {

 case -1: size = val; break;

 case 0: if (stkTop < size) A[stkTop++] = val; break;

 default: if (stkTop) return A[--stkTop]; 

}
return -1;
} 

int main()

 {
int B[20]; 

A = B;

stkTop = -1;
stkFunc (-1, 10); 

stkFunc ( 0, 5); 

stkFunc ( 0, 10);

 printf ("%d\n", stkFunc(1, 0) + stkFunc(1, 0));
}
The value printed by the above program is_______

stkFunc (-1, 10)     initialize stack size as 10. 

stkFunc ( 0, 5)and stkFunc ( 0, 10) push 5 and 10 in sequence.

stkFunc(1, 0)and stkFunc(1, 0)pop 10 and 5 in sequnce.

The sum 10+5 = 15 will be printed.

 

65) Consider the intermediate code given below.

(1) i = 1

 (2) j = 1

 (3) t1 = 5 * i 

(4) t2 = t1 + j 

(5) t3 = 4 * t2

 (6) t4 = t3

 (7) a [t4] = -1

 (8) j = j + 1

 (9) if j<=5 goto (3) 

(10) i=i+1

 (11) if 1<5 goto (2) 

The number of nodes and edges in the control-flow-graph constructed for the above code, respectively, are 

(A) 5 and 7 

(B) 6 and 7

(C) 5 and 5

 (D) 7 and 8

 

Ans: B

Do you know any question other than posted here? Feel free to comment  here.  :)

 

Posted in: Career , Computer Science , Computer Science MCQ , CS PSU questions , GATE