I85PREP
⌘ K
ISRO Scientist/Engineer SC (Computer Science) study materials
ISRO Scientist/Engineer SC (Computer Science) study resources

ISRO Scientist/Engineer SC (Computer Science) practice questions

One question at a time. Build your ISRO Scientist/Engineer SC (Computer Science) understanding.

First 50 of 200 questions. Each one lists the choices, the correct answer, and an explanation. The checker at the top of this page saves progress in this browser when it is available.

Continue in the practice tool above to load more questions, 50 at a time.

Question 1Engineering Mathematics and Discrete Mathematics

Which of the following propositional formulas is a tautology?

  1. (p ↔ q) → p
  2. (p ∧ q) → p Correct answer.
  3. (p ∨ q) → p
  4. (p → q) → p

Explanation

A tautology is true under every truth assignment. In (p ∧ q) → p, the antecedent can be true only when both p and q are true, so the consequent p is then true and the implication is always true. For example, with p false and q true, (p ∨ q) → p is false; with p false and q false, the other two implications are false.

Question 2Engineering Mathematics and Discrete Mathematics

Let A and B be finite sets with |A| = 5, |B| = 7, and |A ∩ B| = 3. What is |A ∪ B|?

  1. 12
  2. 8
  3. 15
  4. 9 Correct answer.

Explanation

By the inclusion-exclusion principle for two sets, |A ∪ B| = |A| + |B| - |A ∩ B|. Substituting the given cardinalities gives 5 + 7 - 3 = 9. The intersection is counted twice in |A| + |B|, so it must be subtracted once.

Question 3Engineering Mathematics and Discrete Mathematics

The complete graph K_8 has how many edges?

  1. 28 Correct answer.
  2. 64
  3. 16
  4. 56

Explanation

In a complete graph on n vertices, every pair of distinct vertices is joined by exactly one edge. The number of unordered pairs is C(n,2) = n(n-1)/2. For n = 8 this gives 8·7/2 = 28 edges.

Question 4Engineering Mathematics and Discrete Mathematics

In the cyclic group Z_12 under addition modulo 12, how many elements generate the whole group?

  1. 4 Correct answer.
  2. 2
  3. 12
  4. 6

Explanation

An element a generates Z_n exactly when gcd(a,n) = 1, and the number of such elements is Euler's totient φ(n). For n = 12, φ(12) = 12(1 - 1/2)(1 - 1/3) = 4. The generators are 1, 5, 7, and 11.

Question 5Engineering Mathematics and Discrete Mathematics

How many onto functions are there from a 5-element set to a 3-element set?

  1. 120
  2. 180
  3. 243
  4. 150 Correct answer.

Explanation

The number of surjections from an m-element set to an n-element set is given by inclusion-exclusion: n^m - C(n,1)(n-1)^m + C(n,2)(n-2)^m - ... . With m = 5 and n = 3 this is 3^5 - 3·2^5 + 3·1^5 = 243 - 96 + 3 = 150. Equivalently, every target element must receive at least one preimage.

Question 6Engineering Mathematics and Discrete Mathematics

The eigenvalues of the real symmetric matrix A = [[2, 1], [1, 2]] are:

  1. -1 and 5
  2. 1 and 3 Correct answer.
  3. 2 and 2
  4. 0 and 4

Explanation

The characteristic polynomial of a 2×2 matrix is λ^2 - (trace A)λ + det A. Here trace A = 4 and det A = 2·2 - 1·1 = 3, so λ^2 - 4λ + 3 = (λ - 1)(λ - 3). Thus the eigenvalues are 1 and 3.

Question 7Engineering Mathematics and Discrete Mathematics

Using the master theorem, the recurrence T(n) = 2T(n/2) + n for n > 1, with T(1) = 1, has solution:

  1. Θ(log n)
  2. Θ(n log n) Correct answer.
  3. Θ(n^2)
  4. Θ(n)

Explanation

