Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

A Level Computer Science > Data Structures > Flashcards

Data Structures Flashcards

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
Q

Data Type

A

Defines potential set of values a variable can hold and the operations that can be performed on it

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

Aspects of Data types

A
  • Range of values
  • Size of memory required
  • How binary data is interpreted
  • Operations that can be performed on it
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Abstract Data Type (ADT)

A

Conceptual model of how data is to be stored and the operations that can be carried out on it

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

Data Structure

A
  • (Partial) implementation of user-defined types (ADTs)
  • Each item known as member and can be of different data types
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Purpose of data structures

A

To combine multiple data items under a single identifier

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

Key ADTs

A
  • Stacks
  • Queues
  • Graphs
  • Trees
  • Hash tables
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Static data structures

A
  • Max size fixed at compilation
  • Data stored in contiguous memory locations
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Advantages of static data structures

A
  • Fast to access
  • (Sometimes) require less memory
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Disadvantages of static data structures

A
  • Inflexible
  • (Sometimes) wastes space
  • Operations like insertion and deletion are very slow
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Dynamic data structures

A
  • Can change size at run-time
  • Data not (usually) stored contiguously
  • Each item points to the next item in the structure
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Advantages of dynamic data structures

A
  • More flexible
  • No wasted space or limits
  • (Sometimes) require less memory
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Disadvantages of dynamic data structures

A
  • (Sometimes) require more memory (have to store pointers)
  • Slower to access
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Queue

A

Data structure comprised of sequence of items and front and rear pointers

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

Order of item insertion in Queue

A

Items added at rear and retrieved from front in First-in-First-Out (FIFO)

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

Key operations of Queue

A
  • Enqueue
  • Dequeue
  • isEmpty
  • isFull
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Enqueue

A

If not isFull() then add new item to rear

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

Dequeue

A

If not isEmpty() then remove front item

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

isFull

A

Test whether queue is full

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

isEmpty

A

Test whether queue is empty

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

Uses of queues

A
  • Queues of print jobs
  • Managing input buffers
  • Handling multiple file downloads
  • Priority-based resource allocation
  • …
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Queue implementations

A
  • Linear queues
  • Circular queues
  • Priority queues
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Linear queues

A
  • Stores items in ‘line’
  • Front and rear pointers move down memory
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Advantages of linear queues

A
  • Simple to program
  • Limited capacity useful when representing finite resources
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Disadvantages of linear queues

A

Wasted capacity (whole queue shifts down)

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

Solving waste problem in linear queue

A
  • Shuffling every item one index forward when first item deleted
  • However, it’s inefficient (O(n))
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Circular queues

A
  • ‘Wraps’ front and rear pointers using MOD function
  • Static, array-based
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Advantages of circular queues

A
  • Avoids wasting space
  • No need for shuffling
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Disadvantage of circular queue

A

More complex to program

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

Priority queue

A

Items enqueued (or dequeued) based on priority

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

Priority queue implementations

A
  • Can be implemented statically using a 2D array
  • More efficient to implement dynamically, with each node storing value and priority
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Disadvantages of static priority queue

A
  • Inherent drawbacks of static (e.g. space limitation)
  • However, dequeue and enqueue time is still O(n) since linear search required to find highest priority
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Stack

A
  • Comprised of sequence of items and stack pointer that points to top of stack
  • Last-in-First-Out (LIFO) - items added to top and removed from top
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Stack structure

A

int maxSize;
int items[maxSize];
int stackPointer = -1;

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

Stack operations

A
  • Push
  • Pop
  • Peek
  • isFull
  • isEmpty
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

Push

A

If not isFull, push value to top of stack

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

Pop

A

If not isEmtpy, returns value at top of stack and removes it

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

Peek

A

Returns item at top of stack (doesn’t remove it)

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

Uses of stack

A
  • Reversing sequence of items
  • Storing stack frames
  • Storing processor state when handling interrupt
  • Evaluating mathematical expressions written in Reverse Polish (postfix) notation
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

Stack overflow

A

Attempt to push item when stack is full

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

Stack underflow

A

Attempt to pop item when stack is empty

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

Call stack

A

Area of memory used to store data used by running processes and subroutines

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

Stack frame

