Data Structures and Algorithm, Database System 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: B. The upper bound on the growth rate of an algorithm's time or space as input size tends to infinity

Big-O notation, written as O(f(n)), provides an asymptotic upper bound on how an algorithm's resource usage (time or space) grows with input size n. It captures the dominant term of a complexity function and discards constant factors and lower-order terms. For example, if an algorithm takes T(n) = 3n^2 + 5n + 20 steps, we say T(n) = O(n^2) because, for sufficiently large n, n^2 dominates the growth. Big-O is typically used for worst-case analysis: for instance, worst-case time of insertion sort is O(n^2). Complementary notations are Big-Omega Ω(f(n)), which gives an asymptotic lower bound, and Big-Theta Θ(f(n)), which simultaneously gives both an asymptotic upper and lower bound, tightly characterizing growth. Mastering these notations is essential for comparing algorithms independently of specific hardware or implementation details.

Answer: B. Θ(n log n)

The time complexity T(n) = 5n log n + 2n + 100 consists of three terms. Among these, n log n grows faster than n and any constant as n → ∞. The coefficient 5 does not affect the asymptotic class. Therefore, T(n) is in O(n log n) (upper bound) and Ω(n log n) (lower bound), which together imply T(n) = Θ(n log n). A Θ bound means that n log n both upper-bounds and lower-bounds T(n) up to constant factors. This kind of reasoning is standard when analyzing divide-and-conquer algorithms like mergesort and heapsort, which typically have Θ(n log n) time complexity.

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. Doubly linked list

In a doubly linked list, each node maintains two pointers: one to the next node and one to the previous node. This structure allows traversal in both forward and backward directions by following next and prev pointers respectively. It also makes certain operations such as deletion of a known node easier, because you can directly access both its predecessor and successor without a separate search. A singly linked list only stores next pointers, so to move backward you would have to start again from the head or maintain auxiliary structures. Circular lists alter the boundary behavior (last node points back to first) but do not inherently add backward traversal unless they are circular doubly linked lists.

Answer: B. It allows easily cycling through all nodes from any starting node without hitting a null pointer

In a circular linked list, the last node points back to the first node instead of storing a null next pointer. This makes the list logically circular. As a result, if you start from any node and keep following next pointers, you will eventually return to the starting node after visiting all others, and you will never hit a null. This property is useful in applications like round-robin scheduling, buffer management, or games where you conceptually move around a ring of elements. However, circular lists do not by themselves improve time complexity for search or insertion; they mostly affect boundary conditions and traversal patterns.

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: B. In-order traversal

For a Binary Search Tree, by definition all keys in the left subtree of a node are less than the node’s key and all keys in the right subtree are greater. An in-order traversal (Left, Root, Right) recursively visits all nodes in the left subtree, then the node itself, then all nodes in the right subtree. Because of the BST ordering property, this yields the keys in non-decreasing sorted order. This property is fundamental: many BST-based algorithms rely on in-order traversal to output sorted sequences or to check that a tree maintains the BST invariant.

Answer: B. The height of the node's left subtree minus the height of its right subtree

The balance factor of a node in an AVL tree is defined as BF(node) = height(left subtree) − height(right subtree). For an AVL tree, this balance factor must be −1, 0, or +1 for every node. If insertion or deletion causes the balance factor of some node to go outside this range, the tree is rebalanced by performing one or more rotations (LL, RR, LR, RL) to restore the AVL property. By maintaining strictly bounded imbalance, AVL trees guarantee that the tree height stays in O(log n), providing O(log n) worst-case time for search, insertion, and deletion, unlike plain BSTs which can degenerate to O(n) height in pathological cases.

Answer: B. AVL tree

An AVL tree is a self-balancing binary search tree in which the height difference (balance factor) between the left and right subtrees of any node is at most 1. After every insertion or deletion, the tree is checked for balance factor violations; if found, local tree rotations (single or double) are performed to restore the AVL property. Because the height of an AVL tree with n nodes remains O(log n), searching, inserting, and deleting all take O(log n) in the worst case. In contrast, an unbalanced BST can degenerate into a chain with O(n) height. Hash tables typically have O(1) expected-time operations but not the strict worst-case logarithmic bound, and they do not maintain a sorted key order.

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: B. b) Last node

In a circular doubly linked list, the previous pointer of the first node points to the last node. This creates a circle where the last node's next pointer also points back to the first node. This structure allows traversal in both directions without reaching a null pointer. It's useful for round-robin scheduling and playlist applications where you need to loop through elements.

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. A balanced binary search tree

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

Answer: A. Big Oh (O)

Answer: D. Binary Linked List

Answer: C. ⌊log₂n⌋

Answer: B. Pre-order

Answer: A. O(1)

Answer: C. O(n²)

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

Answer: A. Transitive closure

