Studied by 18 people

0.0(0)

Get a hint

Hint

[ 1.4.2 ]

1

what is an **array**?

an ** ordered, finite** set of elements

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

New cards

8

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

** removes** the value

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

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

New cards

15

what is a **record**?

more commonly referred to as

__a row in a file__a record is

, and is widely used in databases__made up of fields__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__, meaning it cannot be changed__immutable and static__initialised with regular brackets rather than square brackets

New cards

17

what is a **queue**?

a

(FIFO) data structure__first in first out__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

, starting from the front__added into the next available space__items are removed from the front of the queue

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

, as positions from which data has been removed__uses space inefficiently____cannot be reused__

New cards

19

what is a **circular queue**?

a queue that uses a

**rear pointer**and utilises empty space at the front, if it’s available__it loops back to the front of the queue__that a linear queue__harder to implement__

New cards

20

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

** adds a new item** to the

New cards

21

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

** removes and returns** the item from the

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

used to hold an__dynamic data structure____ordered sequence__items

__do not have to be in contiguous data locations__each item is called a

, and contains a data field and a link (__node__**pointer field**)a linked list must also store

, to identify the beginning of the list__a start index/pointer__

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__, and continue until you reach the desired item__follow this pointer to the next value__

New cards

28

what is a **stack**?

a

(LIFO) data structure__last in first out__items can only be popped/pushed from the

__top of the stack__used to

, (eg. back buttons/undo buttons)__reverse actions__can be implemented as a static or dynamic structure

uses

(head pointer)__one 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

connected by__vertices/nodes____edges/arcs__implemented using an

or an adjacency list__adjacency matrix__

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 algorithmbe 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

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 valuescan 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

New cards