For T(n) = aT(n/b) + f(n), compare f(n) with n^(log_b a). Here a = 2 and b = 2, so n^(log_2 2) = n, which matches f(n) = n. This is the master theorem's balanced case, giving T(n) = Θ(n log n).

Question 8Engineering Mathematics and Discrete Mathematics

Two fair six-sided dice are rolled independently. What is the probability that the sum of the two outcomes is 7?

  1. 5/36
  2. 7/36
  3. 1/12
  4. 1/6 Correct answer.

Explanation

There are 6 × 6 = 36 equally likely ordered outcomes. The favorable pairs are (1,6), (2,5), (3,4), (4,3), (5,2), and (6,1), six in total. Hence the probability is 6/36 = 1/6.

Question 9Engineering Mathematics and Discrete Mathematics

How many non-isomorphic groups of order 6 are there?

  1. 3
  2. 2 Correct answer.
  3. 6
  4. 1

Explanation

Groups of order 6 are either cyclic or non-cyclic. The cyclic group C6 exists, and the symmetric group S3 is non-abelian of order 6; these two are not isomorphic. Therefore there are exactly two isomorphism classes.

Question 10Engineering Mathematics and Discrete Mathematics

Let A be a 3×3 real matrix with eigenvalues 1, 2, and 3. What is det(A^2 - 4A + 3I)?

  1. 6
  2. 0 Correct answer.
  3. 24
  4. -1

Explanation

If λ is an eigenvalue of A, then p(λ) is an eigenvalue of p(A) for any polynomial p. Here p(x) = x^2 - 4x + 3 = (x - 1)(x - 3), so the eigenvalues of p(A) are p(1) = 0, p(2) = -1, and p(3) = 0. The determinant is the product of these eigenvalues, which is 0.

Question 11Engineering Mathematics and Discrete Mathematics

Euler's totient function φ(n) counts the integers in {1, 2, ..., n} that are coprime to n. What is φ(36)?

  1. 12 Correct answer.
  2. 18
  3. 24
  4. 6

Explanation

Factor 36 as 2^2 × 3^2. Then φ(36) = 36(1 − 1/2)(1 − 1/3) = 36 × 1/2 × 2/3 = 12. Equivalently, among 1 through 36, exactly 12 integers are coprime to 36.

Question 12Engineering Mathematics and Discrete Mathematics

How many binary strings of length 8 contain exactly three 1s?

  1. 56 Correct answer.
  2. 28
  3. 512
  4. 336

Explanation

Choose the three positions occupied by 1s among the eight positions, giving C(8, 3) = 56 strings. The remaining five positions are fixed as 0s.

Question 13Engineering Mathematics and Discrete Mathematics

A real 4×6 matrix A has rank 3. What is the dimension of the null space of A?

  1. 1
  2. 4
  3. 3 Correct answer.
  4. 2

Explanation

The rank-nullity theorem gives rank(A) + nullity(A) = number of columns. Here the matrix has 6 columns and rank 3, so nullity(A) = 6 − 3 = 3.

Question 14Engineering Mathematics and Discrete Mathematics

Which formula is logically equivalent to ¬∀x (P(x) → Q(x))?

  1. ∃x (P(x) ∧ ¬Q(x)) Correct answer.
  2. ∀x (¬P(x) ∨ Q(x))
  3. ∃x (¬P(x) ∧ Q(x))
  4. ∀x (P(x) ∧ ¬Q(x))

Explanation

Negating a universal statement gives an existential statement, and negating P(x) → Q(x) gives P(x) ∧ ¬Q(x). Therefore the equivalent formula is ∃x (P(x) ∧ ¬Q(x)).

Question 15Engineering Mathematics and Discrete Mathematics

Urn A contains 3 red and 2 blue balls; urn B contains 1 red and 4 blue balls. An urn is chosen uniformly at random and one ball is drawn; the ball is red. What is the probability that urn A was chosen?

  1. 1/4
  2. 3/4 Correct answer.
  3. 3/5
  4. 1/5

Explanation

