Data Structures Fundamentals: 329 MCQs with answers

At compile time

Static data structures allocate memory at compile time, meaning the size is fixed before the program runs.

Linked list

A linked list is dynamic because nodes are created at runtime and can be added or removed.

Faster access due to contiguous memory

Static structures use contiguous memory, enabling direct indexing and faster access.

The size is fixed

Static refers to the fixed size, not immutability of values. You can modify elements but not the number of elements.

They are slower to access due to pointer traversal

Dynamic structures often use non-contiguous memory, so accessing elements requires following pointers, which is slower.

free()

free() is used to release memory that was previously allocated with malloc() or calloc().

Storing the 12 months of a year

When the data size is known and fixed, like 12 months, a static array is efficient and simple.

Memory that is allocated but never freed

A memory leak occurs when dynamically allocated memory is not freed, gradually exhausting available memory.

They can be contiguous while still being dynamic in size

Dynamic arrays use contiguous memory but can resize at runtime using realloc, so they combine contiguity with flexibility.

They can handle variable and large data sizes

Real-world data sizes are often unpredictable, so dynamic structures provide the scalability and flexibility needed.

True

Static refers to the fixed size, not immutability. You can modify elements in a static array.

False

While linked lists are non-contiguous, dynamic arrays can use contiguous memory while still being dynamic in size.

—

This is the core distinction based on memory allocation time and size flexibility.

—

These have fixed sizes determined at compile time.

—

These can grow or shrink at runtime by allocating and deallocating nodes.

—

Contiguous memory enables O(1) access to any element by index.

—

Manual memory management adds complexity and risk.

—

These are standard library functions for runtime memory allocation.

—

This illustrates the fixed-size nature and potential wastage.

—

Nodes are scattered in RAM and connected via pointers.

42

A data item is a single unit of value, like 42. Student record, file, and group are collections.

A collection of related data items

A group item is a collection of related data items, like a point (x, y). A file is a collection of records, not a group item.

Field

A field is a single attribute of a record. 'Name' is one attribute, so it's a field.

A logical model for organizing data

A data structure is a logical model for organizing data for efficient access and modification. Storage structure is the physical layout.

Contiguous memory

An array uses contiguous memory locations, while a linked list uses scattered memory with pointers.

Compile

Compile is a programming language operation, not a data structure operation. Insert, delete, search, and traverse are common operations.

A record

The struct defines a record with fields. An array of such structs would be a file.

An array of student records

A file is a collection of related records. An array of student records is a file.

Insertion only requires updating pointers

In a linked list, insertion only requires updating pointers, avoiding the need to shift elements as in an array. This makes insertion faster.

The data structure is abstract; the storage structure is concrete

A data structure is a logical model (abstract), while a storage structure is the physical implementation (concrete).

Data item -> Group item -> Record -> File

The hierarchy is data item (smallest) -> group item -> record -> file (largest).

False

A data structure is a logical model, while a storage structure is the physical implementation. They are distinct concepts.

True

This is the standard definition: a record is a complete collection of fields, and a file is a collection of related records.

—

Data is the general term for raw values.

—

A data item is a specific single value.

—

Group items combine related data items.

—

Fields are the individual attributes.

—

A record represents one entity with all its attributes.

—

Files group related records together.

—

It's the abstract organization of data.

—

It's the physical implementation in memory.

—

These are the basic operations.

A specialized format for organizing, storing, and managing data

A data structure is a specialized format for organizing, storing, and managing data efficiently. It is not a language feature, algorithm, or hardware.

Compile

Common operations include insert, delete, search, traverse, and sort. Compiling is a process of translating code, not an operation on data structures.

In contiguous memory locations

Arrays store elements in contiguous memory locations, meaning elements are placed next to each other. This allows direct access by index.

Linked list

A linked list stores elements in scattered memory locations, with each element containing a pointer to the next element. Arrays use contiguous memory.

