# data structures

Studied by 18 people
0.0(0)
Get a hint
Hint

what is an array?

1 / 51

# Earn XP

## Description and Tags

[ 1.4.2 ]

### 52 Terms

1

what is an array?

an ordered, finite set of elements of a single type

New cards
2

what is a one-dimensional array?

a linear array

New cards
3

what is a two-dimensional array?

• it can be visualised as a table/spreadsheet

• when searching an array, first go down the rows and then across the columns

New cards
4

what is a three-dimensional array?

• it can be visualised as a multi-page spreadsheet

• an element is represented by: myArray[x][y][z]

• x = array number,  y = row number,  z = column number

New cards
5

what is a list?

• a data structure that consists of a number of ordered items

• items can occur more than once

• data is stored in non-contiguous locations

• can contain items of different data types

New cards
6

what is the function of the list operation isEmpty() ?

checks if the list is empty

New cards
7

what is the function of the list operation append(value) ?

adds a new value to the end of the list

New cards
8

what is the function of the list operation remove(value) ?

removes the value the first time it occurs in the list

New cards
9

what is the function of the list operation search(value) ?

searches for a value in the list

New cards
10

what is the function of the list operation length() ?

returns the length of the list

New cards
11

what is the function of the list operation index(value) ?

returns the position of the item

New cards
12

what is the function of the list operation insert(position, value) ?

inserts a value at a given position

New cards
13

what is the function of the list operation pop() ?

returns and removes the last item in the list

New cards
14

what is the function of the list operation pop(position) ?

returns and removes the item at the given position

New cards
15

what is a record?

• more commonly referred to as a row in a file

• a record is made up of fields, and is widely used in databases

• each field in a record can be identified by recordName.fieldName

• when a record is created, the program must declare the data type for each field

New cards
16

what is a tuple?

• an ordered set of values of any data type

• immutable and static, meaning it cannot be changed

• initialised with regular brackets rather than square brackets

New cards
17

what is a queue?

• a first in first out (FIFO) data structure

• items are added to the end and are removed from the front of the queue

• uses two pointers (head and tail)

• used in printers, keyboards and simulators

New cards
18

what is a linear queue?

• items are added into the next available space, starting from the front

• items are removed from the front of the queue

• uses two pointers: pointing to the front/back of the queue

• uses space inefficiently, as positions from which data has been removed cannot be reused

New cards
19

what is a circular queue?

• a queue that uses a rear pointer

• it loops back to the front of the queue and utilises empty space at the front, if it’s available

• harder to implement that a linear queue

New cards
20

what is the function of the queue operation enQueue(value) ?

adds a new item to the end of the queue

New cards
21

what is the function of the queue operation deQueue() ?

removes and returns the item from the front of the queue

New cards
22

what is the function of the queue operation isEmpty() ?

checks if the queue is empty

New cards
23

what is the function of the queue operation isFull() ?

checks if the queue is full

New cards
24

what is a linked list?

• a dynamic data structure used to hold an ordered sequence

• items do not have to be in contiguous data locations

• each item is called a node, and contains a data field and a link (pointer field)

• a linked list must also store a start index/pointer, to identify the beginning of the list

New cards
25

what is held in the data field of an item in a linked list?

contains the actual data associated with the list

New cards
26

what is held in the pointer field of an item in a linked list?

contains the address of the next item in the list

New cards
27

steps to traverse a linked list.

• go to the first position, indicated by the start pointer

• from the first position, read the next pointer value

• follow this pointer to the next value, and continue until you reach the desired item

New cards
28

what is a stack?

• a last in first out (LIFO) data structure

• items can only be popped/pushed from the top of the stack

• used to reverse actions, (eg. back buttons/undo buttons)

• can be implemented as a static or dynamic structure

• uses one pointer (head pointer)

New cards
29

what is a tree?

a connected graph, with a root and child nodes

New cards
30

what is an edge?

an edge connects two nodes together (also called a branch/arc)

New cards
31

what is a node?

an item in a tree/graph

New cards
32

what is a root?

a node with no incoming edges

New cards
33

what is a child node?

a node with incoming edges

New cards
34

what is a parent node?

a node with outgoing edges