By Bayes' theorem, P(A | red) = (1/2 × 3/5) / (1/2 × 3/5 + 1/2 × 1/5) = (3/10) / (4/10) = 3/4. The red ball is three times as likely under urn A as under urn B.

Question 16Engineering Mathematics and Discrete Mathematics

How many distinct spanning trees does the complete bipartite graph K_{2,3} have?

  1. 6
  2. 8
  3. 12 Correct answer.
  4. 18

Explanation

For K_{m,n}, the number of spanning trees is m^(n−1) n^(m−1). With m = 2 and n = 3, this is 2^2 × 3^1 = 12.

Question 17Engineering Mathematics and Discrete Mathematics

A sequence satisfies a_n = 5a_{n−1} − 6a_{n−2} for n ≥ 2, with a_0 = 1 and a_1 = 2. Which closed form gives a_n?

  1. 3^n
  2. 2·3^(n−1)
  3. 3·2^(n−1) − 2
  4. 2^n Correct answer.

Explanation

The characteristic equation is r^2 − 5r + 6 = 0, with roots 2 and 3, so a_n = A·2^n + B·3^n. The initial values give A + B = 1 and 2A + 3B = 2, hence B = 0 and A = 1, so a_n = 2^n.

Question 18Engineering Mathematics and Discrete Mathematics

Applying the Newton–Raphson method to f(x) = x^2 − 2 with initial guess x_0 = 1 gives x_1 equal to:

  1. 5/4
  2. 3/2 Correct answer.
  3. 4/3
  4. 2

Explanation

Newton–Raphson uses x_1 = x_0 − f(x_0)/f'(x_0). Here f(1) = −1 and f'(1) = 2, so x_1 = 1 − (−1)/2 = 3/2.

Question 19Engineering Mathematics and Discrete Mathematics

How many integer solutions are there to x_1 + x_2 + x_3 + x_4 = 20 with 1 ≤ x_i ≤ 6 for each i?

  1. 35 Correct answer.
  2. 84
  3. 20
  4. 56

Explanation

Set z_i = 6 − x_i. Then each z_i ≥ 0 and z_1 + z_2 + z_3 + z_4 = 24 − 20 = 4. The upper bound z_i ≤ 5 is automatic because the total is only 4, so the count is C(4 + 4 − 1, 4 − 1) = C(7, 3) = 35.

Question 20Engineering Mathematics and Discrete Mathematics

How many non-isomorphic simple undirected graphs with exactly 4 vertices are there?

  1. 11 Correct answer.
  2. 12
  3. 9
  4. 10

Explanation

Classifying by edge count gives 1 graph with 0 edges, 1 with 1 edge, 2 with 2 edges, 3 with 3 edges, 2 with 4 edges, 1 with 5 edges, and 1 with 6 edges. The total is 1+1+2+3+2+1+1 = 11.

Question 21Digital Logic and Computer Organization

A four-variable Boolean function is given by F(A, B, C, D) = Σm(0, 1, 2, 3, 8, 9, 10, 11). Which single literal is the minimal sum-of-products expression for F?

  1. C′
  2. A′
  3. B′C′
  4. B′ Correct answer.

Explanation

Every listed minterm has B = 0, while A, C and D each take both values across the two 4-cell groups m0–m3 and m8–m11. Merging those two groups eliminates A, C and D, so the minimal sum-of-products collapses to the single literal B′.

Question 22Digital Logic and Computer Organization

What is the range of integers representable in an 8-bit two's complement register?

  1. −127 to +128
  2. −127 to +127
  3. −128 to +127 Correct answer.
  4. −128 to +128

Explanation

In n-bit two's complement the range is −2^(n−1) through +2^(n−1) − 1, because the single zero pattern frees one code for a negative magnitude. Substituting n = 8 gives −128 to +127.

Question 23Digital Logic and Computer Organization

The decimal value 100.0 is stored in IEEE 754 single precision. What is the 8-bit biased exponent field?

  1. 10000101 Correct answer.
  2. 10000011
  3. 10000110
  4. 10000100

Explanation

