PPSC Lecturer Test Computer Science (Subject Specialist Portion) Syllabus

What is the difference between a stack and a queue?

A stack is LIFO (add and remove from the same end/top); a queue is FIFO (add at rear, remove from front).

What is a linked list and what are its advantages over arrays?

A linear collection of nodes where each node holds data and a pointer to the next. Advantages: dynamic size and O(1) insertion/deletion without shifting elements.

Differentiate between a singly linked list, doubly linked list, and circular linked list.

Singly: each node points to the next only. Doubly: each node has pointers to both next and previous. Circular: the last node points back to the first node.

What is a binary tree and a binary search tree (BST)?

A binary tree is a tree where each node has at most two children. A BST is a binary tree where the left subtree holds smaller values and the right subtree holds larger values than the node.

Name the three depth-first tree traversal orders and the visiting sequence of each.

Inorder (Left, Root, Right), Preorder (Root, Left, Right), and Postorder (Left, Right, Root).

What is a graph, and how do an undirected and a directed graph differ?

A graph is a set of vertices connected by edges. In an undirected graph edges have no direction; in a directed graph (digraph) edges have a direction (from one vertex to another).

What are the two common ways to represent a graph, and their space costs?

Adjacency matrix (O(V^2) space, fast edge lookup) and adjacency list (O(V+E) space, efficient for sparse graphs).

Compare BFS and DFS graph traversals.

BFS (Breadth-First Search) explores level by level using a queue; DFS (Depth-First Search) explores as deep as possible using a stack or recursion.

How does linear search work and what is its time complexity?

It checks each element sequentially until the target is found or the list ends. Time complexity is O(n); works on unsorted data.

How does binary search work, what is its precondition, and its time complexity?

It repeatedly halves a sorted array, comparing the target with the middle element. Precondition: the array must be sorted. Time complexity is O(log n).

State the best, average, and worst-case time complexity of Bubble Sort.

Best: O(n) (already sorted, with optimization); Average and Worst: O(n^2). Space: O(1).

State the average and worst-case time complexity of Quick Sort, and when the worst case occurs.

Average: O(n log n); Worst: O(n^2), which occurs with poor pivot choice (e.g., already sorted data with the first/last element as pivot).

What is the time complexity of Merge Sort in all cases, and is it stable?

O(n log n) in best, average, and worst cases; it is stable. Space complexity is O(n).

Compare Selection Sort and Insertion Sort.

Selection Sort repeatedly selects the minimum and places it in order (O(n^2), not stable, fewer swaps). Insertion Sort builds the sorted list by inserting each element into its correct position (O(n^2), stable, fast for nearly sorted data).

What is Big-O notation?

An asymptotic notation describing the upper bound (worst-case growth rate) of an algorithm's running time or space as the input size grows.

Order these complexities from fastest to slowest growth: O(n^2), O(1), O(n log n), O(log n), O(n), O(2^n).

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n).

Differentiate Big-O, Big-Omega (Ω), and Big-Theta (Θ).

Big-O is the upper bound (worst case), Big-Omega is the lower bound (best case), and Big-Theta is the tight bound (both upper and lower).

In OOP, what is the difference between a class and an object?

A class is a blueprint/template defining attributes and methods; an object is a concrete instance of a class with actual values in memory.

What is a constructor and a destructor?

A constructor is a special method automatically called when an object is created to initialize it; a destructor is called when an object is destroyed to release resources.

What is inheritance in OOP and what is its main benefit?

A mechanism where a child (derived) class acquires the properties and methods of a parent (base) class. Main benefit: code reusability and establishing an is-a relationship.

What is polymorphism, and what are its two main types?

Polymorphism means 'many forms' - the ability of one interface to behave differently. Types: Compile-time (static, via method/operator overloading) and Run-time (dynamic, via method overriding/virtual functions).

What is the difference between method overloading and method overriding?

Overloading: same method name with different parameter lists in the same class (compile-time). Overriding: redefining a parent class method in a child class with the same signature (run-time).

What is encapsulation in OOP?

The bundling of data (attributes) and the methods that operate on them into a single unit (class), and restricting direct access to internal data using access modifiers (data hiding).

What is abstraction, and how does it differ from encapsulation?

Abstraction hides implementation complexity and shows only essential features (the 'what'). Encapsulation hides data by wrapping it with methods (the 'how' is protected). Abstraction is design-level; encapsulation is implementation-level.

Name the common access specifiers in OOP and their visibility.

Public (accessible everywhere), Private (accessible only within the class), and Protected (accessible within the class and its derived classes).

What is a DBMS and what are its key advantages over file systems?

A Database Management System is software to define, store, manage, and query data. Advantages: reduced data redundancy, data integrity, security, concurrent access, and backup/recovery.

What are the three levels of the ANSI-SPARC database schema architecture?

Internal (physical) level, Conceptual (logical) level, and External (view) level - providing physical and logical data independence.

Name three database data models.

Hierarchical model, Network model, and Relational model (also Object-oriented and Entity-Relationship models).