New cards
35

what is a subtree?

a part of a tree consisting of a parent and children

New cards
36

what is a leaf?

a node with no children

New cards
37

what are the two ways to traverse a tree?

trees can be traversed by a depth-first search (DFS) or a breadth-first search (BFS)

New cards
38

what is a graph?

• a set of vertices/nodes connected by edges/arcs

• implemented using an adjacency matrix or an adjacency list

New cards
39

what is a directed graph?

a graph where edges are assigned a direction

New cards
40

what is a undirected graph?

a graph where edges can be traversed in both directions

New cards
41

what is a weighted graph?

a graph where each arc has a cost attached to it

New cards
42

what is a hash table?

• a data structure which holds key-value pairs

• they are used in situations where a lot of data needs to be stored with constant access times

• e.g in caches and databases

• a good hashing algorithm should…

• be calculated quickly

• have a low rate of collisions

• use as little memory as possible

New cards
43

what is a hashing function?

a function applied to an item to determine a hash value (a unique index in the hash table)

New cards
44

what is a collision and how are they handled?

• collisions occur if two keys produce the same hash value

• in this situation the item is usually placed in the next available location (open addressing)

• to find the item later, the hashing function delivers a start position, from which a linear search can be applied (linear probing)

New cards
45

what is the drawback of open addressing and how can it be handled?

• open addressing can result in clustering, where several positions are filled around common collision values

• can be handled by using…

• a 2D hash table

• an overflow table for hash values where collisions have occurred

New cards
46

what is a binary search tree?

• a type of tree where each node has a maximum of two child nodes

• stores information in a way that is easy to search through

• commonly represented by storing each node with a left pointer and a right pointer

New cards
47

what are the three types of depth-first search?

• pre-order

• in-order

• post-order

New cards
48

how do you traverse a binary search tree using breadth-first search?

• first visit the top level/root node

• then search all the nodes at the next depth level down

• continue until you have searched all the leaf nodes of the tree

New cards
49

how do you traverse a binary search tree using pre-order traversal?

• it follows the order:

• root node → left subtree → right subtree

• using the outline method, nodes are traversed in the order in which you pass them on the left

New cards
50

how do you traverse a binary search tree using in-order traversal?

• follows the order:

• left subtree → root node → right subtree

• using the outline method, nodes are traversed in the order in which you pass under them

• useful for traversing the nodes in sequential order by size

New cards
51

how do you traverse a binary search tree using post-order traversal?

• follows the order

• left subtree → right subtree → root node

• using the outline method, nodes are traversed in the order in which they are passed on the right

New cards
52

how is backtracking used in a depth-first traversal?

when a leaf node is reached, the traversal backtracks to the leaf’s parent node // to the last node with unvisited children

New cards

## Explore top notes

Note
Studied by 6 people
Updated ... ago
5.0 Stars(1)
Note
Studied by 3 people
Updated ... ago
5.0 Stars(1)
Note
Studied by 4 people
Updated ... ago
5.0 Stars(1)
Note
Studied by 16 people
Updated ... ago
5.0 Stars(2)
Note
Studied by 10 people
Updated ... ago
5.0 Stars(1)
Note
Studied by 71 people
Updated ... ago
5.0 Stars(2)
Note
Studied by 28 people
Updated ... ago
5.0 Stars(1)
Note
Studied by 71 people
Updated ... ago
5.0 Stars(1)

## Explore top flashcards

Flashcard23 terms
Studied by 4 people
Updated ... ago
5.0 Stars(1)
Flashcard744 terms
Studied by 13 people
Updated ... ago
5.0 Stars(2)
Flashcard42 terms
Studied by 256 people
Updated ... ago
4.8 Stars(5)
Flashcard177 terms
Studied by 507 people
Updated ... ago
5.0 Stars(2)
Flashcard103 terms
Studied by 7 people
Updated ... ago
5.0 Stars(3)
Flashcard48 terms
Studied by 11 people
Updated ... ago
5.0 Stars(1)
Flashcard72 terms
Studied by 9 people
Updated ... ago
5.0 Stars(1)
Flashcard44 terms
Studied by 65 people
Updated ... ago
5.0 Stars(4)