fundamentals of data structure Flashcards
what is a static data structure
- a data structure fixed in size which cannot increase in size or free up memory while the programming is running.
e. g. an array
what is a dynamic data structure
- a collection of data in memory which can increase or decrease in size using heap
- heap allocates and de-allocates space as its needed
e. g. linked list
what is a queue
- a first in first out (FIFO) data structure.
- elements are added to the end of the queue and removed form the front.
- this sequence is determined by the order they are placed in the queue
what is a linear queue
- a queue implemented with pointers to the front and rear of the queue.
- rear points to the last item in queue and front points to the first
- an integer holding the arrays max size is created
- a variable holding the number of current items is created
- items cannot be added to the front even if those elements are free
- they are added to the back until the rear pointer points to the last element in queue
what is a circular queue
-a queue where the rear pointer points to the fist element when another item is added if the first element is free and the array is full
what is a priority queue
- a queue where items are removed from the front but their place in queue is determined by priority.
- this makes it possible for items to join the front of the queue.
- this can be implemented by checking each new items priority against the the current
what is a stack
- a last in, first out(LIFO) data structure
- items are added to the top and removed form the top
name 4 uses for stacks
- calculations
- subroutines: hold and return memory addresses when subroutines are called
- browsers: hold webpages allowing you to move back and forth between them
- undo: last operation is popped from the stack and undone
name 5 stack operations
- push(item) :adds new item to the top of the stack
- pop() :removes item form the top of the stack
- peek() : returns item on the top of the stack but does not pop it
- isEmpty() : checks if stack is empty
- isFull() : checks if stack is full
name 3 uses of a queue
- print jobs: first jobs put in are printed first.
- character typed: held in queue on keyboard buffer.
- simulation problems: customers arriving at checkouts
name 4 queue operations
- enQueue(item) :adds new item to the end of the queue
- deQueue() :removes item form the front of the queue
- isEmpty() :checks if queue is empty
- isFull() :checks if queue is full
what are stack underflow and stack overflow
- stacks have a maximum size as memory cannot grow
- if a stack is full and an attempt to push an item is made an overflow error will occur
- if a stack is empty and an attempt to pop an item is made an underflow error will occur
what is a call stack
a stack data structure is used to store information about a subroutine while the program is running
what are 3 functions of a call stack
- holding the return address: keeping track of the address of the instruction that control should return to
- holding parameters:
- local variables: each call to a subroutine gets its own space for its local variables without using heap space
what is a graph
-a data structure used to
represent more complex relationships. using a set of vertices/nodes connected by edges/arcs
directed graph vs undirected graph
- undirected: the edges are bi-directional
- directed: the edges are one-way
what is a weighted graph
-a graph where the edges show the cost of moving from one vertex to another
what is an adjacency matrix (3)
- a way to implement a graph using a two dimensional array to store the information
- each row and column represent a node
- if the graph is weighted the value will be stored if not 1s will be used.
what is an adjacency list
- a more space efficient way to implement a graph using a list.
- a list of all the nodes which point to the nodes they are directly linked with. the weight can be held next to each linked node
5 applications of graphs
- computer networks - weight=bandwidth
- roads between towns - weights=distance
- tasks in projects
- states in finite state machine
- web links and pages
what is a tree
a connected undirected graph with no cycles
name the 7 parts of a tree
- node: contains tree data
edge: connects 2 nodes - root: only node with no incoming edges or parent
- child: set of nodes with the same parent/ incoming edges form the same node
- parent: connects with outgoing edges
- subtree: set of nodes made of a parent and descendent
- leaf node: a node with no children
what is a rooted tree
a tree with only one root node ( a node with no parents)
3 uses of a rooted tree
- manipulating hierarchical data
- making information easier to search
- manipulating sorted lists of data
what is a binary tree
a rooted tree with a maximum of two children per parent which is used to search for items quickly
benefits of binary trees
- easy to search for a specific item
- easy to add an item
- easy to print the whole tree in sequence
what are the three ways of traversing a binary tree
- pre order traversal: output data as you pass its left
- in order traversal: output data as you pass under it
- post order traversal: output data as you pass its right
how to implement a binary tree
a binary tree is implemented using an array of records with each node consisting of a left pointer, the data item and a right pointer
what can 1-D arrays be used to represent
vectors
each element of the array hold a sequential number in the vector
array vector[0]= 2.0 vector[1]= 3.14159 vector[2]= 1.0 vector[3]=2.71
what is an array
an array is a finite ordered set of elements of the same type
what is a 1 dimensional array
a 1 dimensional array can be thought of as a simple table
what is a 2 dimensional array
a 2 dimensional array has 2 dimensions.
can be thought of as having a x and y axis
what is a multi dimensional array or an array of n dimensions
an array that is a set of elements of the same type indexed by a tuple of n integers.
a tuple is an ordered list of elements
adjacency list pros and cons
con: Time efficient
Slow to query, as each item in a list must
be searched sequentially until the desired
edge is found
pro: Memory efficient
Only stores the edges that exist in the
graph.
Well suited to sparse graphs, where there
are few edges.
adjacency matrix pros and cons
con: Memory inefficient.
Stores every possible edge between
nodes, even those that don’t exist.
Almost half of the matrix is repeated data.
pro: Time efficient
Allows a specific edge to be queried very
quickly, as it can be looked up by its row
and column.
Well suited to dense graphs, where there
are a large number of edges.
pros, cons and best use of static data structure
pros: doesn’t need to store pointers
cons: can end up with empty element which is memory inefficient
best use: when the amount of data is known
pros, cons and best use of dynamic data structure
pros: can increase in size
cons: has to store pointers which takes up memory
- complicated to keep track off
best use: when there is no max size of the data structure
