Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Computer Science - A-Level > Data structures > Flashcards

Data structures Flashcards

(137 cards)

Start Studying
1
Q

def Variable

A

a Variable is a named reference to a memory location that stores data that can change during the runtime of the program

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

why is declaring variable type important

A

So that the computer knows how much memory space it has to allocate for the data and how to process it

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

example of importance of declaring data type of variable

A

float vs integer

integer dealt with in ALU
float dealt w/ in FPU - floating point unit

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

def casting

A

converting data from one type to another?

assigning a variable a data type?

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

def Constant

A

named reference to a memory location where the data inside the constant cannot change during the runtime of the program

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

whats an ADT(abstract data type)

A

ADT is logical description of how we view data and the possible operations
e.g queue of print jobs, stack of books, list of tasks to do

Only concerned w/ what data is representing, not how its constructed

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

2d array: array[x,y]

which is column which is row

A

row = x
column = y

Remember matrices (3x1)

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

What are the pointers used in a queue
and the important variables to use in queue

A

Front
Rear
maxSize
currentSize

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

In memory, after the first elements memory location, where are the other elements stored

A

in the next consecutive memory location

In low level langs, amount of data needed 4 array is reserved, starting from 1st reserved mem location, it checks the next mem location, until end of reserved mem locations 4 array.

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

where do dynamic data structures allocate and deallocate memory from

A

the heap - an area of memory used for ____________________

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

3 types of queues

A

linear
circular
priority

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

in what manner do queues operate?

A

FIFO

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

advantages priority queue

A

gives preference to more important items

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

how do priority queues work

A

Items qiven priority
If item has higher priority than item in front of it, it can jump in front of it
If same or greater, stay put

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

in what manner do stacks operate

A

FILO

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

4 operations of a queue

A

enQueue - add an item to the REAR of the queue
deQueue - remove and return an item from the FRONT of the queue
isFull - check if queue is full
isEmpty - check if queue is empty

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

Circular queues

A

Reuse the empty spaces freed by dequeueing from front of the array

(rear + 1) MOD max

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

excessive amount of allocation without deallocation leads to

A

overflow

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

example dynamic data structre
example static data structure

A

dynamic: list

static: array

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

advantage using queues in a list

A

list is dynamic data structure, will use enough memory for number of elements inside the list

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

disadvantage using queues as a list

A

can keep adding items to the list - eventually all the memory will be exhausted and cant keep adding more

To solve this, make it so list has maxsize
Can change the maxsize when needed if need to add more items

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

advantages of linear queues (created using arrays)

A

