5. Abstract Data Structure (HL) Flashcards

1
Q

List and describe three common types of abstract data structures. (4 marks)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Compare and contrast abstract data structures with concrete data structures. Provide one example of each. (4 marks)

A

ADS: Defines operations conceptually, e.g., Stack (2).
Concrete: Actual implementation in memory, e.g., Array (2).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Explain how abstraction in data structures helps manage complexity in software design. (4 marks)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Define a stack and explain the LIFO (Last In, First Out) principle. (3 marks)

A

Stack: Data structure that follows LIFO order (1).
LIFO Principle: Last element added is the first one removed (1).
Example: Stack of plates (1).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Describe two operations of a stack (push and pop) and provide a real-life analogy. (4 marks)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Write pseudocode for implementing a stack using an array and explain the main steps. (5 marks)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Discuss a practical use case for a stack in computing, like function call management. (4 marks)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Define a queue and explain the FIFO (First In, First Out) principle. (3 marks)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Describe two operations of a queue (enqueue and dequeue) and provide a real-life analogy. (4 marks)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Write pseudocode for implementing a queue using an array and explain the main steps. (5 marks)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Discuss a practical application of a queue in computing, such as task scheduling. (4 marks)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Define a linked list and describe the structure of a node. (4 marks)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Compare singly linked lists with doubly linked lists, including one advantage and one disadvantage. (5 marks)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Describe a scenario where a linked list is preferred over an array and explain why. (4 marks)

A

Scenario: Dynamic data structure with frequent insertions/deletions (2).
Advantage: Linked lists have efficient insertion/deletion without shifting (2).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Explain how to perform insertion at the head of a linked list and provide pseudocode. (6 marks)

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Define a binary tree and explain the concepts of parent and child nodes. (3 marks)

A

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

17
Q

Explain the difference between a binary tree and a binary search tree (BST). (4 marks)

A

Binary Tree: Any structure with up to two child nodes per parent (2).
BST: Special binary tree where left < parent < right (2).

18
Q

Describe the process of inserting a new node into a binary search tree and provide pseudocode. (5 marks)

A

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

19
Q

Discuss the importance of tree traversal methods and explain the differences between in-order, pre-order, and post-order traversal. (6 marks)

A

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

20
Q

Define recursion and how it differs from iteration.

A

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

21
Q

Explain recursion depth and its effect on performance.

A

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

21
Q

What is a base case in recursion, and what happens if it’s missing?

A

Base case: Condition that ends recursion (1).
Importance: Prevents infinite recursion (1).
Without it: Infinite calls, causing a stack overflow (1).

21
Q

Write a recursive function in pseudocode to calculate 𝑛!.

A

Pseudocode:
function factorial(n)
if n == 0
return 1
else
return n * factorial(n - 1)

22
Q

State one advantage and one disadvantage of recursion.

A

Advantage: Simplifies code for problems like tree traversal (1).
Disadvantage: Higher memory use due to stack calls (1).

22
Q

Write a recursive function to compute the nth Fibonacci number.

A

pseudocode:
function fibonacci(n)
if n == 0
return 0
else if n == 1
return 1
else
return fibonacci(n - 1) + fibonacci(n - 2)