Warshall's algorithm computes the transitive closure of a directed graph, determining path existence between all vertex pairs.

Answer: A. Greedy

Dijkstra's shortest path uses greedy paradigm.

Answer: A. Transitive closure

Warshall's algorithm computes transitive closure of directed graph.

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: B. To map keys to array indices in a way that spreads them out uniformly

A hash function h(key) takes a key (for example, a string, integer, or other object) and computes an integer index within the bounds of the hash table array. A good hash function distributes keys approximately uniformly across the table to minimize the number and length of collisions (when different keys map to the same index). Ideal hashing would give O(1) expected time for lookup, insertion, and deletion, but in practice some collisions are unavoidable. Collision resolution strategies (like chaining or open addressing) are used in combination with the hash function. While cryptographic hash functions also map arbitrary data to fixed-size outputs, hash tables typically use faster non-cryptographic hash functions designed for uniform distribution rather than security.

Answer: C. Separate chaining

In separate chaining, each index (bucket) of the hash table stores a pointer to a linked list (or another structure like a balanced tree). All keys that hash to the same index are inserted into that list. Lookup and deletion involve traversing only the list for that bucket. If the load factor (n / table_size) remains bounded (by resizing when too large), the expected length of each chain remains constant, keeping average operation times near O(1). This method is simple to implement and works well when the underlying memory allocator handles small allocations efficiently. Open addressing schemes like linear probing, quadratic probing, and double hashing instead store all keys directly in the array and resolve collisions by probing alternative indices.

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: B. Kruskal's algorithm

Kruskal's algorithm is a greedy algorithm for finding a minimum spanning tree in a connected weighted undirected graph. It sorts all edges in non-decreasing order of weight and then, starting from an empty forest, repeatedly adds the lightest edge that does not form a cycle until all vertices are connected. Cycle detection is typically implemented with a disjoint-set (union–find) data structure. Prim's algorithm is another MST algorithm that grows a tree from an arbitrary root by repeatedly selecting the minimum-weight edge that connects a visited vertex to an unvisited vertex. Dijkstra's and Bellman–Ford are shortest-path algorithms, and Warshall's algorithm computes transitive closure/all-pairs reachability.

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. Warshall's algorithm

Warshall's algorithm (often called Floyd–Warshall when extended to weighted graphs) computes the transitive closure of a directed graph, meaning it determines for every pair of vertices (i, j) whether there exists a path from i to j. Using an adjacency matrix representation, it iteratively updates reachability information by allowing intermediate vertices in paths. At each step k, it checks whether going from i to j via k gives a new reachable path. The algorithm runs in O(V^3) time for a graph with V vertices and is especially suitable when V is relatively small and the graph is dense. For sparse graphs, repeated DFS or BFS from each vertex may be more efficient.

Answer: B. An ordering of vertices such that for every directed edge u → v, u appears before v in the ordering

A topological sort of a DAG is a linear ordering of its vertices such that if there is a directed edge u → v, then u precedes v in the order. This is possible only if the graph has no cycles. Topological ordering is fundamental in scheduling tasks with dependencies, resolving symbol dependencies in compilers, and evaluating circuits. Standard algorithms to compute such an order use DFS (recording vertices in reverse post-order) or Kahn’s algorithm (repeatedly removing nodes with zero in-degree). Both rely on the acyclic nature of the graph.

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. h(k) = k mod m

The division method hash function is: h(k) = k mod m, where k is the key and m is the hash table size. Division method characteristics: (1) Simple to implement - Just one modulo operation, (2) Fast computation - Direct calculation, (3) Widely used - Common in practice. How it works: (1) Divide key by table size (m), (2) Remainder is hash value, (3) Result is between 0 and m-1 (valid table indices). Example: (1) Table size m = 10, (2) Key k = 23, (3) h(23) = 23 mod 10 = 3, (4) Key stored at index 3. Choosing m (table size): (1) Avoid m as power of 2 - Poor distribution for binary keys, (2) Avoid m as power of 10 - Poor distribution for decimal keys, (3) Use prime number - Generally provides good distribution, (4) Example: m = 11, 13, 17, 19, 23 (primes) work well. Hash function quality: (1) Uniform distribution - Keys spread evenly across table, (2) Deterministic - Same key always produces same hash, (3) Fast computation - O(1) time. Load factor: (1) λ = n/m (n = number of keys, m = table size), (2) Affects collision frequency, (3) Typically keep λ < 0.75. Other hash methods: (1) Multiplication method - h(k) = ⌊m(kA mod 1)⌋, (2) Universal hashing - Multiple hash functions. Collision resolution: (1) Chaining - Store colliding keys in linked list, (2) Open addressing - Find another empty slot (linear probing, quadratic probing, double hashing). The division method is practical despite its simplicity.

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: A. Two different keys hash to the same value

Answer: B. Fast data retrieval

Answer: C. Dijkstra's algorithm