Normalising 100 gives 1.5625 × 2^6, so the unbiased exponent is 6. Adding the single-precision bias of 127 yields 133, which in 8-bit binary is 1000 0101.

Question 24Digital Logic and Computer Organization

A processor with 32-bit physical addresses uses a 32 KB, 8-way set-associative cache with 64-byte blocks. How many bits are in the tag field?

  1. 20 bits Correct answer.
  2. 19 bits
  3. 21 bits
  4. 18 bits

Explanation

Each set holds 8 blocks of 64 bytes, i.e. 512 bytes, so the cache has 32 KB ÷ 512 B = 64 = 2^6 sets and needs a 6-bit index. The block offset also needs log2(64) = 6 bits, leaving 32 − 6 − 6 = 20 tag bits.

Question 25Digital Logic and Computer Organization

A 5-stage single-issue instruction pipeline runs at 1.2 GHz and suffers no stalls. What is its sustained instruction throughput in steady state?

  1. 1.2 × 10^9 instructions per second Correct answer.
  2. 6.0 × 10^9 instructions per second
  3. 2.4 × 10^8 instructions per second
  4. 2.4 × 10^9 instructions per second

Explanation

Once the pipeline is filled, one instruction leaves the last stage every clock cycle, so throughput equals the clock frequency. With a 1.2 GHz clock that is 1.2 × 10^9 instructions per second; the 5 stages affect only the fill latency, not steady-state rate.

Question 26Digital Logic and Computer Organization

A 4-bit Johnson (twisted-ring) counter is built from four flip-flops with the inverted output of the last stage fed back to the first. How many distinct states does it pass through before repeating?

  1. 4
  2. 15
  3. 16
  4. 8 Correct answer.

Explanation

An n-bit Johnson counter cycles through 2n states: after n shifts the register holds all ones and after 2n shifts it returns to all zeros. For n = 4 the sequence length is therefore 8.

Question 27Digital Logic and Computer Organization

A machine has 8-bit words and 16-bit instructions held one per word. An instruction stored at address 100 uses PC-relative addressing with an 8-bit signed displacement of −6. What effective address does it reference?

  1. 107
  2. 95 Correct answer.
  3. 94
  4. 92

Explanation

PC-relative addressing adds the displacement to the address of the following instruction, not to the current one. Since the instruction occupies one 8-bit word, the updated PC is 101, and 101 − 6 = 95.

Question 28Digital Logic and Computer Organization

A two-level cache has an L1 hit time of 1 cycle and a 90% L1 hit rate; the L2 hit time is 10 cycles with a local hit rate of 80%; main memory access takes 100 cycles. What is the average memory access time in cycles?

  1. 4.6 cycles
  2. 4.0 cycles Correct answer.
  3. 2.9 cycles
  4. 3.2 cycles

Explanation

Only 10% of references miss in L1; those cost a 10-cycle L2 access plus, with 20% probability, a further 100-cycle memory access. AMAT = 1 + 0.10 × (10 + 0.20 × 100) = 1 + 3 = 4.0 cycles.

Question 29Digital Logic and Computer Organization

A pipelined processor has a base CPI of 1.0 when no hazards occur. Of all instructions, 20% are branches costing a 2-cycle penalty each, and 30% are loads of which 50% are immediately followed by a dependent instruction costing a 1-cycle stall. What is the effective CPI?

  1. 1.55 Correct answer.
  2. 1.15
  3. 1.50
  4. 1.70

Explanation

The base CPI is 1.0. Branches contribute 0.20 × 2 = 0.40 cycles and load-use hazards contribute 0.30 × 0.50 × 1 = 0.15 cycles, giving 1.0 + 0.40 + 0.15 = 1.55.

Question 30Digital Logic and Computer Organization

A 32-bit instruction set has 40 distinct opcodes, two register fields each able to name 32 registers, and one immediate field, with no other fields. What is the width of the immediate field?

  1. 17 bits
  2. 16 bits Correct answer.
  3. 15 bits
  4. 14 bits

Explanation

