Chapter 7: Data Structures, Database and Operating System¶
Syllabus: AEiE07
Coverage: AEiE0701 through AEiE0706
Status: DRAFT - syllabus and assigned-question pass complete; independent source audit pending
Exam use: Recall, ADT recognition, complexity comparison, normalization, transaction, and OS-memory-management MCQs
Chapter map¶
| Code | Area | Fast recognition cue |
|---|---|---|
AEiE0701 |
Data structure and algorithm | ADT, stack, queue, lists, linked list, trees |
AEiE0702 |
Sorting, searching, and graphs | Complexity, stability, DFS/BFS, Dijkstra |
AEiE0703 |
Data modeling | ER model, keys, dependencies, normal forms, SQL classes |
AEiE0704 |
Transaction processing, concurrency control and crash recovery | ACID, serializability, locks, deadlocks, logs |
AEiE0705 |
Operating system and process management | Process, thread, scheduling, race, mutual exclusion |
AEiE0706 |
Memory management, file systems and system administration | Paging, virtual memory, file systems, admin tasks |
Chapter rapid-revision sheet¶
| Topic | Must-remember cue |
|---|---|
| ADT | Defines operations, not representation |
| Stack and queue | LIFO vs FIFO |
| Binary search | Requires sorted random-access sequence |
| BFS / DFS | Queue vs stack or recursion |
| Dijkstra | Greedy, nonnegative weights only |
| Sorting comparison | Merge stable + extra space; heap in-place + unstable |
| Schema vs instance | Design vs current contents |
| Normal forms | 1NF atomic, 2NF no partial, 3NF no transitive, BCNF determinant is super key |
| ACID | Atomicity, Consistency, Isolation, Durability |
| Locks | Shared read, exclusive write |
| Process vs thread | Resource owner vs lightweight execution path |
| Scheduling | Round robin identified by time quantum |
| Paging | Page virtual, frame physical |
| Demand paging | Load on first use |
| File allocation | Contiguous, linked, indexed trade-offs |
Assigned-question audit¶
| Target | Deciding fact | Result |
|---|---|---|
set1-037 |
a stack follows LIFO | Supported by AEiE0701 |
set1-038 |
binary search repeatedly halves a sorted random-access search interval | Supported by AEiE0702 |
set1-039 |
a weak entity lacks a complete key of its own | Supported by AEiE0703 |
set1-040 |
avoidance grants requests only while the resulting allocation remains safe | Supported by AEiE0704 |
set1-041 |
many-to-many maps many user threads over a smaller or equal number of kernel threads | Supported by AEiE0705 |
set1-042 |
demand paging loads a page when referenced | Supported by AEiE0706 |
set1-085 |
stack and queue are ADTs defined by operations rather than one representation | Supported by AEiE0701 |
set1-086 |
DFS uses an explicit stack or recursion's call stack | Supported by AEiE0702 |
set1-087 |
a weak entity depends on an owner and has a partial key | Supported by AEiE0703 |
set1-088 |
in a conventional local-disk boot, the bootloader loads the kernel from secondary storage into RAM | Supported by AEiE0706 |
Sources and verification note¶
- Coverage authority: NEC syllabus in
syllab.mdforAEiE0701throughAEiE0706. - Recommended data-structure verification: Horowitz, Sahni, and Anderson-Freed, Fundamentals of Data Structures in C; Cormen et al., Introduction to Algorithms.
- Recommended database verification: Korth, Silberschatz, and Sudarshan, Database System Concepts; Elmasri and Navathe, Fundamentals of Database Systems.
- Recommended operating-system verification: Silberschatz, Galvin, and Gagne, Operating System Concepts; Tanenbaum and Bos, Modern Operating Systems.
- Verification posture: this is a review-dense first edition aimed at recall, concept discrimination, and light calculations. Conditions that are often dropped in weak model keys, such as binary-search prerequisites and exact normalization meanings, are stated explicitly here.