MS Master of Computer Science 2 — Questions and Answers
Question 1: Which concurrency primitive prevents multiple threads from simultaneously entering a critical section?
- Semaphore
- Mutex (Correct answer)
- Condition variable
- Spinlock
Correct answer: Mutex
A mutex (mutual exclusion lock) ensures only one thread at a time can execute the protected critical section.
Question 2: In the CAP theorem, which two properties can a distributed system guarantee during a network partition?
- Consistency and Availability
- Availability and Partition tolerance
- Consistency and Partition tolerance (Correct answer)
- Durability and Consistency
Correct answer: Consistency and Partition tolerance
During a partition, a system must choose between consistency (CP) or availability (AP); it cannot guarantee both simultaneously.
Question 3: What is the worst-case time complexity of the QuickSort algorithm?
- O(n log n)
- O(n²) (Correct answer)
- O(n)
- O(log n)
Correct answer: O(n²)
QuickSort degrades to O(n²) when the pivot is always the smallest or largest element, causing maximally unbalanced partitions.
Question 4: Which normal form eliminates transitive functional dependencies from a relational database table?
- First Normal Form (1NF)
- Second Normal Form (2NF)
- Third Normal Form (3NF) (Correct answer)
- Boyce-Codd Normal Form (BCNF)
Correct answer: Third Normal Form (3NF)
3NF requires that every non-key attribute depend only on the primary key, not on other non-key attributes.
Question 5: In TCP/IP, which layer is responsible for end-to-end error detection and flow control between hosts?
- Network layer
- Data link layer
- Transport layer (Correct answer)
- Session layer
Correct answer: Transport layer
The transport layer (e.g., TCP) handles end-to-end reliability, flow control, and error recovery between communicating processes.
Question 6: What does Amdahl's Law primarily predict in parallel computing?
- Memory bandwidth saturation
- The maximum speedup achievable by parallelizing a program (Correct answer)
- Cache hit ratio improvements
- Energy consumption reduction
Correct answer: The maximum speedup achievable by parallelizing a program
Amdahl's Law states that the speedup of a program is limited by its sequential fraction, regardless of how many processors are added.
Question 7: Which data structure supports O(1) average-case insertion, deletion, and lookup?
- AVL tree
- Hash table (Correct answer)
- Sorted array
- Skip list
Correct answer: Hash table
Hash tables achieve O(1) average-case performance for all three operations by computing an index directly from the key.
MS Master of Computer Science 2
Which concurrency primitive prevents multiple threads from simultaneously entering a critical section?