Data Structures, Database and Operating System

Answer: C. 2^(h+1) - 1

Maximum nodes in binary tree of height h = 2^(h+1) - 1. This occurs in a complete binary tree.

Answer: C. 2^(h+1) - 1

Maximum nodes in binary tree height h is 2^(h+1) - 1.

Answer: B. A data structure is a concrete implementation; an ADT is a logical model specifying operations and behavior

An abstract data type (ADT) describes *what* operations are available and the logical behavior of a collection of data, without prescribing *how* the operations are implemented. For example, a Stack ADT specifies push, pop, top, isEmpty, and their semantics (LIFO), but it does not say whether the stack is realized with an array or a linked list. A data structure is the concrete representation in memory and the algorithms that implement those operations: for instance, an array-based stack with a top index, or a linked-list-based stack with a head pointer. Separating ADT from data structure gives design flexibility: client code can depend on the ADT interface and later swap implementations for better performance or memory usage without changing that code. This distinction is foundational for algorithm design, API design, and clean software architecture.

Answer: A. Push

In an array-based stack, the stack is represented by an array and a top index that indicates the position of the current top element. A push operation increments the top index and writes the new value at that position, which is a constant-time operation independent of the number of elements, so its time complexity is O(1). Similarly, pop is also O(1) because it just reads from the top index and decrements it. Operations such as searching or removing from the bottom require traversing multiple elements, giving O(n) in the worst case. This constant-time top access is precisely why stacks are efficient and heavily used in language runtimes (for function calls), expression evaluation, and backtracking algorithms.

Answer: A. AB+CD-*

To convert (A + B) * (C - D) to postfix, process the innermost sub-expressions: A + B becomes AB+, and C - D becomes CD-. Then the entire expression is (AB+) * (CD-), so the postfix is AB+CD-*. In general, postfix notation places the operator after its operands and eliminates parentheses, relying on the operator position and stack-based evaluation. This format is ideal for stack evaluation algorithms: scanning from left to right, operands are pushed on a stack and operators pop operands, compute a result, and push it back. Many expression evaluators, compiler back ends, and calculators use postfix or similar internal representations because they make precedence and associativity explicit and unambiguous.

Answer: A. Pop first operand as right, second as left

When evaluating a postfix expression, each time an operator is encountered, two operands are popped from the stack. The first popped operand corresponds to the *right* operand, and the second popped operand corresponds to the *left* operand. For example, for the postfix sequence "A B -", after pushing A then B, encountering '-' means: pop B (right operand), pop A (left operand), compute A − B, and push the result. This order is crucial for non-commutative operations such as subtraction and division. If you reversed them, you would compute B − A, which is incorrect. This right-then-left rule ensures postfix representation faithfully captures the original infix semantics.

Answer: A. O(1)

In a singly linked list where you maintain a pointer to the head node, inserting at the front requires only allocating a new node, setting its next pointer to the current head, and then updating the head pointer to the new node. These are all constant-time operations, independent of the list length, so the insertion at the head is O(1). In contrast, inserting at the tail is O(1) only if you also maintain a tail pointer; otherwise, it is O(n) because you must traverse the list to find the last node. Understanding these costs is key when choosing between array-based and linked-list-based representations for lists, stacks, and queues.

Answer: B. 0

If height is defined as the number of edges on the longest simple path from the root to any leaf, then a single-node tree (with just the root, which is also a leaf) has height 0, because there are no edges. Some texts instead define height as the number of nodes on that path, in which case the same tree would have height 1. It is important to check the convention being used. For algorithm analysis involving trees (such as AVL trees or heaps), the edge-based definition (height 0 for a single node) is common, because each level adds one edge of distance from the root.

Answer: C. 2^(h+1) - 1

Maximum nodes in binary tree of height h = 2^(h+1) - 1.

Answer: C. Sorted

Binary search tree requires sorted order: left < root < right.

Answer: C. Linked List

Linked list is linear collection where each element points to next.

Answer: A. Queue

Queue follows FIFO: first element added is first removed.

Answer: A. Linked list

Linked lists commonly implement queues for dynamic size management.

Answer: B. Stack

Stack implements LIFO: last element added is first removed.

Answer: B. L = I + 1

In full binary tree, leaves = internal nodes + 1.

Answer: B. LIFO

Stack uses LIFO: last pushed element popped first.

Answer: C. Both

Deque allows insertion and deletion at both ends.

Answer: A. AB+C*

