Computer Science & Information Technology — SAMPLE (IIT Guwahati

style)

Q1–Q10 (1 mark each) — Discrete / Math / Basic CS

1. (1 mark) Let X be a discrete random variable with
P(X=0)=0.5, P(X=1)=0.5. The entropy H(X) (in bits) is:
(A) 1 (B) 0.5 (C) 0 (D) 2

2. (1 mark) Which of these relations is true for functions

f(n)=n and g(n)=n log n?
(A) f ∈ o(g) (B) f ∈ Θ(g) (C) f ∈ Ω(g) (D) f ∈ O(g)

3. (1 mark) The in-degree sequence of a directed acyclic

graph (DAG) can have a vertex of in-degree n−1. (A)
True (B) False

4. (1 mark) NAT: The value of floor( √10 ) is ____.

5. (1 mark) Which sorting algorithm has worst-case time

complexity O(n log n)?
(A) QuickSort (random pivot) (B) MergeSort (C)
HeapSort (D) InsertionSort
 6. (1 mark) A bijection between two finite sets implies
they have the same: (A) cardinality (B) order (C) type
(D) none

7. (1 mark) The minimum number of colors required to

color a tree with at least one edge is: (A) 1 (B) 2 (C) 3
(D) depends on tree

8. (1 mark) For a binary heap with n elements, extracting

min is O(log n) — (A) True (B) False

9. (1 mark) The RISC pipeline generally reduces CPI by

increasing: (A) instruction count (B) clock cycle time
(C) instruction-level parallelism (D) branch penalty

10. (1 mark) NAT: Number of bits required to encode

1000 distinct symbols using fixed-length binary =
_____.

Q11–Q20 (1 mark each) — Programming / OS / Networks

11. (1 mark) In TCP, the initial congestion window
(IW) is typically measured in: (A) bytes (B) segments
(C) packets (D) milliseconds
12. (1 mark) A page fault always causes a process
context switch. (A) True (B) False

13. (1 mark) SQL: Given table T(a,b) with rows (1,2),

(1,3),(2,4), the result of SELECT COUNT(DISTINCT a) FROM T; is:
(A) 1 (B) 2 (C) 3 (D) 0

14. (1 mark) In RAID 1, disk mirroring provides: (A)

increased performance for writes (B) redundancy (C)
parity storage (D) striping

15. (1 mark) A functional dependency A → B means:

(A) A is key (B) B determines A (C) for any two rows
equal on A, they are equal on B (D) none

16. (1 mark) NAT: Sum of ASCII codes of characters

'A' and 'a' = ____.

17. (1 mark) Endianness concerns: (A) byte order (B)

bit order inside byte (C) both (D) neither
 18. (1 mark) For directed graph, strongly connected
component implies path both ways between any two
vertices. (A) True (B) False

19. (1 mark) In context switching, saving and

restoring registers is performed by: (A) OS kernel (B)
hardware automatically (C) compiler (D) user program

20. (1 mark) The subnet mask /24 represents: (A) 16

bits network (B) 24 bits network (C) 8 bits network (D)
none

Q21–Q30 (1 mark each) — DB/TOC/COA/Compilers

21. (1 mark) Boyer-Moore algorithm is used for: (A)
string matching (B) sorting (C) parsing (D) garbage
collection

22. (1 mark) The FIRST set in grammar is used

during: (A) semantic analysis (B) lexical analysis (C)
parsing (D) code generation

23. (1 mark) The following grammar S → aSb | ε is:

(A) regular (B) context-free but not regular (C)
context-sensitive (D) recursive?
24. (1 mark) NAT: Two’s complement of binary 0001
is ____.

25. (1 mark) In a cache of block size 4 bytes and

address size 16 bits, block offset requires how many
bits? (A) 2 (B) 4 (C) 8 (D) 16

26. (1 mark) Which is NOT part of the three-address

