Computer Science A Level OCR > 1.4.2 Data Structures > Flashcards

1.4.2 Data Structures Flashcards

(53 cards)

Study These Flashcards
1
Q

Array

A
  • a static data structure in which data is stored in continuous, Adjacent memory locations [1]
  • can only store one data type [1]
  • provides direct access to elements
  • are usually zero indexed
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Record

A
  • is a row in a file and is made up of fields
  • is widely used in databases
  • can be implemented using OOP in python
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Tuple

A
  • a static data structure
  • An ordered collection of elements that can contain multiple data types
  • is immutable - so elements can’t be added or removed once it has been created [1]
  • are initialised using regular brackets instead of square ones
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Static Datastrcute

A

Size can’t change during processing [1]

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

Dynamic data structure

A
  • size can change during processing [1]
  • disadvantage : storage requirements are unknown initially [1]
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Linked lists

A
  • a dynamic data structure used to hold an ordered sequence [1]
  • each item/node consist of a data field and a pointer field [1]
  • data field contains the actual data
  • pointer field gives the location of the next node/item in the list [1]
  • linked list needs to be traversed until desired element is found [1]
  • takes longer to search (as more nodes are added) [1]
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Linked lists + array comparison

A
  • array provides direct access to all elements [1] whereas a linked list needs to be traversed until desired element is found [1]
  • contents of an array are stored continuously in memory [1]
  • whereas contents of linked list do not have to be in continuous data locations [1]
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Linked list operations

A
  • adding node
  • deleting node
  • traversing linked list
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Linked list traversal

A
  • is used to access each element of the linked list
  • first position is indicated by the start pointer [1]
  • linked list can be traversed by following each items next pointer until the end of the list is located (null)
  • pointer = null means end of list has been reached
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Linked list : adding node

A
  • advantage: nodes can be added or removed easily by editing the pointers
    1. Allocate memory and create new node containing the data [1]
    2. Change the new node to point to the previous nodes next node [1]
    3. Change the previous nodes next node to point to the new node [1]
  • if the new node is added to the start change its pointer to point to the head node
  • if added at the end let it point to null
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Linked list: Removing node

A
  • involves updating nodes to bypass the deleted node
  • node is not truly removed but ignored instead which wastes memory
  • so to delete a node, change the next pointer of the previous node to bypass the node being deleted and instead point to the next node
  • linked list requires more memory than arrays due to storing pointers
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Stack

A
  • is a LIFO data structure [1]
  • items can only be added or removed from the top of the stack
  • stacks are used to reverse actions eg back buttons and undo buttons use stacks
  • stacks use a pointer which points to the top of the stack
  • when initialising stack we set TOP pointer = -1
  • thus is stack is empty TOP = -1
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Stack operations

A
  • push(value)
  • pop()
  • isEmpty()
  • isfull()
  • Size()
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Push(value)

A
  • adds an element to the top of the stack (checks if stack is full first)
  • once value is pushed, the top pointer is incremented by 1
  • attempting to push an item onto a full stack is called stack overflow
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Pop()

A
  • removes and returns value at the top of the stack (checks if stack is empty first)
  • once popped, the pointer is decremented by 1
  • attempting to pop an item from an empty stack is called stack underflow
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

IsEmpty()

A
  • checks if stack is empty
  • eg if Top == -1 return true
  • or return len(stack) == 0
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Isfull()

A
  • Checks jf stack is full
  • compares stack size to the top pointer
  • if len(stack) == Top return true
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Size()

A

Returns size of the stack

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

Queues

A
  • a FIFO data structure
  • in which items are added at the end of the queue
  • and items are removed from the front of the queue
  • Consist of a head and tail pointer
  • similar to stacks there is also queue overflow and queue underflow
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Types of queue

A
  • linear queue
  • circular queue
  • priority queue
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Queue operations

A
  • Enqueue(value)
  • dequeue()
  • peek()
  • isfull()
  • isempty()
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Enqueue

(initially set value of head and tail pointer = -1 )
(for the first element increment both head and tail pointer to 0)

Study These Flashcards
A
  • adds element to the back of the queue
    1. Check if queue is full
    2. Increment tail pointer and add the new element in the position pointed by the tail
    3. Head pointer stays the same
23
Q

Dequeue
( for dequeuing the last element, reset the values of the head and tail to -1 )

Study These Flashcards
A
  • returns an elements from the front of a queue
    1. Check that queue is not empty
    2. Return item at the front of the queue and then increment the head pointer by 1
24
Q

PeeK()

Study These Flashcards
A

Returns the value of the item at the front of the queue without removing it from the queue

25
Linear queue
- same as a normal queue + consists of an array - uses front and rear pointers - easier to implement - however it uses space inefficiently as positions from which data has been removed can’t be reused
26
Circular queue
- have a rear Pointer that can loop back to the front of the queue and utilise the empty space at the front (when the end of the queue is reached ) - circular increment can be performed using modulo division with the queue size - eg. rear= (rear+1) % len(queue)
27
Graphs
- a set of vertices/nodes connected by edges/arcs [1] - directed graph: can only be traversed in one direction - undirected graph: edges can be traversed in both directions - weighted graphs: each edge has a cost attached to it
28
Adjacency matrix
- a 2D array that records the relationships between each node and all the other nodes in the graph - each of the rows and columns represent a node - for unweighted graphs : - 1 is set when an edge exist between 2 nodes - 0 is set when there is no edge between 2 nodes
29
Adjacency matrix advantages
- easy to add nodes - convenient to work with due to quicker access times
30
Adjacency matrix disadvantages
- in the case of a sparse graph with many nodes but not many edges most of the cells will be empty - the larger the graph, the more memory space will be wasted
31
Adjacency list
- can be implemented as a list of dictionaries with the key in each dictionary being the node and the value being the edge weight - the adjacency list is a more space efficient way to implement a sparsely connected graph
32
Traversing a graph
Graphs can be traversed using a DFS traversal or BFS traversal
33
DFS (depth first) traversal
- in this traversal we go as far down one route as we can before backtracking and taking the next route. - is implemented using a stack - can be pre order, in order, post order
34
Pre order
Root , left , right
35
In order
Left , root, right
36
Post order
Left, right, root
37
BFS (breadth first traversal)
- systematically explores all the neighbour vertices at the current depth before moving onto vertices at the next depth level and so on
38
Graphs applications
- computer networks => nodes = computers, weighted edges = bandwidth between them - roads between towns with edge weights representing distances - webpages and linked
39
Tree
- a tree is a connected form of a graph - has a root node which is the top of the tree so is hierarchical - has leaf nodes
40
Height of a tree
Number of edges that connect the root node to the leaf node that is furthest away from it
41
Node (trees)
An item in a tree
42
Edge
Connects two nodes together also known as branch/arc
43
Child node
A node with incoming edges
44
Parent node
A node with outgoing edges
45
Subtree
A subsection of a tree consisting of a parent node and all the children of a parent
46
Leaf
A node with no children
47
Tree and graph comparison
- both consists of nodes - both are connected by edges - both are dynamic data structures - tree is unidirectional whereas graph can be bidirectional - tree will not have cycles whereas graphs can have cycles - tree will not be weighted whereas edges in a graph can be weighted
48
Tree use case
- managing folder structures - binary trees are stored in routes to store routing tables - binary search trees can be built to speed up searching
49
Binary tree
- A generic tree structure where each node has at most two children with no specific ordering. - the most common way to represent a binary tree is by storing each node data along side a left and right pointer
50
Binary search tree
- A specialized binary tree optimised for searching - where each node follows the ordering property (left child < node < right child). - So all nodes from the left subtree are less than the root node - all nodes from the right subtree are greater than the root node
51
Binary search tree (BST) ADDING data
- create a new node and insert data into it [1] - if the tree is empty, the new value will become the root node - if the value is less than the current nodes value, move to the left child - if the value is greater than the current nodes value, move to the right child - repeat this process until a vacant spot is reached where the new value can be inserted
52
BST removing data
1. Search for the node containing the value that needs to be removed 2. If the node is found : - If the node has no children simply remove it from the tree - if the node has one child, replace the node with its child + delete the child - if it has two replace the node with either the minimum or maximum value in right or left subtree - removed values can be implemented by setting left or right pointers of parent nodes to null
53
Hash tables
• Hash tables are data structures that store key-value pairs using a hash function to compute an index for fast data retrieval. • They offer average-case O(1) time complexity for insertion, deletion, and lookup. • Collisions are handled using techniques like chaining or linear probing
Computer Science A Level OCR
flashcards
Decks in class (24)
# Cards
Brainscape helps you reach your goals faster, through stronger study habits.
© 2026 Bold Learning Solutions. Terms and Conditions