It brings efficiency, clarity, and organization to programs

Data structures organize data so that operations become efficient and code becomes clear and maintainable. They do not always use less memory and still require algorithms.

Direct

Direct access uses an index to retrieve an element immediately, as in arrays. Sequential access requires traversing elements one by one.

Data structures organize data; algorithms manipulate data

Data structures define how data is organized, while algorithms are step-by-step procedures to process that data. They work together.

Undo feature in a text editor

Stacks are used for undo features because they follow Last-In-First-Out (LIFO) order, allowing the most recent action to be undone first.

Arrays allow fast access by index but slow insert/delete; linked lists allow fast insert/delete but slow access by index

Arrays provide O(1) access by index but require shifting elements for insert/delete. Linked lists allow O(1) insert/delete at known positions but require traversal for access.

It balances memory usage and performance for the required operations

Different data structures have different strengths and weaknesses. Choosing the right one optimizes memory usage and performance for the specific operations needed.

Graph

Graphs represent roads and intersections, and algorithms like Dijkstra's work on graphs to find the shortest path.

It defines how data is grouped, what operations are allowed, and how data is stored in memory

A data structure is a logical and mathematical model that defines grouping, operations, storage representation, and efficiency impact.

False

A linked list stores elements in scattered memory locations with pointers linking them, not contiguous memory.

False

Data structures organize data, while algorithms are step-by-step procedures to manipulate data. They are distinct but complementary.

—

Full marks require mentioning organization, storage, and efficiency.

—

Each component is essential: data values, how they are stored, what operations can be performed, and how they are accessed.

—

These are the fundamental operations that data structures support.

—

Direct access uses an index, sequential access uses a loop, and recursive access uses recursion.

—

List the three main benefits.

—

Mention contiguous memory and index calculation.

Queue

Queue is a linear structure that follows FIFO. Trees, graphs, and tries are non-linear.

Stack

Stack follows LIFO; the last element added is the first to be removed.

Exactly one predecessor and one successor

Linear structures have a one-to-one relationship: each element has exactly one predecessor and one successor, except the ends.

Graph

Graph is non-linear because elements can have many-to-many relationships.

Elements are arranged hierarchically or as a graph

Non-linear structures arrange elements hierarchically (tree) or as a network (graph), allowing multiple connections.

People waiting in a line

A queue follows FIFO, like people waiting in a line: the first person in line is served first.

Graph

A social network has many-to-many relationships, which a graph represents naturally with nodes and edges.

Linear structures can use contiguous or linked memory; non-linear mostly use dynamic pointer-based memory

Linear structures like arrays use contiguous memory, while linked lists use pointers. Non-linear structures like trees and graphs typically use dynamic memory.

A tree is a special type of graph with no cycles and a single root

A tree is a connected acyclic graph with a root and exactly one path between any two nodes. Graphs can have cycles and multiple paths.

Trie

Tries are designed for efficient word searching and prefix matching, making them ideal for autocomplete.

$O(\log n)$

A balanced BST keeps height logarithmic, so search is $O(\log n)$.

False

A linked list is linear because each node points to exactly one next node, forming a sequence.

False

Non-linear structures like balanced trees can be faster for search operations than linear structures like linked lists.

—

This definition captures the sequential layout and one-to-one relationship.

—

Non-linear structures have one-to-many or many-to-many relationships.

—

These principles define the order of operations in stacks and queues.

—

Stack's LIFO behavior matches the undo feature.

—

Queue's FIFO behavior matches a physical queue.

—

This is a defining characteristic of linear structures.

—

Because the structure grows and shrinks as connections change.

—

These analogies illustrate hierarchical or network-like relationships.

`int`

Primitive data types are basic types provided by the language, such as `int`, `char`, `float`, `bool`, and `pointer`. Arrays, stacks, and trees are non-primitive because they organize multiple values.

Queue

