A Level Computer Science > Data Structures > Flashcards

Data Structures Flashcards

(66 cards)

Study These Flashcards
1
Q

What is a variable?

A

An identifier/address in memory for a value stored in RAM

Extra info:
- use direct addressing type
- used to manipulate data behind the scenes
- some languages need explicit variable declarations - define variable name + type

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

What is a constant?

A

Like a variable but you can’t change the value stored in it - immutable

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

What is an array?

A
  • A set of data items of the same type grouped together using a single identifier
  • they are zero indexed - the first value is index zero
  • values are identified by variable name + subscript - Eg. Arr_name[4]
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are the features of an array?

A
  • they have a fixed size, defined at the start
  • they can’t expand or shrink
  • all data must be of the same data type
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a 2D array?

A
  • it’s an array inside an array - can be visualised as a table

Eg. [[a,b],[c,d]]
To choose b:
- pseudocode - arr[0,2]
- python - arr[0][2]

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

what is a 3D array?

A
  • its an array with arrays inside it with arrays inside the sub-arrays
  • can be visualised as a multi page spreadsheet
  • eg. [[[a,b],[c,d]],[[e,f],[g,h]]]
    to select e:
  • pseudocode - arr[1,0,0]
  • python - arr[1][0][0]
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

why would you use arrays of multiple dimensions?

A

do this to avoid using multiple arrays - you are the programmer so won’t forget what each array stands for

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

what is a record?

A
  • its essentially a row in a table
  • data is organised via attributes/fields (columns) which hold one item of data - the primary key and/or secondary keys can be used to order multiple records
  • more user-friendly than a list/array because you can identify data by attribute
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

how do you declare a record in pseudocode?
(eg define record studentType with fields ID, firstname, surname, dateOfBirth, class)

how do you identify a field in a record

A 
studentType = record
    integer ID
    string firstname
    string surname
    date dateOfBirth
    string class
end record

variable must be declared first like this:
~~~

<variable> : <variableType>
<recordname>.<fieldname>
~~~
</fieldname></recordname></variableType></variable>

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

what is a tuple?

A
  • an ordered set of elements of any data type
  • elements do not have to be of the same data type
  • it is immutable - elements can’t be changed, added or deleted dynamically
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

how do you define a tuple in python and refer to a value in it?

A

use parenthesis

pupil = ("John", 78, "a") 

name = pupil[0]
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

what is a list?

A
  • its a dynamic data type consisting of a number of ordered items where the same item may occur more than once
  • they are dynamic - items can be added, removed and edited
  • items can be of different data types
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

what are some common operations on a list?

A
  • isEmpty() - test for empty list
  • append(item) - add an item to the end of the list
  • remove(item) - remove first occurence of an item from the list
  • search(item) - search for an item in the list
  • length() - return the number of items in the list
  • index(item) - return the position of item
  • insert(pos,item) - insert a new item at position pos
  • pop() - remove and return the last item in the list
  • pop(pos) - remove and return the item at position pos
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

when and how might an array be used instead of a list?

A
  • if list data type isnt supported by the programming language
  • maximum no of items is small + known in advance
  • programmer has to work out + code algorithms for each list operation
  • empty array must be declared in advance as being a particular length
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

what is a linked list?

A

a set of data elements where each element contains:
- the data itself
- a pointer to the next element

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

what are the key features of a linked list?

A
  • items in sequence aren’t necessarily in in contiguous data locations (the order in which they occur in the sequence)
  • each item in the list = node -> made up of data field+ next address field (link/pointer field)
  • data field = actual data associated with list item
  • pointer field = address of next item in sequence
  • last item has null pointer in link field - shows there are no further items
  • pointer variable = contains the address of the first mode in the list
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

what are the benefits of linked lists?

A
  • new items can be inserted without rearranging all the other elements
  • if programmed dynamically it uses memory more efficiently
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

what are some drawbacks of linked lists?

A
  • more complex to program/manipulate than an array
  • extra programming needed to access data in the opposite direction (or list needs to be doubly linked)
  • can only be accessed in a linear manner - no binary search
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

how do you add a node to a linked list?

A
  1. add new node at FSP (free storage pointer) address + update FSP
  2. find previous node by following links from SP (start pointer) until last node where data value is less than new node
  3. change new node [pointer] to previous node [pointer] to the address of the new node
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

how do you delete a node from a linked list?

A
  1. follow the pointers until node to delete is found - make a note of the previous node
  2. change previous node’s pointer to the node to delete’s pointer
  3. change the node to deleted’s pointer to the overwrite indicator or the FSP[pointer] to the node to deleted’s address
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

