Unit 7 : Data Structures Flashcards
What is an array
● An array is an ordered, finite set of elements of a single type.
● A 1D (one- dimensional) array is a linear array.
● A 2D (two-dimensional) array can be visualised as a table/spreadsheet.
● When searching an array, first go down the rows and then across the columns.
● A 3D (three-dimensional) array can be visualised as a multi-page spreadsheet
● An element in a 3D array using: three Dimensional Array[z,y,x] z = array number, y = row number, x = column number.
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.
What is a list
● Consists of a number of items, where items can occur more than once.
● Data can be stored in non-contiguous locations and be of more than one data type.
What are tuples
● An ordered set of values of any data type .
● Cannot be changed: elements cannot be added, edited or removed once initialised.
● Initialised with regular brackets rather than square brackets
What is a linked list
● 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 or pointer field.
● Data field: contains the actual data associated with the list
● Pointer field: contains the address of the next item in the list
What are graphs
● Set of vertices/nodes connected by edges/arcs. ,
○ Directed Graph: Edges can only be traversed in one direction
○ Undirected Graph:Edges can be traversed in both directions,
○ Weighted Graph: Each arc has a cost attached to it
● Implemented using an adjacency matrix or an adjacency list.
Advantages of using adjacency matrix
- Convenient to work with
- Easy to add nodes
Advantages of using adjacency list
- Space efficient for large sparse networks
What are stacks
● Last in first out (LIFO) data structure:
○ Items can only be added to/ removed from the top of the stack.
● Used to reverse actions, eg. back buttons and undo buttons use stacks
● Can be implemented as a static or dynamic structure.
What are queues
● First in first out (FIFO) data structure:
○ Items are added to the end and are removed from the front of the queue.
● Used in printers, keyboards and simulators.
● 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 and back of the queue.
○ Use space inefficiently, as positions from which data has been removed cannot be reused
● Circular queues have a rear pointer that can loop back to the front of the queue and utilise empty space at the front.
○ Are harder to implement.
What are trees
● A connected graph, with a root and child nodes.
● Node: Item in the tree,
● Edge: Connects two nodes together and is also called a branch/arc
● Root: Node with no incoming nodes
● Child: Node with incoming edges
● Parent: Node with outgoing edges
● Subtree: Section of a tree consisting of a parent and its children
● Leaf: Node with no children.
● A binary tree is a type of tree where each node has a maximum of two children.
● Store information in a way that is easy to search through
● Commonly represented by storing each node with a left pointer and a right pointer.
What are hash tables
● An array coupled with a hash function.
● Hash function takes in data (a key) to produce a unique output (the hash).
● Typically used to map the key to a unique index in the hash table.
● Two keys producing the same hashed value is called a collision
● If this occurs, the item is typically placed in the next available location.
● A good hashing algorithm should have a low rate of collisions.
What is a pre-order traversal’s
Pre-order traversal follows the order: root node, left subtree, then right subtree. Using the outline method, nodes are traversed in the order in which you pass them on the left, beginning at the left-hand side of the root node.
What is an in-order traversal
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, beginning at the first node from the left which does not have two child
nodes. This is useful for traversing the nodes in sequential order by size.
What is a post order traversal
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, beginning at the left of the root node.