code (TAC) characteristics? (A) one operator per
instruction (B) easy to optimize (C) machine specific
(D) uses temporaries

27. (1 mark) A leftmost derivation corresponds to

which parser type? (A) LL parser (B) LR parser (C)
LALR parser (D) SLR parser

28. (1 mark) In normalization, BCNF is stronger than

3NF. (A) True (B) False

29. (1 mark) The expression (a ∧ b) ∨ (a ∧ ¬b)

simplifies to: (A) a (B) b (C) false (D) true
 30. (1 mark) NAT: If a function takes time 3n^2 + 2n
+ 1, leading term coefficient = ____.

Q31–Q45 (2 marks each) — Algorithms, DS, OS,

Networks
31. (2 marks) (MCQ) Consider a directed graph with
5 vertices and a single topological order. Which
statement must be true: (A) graph is a chain (B) graph
is fully connected (C) graph has exactly one
Hamiltonian path (D) graph has no edges

32. (2 marks) (MCQ) For recurrence T(n)=2T(n/2)+n,

T(1)=1, T(n) ∈: (A) Θ(n) (B) Θ(n log n) (C) Θ(n^2) (D)
Θ(log n)

33. (2 marks) (NAT) A CPU with clock 2 GHz

executes instruction A in 5 cycles and instruction B in
10 cycles. If a program has 40% A and 60% B
instructions, average CPI = ____ (give numeric).

34. (2 marks) (MCQ) In the following C snippet, what

prints?
int f(){ static int x=0; return ++x; }
int main(){ printf("%d %d", f(), f()); }
(A) 1 1 (B) 2 1 (C) 1 2 (D) undefined
35. (2 marks) (MCQ) Consider a FIFO page
replacement with 3 frames. Page reference string:
1,2,3,4,1,2,5,1,2,3. Number of page faults = ? (A) 6
(B) 7 (C) 8 (D) 9

36. (2 marks) (MCQ) In TCP, if sender’s cwnd is 8

MSS and receives 3 ACKs without loss, after fast
recovery it becomes (approx): (A) 9 MSS (B) 8 MSS
(C) 12 MSS (D) 4 MSS

37. (2 marks) (NAT) A binary search on sorted array

of size 1024 performs at most ____ comparisons in
worst case.

38. (2 marks) (MCQ) For grammar G: S→aSb|ε.

Which strings are in L(G)? (A) {anbn | n≥0} (B) {anbm
| n,m≥0} (C) {abab} (D) none

39. (2 marks) (MCQ) In a balanced BST with n

nodes, the height is: (A) Θ(n) (B) Θ(log n) (C) Θ(√n)
(D) Θ(1)
40. (2 marks) (MCQ) For an undirected graph with
adjacency matrix, to check if graph is connected
takes: (A) O(V+E) (B) O(V^2) (C) O(E log V) (D) O(1)

41. (2 marks) (MCQ) Which of the following SQL

queries will return duplicates removed? (A) SELECT *
FROM T; (B) SELECT DISTINCT * FROM T; (C)
SELECT UNIQUE * FROM T; (D) SELECT * FROM T
GROUP BY *;

42. (2 marks) (MCQ) In a 5-stage RISC pipeline, a

data hazard that can be resolved by forwarding
requires which technique? (A) Stall (B) Forwarding
(C) Register renaming (D) Branch delay slot

43. (2 marks) (NAT) A link has bandwidth 10 Mbps

and RTT 50 ms. Bandwidth-delay product (in bits) =
____.
44. (2 marks) (MCQ) Given function f(n)=n^2 and
g(n)=2^n, which grows faster asymptotically? (A) f (B)
g (C) equal (D) depends

45. (2 marks) (MCQ) Consider the C expression: int

x=5; printf("%d", x++ + ++x); The behaviour is: (A) well-
 defined (B) undefined (C) implementation defined (D)
prints 12