The postfix notation of the infix expression (A+B)*C is AB+C*. In postfix notation (Reverse Polish Notation), operators appear after their operands. To convert (A+B)*C to postfix: (1) A and B are operands, A B, (2) + operator comes after A and B, so AB+, (3) The result (A+B) is multiplied by C, so AB+ then C and *, giving AB+C*. Postfix notation is useful for expression evaluation using stacks and is used in many calculators and compilers.

Answer: B. Stack

Answer: C. ABC*+

Answer: A. Queue

Answer: B. Data and a pointer to the next node

Answer: C. ⌊log₂n⌋

Answer: A. O(1)

Answer: C. O(n²)

Shell sort worst-case is O(n²) when using poor gap sequences.

Answer: A. Greedy

Dijkstra's shortest path uses greedy paradigm.

Answer: B. O(log n)

Binary search has O(log n) complexity.

Answer: C. O(n²)

Shell sort worst-case is O(n²) with poor gap sequences.

Answer: C. O(n log n)

Quicksort average case is O(n log n).

Answer: B. It performs sorting by using only a constant amount of extra memory, aside from the input array

An internal or in-place sorting algorithm rearranges elements within the original array or list using only a constant amount of additional memory, typically O(1) extra space. Classic examples include insertion sort, selection sort, bubble sort, heapsort, and in-place variants of quicksort. External sorting deals with data sets that are too large to fit in main memory and therefore require disk or external storage; such algorithms (like external mergesort) are not in-place, since they rely on additional temporary files or buffers. Space complexity is important in environments with limited memory, such as embedded systems or when handling large in-memory datasets.

Answer: C. O(n^2)

Insertion sort builds a sorted prefix by repeatedly taking the next element and inserting it into the correct position within the already-sorted part. In the worst case (when the array is in reverse order), each insertion of the i-th element requires comparing and shifting roughly i − 1 elements. Summing over i from 1 to n gives 1 + 2 + … + (n − 1) = O(n^2). However, insertion sort has O(n) best-case complexity (when the array is already sorted) and performs very well on small or nearly sorted data, which is why it is often used as the base case in hybrid sorting algorithms like introsort.

Answer: C. It always performs log n levels of merging, each processing n elements

Merge sort works by repeatedly splitting the array into halves (recursively) until subarrays of size 1 are reached, and then merging those subarrays back together in sorted order. The depth of this recursion tree is about log₂ n (you can divide n by 2 only log n times before reaching 1). At each level of the recursion tree, the algorithm processes all n elements in the merging step. Therefore, the total cost is approximately n (work per level) × log n (number of levels) = Θ(n log n). Mergesort has this complexity in the best, average, and worst cases because the splitting and merging pattern does not depend on the initial arrangement of data.

Answer: C. Sorting keys digit by digit using a stable stable subroutine (like counting sort) for each digit position

Radix sort sorts integers (or string-like keys) by processing individual digits (or characters) from least significant to most significant (LSD) or vice versa (MSD). For LSD radix sort on base-10 numbers, you repeatedly group numbers according to their 1s digit, then 10s digit, then 100s digit, etc., each time using a stable sorting algorithm like counting sort to preserve the relative order of elements with the same digit. Because it does not rely on direct comparisons between keys, radix sort can achieve O(d·(n + k)) time, where d is the number of digits and k is the digit range (base). For fixed-size integers, d and k are bounded constants, giving linear time complexity in n. Radix sort is effective when keys have fixed maximum length and the base is chosen appropriately.

Answer: B. It repeatedly divides the search interval in half by comparing the target to the middle element

Binary search maintains a search interval [low, high] on a sorted array. At each step, it computes mid = (low + high)/2, compares the target value to arr[mid], and discards half the interval: if target < arr[mid], it continues searching in [low, mid − 1]; if target > arr[mid], it continues in [mid + 1, high]. This halving continues until the element is found or the interval becomes empty. Because the search space size halves at each step, the worst-case running time is O(log n). Binary search is one of the classic divide-and-conquer algorithms and relies critically on the array being sorted and random access being O(1).

Answer: C. n(n − 1)/2

In an undirected simple graph (no parallel edges, no self-loops), each edge connects a distinct unordered pair of vertices. The number of such pairs is the binomial coefficient C(n, 2) = n(n − 1)/2. This is the maximum number of edges because any additional edge would either duplicate an existing edge between the same two vertices or create a self-loop, both of which are disallowed in a simple graph. Graph density, adjacency matrix vs adjacency list storage, and complexity of algorithms like DFS and BFS all depend strongly on the number of edges relative to n.