Encoding 40 opcodes needs ceil(log2 40) = 6 bits, and each register field needs log2 32 = 5 bits. The immediate therefore occupies 32 − 6 − 5 − 5 = 16 bits.

Question 31Digital Logic and Computer Organization

A JK flip-flop has J = 1 and K = 1, and its present state is Q = 0. What is the next state after the active clock edge?

  1. Q(next) is undefined for J = K = 1
  2. Q(next) = 0
  3. Q(next) remains at its previous value
  4. Q(next) = 1 Correct answer.

Explanation

When J = K = 1, the JK flip-flop toggles on the active clock edge. Since the present state is Q = 0, toggling produces Q(next) = 1. The J = K = 1 condition is a valid toggle condition, not an indeterminate one.

Question 32Digital Logic and Computer Organization

Two 8-bit two's complement numbers are added in an ALU. Which condition correctly signals signed overflow?

  1. The result has even parity
  2. The carry into the MSB and the carry out of the MSB differ Correct answer.
  3. The sign bits of the two operands are different
  4. The carry out of the MSB is 1

Explanation

For two's complement addition, signed overflow occurs when the carry into the sign bit differs from the carry out of the sign bit. Equivalently, it occurs when adding two numbers of the same sign produces a result of the opposite sign. A carry out of the MSB alone is not sufficient because it can happen without signed overflow.

Question 33Digital Logic and Computer Organization

Which Boolean expression is equivalent to A + A'B?

  1. A' + B
  2. A'B'
  3. A + B Correct answer.
  4. AB

Explanation

Using distribution, A + A'B = (A + A')(A + B). Since A + A' = 1, the expression reduces to A + B. This is a standard absorption-like simplification useful in gate-level minimization.

Question 34Digital Logic and Computer Organization

A processor uses a write-back, write-allocate data cache. A store instruction misses in the cache. What is the standard sequence of actions?

  1. Invalidate the addressed line and write the new data using DMA
  2. Allocate a line without fetching the block because the store will overwrite it
  3. Fetch the block, update the cached copy, and mark the line dirty Correct answer.
  4. Write the new data to main memory and do not allocate a cache line

Explanation

A write-allocate cache brings the missed block into the cache before completing the store. Because the cache is write-back, the updated line is marked dirty and is written to the next level only when it is evicted. This avoids a main-memory write on every store.

Question 35Digital Logic and Computer Organization

A 5-stage pipeline (IF, ID, EX, MEM, WB) has full forwarding from EX/MEM and MEM/WB to EX. Consider I1: LW R1, 0(R2) followed immediately by I2: ADD R3, R1, R4. How many stall cycles are required between I1 and I2?

  1. 1 stall cycle Correct answer.
  2. 2 stall cycles
  3. 0 stall cycles
  4. 3 stall cycles

Explanation

The ADD needs the loaded value in EX, but the load data is not available until after the MEM stage. With forwarding, one stall cycle is enough to align the consumer's EX stage with the loaded value. Additional stalls would be needed only if forwarding were incomplete.

Question 36Digital Logic and Computer Organization

In Booth's multiplication algorithm, the multiplier is examined in overlapping pairs (current bit, previous bit). Which action is taken when the pair is 10?

  1. Subtract the multiplicand from the partial product Correct answer.
  2. Perform no arithmetic operation
  3. Add the multiplicand to the partial product
  4. Complement the multiplier and continue

Explanation

Booth recoding interprets the pair 10 as the start of a run of 1s, which corresponds to subtracting the multiplicand at that position. The pair 01 corresponds to adding the multiplicand, while 00 and 11 require no arithmetic operation. This recoding handles signed multipliers uniformly.

Question 37Digital Logic and Computer Organization

An instruction uses base-plus-index addressing with base register R2 = 0x00001000, index register R3 = 0x00000020, and a 16-bit displacement of 0x0004. What effective address is generated?

  1. 0x00001004
  2. 0x00001204
  3. 0x00001020
  4. 0x00001024 Correct answer.

Explanation

