One Stop GATE Forum: GATE – Sample Questions

Message


   
No.
                Question
              
              
                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
                      
                    
                Your Answer
                   (Not
                  Answered)
              
              
                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
                      
                    
                Your Answer
                   (Not
                  Answered)
              
              
                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
                      
                    
                Your Answer
                   (Not
                  Answered)
              
              
                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
                      
                    
                Your Answer
                   (Not
                  Answered)
              
              
                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
                      
                    
                Your Answer
                   (Not
                  Answered)
              
              
                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
                      
                    
                Your Answer
                   (Not
                  Answered)
              
              
                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₁ 

                        
                Your Answer
                   (Not
                  Answered)
              
              
                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
                      
                    
                Your Answer
                   (Not
                  Answered)
              
              
                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%

                        
                Your Answer
                   (Not
                  Answered)
              
              
                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

                        
                Your Answer
                   (Not
                  Answered)
              
              
                Correct Answer
                A
              
              
                11
                Consider three decision problems P₁,
                  P₂ and P₃. It is known that P₁
                  is decidable and P₂ is undecidable. Which one of
                  the following is TRUE?
              
              
                Options
                
                  
                        A) P₃ is decidable if P₁
                          is reducible to P₃
                        B) P₃ is undecidable if P₃
                          is reducible to P₂

                        
                        C) P₃ is undecidable if P₂
                          is reducible to P₃

                        
                        D) P₃ is decidable if P₃
                          is reducible to P₂s complement
                      
                    
                Your Answer
                   (Not
                  Answered)
              
              
                Correct Answer
                A
              
              
                12
                
                  Which one of the following are essential features of an
                  object-oriented

                  programming language?
                  (i) Abstraction and encapsulation

                  (ii) Strictly-typedness

                  (iii)  Type-safe property coupled with sub-type rule

                  (iv) Polymorphism in the presence of inheritance

                  
                Options
                
                  
                        A) (i) and (ii) only
                        B) (i) and (iv) only
                      
                      
                        C) (i), (ii) and (iv) only
                        D) (i), (iii) and (iv) only
                      
                    
                Your Answer
                   (Not
                  Answered)
              
              
                Correct Answer
                B
              
              
                13
                Consider the following relation schema
                  pertaining to a students database:

                  Student (rollno, name, address)

                  Enroll (rollno, courseno, coursename)

                  where the primary keys are shown underlined. The number of
                  tuples in the Student and Enroll tables are 120 and 8
                  respectively. What are the maximum and minimum number of
                  tuples that can be present in (Student * Enroll), where
                  ‘*’denotes natural join?
              
              
                Options
                
                  
                        A) 8, 8 
                        B) 120, 8

                        
                        C) 960, 8 
                        D) 960, 120

                        
                Your Answer
                   (Not
                  Answered)
              
              
                Correct Answer
                C
              
              
                14
                
                  Assume
                  the following C variable declaration
                          
                  int *A [10], B [10][10];
                  Of
                  the following expressions
                  
                  
                  I       
                  A[2]               
                  II    
                  A [2] [3]
                  
                  
                  III    
                  B               
                  IV    B[2][3]
                  which
                  will not give compile-time errors if used as left hand sides
                  of assignment statements in a C program ?
                  
                  
                Options
                
                  
                        A) I, II, and IV only              
                        B) II, III, and IV only
                          
                        
                        C) II and IV only  
                        D) IV only
                          
                           
                Your Answer
                   (Not
                  Answered)
              
              
                Correct Answer
                D
              
              
                15
                How many distinct binary search trees can
                  be created out of 4 distinct keys?
              
              
                Options
                
                  
                        A) 5
                        B) 14
                      
                      
                        C) 24
                        D) 42
                      
                    
                Your Answer
                   (Not
                  Answered)
              
              
                Correct Answer
                B
              
              
                16
                Given the following input (4322, 1334,
                  1471, 9679, 1989, 6171, 6173, 4199) and the hash function x
                  mod 10, which of the following statements are true ?

                  (i) 9679, 1989, 4199 hash to the same value

                  (ii) 1471, 6171 hash to the same value

                  (iii) All elements hash to the same value

                  (iv) Each element hashes to a different value
              
              
                Options
                
                  
                        A) (i) only
                        B) (ii) only

                        
                        C) (i) and (ii) only 
                        D)  (iii) or (iv)
                      
                    
                Your Answer
                   (Not
                  Answered)
              
              
                Correct Answer
                C
              
              
                17
                Packets of the same session may be routed
                  through different paths in
              
              
                Options
                
                  
                        A) TCP, but not UDP
                        B) TCP and UDP

                        
                        C) UDP, but not TCP
                        D) Neither TCP, nor UDP

                        
                Your Answer
                   (Not
                  Answered)
              
              
                Correct Answer
                B
              
              
                18
                The following numbers are inserted into
                  an empty binary search tree in the given order: 10, 1, 3, 5,
                  15, 12, 16. What is the height of the binary search tree (the
                  height is the maximum distance of a leaf node from the root)?
              
              
                Options
                
                  
                        A) 2
                        B) 3
                      
                      
                        C) 4
                        D) 6
                      
                    
                Your Answer
                   (Not
                  Answered)
              
              
                Correct Answer
                B
              
              
                19
                Postorder traversal of a given binary
                  search tree, T produces the following sequence of keys

                  10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29

                  Which one of the following sequences of keys can be the result
                  of an inorder traversal of the tree T?
              
              
                Options
                
                  
                        A) 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60,
                          95
                        B) 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27,
                          29
                      
                      
                        C) 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50,
                          95

                        
                        D) 95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15,
                          29
                      
                    
                Your Answer
                   (Not
                  Answered)
              
              
                Correct Answer
                A
              
              
                20
                Let f: B ®
                  C and g: A ® B be two
                  functions and let h = f o g. Given that h is an onto function.
                  Which one of the following is TRUE?
              
              
                Options
                
                  
                        A) f and g
                          should both be onto functions.
                        B) f should be onto
                          but g need not be onto
                      
                      
                        C) g should be onto
                          but f need not be onto 
                        D) both f and g
                          need not be onto
                      
                    
                Your Answer
                   (Not
                  Answered)
              
              
                Correct Answer
                B


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