Studied by 13 people
Resources: https://github.com/graded-cs-resources/IB-Computer-Science-Notes/tree/main/paper1 https://pbaumgarten.com/ib-compsci/unit-5-data-structures.pdf
What is recursion
A function or method which calls itself
Advantages of recursion
Can reduce time complexity and development time and it can add clarity
Disadvantages of recursion
Complex to implement and memory inefficient as each recursion adds a new call to memory and previous function calls remain open
Why are 2D arrays abstract data structures
They are made up of a group of 1D arrays which are data structures themselves
How is the number of rows in array found
ARR.length
How is the number of columns in an array found
ARR[0].length
In index writing in arrays, which comes first, rows or collumns ?
rows
What policy are stacks based on
LIFO
What is the stack insert method ?
Push
What is the queue insert method ?
enqueue
What is the stack removal operation
Pop
What is the queue removal operation
dequeue
What are the applications of queues? (5 implementations)
printer queues 🖨
music playlists 🎶
interrupt handling 🤫
reversing stacks
modelling physical queues
What policy are queues based on ?
FIFO
What are the two features of the static implementation of stacks and queues ?
have a maximum capacity
rely on pointers to add and ‘remove’ elements.
Why are dynamic data structures needed ?
They allow dynamic memory allocation so we don't need to declare their size at initialisation.
They don't need contiguous memory locations as they are linked by referencing the address of the next node.
Insert and delete operations are not computationally expensive as they don't require element shifting
How do dynamic data structures enable a dynamic variable size
As each node has a pointer to other nodes, only the pointers need to be changed to add, remove or move a node
What is a linked list
a linear collection of self-referential data structures, called nodes, connected by pointers.
Name differences between a static data structure and dynamic data structure
Static structures have a fixed size, dynamic structures have a variable length.
Static structures have declaration-time size allocation, dynamic have runtime size allocation.
Static have random access (indexes), dynamic has sequential access (no indexes).
Static are easier for searching and storing and use less memory.
Dynamic data structures can be more memory efficient overall as the data structure only uses what’s necessary as size will increase or decrease at runtime
Dynamic structures have a possibility of overflow or underflow during runtime if allocations are exceeded. This doesnt happen in static structures as memory size is fixed.
Advantages of a singly linked list
simpler to implement, less memory usage
Disadvantages of singly linked list
unidirectional, so slower for searching and sorting; randomly stored so direct access isn’t allowed (sequential only)
Advantages of a doubly linked list
bidirectional traversal; easier to search in
Disadvantages of doubly linked list
uses more memory in comparison to singly linked list
randomly stored so direct access isn’t allowed (sequential only)
Advantages of circular linked lists
the entire list can be traversed starting at any node.
Disadvantages of circular linked list ↻
inserting at the start would be expensive as it requires searching through for the final element; finding the end is hard.
How do you insert a node into an empty list
When the list is empty, indicated by head == NULL, the insertion sets both the head and tail to the current node
How do you insert a node into the beginning of a list
The pointer of the new head node will point to the previous head node;
The header pointer will point to the new node.
The connection between header node and header pointer is removed
How do you insert a node in to the end of a list
Connect tail node to the new node
The new node will be connected to null (in singly linked list)
How do you insert a node in to the middle of a list
The pointer of the previous node will now point to the new node.
The new node will now point to the next node.
Delete the connection of previous node
Give examples of primitive data types
Double, Integer, Character, Boolean
Dynamic data types have length/ size as a ________
Variable
Static data types have a _____ length/size
Fixed
Applications of stacks
storing recursive calls
implementing function calls
returning memory addresses
translations from one programming language to another
browser history
in calculations and evaluations of expressions.
Where are elements in a queue enqueued
From the back
Where are elements in a queue dequeued
From the front
What does contiguous memory locations refer to? Give an example of a data structure which uses it
It means that all elements need to be stored together. eg. an array
What are the features of a dynamic data structure?
Pointers.
Each node has a pointer, they don’t need to be placed next to each other.
To delete and insert nodes, only the pointers need to be changed.
Enables their dynamic size.
Disadvantages of a doubly linked list
Uses more memory in comparison to singly linked list
randomly stored so direct access isn’t allowed (sequential only)
Advantages of circular linked list
The entire list can be traversed starting at any node.
What is a parent in a binary tree
A node which has children. They will be linked below it.
What is a left/right child in a binary tree
A child node on the left/right-hand of the parent.
What is a subtree in a binary tree
A parent with a child. It can be one or two children.
What is a root in a binary tree
The root is the original node.
What are leaves in a binary tree
All nodes without children
Which way do pre-order traversal flags point
left
Which way do in order traversal flags point
Down
Which way do post order traversal flags point
right
what is the base case
a point at which the recursion will stop because the most basic endpoint has been reached, so a simple answer can be given.
Note 
Flashcard (21)