Answer: B. Breadth First Search (BFS)

Breadth First Search explores a graph in layers starting from a source vertex. It uses a FIFO queue: initially, the source vertex is enqueued, then BFS repeatedly dequeues a vertex, visits it, and enqueues all its unvisited neighbors. This leads to a level-order traversal where all vertices at distance 1 from the source are visited before those at distance 2, and so on. BFS is used to compute shortest paths in unweighted graphs, to test connectivity, and as a building block in algorithms like bipartite graph checking. DFS, in contrast, uses a stack (explicit or via recursion) and explores as deep as possible along each path before backtracking.

Answer: C. Finding single-source shortest paths in a graph with non-negative edge weights

Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph, assuming all edge weights are non-negative. It maintains a set of vertices whose shortest distance from the source is known, and in each step, selects the vertex with the minimum tentative distance (often using a min-priority queue) and relaxes its outgoing edges. Repeating this process n times in a graph with adjacency list representation and a binary heap yields time complexity O((V + E) log V). If negative edge weights are present, Dijkstra's algorithm can give incorrect results and algorithms like Bellman–Ford or Johnson's algorithm are used instead.

Answer: A. Insertion sort

Insertion sort is efficient for already sorted data with O(n) complexity.

Answer: B. O(n log n)

Best-case quicksort is O(n log n) with balanced partitioning.

Answer: A. O(n)

DFS has O(V+E) or O(n) complexity visiting each node once.

Answer: B. Queue

BFS uses queue for level-by-level traversal.

Answer: B. O(n log n)

Merge sort has O(n log n) complexity in all cases.

Answer: C. Dijkstra

Dijkstra finds shortest path in weighted graphs.

Answer: B. b) O(n log n)

The time complexity of Merge Sort in the best case is O(n log n). Unlike quick sort which has best case O(n log n) and worst case O(n²), merge sort maintains O(n log n) in all cases: best, average, and worst. This consistency makes merge sort a stable, predictable sorting algorithm. The n log n comes from dividing the array logarithmically and merging linearly at each level.

Answer: B. Queue

Queue is the data structure used to implement Breadth First Search (BFS). BFS uses a FIFO (First-In-First-Out) queue to explore nodes level by level. Starting from a source node, BFS adds all its unvisited neighbors to the queue. Then it processes the first node in the queue, adds its unvisited neighbors, and continues. This ensures that all nodes at distance k are visited before nodes at distance k+1, providing level-by-level exploration. Stack would implement DFS (Depth-First Search). Linked lists and trees are not data structures for implementing search algorithms but rather the structures being searched.

Answer: C. Quick Sort

Answer: B. O(log n)

Answer: B. Sorted list only

Answer: C. Dijkstra's algorithm

Answer: B. Breadth-First Search

Answer: C. O(n)

Answer: C. O(n²)

Answer: D. Merge Sort

Answer: C. DELETE

DELETE removes rows while preserving table structure. DROP removes entire table. TRUNCATE removes all rows but faster than DELETE.

Answer: B. Whenever two tuples agree on attributes X, they must also agree on attributes Y

A functional dependency X → Y in a relation R means that for any two tuples t1 and t2 in any valid instance of R, if t1.X = t2.X then t1.Y must equal t2.Y. In other words, the attributes in X functionally determine the attributes in Y. This concept is central to normalization: higher normal forms restrict the presence of certain types of functional dependencies to reduce redundancy and anomalies. A key of a relation is a set of attributes K such that K → all attributes in R, and no proper subset of K has that property. Understanding functional dependencies is necessary to reason about schema design, normalization, and lossless-join and dependency-preserving decompositions.

Answer: A. A functionally determines C via transitivity

Given A → B and B → C, Armstrong’s transitivity axiom implies A → C: since knowing A determines B and knowing B determines C, knowing A is sufficient to determine C. There is no given functional dependency involving D, so nothing can be concluded about D from these dependencies alone. Reasoning about closures of attribute sets under given FDs (using reflexivity, augmentation, transitivity, etc.) is a standard technique for testing keys, checking normal forms, and designing decompositions.

Answer: C. Third Normal Form (3NF)

Third Normal Form (3NF) requires that, for every non-trivial functional dependency X → A in a relation, either X is a superkey or A is a prime attribute (part of some candidate key). This condition eliminates transitive dependencies where a non-key attribute depends on a key via another non-key attribute. For example, if in a table we have key K, and K → X, X → Y, and Y is non-key, then K → Y is a transitive dependency that 3NF aims to remove by decomposition. 2NF only eliminates partial dependencies (where a non-key attribute depends on part of a composite key), while BCNF is stricter than 3NF and demands that for every non-trivial FD X → A, X be a superkey, with no exception for prime attributes.