Base-plus-index addressing adds the base register, the index register, and the displacement. Here 0x1000 + 0x0020 + 0x0004 = 0x1024. The displacement is not a byte offset unless the architecture defines it that way, so the units are added directly in this example.

Question 38Digital Logic and Computer Organization

A DMA controller uses cycle stealing to transfer a block to memory while the CPU executes. What is the main effect on the CPU?

  1. The CPU is halted for the entire block transfer
  2. The DMA controller uses only CPU registers, so there is no bus contention
  3. The CPU cache is bypassed, so the CPU runs faster
  4. The CPU is slowed because the DMA controller occasionally steals bus cycles Correct answer.

Explanation

Cycle stealing lets the DMA controller take individual bus cycles as needed, interleaved with CPU activity. The CPU continues executing but loses some memory-bus cycles, so its effective speed is reduced during the transfer. The CPU is not halted for the entire block, as it would be in block DMA.

Question 39Digital Logic and Computer Organization

For a carry-lookahead adder, bit i has generate g_i = a_i b_i and propagate p_i = a_i XOR b_i, where bit 0 is the least significant. Which expression gives carry c4 in terms of c0 and the bit generate/propagate signals for bits 0 through 3?

  1. c4 = p3 + g3p2 + g3g2p1 + g3g2g1p0 + g3g2g1g0c0
  2. c4 = g3g2g1g0 + p3p2p1p0c0
  3. c4 = g3 + p3g2 + p3p2g1 + p3p2p1g0 + p3p2p1p0c0 Correct answer.
  4. c4 = g0 + p0g1 + p0p1g2 + p0p1p2g3 + p0p1p2p3c0

Explanation

The carry out of bit 3 is generated by bit 3, or propagated through bit 3 from a carry generated by bit 2, and so on down to the carry-in c0. Thus c4 = g3 + p3g2 + p3p2g1 + p3p2p1g0 + p3p2p1p0c0. Each term represents a generate signal that is propagated through all more significant bit positions.

Question 40Digital Logic and Computer Organization

A 2-bit saturating branch predictor uses states 00 (strongly not taken), 01 (weakly not taken), 10 (weakly taken), and 11 (strongly taken). It starts in state 01. A branch is taken, taken, not taken, not taken in four successive executions. What is the final state?

  1. 00
  2. 11
  3. 01 Correct answer.
  4. 10

Explanation

Start in 01. A taken outcome moves to 10, then another taken outcome moves to 11. A not-taken outcome moves from 11 to 10, and the final not-taken outcome moves from 10 to 01. The predictor saturates at the strong states and does not wrap around.

Question 41Digital Logic and Computer Organization

A 3-to-8 binary decoder has active-high outputs and no enable input. If the select inputs are A2 A1 A0 = 1 0 1, which output line is asserted?

  1. Y5 Correct answer.
  2. Y3
  3. Y7
  4. Y6

Explanation

The select value 101 is the binary representation of decimal 5, so the decoder asserts output Y5. An active-high 3-to-8 decoder asserts exactly the one output line whose index matches the binary value on A2 A1 A0. The other output lines remain LOW.

Question 42Digital Logic and Computer Organization

A microprogrammed control unit has a control store containing 1024 microinstructions. Each microinstruction is 64 bits wide. What is the total control-store capacity in bytes?

  1. 1 KB
  2. 8 KB Correct answer.
  3. 64 KB
  4. 16 KB

Explanation

The control store holds 1024 x 64 bits = 65,536 bits. Since one byte is 8 bits, this equals 8,192 bytes, or 8 KB. The calculation uses the number of microinstructions multiplied by the width of each microinstruction, then divided by eight.

Question 43Digital Logic and Computer Organization

In a vectored interrupt system, what does the interrupting device supply so that the CPU can locate the correct service routine?

  1. The number of words to be transferred by programmed I/O
  2. A vector number used to index the interrupt vector table Correct answer.
  3. The saved program status word of the interrupted task
  4. The return address of the interrupted instruction

Explanation