A queue is a linear non-primitive data structure. `float`, `bool`, and `char` are primitive types that store single atomic values.

A single atomic value

Primitive data structures represent atomic, single-value data types. They cannot hold multiple values; that is the role of non-primitive structures.

Tree

Non-linear structures arrange elements hierarchically or interconnectedly. Trees, graphs, heaps, and tries are non-linear. Arrays, stacks, and queues are linear.

Linked List

Linear data structures arrange elements in a sequence. Linked lists, arrays, stacks, and queues are linear. Graphs, heaps, and tries are non-linear.

Arrays are non-primitive because they organize multiple elements.

Arrays are non-primitive because they organize multiple elements into a single structure, regardless of the type of elements they store. The fact that they store primitive values does not make them primitive.

They can organize and manipulate collections of data.

Non-primitive structures are designed for manipulation, searching, sorting, and organizing collections of data. Primitives are simple and fast for single values but cannot handle collections.

A library

A library is an organized collection of books, similar to how non-primitive structures organize multiple values. A single brick, book, or chair represents a primitive unit.

Primitives use fixed memory; non-primitives can use dynamic memory.

Primitive data types have a fixed memory footprint (e.g., an `int` always uses a fixed number of bytes). Non-primitive structures can use dynamic memory, allowing them to grow or shrink as needed.

`pointer`

A pointer is a primitive data type that stores memory addresses. It is often used to build dynamic data structures like linked lists.

They can grow, shrink, and reorganize.

Non-primitive structures like linked lists can dynamically adjust their size, whereas primitives have a fixed size. This flexibility allows them to handle varying amounts of data efficiently.

Non-primitive structures are built using primitive types as building blocks.

Non-primitive data structures are composed of primitive types. For example, an array of integers uses `int` as its base type. Primitives are the atoms; non-primitives are the molecules.

They can grow and shrink dynamically.

Primitive data structures have fixed memory and cannot grow or shrink. Dynamic behavior is a feature of many non-primitive structures, such as linked lists.

Linked list

A linked list is a non-primitive structure that can hold multiple records, each composed of primitives like name, age, and grade. Primitives like `int` or `char` can only hold a single value.

To organize and manipulate collections of data

Non-primitive data structures are designed for organizing, storing, and manipulating collections of data. They support operations like searching, sorting, and dynamic resizing, which are essential for complex applications.

False

Arrays are non-primitive because they organize multiple elements into a single structure. Storing primitive values does not make them primitive.

True

Non-primitive structures are classified into linear (e.g., arrays, stacks, queues, linked lists) and non-linear (e.g., trees, graphs, heaps, tries).

—

This tests recall of the definition and examples.

—

This tests recall of the definition and examples.

—

This tests understanding of the classification.

—

This tests the ability to relate abstract concepts to real-world examples.

—

This tests understanding of when to use primitives.

—

This tests recall of primitive types.

—

This tests recall of non-primitive structures.

—

This tests the ability to classify non-primitive structures.

Linked list

A linked list stores elements in scattered memory locations, with each element containing a pointer to the next element. Arrays use contiguous memory.

It brings efficiency, clarity, and organization to programs

Data structures organize data so that operations become efficient and code becomes clear and maintainable. They do not always use less memory and still require algorithms.

A specialized format for organizing, storing, and managing data

A data structure is a specialized format for organizing, storing, and managing data efficiently. It is not a language feature, algorithm, or hardware.

—

This clarifies a common misconception.

—

Static structures are simpler and faster but inflexible.

—

Unreleased memory can exhaust system resources over time.

—

This is the key trade-off in choosing between them.

—

Real-world data sizes are often unpredictable.

A static array, because the size is known in advance and access is faster.

Since the number of readings is fixed at 60, a static array is ideal: it provides fast O(1) access and avoids the overhead of dynamic memory management. A linked list or dynamic array would add unnecessary complexity and slower access without any benefit because the size is known and will not change.