Answer: B. A weak entity set does not have a primary key and is identified by being related to another entity set

A strong entity set has a primary key that uniquely identifies each of its entities independently. A weak entity set, however, does not have a sufficient primary key of its own. It is identified by a combination of its partial key (a discriminator) and the primary key of an owning or identifying strong entity set, through an identifying relationship. For example, in an HR database, an 'Employee' is a strong entity (identified by EmployeeID), while 'Dependent' (child or spouse of employee) may be modeled as a weak entity identified by (EmployeeID, DependentName). This modeling is reflected later in relational design by foreign keys and composite primary keys.

Answer: A. Data Definition Language (DDL)

CREATE TABLE is a Data Definition Language (DDL) command that defines a new relation (table) in the database schema, specifying its attributes, data types, constraints, and keys. Other DDL commands include ALTER TABLE (to change an existing schema) and DROP TABLE (to remove a relation). Data Manipulation Language (DML) commands such as SELECT, INSERT, UPDATE, and DELETE operate on the data within existing schema objects. DCL (like GRANT, REVOKE) controls privileges, and TCL (like COMMIT, ROLLBACK) manages transaction boundaries.

Answer: A. Single-valued

AGE is single-valued attribute: one value per person.

Answer: B. Normal

Redundancy is reduced in database tables by using Normal form. Normalization is the process of organizing database design to reduce redundancy: (1) 1NF (First Normal Form) - Eliminate repeating groups, atomic values only, (2) 2NF (Second Normal Form) - Remove partial dependencies on composite keys, (3) 3NF (Third Normal Form) - Remove transitive dependencies, (4) BCNF (Boyce-Codd Normal Form) - Stricter than 3NF. Benefits of normalization: (1) Reduces data redundancy - Less storage space, (2) Improves data integrity - Eliminates anomalies, (3) Easier updates - No need to update multiple locations, (4) Prevents insert/update/delete anomalies. Normalization process: (1) Start with unnormalized data, (2) Apply rules progressively (1NF → 2NF → 3NF), (3) Each step removes certain types of dependencies. Example of denormalized vs normalized: Denormalized: (Student, Course, Grade, Professor), Normalized: Separate tables for Student, Course, Enrollment with foreign keys. Anomalies in denormalized data: (1) Insert anomaly - Cannot insert new course without student, (2) Update anomaly - Change one grade, must change in multiple places, (3) Delete anomaly - Deleting student removes course information. Trade-offs: (1) Normalization improves integrity but increases complexity, (2) Over-normalization (beyond 3NF) may hurt performance, (3) Denormalization may be necessary for specific queries. Most databases use 3NF as standard balance between normalization and performance.

Answer: C. Boyce-Codd Normal Form (BCNF)

Boyce-Codd Normal Form (BCNF) requires that every determinant must be a candidate key. BCNF is a stricter version of 3NF. In BCNF, every non-trivial functional dependency X→Y must have X as a candidate key or superkey. This eliminates anomalies that can still exist in 3NF. BCNF is considered the ideal form for most databases but can sometimes lead to lossless decomposition issues. Most practical databases aim for 3NF as BCNF can be overly restrictive.

Answer: D. Eliminates all non-trivial functional dependencies where the determinant is not a candidate key

A characteristic of BCNF is that it eliminates all non-trivial functional dependencies where the determinant is not a candidate key. In other words, in BCNF, every determinant must be a candidate key. This is the defining characteristic and the strictest constraint of BCNF. First Normal Form eliminates repeating groups. Second Normal Form eliminates partial dependencies. Third Normal Form eliminates transitive dependencies. BCNF goes beyond 3NF by requiring that every determinant be a candidate key, not just non-key attributes determining other attributes.

Answer: B. Hiding implementation details

Answer: A. Rectangle

Answer: B. An attribute that uniquely identifies each tuple

Answer: B. Depends on another entity for identification

Answer: A. It has no repeating groups

Answer: B. It is in 1NF and has no partial dependencies

Answer: A. Structured Query Language

Answer: C. It is in 2NF and has no transitive dependencies

Answer: D. UPDATE

Answer: B. A virtual table based on a query

Answer: A. CREATE TABLE

Answer: C. INSERT

Answer: C. WHERE