Answer: C. Directed acyclic graph

Answer: B. Breadth-First Search

Answer: A. A tree that connects all vertices with minimum total edge weight

Answer: C. O(n)

Answer: D. Sorting

Answer: A. O(V²)

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: C. Selection (σ) over a Cartesian product (×) of relations

In basic relational algebra, the FROM clause that lists multiple tables corresponds to the Cartesian product of those relations. The WHERE clause then restricts the rows via selection (σ) with a predicate. Finally, the SELECT clause projects specific attributes (π). Thus, a simple SQL query like SELECT A.x, B.y FROM A, B WHERE A.id = B.id AND A.z > 10 is represented as π_{x,y}(σ_{A.id = B.id ∧ A.z > 10}(A × B)). Modern relational algebra adds explicit join operators, but joins are logically definable as selection over Cartesian product. Understanding this mapping is crucial for reasoning about query optimization and expressing queries formally.

Answer: C. To choose an efficient physical execution plan for a given logical query expression

Query optimization takes a logical query (usually an algebraic expression derived from SQL) and explores alternative physical execution plans (different join orders, join algorithms, index usage, and access paths) to minimize estimated cost (I/O, CPU, memory). The optimizer uses statistics about table sizes, value distributions, and index selectivity to estimate costs of various plans. It then picks a near-optimal plan. The logical meaning of the query does not change; only the method of evaluation does. Effective query optimization is crucial to performance in large-scale database systems where naive plans could be orders of magnitude slower.

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: A. A procedural query language

Answer: B. Improve query execution efficiency

Answer: C. 4NF

Answer: C. WHERE

Answer: B. A stored procedure that automatically executes when an event occurs

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: A. A program in execution

Answer: B. Process synchronization

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

Answer: C. Spinlocks

Answer: C. Mutex is owned by a thread and only that thread can release it

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. Semaphore

A semaphore is an abstract data type that maintains a non-negative integer value and supports two atomic operations: wait (P) and signal (V). A wait operation decrements the semaphore if it is positive or blocks the calling process if it is zero; a signal operation increments the semaphore and may wake up a blocked process. A binary semaphore (value 0 or 1) can implement mutual exclusion by allowing only one process into a critical section at a time. Counting semaphores generalize this to allow up to N concurrent entries. Semaphores are powerful but can be error-prone if misused (for example, forgetting to signal), so higher-level constructs like monitors and mutex locks are often preferred in modern systems.

Answer: C. Dining Philosophers problem

The Dining Philosophers problem, introduced by Dijkstra, involves a number of philosophers sitting around a table with one fork between each pair. To eat, a philosopher needs to hold both forks adjacent to them. If each philosopher picks up one fork and waits for the other, a deadlock can occur. Solutions must balance mutual exclusion (only one philosopher may use a fork at a time) with avoidance of deadlock and starvation (some philosophers never getting to eat). The problem is often used to illustrate subtleties in lock acquisition ordering, resource hierarchy, and fairness in scheduling. Producer–Consumer and Readers–Writers are also classical problems but with different characteristics and solutions.

Answer: C. Deadlock detection

Wait-for graph detects deadlock by identifying circular waits.

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: A. Semaphores

Semaphores and mutexes prevent race conditions in shared resources.

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: C. Process synchronization

Answer: A. A mutex can only be used for mutual exclusion, while a semaphore can be used for both mutual exclusion and synchronization

Answer: D. All of these

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. Least Recently Used (LRU)

The Least Recently Used (LRU) page replacement algorithm selects for eviction the page that has not been referenced for the longest time in the past, based on the heuristic that pages used recently are likely to be used again soon (temporal locality). LRU is not the optimal algorithm (which would require knowledge of the future), but it is a good practical approximation. Implementing exact LRU can be expensive, requiring tracking usage order precisely, so real systems often use approximations such as the Clock algorithm or NFU (Not Frequently Used). FIFO replaces the oldest loaded page, which can perform poorly (Belady's anomaly). Optimal (Belady's algorithm) is theoretical, replacing the page that will not be used for the longest time in the future.

Answer: B. Wasted space inside an allocated block due to fixed-size allocation units

Internal fragmentation occurs when memory is allocated in fixed-size units (such as fixed-size partitions or pages), and a process does not use the entire allocated unit. For example, if the system allocates memory in 4 KB pages and a process segment needs 6 KB, it will use two pages (8 KB), leaving 2 KB unused but reserved within the second page. This unused space cannot be allocated to other processes and is thus wasted internally. External fragmentation, by contrast, refers to small free holes scattered between allocated blocks that are collectively large enough to satisfy a request but not contiguous. Paging eliminates external fragmentation but not internal fragmentation; segmentation has the opposite trade-offs.

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: A. Oldest chosen

FIFO replaces oldest page first in memory management.

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: C. Page replacement

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