One Stop GATE Forum: CSE GATE sample papers

Message


   

1
                 What does the following algorithm
                  approximate? (Assume m > 1, Î
                  > 0).

                  x = m;

                  y-i;

                  while (x - y > Î)

                  {     x =   (x + y) / 2 ;

                         y = m/x ;

                  }

                  print (x) ;
              
              
                Options
                
                  
                      
                    
                        A) log m 
                        B)
                          m²
                           
                        
                      
                      
                        C) m^1/2
                        D) m^1/3
                      
                    
                  
                
              
              
                

                

              
              
                Correct Answer
                C
              
              
                

              
              
                2
                The problems 3-SAT and 2-SAT are
              
              
                Options
                
                  
                      
                    
                        A) both in P

                        
                        B) both NP-complete

                        
                      
                      
                        C)  NP-complete and in P respectively
                        D) undecidable and NP-complete respectively
                      
                    
                  
                
              
              
                

                

              
              
                Correct Answer
                C
              
              
                

              
              
                3
                Consider a relation scheme R = (A, B, C,
                  D, E, H) on which the following functional dependencies hold :
                  (A ® B, BC ®
                  D, E ® C, D ®
                  A). What are the candidate keys of R?
              
              
                Options
                
                  
                      
                    
                        A) AE, BE
                        B) AE, BE, DE
                      
                      
                        C) AEH, BEH, BCH
                        D) AEH, BEH, DEH
                      
                    
                  
                
              
              
                

                

              
              
                Correct Answer
                D
              
              
                

              
              
                4
                A circuit outputs a digit in the form of
                  4 bits. 0 is represented by 0000,1 by 0001,..., 9 by 1001. A
                  combinational circuit is to be designed which takes these 4
                  bits as input and outputs 1 if the digit ³ 5, and 0
                  otherwise. If only AND, OR and NOT gates may be used, what is
                  the minimum number of gates required?
              
              
                Options
                
                  
                      
                    
                        A) 2
                        B) 3
                      
                      
                        C) 4
                        D) 5
                      
                    
                  
                
              
              
                

                

              
              
                Correct Answer
                C
              
              
                

              
              
                5
                If 73_x(in base-x number
                  system) is equal to 54_y(in base-y number system),
                  the possible values of x and y are
              
              
                Options
                
                  
                      
                    
                        A) 8, 16 
                        B) 10, 12

                        
                      
                      
                        C) 9, 13 
                        D) 8, 11
                      
                    
                  
                
              
              
                

                

              
              
                Correct Answer
                D
              
              
                

              
              
                6
                In a packet switching network, packets
                  are routed from source to destination along a single path
                  having two intermediate nodes. If the message size is 24 bytes
                  and each packet contains a header of 3 bytes, then the optimum
                  packet size is
              
              
                Options
                
                  
                      
                    
                        A) 4
                        B) 6
                      
                      
                        C) 7
                        D) 9
                      
                    
                  
                
              
              
                

                

              
              
                Correct Answer
                D
              
              
                

              
              
                7
                Consider the following program fragment
                  for reversing the digits in a given integer to obtain a new
                  integer. Let n = d₁d₂... d_m.

                  int n, rev;

                  rev = 0;

                  while (n > 0) {

                  rev = rev * 10 + n % 10 ;

                  n = n/10;

                  }

                  The loop invariant condition at the end of the ith iteration
                  is:
              
              
                Options
                
                  
                      
                    
                        A) n = d₁d₂... d_m-i  
                          and rev = d_md_m-1….d_m-i+1
                        B) n = d_m-i+1...d_m-1d_m 
                          (or)  rev = d_m-i...d₂d₁
                      
                      
                        C) n ¹  rev
                        D) n = d₁d₂...d_m  
                          (or)   rev = d_m...d₂d₁ 

                        
                      
                    
                  
                
              
              
                

                

              
              
                Correct Answer
                A
              
              
                

              
              
                8
                
                  Consider the following program segment for a hypothetical
                  CPU having three user registers Rl, R2 and R3.
                   
                  

                      
                    
                        Instruction
                        Operation
                        Instruction Size (in words)
                      
                      
                        MOV Rl,5000
                        ; Rl ¬
                          Memory[5000]
                        2
                      
                      
                        MOV R2,(R1)
                        ; R2 ¬ Memory[(Rl)]
                        1
                      
                      
                        ADD  R2,R3
                        ; R2 ¬ R2
                          + R3
                        1
                      
                      
                        MOV 6000, R2
                        ; Memory[6000] ¬ R2
                        2
                      
                      
                        HALT
                        ; Machine halts
                        1
                      
                    
                  
                  
Let the clock cycles required for various operations be as
                  follows:

                  Register to/from memory transfer :       
                  3 clock cycles

                  ADD with both operands in register :    1 clock
                  cycle

                  Instruction fetch and decode :              
                  2 clock cycles per word

                  The total number of clock cycles required to execute the
                  program is

                  
                
              
              
                Options
                
                  
                      
                    
                        A) 29
                        B) 24
                      
                      
                        C) 23
                        D) 20
                      
                    
                  
                
              
              
                

                

              
              
                Correct Answer
                B
              
              
                

              
              
                9
                Consider an operating system capable of
                  loading and executing a single

                  sequential user process at a time. The disk head scheduling
                  algorithm used is First Come First Served (FCFS). If FCFS is
                  replaced by Shortest Seek Time First (SSTF), claimed by the
                  vendor to give 50% better benchmark results, what is the
                  expected improvement in the I/O performance of user programs ?
              
              
                Options
                
                  
                      
                    
                        A) 50% 
                        B)  40%

                        
                      
                      
                        C)  25%
                        D) 0%

                        
                      
                    
                  
                
              
              
                

                

              
              
                Correct Answer
                D
              
              
                

              
              
                10
                Consider the following statements with
                  respect to user-level threads and

                  kernel-supported threads

                  (i) Context switch is faster with kernel-supported threads

                  (ii) For user-level threads, a system call can block the
                  entire process

                  (iii) Kernel-supported threads can be scheduled independently

                  (iv) User-level threads are transparent to the kernel

                  Which of the above statements are true?
              
              
                Options
                
                  
                      
                    
                        A) (ii), (iii) and (iv) only 
                        B)  (ii) and (iii) only

                        
                      
                      
                        C)  (i), and (iii) only 
                        D) (i) and (ii) only

                        
                      
                    
                  
                
              
              
                

                

              
              
                Correct Answer
                A


One Stop GATE Forum : GATE Previous Years Test Papers - Discuss Here : CS Papers