A vectored interrupt identifies its service routine by supplying a vector number or index. The CPU uses that vector to read the service routine address from an interrupt vector table. The return address and program status word are saved by the CPU or interrupt hardware, not supplied by the device for vectoring.

Question 44Digital Logic and Computer Organization

A DRAM chip has 4096 rows and every row must be refreshed once every 64 ms. Each refresh operation takes 4 memory clock cycles, and the memory clock is 100 MHz. What percentage of the DRAM's time is spent on refresh?

  1. 0.128%
  2. 0.256% Correct answer.
  3. 0.512%
  4. 1.024%

Explanation

At 100 MHz, one clock cycle is 10 ns, so one refresh operation takes 4 x 10 ns = 40 ns. Refreshing all 4096 rows takes 4096 x 40 ns = 163,840 ns = 163.84 microseconds. Dividing by the 64 ms refresh interval gives 163.84 microseconds / 64,000 microseconds = 0.00256, which is 0.256%.

Question 45Programming and Data Structures

Consider the C declaration int a[5] = {10, 20, 30, 40, 50}; followed by int *p = a + 2;. What is the value of the expression *(p - 1) + p[1]?

  1. 60 Correct answer.
  2. 70
  3. 50
  4. 90

Explanation

p is set to a + 2, so it addresses a[2]. Pointer arithmetic scales by the element size, so *(p - 1) is a[1] = 20 and p[1] is a[3] = 40. Their sum is 60; the value at a[2] itself is not used.

Question 46Programming and Data Structures

A stack-based postfix evaluator processes the expression 5 3 + 8 2 - *. Assuming single-digit operands and the usual integer operators, what value does it produce?

  1. 30
  2. 24
  3. 48 Correct answer.
  4. 42

Explanation

A postfix evaluator pushes operands and pops two values for each operator. First 5 3 + gives 8, then 8 2 - gives 6, and finally 8 * 6 gives 48 because the earlier result stays on the stack as the left operand.

Question 47Programming and Data Structures

A singly linked list stores only a head pointer. Which of the following operations requires Θ(n) time in the worst case?

  1. Deleting the first node of the list
  2. Appending a new node at the tail using only the head pointer Correct answer.
  3. Reading the data field stored in the first node
  4. Inserting a new node after a node whose address is supplied by the caller

Explanation

With only the head pointer, reaching the last node in order to attach a new node means walking through all n nodes, so the cost is Θ(n). Inserting after a known address, deleting the first node and reading the first node's data all touch a constant number of links or fields.

Question 48Programming and Data Structures

What does the following C function print when called as g(3)? void g(int n) { static int k = 0; if (n == 0) return; k++; g(n - 1); printf("%d ", k); }

  1. 3 3 3 Correct answer.
  2. 1 2 3
  3. 3 2 1
  4. 1 1 1

Explanation

k has static storage duration, so a single copy is shared by every recursive activation. The increments all happen while the calls descend, leaving k equal to 3, and each printf executes only after the deeper calls have returned, so every print shows 3.

Question 49Programming and Data Structures

A C implementation aligns int on 4-byte boundaries and short on 2-byte boundaries. What is sizeof(struct S) for the declaration struct S { char a; int b; short c; };?

  1. 7
  2. 16
  3. 8
  4. 12 Correct answer.

Explanation

The char occupies byte 0 and three padding bytes are inserted so that the int can begin at offset 4. The int fills bytes 4 to 7, the short takes 8 to 9, and the structure size is rounded up to a multiple of its 4-byte alignment, giving 12.

Question 50Programming and Data Structures

A binary tree has preorder traversal A B D E C F and inorder traversal D B E A C F. Which sequence is its postorder traversal?

  1. D E B C F A
  2. D E B F C A Correct answer.
  3. E D B F C A
  4. D B E F C A

Explanation

The first preorder element A is the root, and its position in the inorder sequence splits the left subtree D B E from the right subtree C F. Recursing gives postorder D E B for the left subtree and F C for the right, with the root printed last.