Answer: A. Atomicity, Consistency, Isolation, Durability

ACID stands for Atomicity, Consistency, Isolation, and Durability. Atomicity means that a transaction's operations are all-or-nothing: either all are performed or none are. Consistency means that a transaction, when executed alone, takes the database from one valid state to another, preserving all defined integrity constraints. Isolation means that concurrent executions of transactions do not interfere in a way visible to each transaction; each transaction behaves as if it were executing alone. Durability means that once a transaction commits, its effects survive system crashes, typically ensured by writing to stable storage (logs, checkpoints). Together, these properties form the cornerstone of reliable transaction processing in database systems.

Answer: C. To coordinate concurrent access to data items so that the resulting schedule is serializable

Lock-based protocols (such as two-phase locking) use locks (shared and exclusive) to regulate which transactions can access which data items at what times. The idea is that operations that could conflict (for example, two writes to the same item, or a read and a write) are prevented from executing simultaneously by requiring one transaction to wait until another releases its lock. A well-designed locking protocol, especially strict two-phase locking, guarantees conflict-serializable schedules, meaning the effect of interleaved execution is equivalent to some serial order of the transactions. This preserves the Isolation property of ACID without sacrificing all concurrency.

Answer: B. Two transactions each holding a lock on one item and waiting for a lock on the other's item

Deadlock occurs when there is a circular wait among two or more transactions: each transaction holds a lock on some data item that the others need and simultaneously waits to acquire locks that will never be released because the waiting transactions cannot proceed. For example, T1 locks A and then requests B, while T2 locks B and then requests A. Neither can proceed, and both are blocked indefinitely. Deadlock handling strategies include prevention (ensuring one of the Coffman conditions never holds), avoidance (like wait-die and wound-wait schemes), detection (periodically building a wait-for graph and looking for cycles), and recovery (aborting one or more transactions to break the cycle).

Answer: B. To record changes so that the system can undo or redo them after a crash

A write-ahead log (WAL) records all modifications to the database before they are applied to the data pages on disk. Each log record typically specifies the transaction ID, the affected data item, and the old and new values. In case of a crash, the DBMS recovers by reading the log: undo records for transactions that had not committed (to roll back their partial effects) and redo records for committed transactions whose changes might not have reached stable storage. This ensures Atomicity (incomplete transactions are undone) and Durability (completed transactions are redone if necessary) even in the presence of system failures. Logging is central to modern recovery algorithms such as ARIES.

Answer: C. Isolation

Isolation is the ACID property dealing with concurrency anomalies. It ensures that concurrently executing transactions do not interfere with each other in a way that would reveal partial or intermediate states. Ideally, each transaction behaves as if it were executing alone on the system, yielding a schedule that is equivalent to some serial ordering of transactions (serializability). In practice, different isolation levels (such as Read Uncommitted, Read Committed, Repeatable Read, Serializable) provide different trade-offs between strict isolation and performance. Dirty reads, non-repeatable reads, and phantom reads are examples of phenomena controlled by appropriate isolation levels and concurrency control mechanisms like locking and timestamp ordering.

Answer: A. All or nothing

Atomicity ensures transaction either completes fully or not at all.

Answer: D. Concurrency

Concurrency is not transaction property; ACID properties are Atomicity, Consistency, Isolation, Durability.

Answer: B. Logs

It is advisable to store Logs before applying the actual transaction to the database. Transaction logging (write-ahead logging): (1) Before any transaction is applied to database, (2) Write information about transaction to permanent log/storage, (3) Then apply transaction to database. Why logs are essential: (1) Recovery - If system crashes, use logs to recover state, (2) Atomicity - Ensure all-or-nothing transaction property, (3) Durability - Transactions persisted permanently. ACID properties related to logging: (1) Atomicity - All-or-nothing via commit/rollback (uses logs), (2) Consistency - Data relationships maintained (logs track changes), (3) Isolation - Concurrent transaction separation (logs track order), (4) Durability - Permanent once committed (logs backed up). Log contents: (1) Transaction ID - Identifies specific transaction, (2) Operation type - INSERT, UPDATE, DELETE, (3) Before-image - Original values, (4) After-image - New values, (5) Timestamp - When operation occurred. Logging strategies: (1) Write-ahead logging (WAL) - Log written before change to database, (2) Undo logging - Can rollback (undo) transactions, (3) Redo logging - Can recover (redo) transactions, (4) Undo-redo logging - Supports both. Recovery process: (1) Redo transactions in log if not completed, (2) Undo transactions if not committed, (3) Database restored to consistent state. Practical implementation: (1) Transaction log on separate disk - Survives disk failures, (2) Log shadowing - Duplicate copies, (3) Log archiving - Historical records for audit. This is critical for database reliability and is standard in all enterprise databases.

