GATE

Q. Two numbers are chosen independently and uniformly at random from the set {1, 2 , . . . , 13}. The probability (rounded off to 3 decimal places) that their 4-bit (unsigned) binary representations have the same most significant bit is Solution: The 4-bit binary representation of numbers (1, 2, 3, 4………13): 0  – […]

Q. The value of 351 mod 5 is     . Solution: = 351 mod 5 = (33)17 mod 5 = (27)17 mod 5= {(22)8*21} mod 5= {(4)8*(2)} mod 5= {(-1)8*(2)} mod 5= {(1*2)} mod 5= {(2)} mod 5= 2

Q. An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is   Solution: Given an array of 25

Q. Consider the grammar given below: S → Aa A → BD B → b | ϵ D → d | ϵ Let a, b, d, and $ be indexed as follows: a b d $ 3 2 1 0 Compute the FOLLOW set of the non-terminal B and write the index values for the

Q. Which of the following protocol pairs can be used to send and retrieve e-mails (in that order)? (A) IMAP, POP3 (B) SMTP, POP3 (C) SMTP, MIME (D) IMAP, SMTP Ans: SMTP, POP3 Solution: SMTP is push protocol and send e-mail andPOP3 is pull protocol i.e. to retrieve e-mail.

Q. Which one of the following statements is NOT correct about the B+ tree data structure used for creating an index of a relational database table? (A) B+ Tree is a height-balanced tree (B) Non-leaf nodes have pointers to data records (C) Key values in each node are kept in sorted order (D) Each leaf

Q. Let 𝐺 be an undirected complete graph on 𝑛 vertices, where 𝑛 > 2. Then, the number of different Hamiltonian cycles in 𝐺 is equal to Ans: Option D Solution: A simple circuit in a graph G that passes through every vertex exactly once is called a Hamiltonian circuit. In Hamiltonian cycle is a

Q. Consider the following two statements about database transaction schedules: Which of the above statements is/are TRUE? (A) I only (B) II only (C) Both I and II (D) Neither I nor II Ans: Both I and II Solution: Strict 2PL allows only schedules whose precedence graph is acyclic i.e. schedule is Conflict Serial. In

Q. Let 𝐺 be an arbitrary group. Consider the following relations on 𝐺: 𝑅1: ∀𝑎, 𝑏 ∈ 𝐺, 𝑎 𝑅1𝑏 if and only if ∃𝑔 ∈ 𝐺 such that 𝑎 = 𝑔−1𝑏𝑔 𝑅2: ∀𝑎, 𝑏 ∈ 𝐺, 𝑎 𝑅2𝑏 if and only if 𝑎 = 𝑏−1 Which of the above is/are equivalence relation/relations? (A) 𝑅1