Static arrays store elements contiguously, enabling direct arithmetic to compute an element's address.

In a static array, elements are stored in contiguous memory locations. The address of any element can be computed directly using the base address and index (e.g., base + index * size), giving O(1) access. A linked list requires traversing pointers from the head to reach a specific node, which is O(n).

The memory remains allocated but is no longer accessible, leading to a memory leak.

When `malloc()` allocates memory, it must be explicitly released with `free()`. If not, the memory stays allocated but the pointer is lost, making it impossible to free later. This is a memory leak, which gradually consumes available memory and can eventually cause the program or system to run out of memory.

Storing user-generated posts on a social media platform where the number of posts changes constantly.

Social media posts are unpredictable in number and change frequently, so a dynamic structure like a linked list or dynamic array is needed to grow and shrink as posts are added or removed. The other options have known, fixed sizes, making static structures more appropriate.

It uses contiguous memory, but resizing may require copying all elements to a new memory block.

A dynamic array maintains a contiguous block of memory. When resizing is needed, `realloc` attempts to extend the existing block; if that's not possible, it allocates a new contiguous block and copies the elements over. Thus, the memory remains contiguous, but resizing can be costly due to the copy operation.

—

Fields are the individual attributes of the record.

—

The struct defines a record with fields.

—

An array of structs is a collection of related records, i.e., a file.

—

The same logical structure can have different physical implementations.

—

The logical behavior (LIFO) remains the same, but the storage differs.

They are fields because each is a single attribute of a record.

In the context of a record, `roll`, `name`, and `marks` are individual attributes, which are called fields. A record is the entire struct (one student), and a group item is a collection of related data items, but here they are specifically fields of a record.

A linked list requires only updating pointers for insertion/deletion, not shifting elements.

In a linked list, each node stores data and a pointer to the next node. Inserting or deleting a node involves adjusting a few pointers, whereas an array requires shifting elements to maintain contiguous storage. This makes linked lists more efficient for frequent insertions/deletions.

A stack can be implemented using either an array or a linked list, with different trade-offs.

A stack is a logical data structure with LIFO behavior. It can be implemented using an array (contiguous memory, fixed size) or a linked list (scattered nodes, dynamic size). The logical model is separate from the physical storage, so multiple storage structures are possible.

A file

A file is defined as a collection of related records. In this example, each book entry is a record, and the entire catalog (all book entries) is a file. A group item is a collection of related data items, not necessarily records, and a data item is a single value.

Because different storage structures have different time and space trade-offs for operations like access and insertion.

The storage structure (e.g., array vs. linked list) affects how operations are implemented. Arrays provide O(1) random access but O(n) insertion/deletion, while linked lists provide O(1) insertion/deletion (given a pointer) but O(n) access. These trade-offs directly impact performance, so the choice matters.

—

Mention the trade-off between access speed and modification flexibility.

—

Highlight the contrast between organized and unorganized data.

—

Clarify that they are distinct but complementary.

—

Mention both access speed and modification flexibility.

—

Any valid example from the source material is acceptable.

—

Include grouping, operations, storage, and efficiency.

—

Mention LIFO and push/pop operations.

—

Mention contiguous vs. scattered and performance impact.

Linked list, because insertion at the head only requires updating a few pointers.

Inserting at the beginning of an array requires shifting all existing elements, which is O(n). A linked list can insert at the head in O(1) by updating the head pointer and the new node's next pointer. Stacks and hash tables are not designed for arbitrary insertion at the beginning.

Graph

A graph is the natural data structure to represent a road network, with intersections as vertices and roads as edges. Algorithms like Dijkstra's operate on graphs to find shortest paths. Arrays, linked lists, and stacks do not capture the complex relationships between locations.

A data structure organizes data, and an algorithm is a procedure that operates on that data.