Answer: B. Concurrent transactions produce the same result as if executed serially

Answer: A. Atomicity, Consistency, Isolation, Durability

Answer: B. Two or more transactions are waiting for each other to release locks

Answer: C. Recover from system failures

Answer: B. Ensuring serializability

Answer: C. Deadlock detection

Wait-for graph is used for deadlock detection by identifying cycles in resource waiting relationships.

Answer: C. Deadlock detection

Wait-for graph detects deadlock by identifying circular waits.

Answer: A. A program in execution

Answer: B. Threads share memory space while processes have separate memory spaces

Answer: B. System software

Answer: B. An instance of a program in execution, including its code, data, and execution context

A process is an active entity that represents a running program. It includes the program code (text segment), data segments (global, heap), stack, and the current execution context: register contents, program counter, and other OS-managed metadata such as open file descriptors and scheduling information. A program on disk is a passive entity (an executable file), while a process represents that program in motion. Multiple processes can be instances of the same program. The OS uses the Process Control Block (PCB) to store per-process state and to perform context switches among processes.

Answer: B. Threads within the same process share the same address space, while processes have separate address spaces

A process has its own virtual address space, including code, data, heap, and stack segments, and is isolated from other processes at the memory level. Threads are lighter-weight execution units that run within a process. All threads of a process share the same address space and many OS resources (such as open files), but each thread has its own stack and registers (i.e., its own execution context). This sharing makes context switches between threads cheaper than between processes and allows efficient inter-thread communication via shared variables, at the cost of requiring explicit synchronization (locks, semaphores, etc.) to avoid race conditions.

Answer: D. Preemptive priority scheduling without aging

In preemptive priority scheduling, the CPU is always assigned to the ready process with the highest priority. If new high-priority processes arrive frequently, low-priority processes may never get CPU time, a situation called starvation. Without aging (a technique that gradually increases the priority of waiting processes), these low-priority processes might be postponed indefinitely. FCFS and non-preemptive SJN do not cause starvation by design (though SJN can be unfair in other ways), while Round Robin ensures all ready processes eventually get time slices, preventing starvation at the expense of potential overhead due to frequent context switching.

Answer: B. A condition where the output depends on the relative timing of concurrent operations on shared data

A race condition occurs when two or more concurrent threads or processes access shared data, and at least one of them performs a write, without proper synchronization. The program's behavior then depends on the precise timing and interleaving of operations, which is usually unpredictable and non-deterministic. For example, if two threads increment a shared counter without atomic operations or locks, interleavings can cause increments to be lost. Proper synchronization mechanisms (critical sections, mutexes, semaphores, monitors) are needed to enforce mutual exclusion, ensuring that critical regions of code are not executed by more than one thread at the same time and thus avoiding race conditions.

Answer: B. Multitasking

Multitasking allows multiple processes to share single CPU.

Answer: A. Process independent

Process is independent; thread is subset of process sharing memory.

Answer: C. Round Robin

Round Robin is preemptive: each process gets time slice then preempted.

Answer: B. Different processes

fork() creates new child process separate from parent.

Answer: A. Mutual Exclusion

To enforce Mutual Exclusion, two functions are provided: enter-critical and exit-critical. Mutual exclusion ensures only one process/thread accesses shared resource at a time. Critical section: (1) Code segment accessing shared resource, (2) Only one process can execute at a time, (3) Protected by locks/semaphores. Enter-critical function: (1) Called before accessing shared resource, (2) If resource free, allows entry and locks it, (3) If resource locked, process waits/blocks. Exit-critical function: (1) Called after using shared resource, (2) Unlocks the resource, (3) Allows waiting process to acquire resource. Example pseudocode: process1: enter-critical(resource); access shared resource; exit-critical(resource); Implementation mechanisms: (1) Semaphores - Counter-based synchronization, (2) Mutexes - Binary lock/unlock, (3) Monitors - Higher-level synchronization, (4) Spinlocks - Busy-wait locking. Problems without mutual exclusion: (1) Race condition - Unpredictable results from concurrent access, (2) Data corruption - Inconsistent state, (3) Lost updates - One process overwrites another's changes. Related concepts: (1) Synchronization - Coordinate multiple processes (broader term), (2) Deadlock - Mutual waiting (different problem), (3) Starvation - Process never gets resource (different problem). Practical importance: (1) Database transactions - Concurrent access control, (2) Operating systems - Process/thread management, (3) Embedded systems - Shared hardware resources, (4) Multithreading - Thread-safe code. Modern solutions: (1) Locks (explicit), (2) Atomic operations (implicit), (3) Message passing - Avoids shared resources.