A
  • Return addresses (keeps reference to parent subroutine)
  • Parameter values (keeps parameter values of different subroutines separate)
  • Local variables (isolates these from rest of system)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

Call stack pushing and popping

A
  • Stack frame is pushed with each new subroutine call
  • Stack frame popped when process completes
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

Linked list

A

Dynamic data structure comprised of nodes that point to its consecutive node in the list

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

Aims of linked lists

A
  • Convenience of storing multiple values per element
  • Flexibility to grow
  • Quick at inserting and deleting items (no shuffling)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

Disadvantages of linked lists

A
  • Slower to access items (traversal)
  • Takes up more memory (each node store value + 64 bit pointer)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

Graphs

A

Set of nodes connected by edges

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

Directed vs undirected graph

A
  • In directed, edges can be unidirectional
  • In undirected, all edges are bidirectional
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
49
Q

Weighted graph

A

Edges have a cost of traversing (e.g. time)

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

Purpose of graphs

A

Modelling complex relationships between interralated entities

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

Uses of graphs

A
  • Human (social) networks
  • Transport networks
  • Computer networks
  • Planning telecommunication networks
  • Project management
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
52
Q

Typical graph operations

A
  • Adding / removing node
  • Adding / removing edge
  • Test edge existence
  • Get edges / adjacent nodes
  • Get weight of edge
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q

Implementations of graphs

A
  • Adjacency matrix (static)
  • Adjacency list (dynamic)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
54
Q

Adjacency matrix

A

Edges between nodes represented by ‘1’ at intersection in matrix
E.g. if edges[0][1] == 1, then there is an edge between node 0 and node 1

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

Representing direction in adjacency matrix

A
  • From and to index must be predefined and consistent throughout
  • Unidirection = edges[0][1] == 1, but edges[1][0] == 0
56
Q

Representing weights in adjacency matrix

A

Store weight at intersection or NULL for no edge

57
Q

Size of adjacency matrix

A

N^2 (where n = no. nodes)

58
Q

Advantages of adjacency matrix

A
  • Edges can be quickly identified in O(1) time
  • Optimised for dense graphs (many edges that need updating) due to O(1) look-up
  • Simple implementation using 2D array
59
Q

Disadvantages of adjacency matrix

A
  • More memory required ( Mathjax )
  • Less efficient insertion and deletion (limited space or shuffling -> O(n))
  • If sparse graph, matrix is sparsely populated -> Wasted space
60
Q

Adjacency list

A

Array of nodes (representing every node) pointing to list of adjacent nodes

61
Q

Size of adjacency list

A

N + E (where N = no. nodes & E = no. edges)

62
Q

Implementing adjacency list

A
  • Python - dictionary
  • C - linked list and pointers
63
Q

Representing direction in adjacency list

A

edges[A] → B but edges[B] doesn’t → A

64
Q

Representing weight in adjacency list

A

Each node in linked list stores weight

65
Q

Advantages of adjacency list

A
  • Requires less memory (data only stored where edges exist)
  • Easier and quicker to insert/delete nodes (no shuffling)
  • Optimised for sparse graphs (fewer edges and frequent adding and deletion of nodes)
66
Q

Disadvantages of adjacency list

A
  • Slower to test presence of edge (traversal = O(n))
  • Harder to implement
  • Less optimised for dense graph (more edges → more nodes in lists → slower traversal and more memory)
67
Q

Graph traversal methods

A
  • Depth-first
  • Breadth-first
68
Q

Depth-first

A
  • Traverse one whole route before exploring breadth
  • Recursively visits adjacent nodes from a given starting point until there are no adjacent nodes left, at which point the function returns
  • Uses a stack (automatically implemented via call stack) to maintain FIFO order
69
Q

Uses of depth-first traversal

A
  • Solution to maze (when modelled as graph)
  • Find valid path between nodes (not shortest path)
  • Determining order of dependent processes (e.g. module compilation)
70
Q

Breadth-first

A
  • Visits all adjacent node before exploring depth
  • Uses queue to maintain LIFO order of visiting
71
Q

Uses of breadth-first traversal

A
  • Identifiying friends in social networks
  • Finding immediately connected devices and networks
  • Crawling web pages to build index of linked pages
72
Q

Tree

A