simple to program
predictable memory usage

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
what to do w/ pointers when dequeue item
move the front pointer (and rear if needed) You dont actually delete item When need to add to slot where item is but not in queue, you overwrite it Saves processing time
26
advantages circular queue
can reuse free spaces
27
What is an array
An array is a data structure that holds a number of data items or elements of the same data type.
28
disvantages linear queue
fixed length single pass cant reuse spaces
29
30
disadvantages circular queue
harder to program
31
32
disadvantages priority queue
additional processing required to keep order
33
features of array
Indexed - each element has its own index Mutable - contents of array can change during runtime of program
34
list of list operations
isempty() append(item) remove(item) count(item) len(item) index(item) insert(pos,item) pop() pop(pos)
35
remove(item) does
remves first occurance of item from the list
36
count(item)
returns number of occurances of item from list
37
len(item)
returns num of items in list
38
insert(pos,item)
insert item at position pos
39
Implementing a queue as a list
No need for size variable as you have len function maxSize needed to prevent exhauston of memory isFull function needed
40
Common operations on lists
merging, sorting, searching, comparing lists
41
Linked Lists
dynamic ADT which can be implemented as array and pointers Composed of nodes
42
what are nodes in linked lists composed of
the data pointer of the next node (and of node pointing to it if doubly linked list)
43
Pointers in linked lists
Start pointer Nextfree pointer Pointer in each node pointing to nxt (or prev) node
44
Adding node to linked list
Store data in the node pointed to by the nextfree pointer Adjust pointer of the previous item to point to the added item Added item assumes the value of the pointer of the previous item before the item was added
45
deleting node in linked list
pointer of node before the deleted item points to node after the deleted item deleted node points to nextfree index position after itself (might not be same value as nextfree pointer)
46
an application of stacks
reversing lists any other good examples add them here
47
what pointers used in stacks + what variables
one pointer - the top of the stack size, maxSize variables can be used
48
operations on stacks
push(item) - add item to top of the stack pop() - removes and returns the item on the top of the stack isFull() - check if stack is full isEmpty() - check if stack is empty peek() - return top item w/o removing it size() - return num of items in stack
49
def overflow
attemping to push into a full stack
50
def underflow
attempting to pop from an empty stack
51
stack overflow def
a computer program tries to use more memory space in the call stack than has been allocated to that stack.
52
Call stack
system level data structure provides mechanism for passing parameters + return addresses to subroutines IN OTHER WORDS: REMEMBERS THE PARAMETERS PASSED INTO SUBROUTINE + WHAT LINE THE SUBROUTINE WAS CALLED SO PROGRAM CAN REMEMBER WHERE TO GO BACK TO
53
Subroutine calls
calls to subroutine executed as follows: 1st step - parameters saved onto the stack 2nd - address to which program returns to after subroutine is executed saved onto the stack 3rd - execution transferred to subroutine code
54
Subroutine execution
subroutine executed as follows: stack space allocated for local variables subroutine code executes return address retrieved parameters popped execution trasnferred back to return address
55
hashing is
Hashing is the practice of transforming a given key or string of characters into another value
56
how is the hashed item found in thedatabase
calculated from the data istelf, using hashing algo
57
hashing algo use cases
encryption checking for errors in downloaded code searching datasets verifying integrity of data
58
what is used to ensure records are assigned a unique address and how
hashing is used some part of the record eg primary key is hashed to give a unique destination address
59
what is the data structure that stores the results of hashing algorithms
hash table
60
primary key def
unique identifier of a record
61
whats a collision
When hashing algo returns same address for different primary keys
62
Table of items to be inpuuted into hash algo size compared to hash table size
Hash table size must be bigger
63
load factor def
The number of elements in a hash table divided by the number of slots.
64
simplest method w/ dealing w/ collisions
put item in next available slot
65
disvantage of put item in next available slot method hashing
leads to clustering of items
66
how to make the method of puting an item in next slot hashing better
increment the skip e.g 1st skip is by 1, next is by 3, next is by 5 etc
67
how big should the hash table be
prime number size
68
good load factor size
0.7 or below
69
Mid square method
square the item take middle digits perform mod step to get the address if it has letters or symbols, take denary value of them
70
folding method
divide item into equal isze pieces (last piece may be unequal size) add pieces together (e.g 13+12 = 25) perform mod step
71
Why do you mod the key by number of slots - hashing
So the result can always fit in the table
72
Searching for items in hash table if collision occured
From the slot it would have been placed in, check each next slot until the next empty space
73
Dealing w/ deletion in hash table
When delete an item, put a dummy value in it e.g 'Deleted' That way when searching through, it is not treated as an empty space
74
hashing characters + symbols
take their denary values from ascii table
75
what is dictionary
ADT made up of key:value pairs value is accessed via the key
76
can you have dictionary in dictionary
ya
77
uses of dictionaries
ascii/unicode table in translation program - foreign lang dictionary trees + graphs can be implemented w/ dicts
78
can multiple items have same key dictionary
ya
79
Dictionary operations
add new key:value pair to dict delete a pair from dict amend value in key:value pair return value associated w/ a key return true/false depending on whether key is in dict return len of dict
80
when hashing: are key:value pairs held in any particular order
no
81
chaining
instead of storing actual data in hash table, you store pointer that point to where that data is stored
82
3 attributes that data in linked list in hash table (chaining) has
key value data pointer to next node
83
if there are multiple collisions in one slot, how does the chaining work
pointer pointing to next collided item (node a) is put in hash table node a points to next collided item (node b) node b point to node c etc
84
When could chaining become a problem
If there is lots of clustering will take time going thru linked list , too long of a list
85
what direction undirected graphs
bidriectional
86
what do edge weights represent
cost of travel
87
graph def
set of vertices/nodes connected by edges/arcs
88
directed graph aka
digraph
89
2 ways a graph can be represented
adjacency list + matrix
90
adjacency matrix
each row and column represent a node item at [row,column] indicate connection
91
in which graph will matrix be syymetric
undirected
92
what could entries in adjacency matrix represent
edge weights
93
advantages adjacency matrices
adding an edge/node is simple
94
disavantage ajaceny matrix
sparse graph w/ little connections will leave most cells empty wasting mem space
95
ajaceny list
list of nodes created each node points to list of ajacent nodes
96
representing a wegihted graph
can be represented as dict of dicts each key in dict is the node the value is a dict of adjacent edges + edge weights
97
avantae ajaceny list
only uses storage for existing connections good way to represent large sparse graph
98
graph applications
computer netowrks states in finite state machine social networks web pages + links chemistry project management maps search engines
99
trees
an adt has a root, branches and leaves
100
can trees be weighted
No
101
tree def
connected undirected graph with no cycles (unique path from each node to any other node)
102
rooted tree
one node identified as root each node except root has 1 unique parent
103
terminology for trees
root node edge child parent subtree leaf
104
nodes w/ no children
leaf
105
binary tree def
a rooted tree with at max 2 children
106
can you represent trees as matrices
ya
107
binary tree node - 3 parts
data left pointer right pointer
108
binary search tree
nodes added in order given, first item as root if item larger, put to right if less, put to left
109
2 types of traversal
depth first tree traversal (DFT) breadth first tree traversal
110
3 types of DFT
pre order - NLR in order - LNR post order - LRN
111
where are subroutines for tree traversals put in when carried out
in a stack in case backtracking needs to occur
112
backtrackin def
Going back a step after there are no more options to explore down the route you just went
113
avantage storing data in binary search tree
large chunks of data can be eliminated while searching for data
114
balanced binary trees
nodes distributed in a way height kept to a minimum leads to efficient searching
115
deleting leaf node
pointer of parent pointing to leaf changes value to -1
116
deleting node w/ one child
child takes place of deleted node parent of deleted node points to child of deleted node
117
deleting node w/ 2 children
next largest number replaces the deleted node parent of deleted node has its pointers changed
118
deleting nodes - why may they be bad
whole tree may have to be rebuilt - time consuming trees used for searching, shouldnt be used as a generalised ADT
119
def parameter
Local variable which passes an argument into the subroutine and ceases to exist once the subroutine is executed good practice to have: pVariableName
120
def argument
actual value of the parameter
121
def function
subroutine that returns a value
122
def procedure
subroutine not retunring a value
123
passing by value
Passing variables by value means that copies of the values stored in the variables are provided to the function. Changes to parameter variables do not affect the original variables
124
Passing by reference
pass a parameter to a function by providing its memory address instead of the value stored in it. Original variable can be accessed and changed
125
126
127
128
129
130
131
132
133
134
135
136
137

Computer Science - A-Level (11 decks)

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