A data structure is the logical organization of data (e.g., array, tree), while an algorithm is a step-by-step procedure to perform a task (e.g., binary search). They work together: algorithms often require specific data structures to be efficient.

Array, because it allows direct access by index in O(1) time.

Arrays provide O(1) direct access by index, which is ideal for frequent positional access. Linked lists require O(n) traversal to reach a specific position. While arrays may have overhead for insertions/deletions, the scenario emphasizes searching by position, making arrays the better choice.

How data is physically laid out in memory, such as contiguous or scattered.

Storage representation describes how data is placed in memory—contiguously (like arrays) or scattered with pointers (like linked lists). This affects access speed and flexibility. The logical relationship and operations are separate aspects of a data structure.

—

Tries allow fast prefix-based searches.

—

This affects how you implement algorithms to visit all elements.

—

The tree's structure allows halving the search space each step.

—

All trees are graphs, but not all graphs are trees.

—

Linear structures are easier to implement and traverse for sequential processing.

—

Non-linear structures model one-to-many or many-to-many relationships.

—

Efficiency depends on the operation and the specific structure.

A trie, because it is a non-linear structure that stores characters in a tree-like layout, sharing common prefixes.

A trie is a non-linear, tree-like data structure specifically designed for storing strings with common prefixes. It shares those prefixes, reducing memory usage and enabling fast prefix-based searches, which is ideal for autocomplete. The other options are linear structures that do not share prefixes and would store ea…

A sorted array has $O(\log n)$ search time but $O(n)$ insertion time, while a balanced BST has $O(\log n)$ for both search and insertion.

A sorted array supports binary search in $O(\log n)$ time, but inserting an element requires shifting elements, which is $O(n)$. A balanced BST maintains $O(\log n)$ time for both search and insertion because it keeps the tree height logarithmic. This trade-off is a key difference between linear and non-linear structur…

A tree has a single root and exactly one path between any two nodes, ensuring a clear hierarchy without cycles.

A tree is a non-linear, hierarchical structure with a single root and exactly one path between any two nodes. This ensures no cycles and a clear parent-child relationship, which matches how directories contain subdirectories. A general graph can have cycles and multiple paths, which would not represent a strict hierarc…

Because each element has exactly one predecessor and one successor, forming a single sequence.

The linearity of a data structure is defined by the logical arrangement of elements, not the physical memory layout. In a linked list, each node (except the first and last) has exactly one predecessor and one successor, so elements form a single sequence. This is true even though memory is dynamically allocated and nod…

A graph allows many-to-many relationships and cycles, representing mutual friendships and multiple connections.

A graph is a non-linear structure that allows many-to-many relationships and cycles. In a social network, a person can have many friends, and friendships can form cycles (e.g., A is friends with B, B with C, C with A). A tree, by contrast, has a hierarchical structure with exactly one path between nodes and no cycles,…

—

This targets the common misconception about arrays.

—

This tests understanding of memory allocation.

—

This tests the flexibility characteristic.

—

This tests understanding of when to use non-primitives.

—

This tests understanding of the term 'atomic'.

—

This tests understanding of the origin of non-primitives.

—

This tests understanding of pointers as primitives.

Use an array of structs, where each struct combines primitive types (string, int, char) into a single non-primitive unit.

Non-primitive data structures are built on top of primitives. An array of structs organizes multiple primitive values (name, age, grade) into a structured, indexable collection, demonstrating how non-primitives combine primitives. The other options either misuse primitives or incorrectly classify arrays as primitive.

Because it holds multiple values and provides an organized, indexable collection.

The key distinction is that non-primitive structures organize multiple elements into a single unit. An array groups five `int` values into one indexable structure, making it non-primitive. It is not user-defined (arrays are built-in), and it has a fixed size, so the other options are incorrect.

Primitive types use a fixed amount of memory, while non-primitive types can use dynamic memory and often require additional overhead for organization.

Primitive types have a fixed memory footprint (e.g., an `int` is always 4 bytes on many systems). Non-primitive structures like linked lists or arrays may use dynamic memory and often include extra overhead (e.g., pointers, metadata) to manage the collection. The other options misrepresent the typical memory behavior.

A tree, because it arranges elements hierarchically with parent-child relationships.

A file system naturally forms a hierarchy—folders contain subfolders, which contain files. Trees are non-linear non-primitive structures designed for hierarchical relationships. Queues and stacks are linear structures for ordered processing, and arrays are linear collections, none of which capture the hierarchical natu…

They are created by combining primitive types and other structures to suit specific needs.

Non-primitive structures are built by the programmer using primitives and other structures (e.g., a struct combining int and char). They are not predefined by the language; the user designs them to solve specific problems. The other options incorrectly describe their origin or flexibility.

—

It is a serious issue in long-running programs.

—

This shows that dynamic refers to size flexibility, not necessarily memory layout.

A static array because it provides O(1) access and avoids runtime allocation overhead, ensuring the strict deadline is met.

The data size is known and fixed (1,000 readings per batch), and the system has a strict performance deadline. A static array allocates memory at compile time, providing contiguous storage and O(1) access with no runtime allocation overhead. Dynamic structures like linked lists or `realloc` introduce runtime overhead a…

The `realloc` function may extend the existing memory block in place or move it to a new location; in either case, the logical order of elements is preserved.