A connected, undirected graph with no cycles

73
Q

Purposes of trees

A
  • Manipulating and storing hierachical data (e.g. folder structures)
  • Making information easy to search
  • Manipulating sorted lists of data
74
Q

Uses of trees

A
  • Processing syntax
  • Huffman trees
  • Implementing probability and decision trees
75
Q

Root

A

Node that has no incoming edges

76
Q

Child

A

Node that has an incoming edge

77
Q

Parent

A

Node that connects to its children nodes via outgoing edges

78
Q

Subtree

A

Set of nodes and edges comprised of a parent and all its descendants

79
Q

Leaf node

A

Node that has no children

80
Q

Rooted tree

A

Has one node dedicated as the root

81
Q

Binary tree

A

Rooted tree in which each node has a maximum of two children

82
Q

Binary search tree

A

Holds items in a way that the tree can be searched quickly in O(log n) time complexity

83
Q

Tree operations

A
  • Determing whether node is root
  • Getting list of children nodes
  • Adding a child node
  • …
84
Q

Static implementations of binary tree

A
  • Associative arrays
  • Dictionary
  • Adjacency matrix
85
Q

Associative array implementation of binary tree

A
  • Uses 3 1D arrays
  • Nodes[] - stores data values in each node
  • Left[] - stores index of node to left of node represented by index number
  • Right[] - stores index of node to right of node represented by index number
86
Q

Adjacency matrix

A

Same as graph

87
Q

Dictionary implementation of binary tree

A
  • Key = Value stored in node (e.g. name)
  • Each index stores tuples holding keys of left and right nodes
88
Q

Dynamic implementation of Binary tree

A
  • Double linked list of nodes
  • Each node store payload value, left node pointer and right node pointer
89
Q

Advantages of dynamic binary tree

A
  • Quicker insertion and deletion
  • Maintains O(log n) search time (even with traversal requirement)
90
Q

Tree traversal algorithms

A
  • Pre-order
  • In-order
  • Post-order
91
Q

Pre-order traversal

A
  1. Visit current node
  2. Traverse left subtree (recurse call function on left)
  3. Traverse right subtree (recurse call function on right)
92
Q

In-order traversal

A
  1. Traverse left subtree
  2. Visit current node
  3. Traverse right subtree
93
Q

Post-order traversal

A
  1. Traverse left subtree
  2. Traverse right subtree
  3. Visit current node
94
Q

Hand-tracing tree traversal algorithms

A
  • Draw outline around tree, starting from left of root and ending at right of root
  • Pre-order - place dot to left of each node
  • In-order - place dot beneath each node
  • Post-order - place dot to right of each node
  • When outline passes node, write/output its value
95
Q

Uses of pre-order traversal

A
  • Copying a tree
  • Evaluating mathematical expression tree using prefix notation
96
Q

Uses of in-order traversal

A

Outputting contents of binary tree in ascending order

97
Q

Uses of post-order traversal

A
  • Converting mathematical expressions from infix to postfix
  • Producing postfix notation from expression tree
  • Emptying a tree
  • Completing dependent processes in order (e.g. recursive functions with multiple recursive calls)
98
Q

Key-value pair

A

Association of a key with a value

99
Q

Static implementations of key-value structure

A
  • Multidimensional array
  • 2 (or more) associative arrays to store key-value pairs
100
Q

Limitations of static key-value implementations

A
  • Searching for key requires linear search (O(n) time complexity)
  • If improved via binary search, requires costly insertion/deletion to maintain order (worse for associated arrays)
  • Fixed size (wasted/limited space)
101
Q

Hash table

A

ADT whose purpose is to provide an efficient means of accessing items from a large, unordered data set

102
Q

Inserting data into hash table

A
  • Value processed by hashing algorithm which returns hash value
  • Data then placed in index specified by hash value
103
Q

Hashing algorithm

A

Always outputs same when given the same input such that the output is practically unique

104
Q

Accessing data in hash table

A

Get data’s index by running hashing algorithm over input data again

105
Q

AQA definition of hash table

A

Data structure that stores key-value pairs based on an index calculated from a hashing algorithm

106
Q

AQA component’s of hash table

A
  • An array or multidimensional array to hold data
  • Data comprised of keys paired with values
  • Hashing algorithm to determine index of data
