Home / GATE 2017-2018 / GATE CSE :: Practice Test Paper 2

GATE 2017-2018 :: GATE CSE

  1. Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?
  2. A.
    1/8
    B.
    1
    C.
    7
    D.
    8

    View Answer

    Workspace

    Discuss Discuss in Forum


  3. Which of the following statements is/are TRUE for undirected graphs? 
    P: Number of odd degree vertices is even. 
    Q: Sum of degrees of all vertices is even.
  4. A.
    P only
    B.
    Q only
    C.
    Both P and Q
    D.
    Neither P nor Q

    View Answer

    Workspace

    Discuss Discuss in Forum


  5. The line graph L(G) of a simple graph G is defined as follows: 
    · There is exactly one vertex v(e) in L(G) for each edge e in G.
    · For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e' are incident with the same vertex in G.
    Which of the following statements is/are TRUE?
    (P) The line graph of a cycle is a cycle.
    (Q) The line graph of a clique is a clique.
    (R) The line graph of a planar graph is planar.
    (S) The line graph of a tree is a tree.
  6. A.
    P only
    B.
    P and R only
    C.
    R only
    D.
    P, Q and S only

    View Answer

    Workspace

    Discuss Discuss in Forum


  7. What is the logical translation of the following statement? 
    "None of my friends are perfect.
  8. A.
    ÆŽx(F(x) á´§ ¬ P(x))
    B.
    ÆŽx(¬ F(x) á´§ P(x))
    C.
    ÆŽx(¬ F(x) á´§ ¬ P(x))
    D.
    ¬ ÆŽx(F(x) á´§ P(x))

    View Answer

    Workspace

    Discuss Discuss in Forum


  9. Consider the following sequence of micro-operations.
    MBR ← PC
    MAR ← X
    PC ← Y
    Memory ← MBR
    Which one of the following is a possible operation performed by this sequence?
  10. A.
    Instruction fetch
    B.
    Operand fetch
    C.
    Conditional branch
    D.
    Initiation of interrupt service

    View Answer

    Workspace

    Discuss Discuss in Forum


  11. Consider a hard disk with 16 recording surfaces (0-15) having 16384 cylinders (0-16383) and each cylinder contains 64 sectors (0-63). Data storage capacity in each sector is 512 bytes. Data are organized cylinder-wise and the addressing format is . A file of size 42797 KB is stored in the disk and the starting disk location of the file is <1200, 9, 40>. What is the cylinder number of the last sector of the file, if it is stored in a contiguous manner?
  12. A.
    1281
    B.
    1282
    C.
    1283
    D.
    1284

    View Answer

    Workspace

    Discuss Discuss in Forum


  13. The number of elements that can be sorted in Θ(log n) time using heap sort is
  14. A.
    Θ(1)
    B.
    Θ(√log n)
    C.
    Θ(log n/log log n)
    D.
    Θ(log n)

    View Answer

    Workspace

    Discuss Discuss in Forum


  15. Consider the following function:

    The return value of the function is
  16. A.
    Θ(n2)
    B.
    Θ(n2log n)
    C.
    Θ(n3)
    D.
    Θ(n3log n)

    View Answer

    Workspace

    Discuss Discuss in Forum


  17. Consider the following languages. 
    L1 = {0p 1q 0r | p, q, r ≥ 0} 
    L2 = {0p 1q 0r | p, q, r ≥ 0, p ≠ r} 
    Which one of the following statements is FALSE?
  18. A.
    L2 is context-free.
    B.
    L1 ∩ L2 is context-free.
    C.
    Complement of L2 is recursive.
    D.
    Complement of L1 is context-free but not regular.

    View Answer

    Workspace

    Discuss Discuss in Forum


  19. Consider the DFA A given below.

    Which of the following are FALSE?
    1. Complement of L(A) is context-free.
    2. L(A) = L((11*0+0)(0 + 1)*0*1*)
    3. For the language accepted by A, A is the minimal DFA.
    4. A accepts all strings over {0, 1} of length at least 2.
  20. A.
    1 and 3 only
    B.
    2 and 4 only
    C.
    2 and 3 only
    D.
    3 and 4 only

    View Answer

    Workspace

    Discuss Discuss in Forum