GATE Technical: Computer Science and Information Technology (CS, Set-1) questions with solutions

Q1. The decimal number 42 is represented in base 3 as 1120. What is the hexadecimal representation of 42?

1. 2A
2. 28
3. 24
4. 528

Answer: 2A

The hexadecimal representation of a decimal number is obtained by converting the decimal value directly to base 16. For the decimal number 42, the conversion results in 2A, where '2' represents 2 times 16 and 'A' represents 10, summing to 32 + 10 = 42.

Q2. Suppose a database system crashes again while recovering from a previous crash. Assume checkpointing is not done by the database either during the transactions or during recovery.

1. The system cannot recover from the crash.
2. The system can recover only if the log is archived.
3. The system can recover using the log, but recovery may repeat some actions.
4. The system can recover only if all transactions were committed before the first crash.

Answer: The system can recover using the log, but recovery may repeat some actions.

The log maintains a record of all transactions and their states, allowing the system to replay actions to restore the database to a consistent state. However, since there is no checkpointing, some actions may be repeated during recovery, leading to potential inconsistencies.

Q3. Consider the following representation of a number in IEEE 754 single-precision floating point format with a bias of 127. S: 1 E: 10000001 F: 11100000000000000000000 Here S, E and F denote the sign, exponent and fraction components of the floating point representation. The above representation (rounded to 2 decimal places) is

1. -7.00
2. -7.50
3. -15.00
4. -15.50

Answer: -7.50

E=10000001=129 so exponent=129-127=2, and mantissa 1.111b = 1.875; with sign bit 1 the value is -1.875 x 2^2 = -7.50. The stored -15.50 is wrong.

Q4. The following relation records the age of 500 employees of a company, where empNo (indicating the employee number) is the key: empAge(empNo, age) Consider the following relational algebra expression: π_empNo, age (σ_age > age1 (ρ_empNo1, age1 (empAge))) What does it generate?

1. employees whose age is the maximum.
2. employees whose age is more than the age of some other employee.
3. employees whose age is not the minimum.
4. employees whose age is the minimum.

Answer: employees whose age is more than the age of some other employee.

The expression filters the employees based on their age being greater than a specified age (age1), which represents the age of at least one other employee, thus selecting those who are older than some employee in the dataset.

Q5. Let G be a group of order 6, and H be a subgroup of G such that 1 < |H| < 6. Which one of the following options is correct?

1. Both G and H are always cyclic.
2. There exist groups G and H such that G is cyclic and H is not cyclic.
3. There exist groups G and H such that G is not cyclic and H is cyclic.
4. Both S1 and S2 are false.

Answer: There exist groups G and H such that G is not cyclic and H is cyclic.

A group of order 6 can either be cyclic or isomorphic to the symmetric group S3, which is not cyclic. If G is isomorphic to S3, it has a subgroup of order 3 that is cyclic, demonstrating that H can be cyclic while G is not.

Q6. For a Turing machine M, ⟨M⟩ denotes an encoding of M. Consider the following two languages. L1 = {⟨M⟩ | M takes more than 2021 steps on all inputs} L2 = {⟨M⟩ | M takes more than 2021 steps on some input}

1. L1 is decidable and L2 is undecidable
2. L1 is undecidable and L2 is decidable
3. Both L1 and L2 are decidable
4. Both L1 and L2 are undecidable

Answer: Both L1 and L2 are undecidable

Both languages L1 and L2 are undecidable because they involve determining the behavior of Turing machines over all inputs or some inputs, which relates to the Halting Problem. Specifically, there is no algorithm that can universally decide whether a Turing machine will exceed a certain number of steps for all or any input.