Q46–Q55 (2 marks each) — DB, COA, Compilers,

Theory
46. (2 marks) (MCQ) Consider relation R(A,B,C) with
FDs: A→B and B→C. Candidate key is: (A) A (B) B
(C) C (D) (A,B)

47. (2 marks) (NAT) For fully associative cache with

16KB capacity and block size 64B, number of blocks
= ____.

48. (2 marks) (MCQ) In LR parsing, shift-reduce

conflict indicates: (A) grammar ambiguous (B)
grammar left recursive (C) grammar right recursive
(D) grammar regular

49. (2 marks) (MCQ) Consider language L = {0^n 1^n

| n≥0}. Which automaton recognizes L? (A) DFA (B)
PDA (C) TM (D) Regular expression

50. (2 marks) (NAT) Given a relation with 10 tuples, a

projection on a column that has 3 distinct values will
 return at most ____ tuples (no duplicates removed),
and after DISTINCT at most ____.

51. (2 marks) (MCQ) Which optimization is

performed by compilers to eliminate common
subexpressions? (A) loop unrolling (B) constant
folding (C) common subexpression elimination (D)
dead code elimination

52. (2 marks) (MCQ) Which storage device has

highest seek time? (A) HDD (B) SSD (C) RAM (D)
Tape

53. (2 marks) (NAT) A 32-bit virtual address with

page size 4 KB: number of pages in virtual address
space = ____.

54. (2 marks) (MCQ) Consider the relation between

normalization forms: (A) BCNF ⊆ 3NF (B) 3NF ⊆
BCNF (C) BCNF = 3NF (D) none

55. (2 marks) (MCQ) In code generation, register

allocation is typically solved by: (A) graph coloring (B)
 dynamic programming (C) greedy knapsack (D)
branch and bound

Q56–Q65 (2 marks each) — Misc / Higher difficulty /

Integration
56. (2 marks) (MCQ) Given two polynomials p(n)=n^3
and q(n)=n^2 log n, p(n) ? q(n) as n→∞: (A) p ∈ o(q)
(B) p ∈ ω(q) (C) p ∈ Θ(q) (D) p ∈ O(q)

57. (2 marks) (NAT) Let G be a tree with 15 vertices.

Number of edges = ____.

58. (2 marks) (MCQ) Consider the relation between

deterministic and nondeterministic space complexity:
(A) NSPACE(s(n)) = DSPACE(s(n)) (B) NSPACE(s)
⊆ DSPACE(s^2) (Savitch) (C) NSPACE(s) ⊆
DSPACE(2^{s}) (D) none
59. (2 marks) (MCQ) In RSA, if modulus n = pq,
factorization of n breaks the system because: (A)
primes are large (B) knowledge of p and q gives φ(n)
(C) encryption uses small exponents (D) padding is
weak
60. (2 marks) (NAT) In a binary tree stored as array
(1-based) where node i has children 2i and 2i+1,
parent of node 100 is index ____.

61. (2 marks) (MCQ) Which hashing collision

resolution technique uses secondary hash to compute
step size? (A) chaining (B) linear probing (C)
quadratic probing (D) double hashing

62. (2 marks) (NAT) A program has 3 instructions: I1

takes 2ns, I2 takes 3ns, I3 takes 5ns. If pipeline
perfectly overlaps, ideal CPI ~ ____ (in cycles
assuming 1 cycle = 1ns).

63. (2 marks) (MCQ) Regarding NP problems: (A) P

⊂ NP (B) P = NP (C) NP ⊆ P (D) unknown

64. (2 marks) (MCQ) Consider two processes P and

Q accessing shared variable x: P executes x = x + 1;
Q executes x = x + 1. The final value can be incorrect
without: (A) mutex (B) atomicity (C) locks (D) all of the
above
65. (2 marks) (NAT) If a directed graph has indegree
sequence [0,1,1,2] for 4 vertices, total number of
edges = ____.