107
Q

Advantages of hash tables

A
  • O(1) time complexity
  • Determines item’s existence without linear search
108
Q

Collision

A

When a hashing algorithm generates same hash value for two or more keys

109
Q

Collision handling methods

A
  • Rehashing (bad)
  • Linear probing (worse)
  • Chaining (good)
110
Q

Rehashing

A

Apply additional algorithm to original key or conflicting hash value to generate new hash value

111
Q

Limitations of rehashing

A
  • Increases sparsity of array → wasted space
  • Knock-on effect - further collisions may occur, meaning more rehashing is needed
  • Additional process → Slower insertion and searching
112
Q

Linear probing

A

Looks for next available index

113
Q

Limitations of linear probing

A
  • No known association between key and index
  • Increases potential for further collisions (knock-on)
  • Promotes clustering (indices not evenly distributed)
  • Items whose hash value point to shunted index have to be moved elsewhere
  • Worst-case, linear search across whole table required
114
Q

Chaining

A
  • Store linked list at each location in hash table
  • If collision, simply link item to end of list
115
Q

Limitations of chaining

A

Requires some linear searching (however not too much depending on spread of items across buckets)

116
Q

Benefits of chaining

A
  • Can keep adding items without clustering or increasing chance of collisions
  • Retains most efficiency benefits of hash tables
117
Q

Writing good hashing algorithms

A
  • Can handle text input
  • Same hash value for a given key
  • Evenly distributed hash values
  • Use most of input data
  • Use computationally fast operations (e.g. integer calculations)
  • Handle collisions efficiently
118
Q

Uses of hash tables

A
  • Dictionary data structures (store key-value pairs)
  • Databases (for quick storage and retrieval)
  • Cache memory (determine memory address quickly)
  • Operating systems (store location of apps and file for quicker access)
119
Q

Dictionaries

A

Data structrues that store collections of key-value pairs where the value is accessed via its associated key

120
Q

Dictionary operations

A
  • Retrieving value from given key
  • Inserting values with a new key
  • Updating values of a given key
  • Removing a key-value pair
  • Testing if a key exists in a dictionary
121
Q

Uses of dictionaries

A

Wherever data can be stored in a key-value relationship

122
Q

Implementations of dictionaries

A
  • Associative arrays
  • Multi-dimensional array
  • Hash table
  • Binary search tree
123
Q

Associative array implementation of dictionary

A

Pair of 1D arrays storing key and value

124
Q

Multi-dimensional array implementation of dictionary

A

Key and paired value stored in same master index

125
Q

Limitations of array implementations of dictionary

A
  • Fixed size (wasted or limited space)
  • Linear search required for access (O(n) complexity)
126
Q

Hash table implementation of dictionary

A

Most directly echoes mapping concept

127
Q

Limitations of hash table dictionary implementation

A

Application of hash algorithm “heavy” (I.e. too relatively computationally expensive) for a few key-value pairs

128
Q

Binary search tree implementation of dictionary

A

Each node contains both key and paired value (sorted based on key’s value)

129
Q

Benefits of binary search tree implementation of dictionary

A
  • O(log n) time complexity for searching
  • Easy insertion and deletion
  • Can grow or shrink as needed
  • No need for heavy hashing algorithm
130
Q

Vector

A
  • Quantity with magnitude and direction
  • Quantity consisting of multiple values
131
Q

Representations of vectors

A
  • List (1D array)
  • Arrows on coordinate plain
  • As functions (e.g.  f(x) : S → R; f(x) = {V_0 if x = 0, V_1 if x = 1}
  • As dictionaries (useful if viewed as function due to explicit mapping)
132
Q

Vector addition

A

a + b = [a_x + b_x, a_y + b_y]

133
Q

Scalar-vector multiplication

A

ka = [ka_x, ka_y]

134
Q

Dot (scalar) product

A

a ⋅ b = a_x × b_x + a_y × b_y

135
Q

Angle between vectors

A

a ⋅ b = |a||b|cosθ

136
Q

Convex combination

A
  • When sum of two vectors is a vector that sits within the convex hull
  • D = ⍺v βu where ⍺, β ≥ 0, ⍺ + β = 1

A Level Computer Science (12 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions