5. Abstract Data Structure (HL) Flashcards
List and describe three common types of abstract data structures. (4 marks)
Stack: LIFO structure for temporary data storage (1).
Queue: FIFO structure for sequential data handling (1).
Linked List: Dynamic structure where elements link to each other (1).
Benefit: Each has unique use cases based on operation needs (1).
Compare and contrast abstract data structures with concrete data structures. Provide one example of each. (4 marks)
ADS: Defines operations conceptually, e.g., Stack (2).
Concrete: Actual implementation in memory, e.g., Array (2).
Explain how abstraction in data structures helps manage complexity in software design. (4 marks)
Allows focusing on high-level operations rather than implementation (2).
Reduces coding complexity and errors in software (1).
Enables modularity, making changes easier to manage (1).
Define a stack and explain the LIFO (Last In, First Out) principle. (3 marks)
Stack: Data structure that follows LIFO order (1).
LIFO Principle: Last element added is the first one removed (1).
Example: Stack of plates (1).
Describe two operations of a stack (push and pop) and provide a real-life analogy. (4 marks)
Push: Adds an item to the top of the stack (1).
Pop: Removes the top item from the stack (1).
Analogy: Stack of books; add/remove from the top only (2).
Write pseudocode for implementing a stack using an array and explain the main steps. (5 marks)
Define array and top pointer (1).
Push operation: Increment top, add item at top position (2).
Pop operation: Return item at top, decrement top pointer (2).
Discuss a practical use case for a stack in computing, like function call management. (4 marks)
Example: Function call stack in programming (1).
Stores function calls and return addresses (1).
Allows tracking of recursive calls and returns (1).
Importance: Manages program control flow effectively (1).
Define a queue and explain the FIFO (First In, First Out) principle. (3 marks)
Queue: Data structure that follows FIFO order (1).
FIFO Principle: First element added is the first removed (1).
Example: Line at a ticket counter (1).
Describe two operations of a queue (enqueue and dequeue) and provide a real-life analogy. (4 marks)
Enqueue: Adds item to the end of the queue (1).
Dequeue: Removes item from the front of the queue (1).
Analogy: People lining up to enter a bus; first in, first served (2).
Write pseudocode for implementing a queue using an array and explain the main steps. (5 marks)
Define array, front, and rear pointers (1).
Enqueue: Add item at rear, increment rear pointer (2).
Dequeue: Return item at front, increment front pointer (2).
Discuss a practical application of a queue in computing, such as task scheduling. (4 marks)
Use case: Printer job scheduling (1).
Manages print tasks in the order received (1).
Ensures efficient and fair access to printer resources (1).
Importance: Essential for sequential task processing (1).
Define a linked list and describe the structure of a node. (4 marks)
Linked List: Sequence of elements where each points to the next (1).
Node Structure: Contains data and a link to the next node (2).
Allows dynamic data storage and efficient insertion (1).
Compare singly linked lists with doubly linked lists, including one advantage and one disadvantage. (5 marks)
Singly Linked List: Each node points to the next, less memory use (2).
Doubly Linked List: Nodes link both forward and backward, easier reverse traversal (2).
Disadvantage: Doubly linked lists use more memory (1).
Describe a scenario where a linked list is preferred over an array and explain why. (4 marks)
Scenario: Dynamic data structure with frequent insertions/deletions (2).
Advantage: Linked lists have efficient insertion/deletion without shifting (2).
Explain how to perform insertion at the head of a linked list and provide pseudocode. (6 marks)
Steps: Create new node, point it to the current head, update head (3).
Pseudocode:
newNode.value = data
newNode.next = head
head = newNode
(3 marks for pseudocode)
Define a binary tree and explain the concepts of parent and child nodes. (3 marks)
Binary Tree: Hierarchical structure where each node has up to two children (1).
Parent Node: Node with a child (1).
Child Node: Node with a parent, part of a subtree (1).
Explain the difference between a binary tree and a binary search tree (BST). (4 marks)
Binary Tree: Any structure with up to two child nodes per parent (2).
BST: Special binary tree where left < parent < right (2).
Describe the process of inserting a new node into a binary search tree and provide pseudocode. (5 marks)
Traverse from root, compare values to find insertion point (2).
Insert new node in left/right based on comparison (1).
Pseudocode:
if newNode < currentNode
if left is empty, insert
else, repeat on left
else
if right is empty, insert
else, repeat on right
Discuss the importance of tree traversal methods and explain the differences between in-order, pre-order, and post-order traversal. (6 marks)
Importance: Needed to access or manipulate all nodes systematically (2).
In-order: Left, root, right; for sorted order (1).
Pre-order: Root, left, right; for copying tree structure (1).
Post-order: Left, right, root; for deleting nodes (1).
Differences: Each suits specific applications like sorting, copying, deleting (1).
Define recursion and how it differs from iteration.
Recursion: Function calls itself to solve smaller sub-problems (1).
Difference: Recursion uses self-calls with a base case, while iteration uses loops (1).
Key: Recursion simplifies certain problems; iteration avoids stack overhead (1).
Explain recursion depth and its effect on performance.
Depth: Number of self-calls before reaching the base case (1).
Effect: Deeper calls increase memory use; may cause stack overflow (2).
Optimisation: Tail recursion reduces memory use (1).
What is a base case in recursion, and what happens if itβs missing?
Base case: Condition that ends recursion (1).
Importance: Prevents infinite recursion (1).
Without it: Infinite calls, causing a stack overflow (1).
Write a recursive function in pseudocode to calculate π!.
Pseudocode:
function factorial(n)
if n == 0
return 1
else
return n * factorial(n - 1)
State one advantage and one disadvantage of recursion.
Advantage: Simplifies code for problems like tree traversal (1).
Disadvantage: Higher memory use due to stack calls (1).