In the relational model, define: relation, tuple, attribute, and degree.

Relation = a table; Tuple = a row/record; Attribute = a column/field; Degree = the number of attributes (columns) in a relation.

Differentiate between a primary key, a candidate key, and a foreign key.

A candidate key uniquely identifies a tuple; the primary key is the chosen candidate key (unique, non-null); a foreign key is an attribute referencing the primary key of another table to enforce referential integrity.

In an ER diagram, what shapes represent an entity, an attribute, and a relationship?

Entity = rectangle; Attribute = ellipse/oval; Relationship = diamond.

What are the three types of cardinality in ER relationships?

One-to-One (1:1), One-to-Many (1:N), and Many-to-Many (M:N).

Differentiate the SQL commands DDL, DML, and DCL with examples.

DDL (Data Definition): CREATE, ALTER, DROP. DML (Data Manipulation): SELECT, INSERT, UPDATE, DELETE. DCL (Data Control): GRANT, REVOKE.

What is the difference between WHERE and HAVING clauses in SQL?

WHERE filters individual rows before grouping; HAVING filters groups after GROUP BY (used with aggregate functions like SUM, COUNT).

Differentiate INNER JOIN, LEFT JOIN, and FULL OUTER JOIN.

INNER JOIN returns only matching rows from both tables; LEFT JOIN returns all rows from the left table plus matches; FULL OUTER JOIN returns all rows from both tables, with NULLs where no match exists.

What is normalization and why is it performed?

Normalization is the process of organizing data to reduce redundancy and eliminate insertion, update, and deletion anomalies by decomposing tables into well-structured relations.

State the requirements of 1NF, 2NF, and 3NF.

1NF: atomic (indivisible) values, no repeating groups. 2NF: 1NF plus no partial dependency (non-key attributes fully depend on the whole primary key). 3NF: 2NF plus no transitive dependency (non-key attributes don't depend on other non-key attributes).

What is BCNF (Boyce-Codd Normal Form)?

A stronger version of 3NF where for every non-trivial functional dependency X -> Y, X must be a superkey. It removes anomalies that 3NF cannot.

What is a process in an operating system, and how does it differ from a program?

A process is a program in execution, with its own state, memory, and resources. A program is a passive set of instructions on disk; a process is its active, running instance.

Name the states in a typical process life cycle.

New, Ready, Running, Waiting (Blocked), and Terminated.

What is the difference between preemptive and non-preemptive scheduling?

In preemptive scheduling the CPU can be taken from a running process (e.g., Round Robin, SRTF); in non-preemptive scheduling a process keeps the CPU until it completes or blocks (e.g., FCFS, non-preemptive SJF).

Define turnaround time and waiting time in CPU scheduling.

Turnaround time = completion time minus arrival time (total time in system). Waiting time = turnaround time minus burst (execution) time (time spent waiting in the ready queue).

What scheduling problem does the Round Robin algorithm solve, and what key parameter does it use?

It provides fair, time-shared CPU allocation to prevent starvation. Its key parameter is the time quantum (time slice) given to each process in turn.

What is the difference between logical and physical address space?

Logical (virtual) address is generated by the CPU as seen by a process; physical address is the actual location in main memory. The MMU maps logical to physical addresses.

What is paging and what problem does it solve?

Paging divides logical memory into fixed-size pages and physical memory into frames, mapped via a page table. It eliminates external fragmentation and allows non-contiguous allocation.

Differentiate internal fragmentation from external fragmentation.

Internal fragmentation is unused space within an allocated block (e.g., partial page). External fragmentation is unused space scattered between allocated blocks, too small to use.

What is virtual memory and what technique commonly implements it?

Virtual memory lets programs use more memory than physically available by keeping only needed parts in RAM. It is commonly implemented using demand paging (loading pages from disk only when needed).

What is a page fault?

An interrupt that occurs when a program accesses a page that is mapped in virtual memory but not currently loaded in physical memory, requiring the OS to fetch it from disk.

What is a deadlock, and what are the four Coffman necessary conditions for it to occur?

A deadlock is when a set of processes are blocked, each holding a resource and waiting for another held by another. Conditions: Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait.

Name the strategies for handling deadlocks.

Deadlock Prevention, Deadlock Avoidance (e.g., Banker's Algorithm), Deadlock Detection and Recovery, and Ignoring the problem (Ostrich algorithm).

What is the critical section problem, and what three requirements must a solution satisfy?

The critical section is the code segment accessing shared resources. A valid solution must ensure Mutual Exclusion, Progress, and Bounded Waiting.

What is a semaphore, and what are its two atomic operations?

A semaphore is an integer variable used for process synchronization. Its two atomic operations are wait/P (decrement) and signal/V (increment).

What is the difference between a mutex and a semaphore?

A mutex is a locking mechanism allowing only one thread into a critical section (ownership-based, binary). A semaphore is a signaling mechanism that can allow multiple threads (counting) and has no ownership.