Programming: Data Structures Flashcards
List some data types
•integer
•string
•float
•boolean
•character
•nothing
What is a data type?
They represent the category of data being stored, not the data itself
List some data structures
Built in:
•List
•Array
•Dictionary
•Tuple
•Set
User defined:
•Stack
•Queue
•Tree
•Graph
•Hash map
Define Static data types
The size of the data structure cannot be changed during run time. The content can be modified but the memory allocated to it stays the same
Is an array:
a) [1,2,3]
b) {1,2,3}
c) {1:’c’, 2:’a’,3:’t’}
b
Describe the meaning of “data structure”
A container within which information is stored
Give three properties of an array
-finite
-indexed
-only containing elements of the same data type
-mutable
Give examples of data types
-interger
-float
-string
-boolean
-null
Give examples of user defined data structures
-stack
-queue
-tree
-linked list
-graph
-hash map
Give examples of built in data structures
-list
-array
-dictionary
-tuple
-set
Describe a static data structure
Size of the data structure is fixed and cannot be changed in runtime. The data contained in the structure may be modified but the memory allocated to it does not.
Describe a dynamic data structure
The size of the data structure can be changed in run time. The data stored in the data structure as well as its memory space allowed can be modified
Difference between dynamic and static data structures:
-dynamic: memory is allocated dynamically/as the program executes
Static: memory is allocated at comple time. Fixed size
Advantage of static data structures:
-easier to add and remove elements, with fast access times
-locations of items within the structure do not need to be kept track of, simple indexing
Disadvantage of static data structures:
-if a large amount of memory is allocated to the structure, space could easily be wasted.
-stack overflow errors possible
Advantage of dynamic data structures:
-uses memory efficiently as the structure only takes up as much space as it needs
Disadvantage of dynamic data structures:
-harder to program with, as the size of the structure and the locations of items within it need to be monitered
Describe an abstract data structure:
Don’t exist as data structures in their own right, but use other data structures (like arrays) to form a new way of storing data
Give an example of an abstract data structure:
-queues
-stacks
-graphs
What data structure is a queue based on?
An array.
What type of abstract data structure is a queue?
FIFO structure
Where are queues used in a computer system?
-used in keyboard buffers. Each key pressed is added to the queue and removed once it has been processed/displayed- meaning letters appear in the same order they were pressed
Give other examples of queues in action:
-keyboard buffer
-printer management
-task scheduling
-breadth-first search algorithms
What is a BFS
breadth first search algorithm
What is a breadth first search algorithm?
Used in searching tree data structures for a specific node. Begins at the root and searches each node on a current depth before moving on to the nodes at the next depth level.
How is a queue used in breadth first search algorithms?
Keeping track of which nodes have been visited
Describe a linear queue containing (in order) the numbers 1,2,3 and 4
Each number would occupy a space in the queue in order. The front queue pointer would point to the 1, at the front of the queue and the rear pointer would point to the EMPTY position after the 4.
Describe the movement of the pointers if an item is added to a linear queue.
The rear pointer moves along a place, to point to the next available position after the most recently added value.
Describe the movement of the pointers if an item is removed from a linear queue
The front pointer moves to the item after the removed item. The rear pointer does not change.
Define a priority queue
A queue in which certain items have priority over others and are ordered as such. Items of a higher priority will leave the queue first.
Give two examples of uses of a priority queue
-processor scheduling
some applications take priority over others when being handled by the processor, an application being used by a user would be prioritised over a background application.
-in a school printer queue, a teachers items may take priority over a students.
describe the movement of pointers if an item is added to a circular queue
the rear pointer, previously pointing to the closest empty position in the queue to the front pointer, will move down by one space. The space previously occupied by the rear pointer will now contain the new value.
describe the movement of pointers if a value is removed from a circular queue
the front pointer will move to the next available space
what are some operations that may need to be carried out before enqueueing or dequeueing?
checking if a queue is empty or full
Describe a stack
A first in, last out abstract data structure
What data structures are stacks based on?
An array
What are some functions that can be performed on a stack?
-push
-pop
-peek
-IsFull()
-IsEmpty()
Errors with stacks and queues
-if an item is added/pushed to a queue or stack when there is no more space, an overflow error occurs
-if an item is removed/popped from a queue or stack when there are no items in the data structure, an underflow error occurs
Describe a graph
An abstract data structure consisting of nodes(or vertices) and edges (or arcs).
Describe a weighted graph
A weighted graph has values assigned to the edges between nodes.
Describe a directed graph
Edges imply direction using arrows between nodes
What is an adjacency matrix?
A grid that assigns a row and a column to each node. If an edge exists a one is placed, if not a 0. For weighted a graphs, the value of an edge can be placed instead of a 1 and infinity instead of 0.
What is an adjacency list?
Each node is listed, with each node it has an edge with listed next to it.
Disadvantage of adjacency matrix
Memory inefficient, stored every possible edge between nodes, even ones without edges. Almost half of the matrix is repeated data.
Adjacency matrix advantage
Time efficient. Allows edge to be queried quickly, just by looking up its row and column
Adjacency list advantage
Memory efficient, only stores edges that exist.
Adjacency list disadvantage
Time inefficient. Each item in the list must be searched sequentially until the desired edge is found.
In what situations should a matrix or a list be used?
Matrix for dense graphs with many edges, lists for sparse graphs with few edges.
Describe three qualities of a tree
-connected
-undirected
-no cycles(circles)
Define a rooted tree
A tree with a root node from which other nodes stem. Contains parent,child nodes and leaf nodes. A node can be both a child and a leaf, a parent and child or a root and a parent node.
Define a binary tree
A rooted tree where each parent has no more than two child nodes.
Describe a use of a rooted tree
-file systems on a computer hard drive
Time complexity of a hash table
O(1)
Describe the concept of a hashing algorithm (4)
-takes an input and returns a hash
-hash is unique to the input
-hash cannot be reversed to retrieve the input value
-hashing algorithms often include MOD function
Describe the process of RECORDING values in a hash table
-the value being stored in the table is hashed, to produce a key.
-the value is then stored, alonside the key, in the table.
Describe the process of RETRIEVING values from a hash table.
-the value being looked up is hashed to produce the key.
-the table is queried with the key generated and the information is located
What happens if two different values produce the same hash value?
-COLLISION
-in a poorly designed hash table, data is overwritten
-rehashing can be used to generate a different position in the table: commonly searching for the next available spot.
-when this rehashing has occurred, the position is found and then each corresponding value is queried until the correct information is found.
Describe a dictionary
-A collection of key value pairs
-a value is accessed by its key
Vector addition can be completed in two ways:
-with arrows, tip to tail.
-adding each component
What does scalar multiplication affect?
Magnitude, not direction
Describe the convex combination of vectors:
for two vectors, a and b, convex combination is ax + by.
Describe the dot/scalar product
A single number derived from the components of the vectors, determine the angle between two vectors.
Perform the dot product (scalar product) on (12,3) (5,8).
(12 x 5) + (3 x 8) = 84