`realloc` attempts to resize the existing memory block. If there is enough contiguous space, it extends in place; otherwise, it allocates a new block, copies the old data, and frees the old block. In both cases, the resulting memory is contiguous and the logical order of elements is preserved. The `free` call after `re…

The linked list uses more memory per element due to the pointer field, and accessing the i-th element requires O(n) time.

A linked list allocates memory dynamically for each node, but each node also stores a pointer to the next node, increasing memory overhead. Accessing the i-th element requires traversing from the head, which is O(n). A dynamic array (using `realloc`) also resizes at runtime but provides O(1) access and uses less memory…

A static array avoids the overhead of runtime memory allocation, reducing the risk of memory leaks and ensuring predictable memory usage.

Static arrays allocate memory at compile time, so there is no runtime allocation overhead, no risk of memory leaks from `malloc`/`free`, and memory usage is fixed and predictable. This is ideal for memory-constrained systems where the size is known. Dynamic structures would introduce overhead and potential fragmentatio…

Replace the linked list with a static array of size 50, using a circular buffer to overwrite the oldest snapshot when full.

A static array of size 50 with a circular buffer provides O(1) access to any element, including the most recent, and respects the fixed limit of 50 steps. Adding a tail pointer to a linked list would give O(1) access to the last node, but the question asks for the best improvement; a circular buffer is simpler and avoi…

—

Performance depends on the storage structure.

`points` is a file, `p1` and `p2` are records, and `x` and `y` are fields.

In the given code, `struct Point` defines a record with fields `x` and `y`. `p1` and `p2` are instances of that record, so they are records. The array `points` is a collection of related records (two points), which fits the definition of a file. The other options misclassify the terms: a data structure is a broader log…

A linked list, because insertions and deletions in the middle are O(1) once the position is known, and searches can be done by traversing.

The requirement emphasizes frequent insertions and deletions in the middle of the collection. A linked list excels at this because, once the node is located, insertion and deletion only involve updating pointers, which is O(1). Searches by `emp_id` would require traversal, but that is acceptable given the emphasis on i…

The data structure is the abstract logical model (stack) with LIFO behavior, and the storage structure is the array that physically stores the elements.

The data structure is the logical organization—here, a stack with LIFO semantics. The storage structure is the concrete implementation—here, an array that holds the elements in memory. They are distinct concepts: the same logical stack could be implemented with a linked list, so they are not identical. The other option…

Each row is a record, each column is a field, and the entire table is a file.

In a relational database, a row is a record because it is a collection of related fields that describe one entity (a student). Columns are fields because they represent a single attribute. The entire table is a file because it is a collection of related records. The other options misapply the hierarchy: a row is not a…

The structure `Point` is a record, each instance is a record, and the array is a file.

The structure `Point` defines a record with fields `x` and `y`. Each instance of `Point` is a record because it holds values for those fields. The array of `Point` objects is a collection of related records, which is a file. The other options misclassify: `Point` is not a group item (it has named fields, making it a re…

—

Emphasize the trade-offs and context-dependence.

Use a balanced binary search tree (e.g., AVL tree) to maintain sorted order with O(log n) insertions and O(log n) search.

A balanced BST (like AVL) supports O(log n) insertions (including at the 'beginning' in sorted order) and O(log n) search, which is efficient. A linked list gives O(1) insertions at the head but binary search on a linked list is O(n) because random access is not possible. An array allows binary search but shifting elem…

Use an adjacency list and Dijkstra's algorithm with a binary heap priority queue.

An adjacency list is memory-efficient for sparse road networks and allows quick updates to edge weights. Dijkstra's algorithm with a binary heap achieves O((V+E) log V) time, which is efficient for shortest path. An adjacency matrix uses O(V^2) memory and is inefficient for sparse graphs. DFS does not guarantee shortes…

Use two stacks: one for undo and one for redo. When an undo occurs, the action is pushed onto the redo stack; when a new action is performed, the redo stack is cleared.

Two stacks are the classic approach: the undo stack holds actions in LIFO order, and the redo stack stores undone actions. When a new action is performed, the redo stack is cleared to maintain consistency. A single stack cannot support redo. A queue would give FIFO order, which is incorrect for undo. An array with a po…

Array, because accessing the 5th task is O(1) via index, while linked list access is O(n) due to traversal.

Arrays provide O(1) random access by index because elements are stored in contiguous memory. Linked lists require traversal from the head to reach the 5th node, which is O(n) in the worst case. Maintaining a pointer to the 5th node is not practical for arbitrary positions. Binary search on an array is O(log n) but only…

Storage representation determines the efficiency of operations; for example, contiguous storage enables O(1) index access, while scattered storage requires traversal for access.

The storage representation (contiguous vs. scattered) directly impacts the time complexity of operations. Arrays (contiguous) allow O(1) random access, while linked lists (scattered) require O(n) traversal for access. Operations are not independent of storage; the physical layout determines how efficiently operations c…

Two stacks: one for undo history and one for redo history. When an action is undone, it is popped from the undo stack and pushed onto the redo stack. A new action clears the redo stack.

Undo/redo requires LIFO behavior for both operations: the most recent action is undone first, and the most recently undone action is redone first. Two stacks perfectly capture this: the undo stack holds actions in reverse chronological order, and the redo stack holds undone actions in reverse order of undoing. A new ac…

A tree has exactly one path between any two nodes, which enforces a strict parent-child relationship and prevents cycles, ensuring that there is no ambiguity in the hierarchy.

The defining property of a tree is that there is exactly one unique path between any two nodes, and it has a single root. This enforces a strict hierarchy where each node (except the root) has exactly one parent, making the structure acyclic. This is ideal for a file system because folders and files are organized in a…

A trie (prefix tree), because it stores common prefixes only once, reducing memory usage when many words share prefixes, and it allows efficient prefix-based searches.

A trie is specifically designed to store strings by sharing common prefixes. Each node represents a character, and paths from the root to leaves represent words. This minimizes memory usage when words share prefixes (e.g., 'cat', 'car', 'can' share 'ca'). It also supports efficient prefix searches: to find all words wi…

A sorted array supports O(log n) search via binary search but O(n) insertion due to shifting elements, while a balanced BST supports O(log n) for both search and insertion.

In a sorted array, binary search can find an element in O(log n) time, but inserting an element requires shifting all subsequent elements to maintain sorted order, which is O(n) in the worst case. A balanced BST (e.g., AVL or Red-Black tree) maintains balance, ensuring that both search and insertion are O(log n) becaus…

Graphs allow cycles and multiple paths, which can represent mutual friendships and the possibility of multiple connection paths between users, whereas trees enforce a strict hierarchy with no cycles.

A social network is inherently non-hierarchical: friendships are mutual (undirected edges) and can form cycles (e.g., A is friends with B, B with C, C with A). There can be multiple paths between two users. Graphs are designed to model such many-to-many relationships with cycles and multiple paths. Trees, by definition…

Use a linked list of `float` values because linked lists allow efficient insertions and deletions at both ends, and `float` is a primitive type.

A linked list is a non-primitive linear data structure that allows O(1) insertions and deletions at both ends (head and tail) if pointers are maintained. An array has fixed size and shifting elements for insertions/deletions is O(n). A stack only allows operations at one end (LIFO), and a queue typically allows inserti…

`classRoom` is a non-primitive array of structures, and each structure is non-primitive because it contains a `char` array, but `age` and `grade` are primitive.

`classRoom` is an array (non-primitive) of `struct Student` objects. Each `struct Student` is a user-defined non-primitive data type because it aggregates multiple fields. Within the struct, `age` (int) and `grade` (char) are primitive types, while `name` is a `char` array (non-primitive). Arrays are never primitive; t…

Use a tree (non-primitive) where each node stores a `string` for name and an `int` for age; children are pointers to other nodes. This leverages primitives for atomic data and non-primitives for hierarchy.

A family tree is a hierarchical structure, best represented by a tree (non-primitive, non-linear). Each node contains primitive data (string for name, int for age) and references to child nodes (pointers, which are primitive). Arrays and linked lists are linear and cannot naturally represent parent-child relationships.…

The array is non-primitive and uses contiguous memory, leading to better cache locality and lower overhead, but it cannot grow dynamically; the linked list is non-primitive and uses scattered memory with per-node overhead, but it can grow dynamically.

Both arrays and linked lists are non-primitive data structures. Arrays use contiguous memory, which improves cache locality and reduces overhead, but have fixed size. Linked lists use non-contiguous memory with extra pointer storage per node, allowing dynamic growth but with higher memory overhead and poorer cache perf…

Use a stack (non-primitive) where each element is a structure (non-primitive) containing primitive fields (`char`, `int`) and a string (non-primitive). This supports LIFO undo and dynamic growth.

Undo functionality requires LIFO (Last-In-First-Out) order, which is exactly what a stack provides. A stack is a non-primitive linear data structure that can grow dynamically. Each operation is a composite data type (struct/class) that aggregates primitive types (`char`, `int`) and a string (which is non-primitive). An…

Use a balanced binary search tree (e.g., AVL tree) to maintain sorted order with O(log n) insertions and O(log n) search.

A balanced BST (like AVL) supports O(log n) insertions (including at the 'beginning' in sorted order) and O(log n) search, which is efficient. A linked list gives O(1) insertions at the head but binary search on a linked list is O(n) because random access is not possible. An array allows binary search but shifting elem…

Use an adjacency list and Dijkstra's algorithm with a binary heap priority queue.

An adjacency list is memory-efficient for sparse road networks and allows quick updates to edge weights. Dijkstra's algorithm with a binary heap achieves O((V+E) log V) time, which is efficient for shortest path. An adjacency matrix uses O(V^2) memory and is inefficient for sparse graphs. DFS does not guarantee shortes…

Array, because accessing the 5th task is O(1) via index, while linked list access is O(n) due to traversal.

Arrays provide O(1) random access by index because elements are stored in contiguous memory. Linked lists require traversal from the head to reach the 5th node, which is O(n) in the worst case. Maintaining a pointer to the 5th node is not practical for arbitrary positions. Binary search on an array is O(log n) but only…