Fundamentals of Data Structures Flashcards
What is a data structure
A common format for storing large volumes of related data, which is an implementation of an abstract data type!
What is an abstract data type
A conceptual model of how data can be stored and the operations that can be carried out on the data
Name the data structure that holds a set of related data items stored under a single identifier.
This can also work on one or more dimensions
Array (List)
What is a Record
Is one line of a text file or array
What is a Field
an item of data
What is a Queue? (use XIXO)
FIFO - can be static or dynamic data strucutre
What is a Stack? (use XIXO)
LIFO - can be static or dynamic data strucutre
What is a Linear Queue? (use XIXO)
FIFO - organised as a line of data (like a list)
What is a Circular Queue? (use XIXO)
FIFO - organised as a ring, using front and rear pointers (re-uses lost memory)
What is a Priority Queue? (use XIXO)
FIFO - some data may leave out of sequence if it has priority, high priorities go to the top
What is a Graph?
A way of describing relationships between pairs of objects
Define vertex/vertices
Object in a graph (known as a node)
What is an Arc?
A join or relationship between two nodes (known as an edge)
Graphs can be undirected, directed and…
weighted and unweighted
What is an Adjacency List?
Data structure to store a list of nodes and adjacent nodes
What is an Adjaceny Matrix?
Data strucutre as a 2D array that shows if there is a relationship between each pair of nodes (think times table grid)
What is a Tree?
Data strucutre very similar to a graph, except with no loops
Define a Hash Table
A data structure made of two parts.
1) A table or array of data
2) a key which identifies the location of the data within the table
Name some uses of hashing algorithms
- Used to create indicies for databases enabling quick storage and retrival of data
- Used to generate memory addresses where data will be stored. (especially with cache memory where it is stored temporarily)
- Used to encrypt data. In this case the algorithm must be complex so it cannot be reverse engineered.
What is a dictionary?
A data structure that maps keys to data
What is an Associative Array?
Like a dictonary but two-dimensional. A 2D data strucutre containing key/value pairs of data.
Define the technique chaining.
A technique for generating a unique index when there is a collision by adding the key/value to a list stored at the same index.
Define the technique rehashing.
The process of running the hashing alogrithm again when a collision occurs.
What is a component of a vector?
The values within the vector
What is a scalar?
A real value used to multiply a vector to scale the vector.
What is a dot product multiplication?
Multiplying two vectors together to produce a number
What is convex combination?
A method of multiplying vectors that produces a resulting vector within the convex hull
Define the term convex hull
A spatial representation of the vector space between two vectors.
Define the term vector space
A collection of elements that can be formed by adding or multiplying vectors together.
Given two vectors, u = [1, 1, 1, 1] and v = [1, 0, 1, 1] work out the dot product u.v
= 1 AND 1 XOR 1 AND 0 XOR 1 AND 1 XOR 1 AND 1
= 1 XOR 0 XOR 1 XOR 1
= 1