what is an abstract data type

A

a logical description of a data structure that specifies the operations that can be performed on it without detailing its implementation - allowing programmers to focus on functionality not internal workings, promoting modular + reusable code
eg. stacks, queues, linked lists, trees

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

what is a queue?

A
  • first in first out structure (FIFO)
  • new elements can only be added to the end of the queue + elements can only be retrieved from the front of the queue
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

what are some applications of a queue?

A
  • printer queue in a room full of networked computers
  • characters typed into a keyboard held in the keyboard buffer queue
  • queue simulation problems like finding the optimum number of checkout points at a supermarket
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

what are the main operations on a queue?

A
  • enQueue(item) - add new item to rear of queue
  • deQueue() - remove front item from queue + return it
  • isEmpty() - test to see whether queue is empty
  • isFull() - test to see whether queue is full
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
what is a dynamic data structure?
a collection of data in memory that has the ability to grow or shrink in size using the heap - a portion of memory from which space can be allocated/deallocated as needed
26
what is a static data structure?
it is fixed in size and cannot increase in size or free up memory while the program is running
27
what are 2 methods of implementing a linear queue?
Method 1: - as items leave the queue, all other items move up the queue 1 place - front of queue is always first element - might take a lot of processing time with long queues Method 2: - an array with front and rear pointers for the queue - needs an integer with the size of the array (max size of queue) + variable giving no of items currently in queue - when many items are added/deleted from queue, there will be space created at front of queue + cant be filled - items are added until rear pointer points to last element of data structure
28
what is a circular queue?
- also a FIFO structure - once rear pointer is equal to max size of queue, it can loo[ back to the front of the array + stores values here provided its empty - more efficient use of space but harder to implement
29
what is a priority queue?
- items are dequeued by removing them from the front of the queue - logical order of items in queue determined by priority - high priority at front, low priority further back - new item may join the front of the queue if it is high priority - check priority of each item moving along until it finds one with lower priority than the item -> new item inserted here
30
what is a stack?
- last in first out (LIFO) structure - items are added to and removed from the top (like a stack of plates)
31
what are some examples of stacks being used?
- back button on a web browser - go through all pages previously visited in reverse order - URLs removed from stack - undo button in word processor - last operation complete is popped out of the stack and undone
32
how can stacks be implemented?
- either as static or dynamic data structure - static: use an array with 2 extra variables - top of stack pointer, maximum size of stack - dynamic: use a list - top of stack = last element of the list
33
what are the main operations on a stack?
- push(item) - add new item to top of the stack - pop() - removes + returns item at top of stack - peek() - returns top item from the stack but doesnt remove it - isEmpty() - tests whether stack is empty and returns boolean value - isFull() - tests whether stack is full and returns boolean value
34
what is an overflow and underflow error?`
- overflow: trying to push an item into the stack when the stack is full - underflow: trying to pop an item out of the stack when it is empty
35
what is the purpose of a call stack?
store information about active subroutines when a computer program is running
36
what are some functions of a call stack?
- holds return addresses - the address of the instruction that control should return to once a subroutine ends - holds parameters required for a subroutine - each call to a subroutine will be given separate space for these extra values - local variables - accessible and usable only within the subroutine. more efficient than using dynamic memory allocation which uses heap space. - the stack frame - makes up a call stack. each stack frame corresponds to a call for the subroutine which has not yet been terminated.
37
how is an index value for an item in a file created?
- hashing algorithm is applied to each record's key field - output (a hash) is the address - this maps a key to an index in the hash table
38
what happens if 2 items have the same results after the hash function was applied (a synonym)?
- this is a collision - 2 record keys hash to the same address - the easiest way to deal with this is to store the item in the next available free space
39
what is a hash table?
- a collection of items stored in a way that they can be quickly located - can be implemented using an array or list with a given number of empty spaces
40
when are hash tables used?
- for efficient lookup of stored data - fast because of unique, one-to-one relationship with address they are stored at - to implement dictionaries, useful for implementing graphs
41
how do you search for an item in a hash table?
- apply the hashing algorithm to the key field of the item - examine the resulting cell in the list - if the item is there, return the item - if the cell is empty, the item is not in the table - if there is another item in that spot, keep looking forward until either the item is found or a blank cell is encountered, meaning the item is not in the table.
42
what are some hashing algorithms?
- divide the key by the number of available addresses and take the remainder as the address - folding method: divide item into equal parts, add the parts to give the hash value - if there are fewer spaces than the the maximum possible sum generated, add an extra set of dividing by 100 - remainder is the location
43
how do you hash a string?
- use the ASCII code for each character - add up the ASCII values for each letter - divide by the number of spaces available - the remainder is the hash value
44
what is rehashing?
- the process of finding an empty slot when a collision has occured - can simply look for the next empty slot - loops back to first cell of table if end is reached - or it can be more complex eg. look at every 3rd cell, increment hash calue by 1,3,5,7... until a free space is found.
45
what is a dictionary?
- an abstract data type made of associated pairs of items, where each pair consists of a key and value. - when user supplies a key, associated value is returned
46
what are some operations on dictionary?
- create a new empty dictionary - add a new key:value pair - delete a key:value pair - amend the value in a key:value pair - return a value associated with key k - return True/False depending on if the key is in the dictionary or not - return the length of the dictionary (how many key:value pairs there are)
47
how can a dictionary be implemented?
- using either a static or dynamic data structure - pairs are not held in any particular sequence - key is hashed using a hashing algorithm and stored in the relevant location using a hash table allowing fast lookup.
48
what is a graph?
a set of vertices or nodes connected by edges or arcs
49
what are the 3 types of graph?
- directed graph - edges can only be traversed in one direction - undirected graph - edges are bi-directional - weighted graph - a cost is attached to each edge
50
how can graphs be represented?
- adjacency matrix - adjacency list
51
what is an adjacency matrix?
- a 2d array storing information about a directed/undirected graph - each row and column represent a node - a value at the intersection of row i and column j shows there is an edge connecting nodes i and j - undirected graph - symmetric - same entry in (0,1) as (1,0) - unweighted graph - represented with 1s instead of weights in each cell
52
advantages and disadvantages of adjacency matrix?
advantages: - convenient - adding an edge is simple disadvantages: - sparse graph with lots of nodes but not many edges will leave most cells empty -> wasted memory space - using static 2D array makes it harder to add/delete nodes
53
what is an adjacency list?
- more space-efficient method of implementing a sparsely connected graph - list of all nodes created, each node points to a list of all adjacent nodes to which it is directly linked - can be implemented as a list of dictionaries - key is the node, value is the edge weight - unweighted doesnt need a dictionary structure - weights arent recorded
54
what is an advantage of using an adjacency list?
- uses much less memory to represent a sparsely connected graph
55
how do you conduct a depth first traversal?
- go as far down one route as possible - backtrack and take the next possible route
56
how do you conduct a breadth first traversal?
- visit all the neighbours of a node, then all neighbours of the first node visited, then all neighbours of the second node, etc. before moving further away from the start node
57
what are some applications of graphs?
- computer networks - nodes = computers, weighted edges = bandwidth - roads between towns - weights = distances, rail fares, journey times - tasks in a project - some have to be completed before others - web pages and links
58
what is a rooted tree graph?
- a connected form of graph - has root, branches and leafs but root is at the top - a node can only be connected to one parent node and its children nodes - no cycles - no connections between children or branches
59
what are rooted trees used for?
- manipulating heirarchical data - eg. folder structure, moves in a game - making information easy to search - manipulating sorted lists of data
60
what are the features of a rooted tree?
- node - contain tree data - edge - connects 2 nodes - root - only node with no incoming edges - child - set of nods that have incoming edges from the same node - parent - node is a parent of all nodes it connects to with outgoing edge - subtree - set of nodes and edges comprised of parent and all its descendants - can also be a leaf - leaf node - a node with no children
61
what is a binary search tree?
- a rooted tree where each node has a maximum of 2 children - holds items so it can be searched quickly and easily for a particular item, new items can be easily added, whole tree can be printed out in sequence
62
how do you make a binary tree?
- place first item at the root - for each item, visit root - if smaller than the root, move left, if larger than the root move right - repeat for each node visited until a leaf node is reached - place item left or right of this node depending on whether it is larger or smaller than the node
63
how do you do a pre order traversal?
- start at root node - traverse left subtree, visit nodes starting from the bottom - traverse right subtree, visit nodes starting from the bottom - output the values
64
how do you do an in order traversal?
- traverse the left subtree - visit nodes starting from the bottom - traverse the right subtree - output the values
65
how do you do a post order traversal?
- traverse the left subtree - traverse the right subtree - visit the root node - output the values
66
how could a binary tree be implemented?
- use an array of records - each node has left pointer, data item, right pointer - use a list of tuples - use 3 separate lists or arrays - one for each pointer, one for the data items
A Level Computer Science
flashcards
Decks in class (17)
# Cards
Brainscape helps you reach your goals faster, through stronger study habits.
© 2026 Bold Learning Solutions. Terms and Conditions