Answer: D. d) Race condition

If mutual exclusion is not enforced, a race condition can occur. Multiple processes access shared resources simultaneously, and the final result depends on the timing of access (the 'race'). This leads to inconsistent and unpredictable behavior. Mutual exclusion ensures only one process accesses a critical section at a time. Techniques like locks, semaphores, and monitors implement mutual exclusion to prevent race conditions.

Answer: A. Process

A Process has its own memory, stack, and code. Process Characteristics: (1) Independent execution unit, (2) Separate memory space, (3) Each has own stack, (4) Each has own code/text segment, (5) Protected from other processes. Process Memory Organization: (1) Text segment - Program code, (2) Data segment - Global variables, (3) Heap - Dynamic memory, (4) Stack - Function calls and local variables, (5) All isolated from other processes. How Processes Differ from Threads: (1) Thread - Shares memory with other threads in same process, (2) Thread - Has own stack but shared code/data, (3) Process - Completely isolated, (4) Process - Heavier resource usage. Process Structure: (1) Process ID (PID), (2) Program counter, (3) CPU registers, (4) Memory tables (page tables), (5) File descriptor table. Context Switch: (1) Saving current process state, (2) Loading new process state, (3) Expensive operation (thousands of cycles), (4) More overhead than thread switching. Protection: (1) Hardware memory management, (2) Memory protection prevents corruption, (3) One process crash doesn't affect others, (4) Isolation enforced by OS. Creation: (1) fork() in Linux creates new process, (2) CreateProcess() in Windows, (3) Inherits parent code/data by default. vs Threads: (1) Lightweight thread - Easy to create, (2) Heavy-weight process - More expensive to create, (3) Thread switching - Cheaper, (4) Process switching - More expensive. Containers vs Processes: (1) Containers use processes, (2) Containers share some OS resources, (3) Processes are fundamental unit. This is fundamental to operating system concepts.

Answer: C. Process scheduler

The process scheduler is the OS kernel component that manages process execution and resource allocation. It decides which process should run next, for how long (time slice/quantum), and allocates CPU time among competing processes. The scheduler implements scheduling algorithms like Round-Robin, Priority-Based, or SJF. Process scheduling is critical for system responsiveness and throughput. File manager handles file operations. Memory manager handles memory allocation. Device drivers handle hardware communication.

Answer: D. Sequential Operating System

Answer: B. To manage computer resources

Answer: A. A program in execution

Answer: B. Ready

Answer: B. Shortest Job First

Answer: B. A light-weight process

Answer: B. A segment of code that accesses shared resources

Answer: B. The outcome depends on the relative timing of events

Answer: B. Only one process can access a shared resource at a time

Answer: D. Idle

Answer: C. Saving the state of one process and loading the state of another

Answer: C. 19.9ms

EAT = 10 + 0.01 × (1000 - 10) = 10 + 9.9 = 19.9ms. This accounts for impact of page faults on average memory access time.

Answer: A. disk

Direct access is seen in disk storage where any location can be accessed directly without sequential traversal.

Answer: C. Operating system

Operating system manages virtual memory by maintaining page tables and handling page faults.

Answer: A. Page table

Page table in memory translates virtual addresses to physical addresses for virtual memory management.

Answer: C. Bootloader functions

BIOS performs system initialization and bootstrap operations during computer startup.

Answer: B. To speed up virtual-to-physical address translation

Answer: B. To translate virtual addresses to physical addresses

Answer: D. To map virtual memory addresses to physical memory addresses

Answer: A. Caching of frequently used data

Answer: C. Stores data in registers

Answer: B. Loading pages into memory only when they are actually referenced

Demand paging is a lazy loading strategy for virtual memory in which only those pages that a process actually accesses are brought into physical memory. Initially, many of a process's pages are marked as not present. When the CPU attempts to access such a page, a page fault occurs. The operating system then locates the page on disk (in the swap area or program file), brings it into a free frame, updates the page table, and resumes execution. This strategy can significantly reduce memory usage and startup time, especially for large programs that do not use all their pages. However, if the working set of pages does not fit in memory or if the replacement algorithm is poor, the system can thrash, spending most of its time handling page faults.

Answer: B. To map file names to file metadata (such as inode or file control block) and sometimes to their locations

A directory is a special type of file that stores entries associating file names with their metadata and sometimes disk location information. In Unix-like file systems, a directory maps file names to inode numbers, and the inode then contains information about file type, permissions, owner, size, timestamps, and disk block addresses. This separation allows multiple directory entries (hard links) to reference the same inode. In other systems, the directory may store a full file control block (FCB) with all metadata and pointers. Directories allow hierarchical naming: users perceive a tree of directories and files, while the file system translates these paths into specific metadata structures and disk blocks.

Answer: B. Linked allocation

In linked allocation, each file is a linked list of disk blocks. Each block contains a pointer to the next block in the file. The directory entry stores the starting block (and sometimes the last block) for each file. This scheme eliminates external fragmentation, since any free block can be used, and file size can grow dynamically. However, random access is inefficient because to reach the k-th block of a file, the system must follow k − 1 pointers from the start, leading to O(k) access. To improve this, some systems maintain a File Allocation Table (FAT) in memory that stores these links centrally, allowing faster traversal and partial indexing.

Answer: B. Loading the kernel into memory, initializing device drivers, mounting file systems, and starting system services

During boot, the firmware (BIOS or UEFI) initializes basic hardware and locates a bootloader. The bootloader then loads the operating system kernel into memory, transfers control to it, and the kernel proceeds to initialize core subsystems (memory management, process scheduler), load and initialize device drivers, mount root and other essential file systems, and start system services or daemons (such as logging, networking, and display managers). Only after these steps does the system present a login prompt or graphical login to the user. Shutdown performs the reverse: stopping services, syncing and unmounting file systems, and powering off safely to avoid data loss.

Answer: C. Operating System

Operating system manages virtual memory through page tables.

Answer: B. /etc/init.d

/etc/init.d scripts initialize system services.

Answer: B. Standard User account

You should create a Standard User account if you want to require that users enter an Administrator password to perform administrative tasks. User account types in Windows: (1) Administrator account - Full unrestricted system access, no prompt needed for admin tasks, (2) Standard account - Limited permissions, prompted for admin password (UAC prompt) to perform admin tasks, (3) Power User - Intermediate privileges (less common in modern Windows), (4) Guest account - Very limited, temporary access. Standard User account benefits: (1) Security - Limits unintended system changes, (2) Protection from malware - Restricted from modifying system files, (3) User privilege separation - Standard vs admin tasks, (4) Audit trail - Admin actions logged separately. UAC (User Account Control) mechanism: (1) Standard user attempts admin task, (2) UAC prompt appears requesting admin credentials, (3) Admin password entered, (4) Task elevated and executed. Security implications: (1) Administrator accounts - Only for actual administrators, (2) Standard accounts - Most users should use these, (3) Run with lowest necessary privileges - Security principle, (4) Separate daily work account from admin account - Best practice. Real-world usage: (1) Enterprise environments - Users in Standard group, (2) Personal computers - Should have standard account for daily use, admin account for maintenance. Administrative task examples: (1) Install/uninstall software, (2) Modify system settings, (3) Access protected files, (4) Manage other user accounts. This principle of least privilege is fundamental to system security.

Answer: D. d) A process tries to access a page not in memory

A page fault occurs when a process tries to access a page not in memory (RAM). The memory management unit detects this and generates an interrupt. The OS then loads the required page from disk (virtual memory) into physical memory, possibly replacing another page. This mechanism allows systems to use more virtual memory than physical memory. Excessive page faults cause thrashing and performance degradation.

Answer: B. Transferring a process between main memory and secondary storage

Swapping in operating systems is the process of transferring an entire process (including its code, data, and stack) between main memory (RAM) and secondary storage (hard disk). When memory is needed, the OS swaps out a less-used process to disk, freeing RAM for other processes. When the swapped-out process is needed, it's swapped back into RAM. Swapping enables systems to run processes larger than physical memory and to manage limited memory resources. However, swapping is slow due to disk I/O. Paging is a related but more efficient technique that swaps memory pages rather than entire processes.

Answer: B. A technique that allows execution of processes that may not be completely in memory

Answer: A. Loading pages into memory only when they are needed

Answer: B. A process accesses a page not in memory

Answer: B. A named collection of related information

Answer: B. A special type of file that contains file names and pointers

Answer: A. Contiguous, linked, and indexed allocation

Answer: B. Wasted space due to allocation methods

Answer: C. Application development