Model Gate Paper Computer science and IT

1. A uni-processor computer system only has two processes, both of which alternate 10 ms CPU bursts with 90 ms I/O bursts. Both the processes were created at nearly the same time. The I/O of both processes can proceed in parallel. Which of the following scheduling strategies will result in the least CPU utilization (over a long period of time) for this system? 
A) First come first served scheduling 
B) Shortest remaining time first scheduling 
C) Static priority scheduling with different priorities for the two processes 
D) Round robin scheduling with a time quantum of 5 ms

2. 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?
a) (ii), (iii) and (iv) only
b) (ii) and (iii) only
c) (i) and (iii) only
d) (i) and (ii) only

3. In a system with 32 bit virtual addresses and 1 KB page size, use of one-level page tables for virtual to physical address translation is not practical because of
a) the large amount of internal fragmentation
b) the large amount of external fragmentation
c) the large memory overhead in maintaining page tables
d) the large computation overhead in the translation process 

4. Let the page fault service time be 10ms in a computer with average memory access time being 20ns. If one page fault is generated for every 10^6 memory accesses, what is the effective access time for the memory?
A) 21ns                  B) 30ns

C) 23ns                  D) 35ns

5. A system uses FIFO policy for page replacement. It has 4 page frames with no pages loaded to begin with. The system first accesses 100 distinct pages in some order and then accesses the same 100 pages but now in the reverse order. How many page faults will occur?

A) 196                                  B) 192                   

C) 197                                    D) 195

6.  A process executes the following code 
  for (i = 0; i < n; i++) fork();

The total number of child processes created is 
A) n                                        B) 2^n-1                  

C) 2ⁿ                                       D) 2^n-1– 1

7. How many zeros are there at the end of the number obtained from 999!

 A) 246                                   B) 247  

C) 248                                    D) 249

8. A certain amount of sum is invested at simple interest. If the sum becomes k times itself in 16 years and 2k times itself in 40 years, in how many years will it become 4k times of itself?

A) 96 years                           B) 88 years       

C) 80 years                           D)64 years

9. A, B and C start running at the same time and from the same point around a circular track of 70m radius. A and B run clockwise and C counter clockwise. If A meets C every 88 seconds and B meets C every 110 seconds, then after how much seconds does A meets B?

A) 22                                      B) 198  

C) 440                                   D) 220

10. Given a number with 1998 digits which is divisible by 9. Let x be the sum of its digits and y be the sum of digits of x and z be the sum of digits of y. Find z

 A) 9                                       B) 27                     

C) 1998                                  D) None of these

11. A tank has 100 liters of water. At the end of every hour the following two operations are performed in sequence: 1) water equal to a% of the current contents of the tank is added to the tank, 2) water equal to b% of the current contents of the tank is removed from the tank. At the end of 5 hours the tank contains exactly 100 litres of water. The relation between a and b is:

A) A=B                   B) A>B 

C) A                   D) none of these

12. A speaks truth 70% of the time; B speaks truth 80% of the time. What is the probability that both are contradicting each other?

A) 0.37                   B) 0.38                

C) 0.44                   D) 0.56

13.Determine cause and effect of the given statements:

(A) All the airlines companies in India have increased the airfares in all routes with immediate effect.

(B) There has been substantial reduction in aviation fuel prices in India during the past few weeks.

A) If statement (A) is the cause and statement (B) is its effect

B) If statement (B) is the cause and statement (A) is its effect

C) If both the statements (A) and (B) are independent causes

D) If both the statements (A) and (B) are effects of independent causes                               

14. Out of following codes, which code is unit distance as well as reflective:

A) Gray                                 B) Excess 3

C) Binary                               D) Hamming

15. A range of integers that can be represented by an n-bit 2’s complement number system is:

A) -2^n-1 to (2^n-1-1)              B) – (2^n-1 -1) to (2^n-1-1)

C) – (2^n-1+1) to (2^n-1-1)       D) – (2^n-1 +1) to 2^n-1

16. In the program below, the number of times the FIRST and SECOND JNZ instructions cause the control to be transferred to LOOP respectively:

                            MVI        H, 02H

                            MVI        L, 05H

LOOP                  DCR        L

FIRST                   JNZ         LOOP

                            DCR         H

SECOND             JNZ         LOOP

A) 5 and 2                             B) 200 and 1        

C) 4 and 1                              D) 6 and 3

17. In a fully associative cache memory consisting of 256 cache lines of 16 bytes each, a tag field is of 14 bits. Then the size of cache memory and main memory is:

A) 2 KB and 1 MB                B) 8KB and 128KB

C) 4KB and 256KB              D) 16KB and 8MB

18. Daisy chained and independent request bus arbitration requires _________ respectively.  (here N stands for number of devices in the configuration.)

A) 3N and 7N signal lines        B) 3 and 2^N signal lines

C) 2N and 2N signal lines         D) 3 and 2N signal lines

19. The 2’s complement representation (-539)₁₀ in hexadecimal is:

A) DE5                                  B) DBC

C) 9E7                                    D) ABE

20. The minterm expansion of f(P,Q,R) = PQ+QR’+PR’ is

