1. Which of the following addressing modes is used in stack operations?
(A) Immediate
(B) Register indirect
(C) Indexed
(D) Implicit
2. Harvard architecture differs from Von Neumann in having:
(A) Separate buses for data and instructions
(B) Shared program and data memory
(C) Microprogrammed control
(D) Only cache-based memory
3. Which scheduling algorithm may lead to convoy effect?
(A) FCFS
(B) Round Robin
(C) Priority
(D) Multilevel Queue
4. A 32-bit processor with byte-addressable memory can access maximum:
(A) 4 KB
(B) 64 KB
(C) 4 GB
(D) 1 TB
5. Which of the following is non-preemptive scheduling?
(A) SJF
(B) FCFS
(C) Priority
(D) Round Robin
6. Which pipeline hazard can be removed by instruction reordering?
(A) Structural hazard
(B) Data hazard
(C) Control hazard
(D) Cache miss
7. Cache mapping technique with highest hit ratio is usually:
(A) Direct mapping
(B) Fully associative
(C) Set associative
(D) Random mapping
8. Which normal form eliminates partial dependency?
(A) 1NF
(B) 2NF
(C) 3NF
(D) BCNF
9. Referential integrity in DBMS is maintained by:
(A) Primary key
(B) Candidate key
(C) Foreign key
(D) Unique key
10. The worst-case time complexity of Quick Sort is:
(A) O(n log n)
(B) O(n²)
(C) O(log n)
(D) O(n)
11. Which graph traversal uses a queue?
(A) DFS
(B) BFS
(C) Dijkstra
(D) Kruskal
12. Page table is generally stored in:
(A) Cache
(B) Main memory
(C) CPU registers
(D) Hard disk
13. The optimal page replacement algorithm requires:
(A) Knowledge of future references
(B) Stack data structure
(C) LRU counter
(D) Clock pointer
14. In B-trees, the number of keys in a node of order m ranges from:
(A) 1 to m
(B) m/2 to m–1
(C) 0 to m
(D) m to 2m
15. The principle of locality exploited by cache is:
(A) Spatial and temporal
(B) Associative
(C) Sequential
(D) Random
16. Which protocol ensures reliable, connection-oriented communication?
(A) IP
(B) TCP
(C) UDP
(D) ARP
17. Which layer of OSI model deals with compression and encryption?
(A) Session
(B) Transport
(C) Network
(D) Presentation
18. The main problem with Distance Vector Routing is:
(A) Hidden terminal problem
(B) Count-to-infinity
(C) Congestion
(D) Broadcast storm
19. IPv4 address size is:
(A) 16-bit
(B) 32-bit
(C) 64-bit
(D) 128-bit
20. Which technique prevents deadlock by resource ordering?
(A) Banker’s algorithm
(B) Wait-die scheme
(C) Preemption
(D) Circular wait prevention
21. Which RAID level provides both mirroring and striping?
(A) RAID 0
(B) RAID 1
(C) RAID 5
(D) RAID 10
22. The worst-case height of an AVL tree with n nodes is:
(A) O(log n)
(B) O(n)
(C) O(n log n)
(D) O(√n)
23. In relational algebra, σ denotes:
(A) Projection
(B) Selection
(C) Join
(D) Union
24. A minimal superkey is also known as:
(A) Candidate key
(B) Primary key
(C) Foreign key
(D) Composite key
25. The major drawback of two-phase locking protocol is:
(A) Deadlock possibility
(B) Phantom problem
(C) Non-serializable schedules
(D) Data loss
26. In context-free grammars, ambiguity arises when:
(A) Two different parse trees for same string exist
(B) Grammar is left-recursive
(C) Null productions exist
(D) No terminals are produced
27. Pumping lemma for context-free languages is used to prove:
(A) Regularity
(B) Non-regularity
(C) Non-context-freeness
(D) Decidability
28. Which parsing method is most suitable for LR grammars?
(A) Recursive descent
(B) Operator precedence
(C) Shift-reduce
(D) Predictive parsing
29. Syntax-directed translation is used in:
(A) Code optimization
(B) Semantic analysis
(C) Symbol table generation
(D) Lexical analysis
30. Which data structure is used in implementing symbol tables?
(A) Hash table
(B) Stack
(C) Queue
(D) Heap
31. Which of the following is a non-primitive data type?
(A) Integer
(B) Float
(C) Array
(D) Character
32. Which algorithm design technique is used in Merge Sort?
(A) Greedy
(B) Divide and Conquer
(C) Dynamic programming
(D) Backtracking
33. The worst-case time for searching in a hash table with chaining is:
(A) O(1)
(B) O(log n)
(C) O(n)
(D) O(n log n)
34. Which algorithm is used to detect cycles in a directed graph?
(A) Kruskal
(B) Bellman-Ford
(C) Depth First Search
(D) Dijkstra
35. The process state immediately after creation is:
(A) Ready
(B) New
(C) Waiting
(D) Running
36. Which scheduling policy is best for time-sharing systems?
(A) FCFS
(B) SJF
(C) Round Robin
(D) Priority
37. DMA stands for:
(A) Direct Memory Allocation
(B) Direct Memory Access
(C) Dynamic Memory Access
(D) Dynamic Memory Allocation
38. Which addressing mode uses displacement + register value?
(A) Immediate
(B) Indexed
(C) Indirect
(D) Relative
39. In pipelining, CPI ideally approaches:
(A) 0
(B) 1
(C) n
(D) log n
40. Which counter is used in dynamic RAM refresh?
(A) Program counter
(B) Refresh counter
(C) Memory counter
(D) Stack counter
41. Two-phase commit protocol is used in:
(A) Concurrency control
(B) Recovery
(C) Deadlock detection
(D) Buffer management
42. The best case time for bubble sort is:
(A) O(n)
(B) O(log n)
(C) O(n log n)
(D) O(n²)
43. Which of the following is not NP-complete?
(A) Hamiltonian cycle
(B) Travelling salesman
(C) 3-SAT
(D) Linear programming
44. Which of the following is decidable?
(A) Halting problem
(B) Membership problem for DFA
(C) Equivalence of CFGs
(D) Post correspondence problem
45. Which grammar type corresponds to finite automata?
(A) Type-0
(B) Type-1
(C) Type-2
(D) Type-3
46. Which operation is not possible in a priority queue?
(A) Insertion
(B) Deletion
(C) Traversal
(D) Find-min / Find-max
47. Which of the following is not a non-preemptive scheduling algorithm?
(A) FCFS
(B) SJF
(C) Priority (non-preemptive)
(D) Round Robin
48. The optimal code generated by Huffman algorithm is:
(A) Fixed length
(B) Prefix free
(C) Suffix free
(D) Run length
49. Which hashing method uses prime number table size for efficiency?
(A) Division method
(B) Multiplication method
(C) Mid-square method
(D) Folding method
50. The spanning tree with minimum total weight is found by:
(A) BFS
(B) DFS
(C) Prim’s algorithm
(D) Topological sort
51. Which of the following is not a page replacement algorithm?
(A) FIFO
(B) LRU
(C) MRU
(D) LOOK
52. Which protocol uses three-way handshake?
(A) UDP
(B) TCP
(C) HTTP
(D) ICMP
53. Which of the following is connectionless?
(A) TCP
(B) IP
(C) FTP
(D) SSH
54. Which transport layer protocol is used for DNS?
(A) TCP only
(B) UDP only
(C) TCP and UDP both
(D) ICMP
55. The default subnet mask for Class C IPv4 address is:
(A) 255.0.0.0
(B) 255.255.0.0
(C) 255.255.255.0
(D) 255.255.255.255
56. Error detection using CRC is based on:
(A) Binary subtraction
(B) Polynomial division
(C) Modular addition
(D) Boolean algebra
57. Which parsing technique cannot handle left recursion?
(A) LL(1)
(B) LR(1)
(C) LALR
(D) SLR
58. Dynamic binding means:
(A) Binding at compile time
(B) Binding at run time
(C) Binding at load time
(D) Binding at link time
59. Which of the following is not a feature of Object-Oriented Programming?
(A) Encapsulation
(B) Inheritance
(C) Polymorphism
(D) Structured programming
60. Which of the following languages is context-sensitive?
(A) {aⁿbⁿ | n ≥ 0}
(B) {aⁿbⁿcⁿ | n ≥ 0}
(C) {aᶦbʲcᵏ | i,j,k ≥ 0}
(D) {wwʳ | w ∈ {a,b}*}
——–THE END——–
Answer Key
1. (D) Implicit
Stack operations use implicit addressing (operand location is implied, e.g., PUSH/POP).
2. (A) Separate buses for data and instructions
Harvard architecture has physically separate instruction & data paths, unlike Von Neumann.
3. (A) FCFS
First-Come-First-Served may cause “convoy effect” when one long job delays all others.
4. (C) 4 GB
32-bit address bus → 2³² = 4 GB addressable memory.
5. (B) FCFS
First-Come-First-Served is non-preemptive. (SJF and Priority can be both).
6. (B) Data hazard
Reordering instructions avoids Read After Write (RAW) hazards.
7. (B) Fully associative
Any block can go into any cache line → max flexibility → highest hit ratio.
8. (B) 2NF
Second Normal Form removes partial dependencies on a candidate key.
9. (C) Foreign key
Ensures that values in one relation correspond to primary key values in another.
10. (B) O(n²)
Worst case of Quick Sort occurs for sorted input if pivot is badly chosen.
11. (B) BFS
Breadth-First Search uses a queue; DFS uses stack/recursion.
12. (B) Main memory
Page tables are stored in main memory; CPU caches part in TLB.
13. (A) Knowledge of future references
Optimal replacement requires knowing which page will be used farthest in future.
14. (B) m/2 to m–1
A B-tree node (except root) must be at least half full.
15. (A) Spatial and temporal
Cache exploits both: recently used (temporal) and nearby locations (spatial).
16. (B) TCP
Transmission Control Protocol → reliable, connection-oriented.
17. (D) Presentation
Handles encryption, compression, and data translation.
18. (B) Count-to-infinity
Distance Vector routing suffers from slow convergence (count to infinity).
19. (B) 32-bit
IPv4 = 32-bit addresses; IPv6 = 128-bit.
20. (D) Circular wait prevention
Assigning order to resources prevents circular wait → avoids deadlock.
21. (D) RAID 10
Combines mirroring (RAID 1) and striping (RAID 0).
22. (A) O(log n)
AVL tree height is logarithmic in worst case.
23. (B) Selection
σ denotes selection in relational algebra.
24. (A) Candidate key
Minimal superkey = candidate key; primary key is chosen from them.
25. (A) Deadlock possibility
Two-phase locking guarantees serializability but may cause deadlock.
26. (A) Two parse trees for same string
Grammar is ambiguous if a string has more than one parse tree.
27. (C) Non-context-freeness
Pumping lemma for CFL is used to prove a language is not context-free.
28. (C) Shift-reduce
LR parsers are shift-reduce parsers → bottom-up.
29. (B) Semantic analysis
Syntax-directed translation links parsing with semantic rules.
30. (A) Hash table
Symbol tables in compilers are implemented using hash tables.
31. (C) Array
Arrays are derived (non-primitive) data types.
32. (B) Divide and Conquer
Merge Sort splits array recursively, then merges.
33. (C) O(n)
Worst-case (all elements in one chain) requires linear time search.
34. (C) Depth First Search
DFS detects cycles by checking back edges.
35. (B) New
A process after creation is in “new” state.
36. (C) Round Robin
RR is best suited for time-sharing systems.
37. (B) Direct Memory Access
DMA allows data transfer between I/O device and memory without CPU.
38. (B) Indexed
Effective address = base register + displacement.
39. (B) 1
With perfect pipelining, CPI approaches 1.
40. (B) Refresh counter
DRAM cells need periodic refreshing with a refresh counter.
41. (B) Recovery
Two-phase commit ensures atomicity in distributed systems.
42. (A) O(n)
Best case of Bubble Sort = already sorted array → one pass.
43. (D) Linear programming
Solvable in polynomial time; not NP-complete.
44. (B) Membership problem for DFA
Checking if DFA accepts a string is decidable.
45. (D) Type-3
Regular languages (finite automata) correspond to Type-3 grammar.
46. (C) Traversal
Priority queues don’t support full traversal like arrays/lists.
47. (D) Round Robin
RR is preemptive; the others can be non-preemptive.
48. (B) Prefix free
Huffman codes are prefix-free to ensure unique decoding.
49. (A) Division method
Works best with prime modulus → reduces clustering.
50. (C) Prim’s algorithm
Used to find minimum spanning tree.
51. (D) LOOK
LOOK is a disk scheduling algorithm, not a page replacement.
52. (B) TCP
Uses 3-way handshake for connection setup.
53. (B) IP
Internet Protocol is connectionless and unreliable.
54. (C) TCP and UDP both
DNS uses UDP for queries, TCP for zone transfers.
55. (C) 255.255.255.0
Default mask of Class C = 24 bits.
56. (B) Polynomial division
CRC detects errors using modulo-2 polynomial division.
57. (A) LL(1)
LL(1) parsers can’t handle left recursion. LR parsers can.
58. (B) Run time
Dynamic binding = method call resolved at run time.
59. (D) Structured programming
Structured programming is not an OOP feature.
60. (B) {aⁿbⁿcⁿ | n ≥ 0}
This requires context-sensitive grammar, not context-free.