A) m₂+m₄+m₆+m₁                        B) m₀+m₁+m₃+m₅

C) m₂+m₃+m₄+m₅                        D) m₀+m₁+m₆+m₁

21. The number of flip-flops required in a decade counter is:

A) 3                                        B) 4                       

C) 5                                         D) 10

22. How many full adders are required to construct m-bit parallel adder?

A) m/2                                   B) m-1 

C) m                                       D) m+1

23. In a simple connected undirected graph with n nodes (n>=2) the max number of nodes with distinct degrees is

A) n-1                                    B) n-2    

C) n-3                                     D) 2

24. Let A be a 2 x 2 matrix. Suppose  and  are Eigen vectors corresponding to the Eigen values 1 and 2 of A respectively. Then A is

A)                           B)              

C)                               D)

25. The system of simultaneous equations

x + 2y + z = 6

2x + y + 2z = 6

x + y + z = 5

has

A) unique solution              B) infinite number of solutions

C) no solutions                   D) exactly two solutions

26. What is the determinant of the matrix?

A) -76                                     B) -28                   

C) +28                                    D) +72

27. If A and B are square matrices of size n x n, then which of the following statement is not true?

A) det(AB)=detA)detB)               B) det(kA)=KⁿdetA)

C) det(A+B)=detA)+detB)        D) det(A^T)=1/det(A^-1)

28. Choose the correct spelled word

A) Etiquete                           B) Ettiquete         

C) Etiquette                        D) Ettiquette

29. Choose the word which best expresses the meaning of the underlined word in the sentence.

“Forgetting their old enmity, they joined hands with a spirit of camaraderie.”

A) animosity                        B) love  

C) friendliness                   D) trust

30. Choose the word which is opposite in meaning of the underlined word in sentence.

“Her impetuous behavior was attributed to her upbringing.”

A) swift                                 B) rash  

C) quiet and gentle          D) sluggish

31. The question below consists of a pair of related words followed by four pairs of words. Select the pair that best expresses the relation in the original pair.

QUISLING: BETRAY

A) taunt : provoke               B) inception : termination

C) juggernaut : crush      D) obstinate : preserve

32. Choose the appropriate answer to complete the following sentence:

“To those of us who had always thought him timid, his__________ came as a surprise.”

A) inability                           B) inevitability

C) intrepidity                     D) inertness

33. Which of the following is correct?

A) 2ⁿ < n² < n³ < 3ⁿ                                              

B) nlogn < nlog²n < n² < 2ⁿ

C) n³logn < n³ < 3ⁿ < 2²ⁿ                

D) n < n² < nlogn < n²logn

34. If there is a polynomial time algorithm for an NP- complete problem, then that would not imply which of t he following:

A) P = NP                               B) NP = Co- NP

C) P = NP ∩ Co-NP               D) P != NP

35. Consider a sequence A of length n which is sorted except for one item that appears out of order. Which of the following can sort the sequence in O(n) time?

A) Heapsort                          B) Quick sort      

C) Merge sort                       D) Insertion sort

36. If T(n)= 3T(n/2)+n, if n>1. T(1)=1. Then T(n)=?

A) Θ(n)                                                 

B) Θ(n (log₂3) ) { n to the power log₂3}

C) Θ(n ^3/2)                                                            

D) Θ(n (log₂³) log₂ⁿ)

37. Fractional knapsack problem can be solved using…

A) Dynamic programming                B) Divide and conquer

C) Greedy approach                         D) Backtracking

38. Assume that each character code consists of 8 bits. The number of characters that can be transmitted per second through a synchronous serial line at 2400 baud rate, and with two stop bits is

A) 109                                    B) 216                   

C) 218                                   D) 219

39. What is the meaning of bandwidth in a network?

A) Transmission capacity of a communication channel

B) Connected computers in a network

C) Class of IP used in network

D) Interconnected by communication channels

40. The subnet mask 255.255.255.192

A) extends the network portion to 16 bits

B) extends the network portion to 26 bits

C) extends the network portion to 36bits

D) has no effect on the network portion of an IP address

41. Choose the best matching between Group 1 and Group 2.

   Group-1                                                             Group-2  

 P. Data link                                     1. Ensures reliable transport of data over a physical point-to-point link

 Q. Network layer      2. Encoder/decodes data for physical                           transmission

 R. Transport layer   3. Allows end-to-end communication        between two processes

                                         4. Routes data from one network node to       the next

A) P-1, Q-4, R-3                                  B) P-2, Q-4, R-1

C) P-2, Q-3, R-1                                    D) P-1, Q-3, R-2

42. A serial transmission Ti uses 8 information bits, 2 start bits, 1 stop bit and 1 parity bit for each character. A synchronous transmission T2 uses 3 eight bit sync characters followed by 30 eight bit information characters. If the bit rate is 1200 bits/second in both cases, what are the transfer rates of Ti and T2?

A) 100 characters/sec, 153 characters/sec  

B) 80 characters/sec, 136 characters/sec

C) 100 characters/sec, 136 characters/sec          

D) 80 characters/sec, 153 characters/sec

43. Anarkali digitally signs a message and sends it to Salim. Verification of the signature by Salim requires

A) Anarkali’s public key                B) Salim’s public key

C) Salim’s private key        D) Anarkali’s private key

44. The number of tokens in the following C statement is

printf("i = %d, &i = %x", i, &i);

A) 9                        B) 10

C) 11                      D) 20

45. Which of the following production rule suffers from left-recursion problem

A)  A->Ba                               B)  S->Ba

C) S->Sa                                 D) B->Aa

46. The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?

A) Finite state automata

B) Deterministic pushdown automata

C) Non-Deterministic pushdown automata

D) Turing Machine

47. Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?

A)      Removing left recursion alone

B)      Factoring the grammar alone

C)      Removing left recursion and factoring the grammar

D)     None of the above

48. Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. The relationship between nl and n2 is

A)      n1 is necessarily less than n2

B)     n1 is necessarily equal to n2

C)      n1 is necessarily greater than n2

D)     none of the above

49.  Language L= {aⁿ bⁿcⁿ} is a

A)      Regular Language

B)      Context-free Language

C)      Recursive Language

D)     none of the above

50.  Minimum number of state in DFA which accept all the strings in which 2^nd symbol from the right end is a over alphabet S= {a, b}

A) 3                        B) 4

C) 5                         D) 2

51. Which of the following statement is correct regarding PDA

A)      DPDA is more power full than NDPDA

B)      DPDA and NDPDA having same power

C)      NDPDA is more power full than DPDA

D)     none of these

52.  Pumping-lemma is used for

A)      Checking the regularity of the Grammar

B)      Checking the non-regularity of the Grammar

C)      both a and b

D)     none

53.  Production rule  ABcdEàab belongs to

A)      Regular grammar

B)      Context free grammar

C)      recursive grammar

D)     recursive enumerable grammar

54. Relation R has eight attributes ABCDEFGH. Fields of R contain only atomic values. F = {CH -> G, A -> BC, B -> CFH, E -> A, F -> EG} is a set of functional dependencies (FDs) so that F+ is exactly the set of FDs that hold for R. How many candidate keys does the relation R have?

A) 3                        B) 4

C) 5                         D) 6

55. Which of the following is TRUE?

A)      Every relation in 3NF is also in BCNF

B)      A relation R is in 3NF if every non-prime attribute of R is fully functionally dependent on every key of R

C)      Every relation in BCNF is also in 3NF

D)     No relation can be in both BCNF and 3NF

56. Given the following two statements:

  S1: Every table with two single-valued

      attributes is in 1NF, 2NF, 3NF and BCNF.

  S2: AB->C, D->E, E->C is a minimal cover for

      the set of functional dependencies

      AB->C, D->E, AB->E, E->C.

Which one of the following is CORRECT?

A)     S1 is TRUE and S2 is FALSE.

B)      Both S1 and S2 are TRUE.

C)      S1 is FALSE and S2 is TRUE.

D)     Both S1 and S2 are FALSE.

57. Consider the relation X (P, Q, R, S, T, U) with the following set of functional dependencies

F = {   {P, R} → {S, T},  {P, S, U} → {Q, R}}

Which of the following is the trivial functional dependency in F+ is closure of F?

A) {P, R}→{S,T}                    B) {P, R}→{R,T}

C) {P, S}→{S}                       D) {P, S,U}→{Q}

58. Given Schedule  S: R2(A); R1(B); W2(A); R3(A); W2(B); W3(A); R2(B); W2(B) is

A)      Conflict Serializable but not View serializable

B)      only View Serializable

C)      only Conflict serializable

D)     both Conflict and View Serializable

59. Heap is a

A) Complete binary tree                B) full binary tree

C) binary search tree                          D) none

60. Worst case time Complexity of Quick-sort and Randomized Quick-Sort algorithm for n i\p is

A) O(n²), O(n²)                     B) O(n logn), (nlogn)

C) O(n logn), O(n²)             D) O(n²), O(n logn)

61. Equivalent Post-fix expression corresponding to Infix expression

A + B * (C + D)/ F + D * E

A) AB+CD*F/+D*E             B) ABCD+*F/+DE*+

C) ABCD+*/F+DE*              D) AB+CD*F/+DE*

62. In-order traversal of BST produces

A)     sorted list in ascending order

B)      sorted list in descending order

C)      Some-times a and some-times b

D)     None

63. Time complexity to add a new node in the middle of the singly-linked list if we have the address of the Starting Node only is

A) O(n)                                 B) O(logn)

C) O(n^1/2)                              D) O(n²)

64.  Consider the following C-program 

 #include 

    int main() {

        short i;

        for (i = 1; i >= 0; i++)

            printf("%d\n", i);

    }

A)The control won’t fall into the for loop
B) Numbers will be displayed until the signed limit of short and throw a runtime error
C) Numbers will be displayed until the signed limit of short and program will successfully terminate
D) This program will get into an infinite loop and keep printing numbers with no errors

65. What is the output of this C code?

    #include

    void main(){

        int k = 0;

        for (k)

            printf("Hello");

    }

A) Compile time error                    B) hello

C) Nothing                                            D) Varies