fundamentals of data structures Flashcards
data structure
the arrangment of data
one dimensional array
stores data in one direction
useful way of representing a vector
two dimensional array
stores data horizontally and vertically
useful way of representing a matrix
example:
triplets = [[a,b,c], [d,e,f], [g,h,i]]
triples[2,1] = h
binary files
formatted so only one a program can read them
text files
contain characters structured as lines of text
why files must be closed
closing free up resources, preventing corruption and ‘flushes’ the buffer
record
usually for a single entity
heterogenous
subprogram
an ‘out of line’ block that performs a specific task
(can be ither user written or pre existing)
how can subprogram be used
by calling their name in a statement causing them to be executed
how can data be passed in to a sub routine
through parameters (variables used for the input to the subroutine)
two types of subprograms
procedure (doesn’t return a value)
functions (returns a value
structured programming
improves the quality and clarity of code
pros for structured programming
code is more readable and easier to understand
easier to test
modules can be reused
steps in adding a record to a hash table
- apply hash function to calculate the hash value for the key .
- use the hash value to find the index in the hash table so that the new record could be stored.
- check if there is a record at the index. if yes, use a collision resolution technique.
- insert the new record at the index in the hash table and update the number of records in the hash table.
two components of a stack frame
local variables and parameters
operation of a stack frame and test whether if empty or full
- initialize an empty stack
- push values onto a stack from left hand side.
- for each number in the expression; push it onto a stack. for each operator; pop the top two numbers off the stack.
- after both have been processed, the stack should contain only one value, which is the result of the expression.
- check if empty by comparing the stack pointer to the initial address of the stack
- check if full by comparing the stack pointer to the max address of the stack
Describe the method that would need to be followed to attempt to remove an item from a queue
- check if the queue is empty by comparing the front and rear pointer. if equal, the queue is empty and no item can be removed.
- if not empty, remove the front item from the front of the queue.
- update the front pointer to the next item in the queue. if the front pointer exceeds the size of the array, reset it to 0.
- reduce the count of items in the queue by 1
Describe the method that would need to be followed to attempt to add an item to a queue
- Check if the number of elements in the queue is equal to the maximum capacity. If it is, the queue is full.
- If it is not full, increment the count of elements in the queue.
Insert the item at the next available position in the queue. - Check if the number of elements in the queue is equal to the maximum capacity. If it is, the queue is full. If it is not full, return false or display an appropriate message.
three differences between dynamic and static data structures
static data structures memory are allocated at compile time/dynamic data structure memory are allocated at run time.
static data structure size is fixed and cannot change during runtime/ dynamic data structure size can be changed during runtime
static data structure memory is managed by compiler/ dynamic data structure memory is managed by the programmer
explain how a single stack can be used to reverse the order of the items in a queue
- deque all the items from the queue and push them onto the stack
- pop them off one by one and enqueue them back into the original queue
- the order of the items in the queue will be reversed
when does collision occur
when two key values compute the same hash.
dictionary
A collection of key-value pairs in which the value is accessed via the associated key.
application of dictionaries
information retrieval
what does vector addition and multiplication achieve
addition achieves translation and multiplication achieves scaling.
applications of dot product
Finding the angle between two vectors.
graph
data structure used to represent more complex relationships.
use of adjacency list instead of an adjacency matrix
when there are few edges between vertices
when edges are rarely changed
weighted graph
a graph where each edge has a weight
how do you know if a graph isnt a tree
if it contains a cycle
tuple
an ordered list of elements
tree
a connected, undirected graph with no cycles
does not have a root
binary tree
rooted tree in which each node has at most two children.
concept and use of a queue
linear data structure that follows the First-In-First-Out (FIFO) principle
used for tasks such as managing processes or handling requests in a sequential and ordered manner.
concept and use of stack
follows the Last-In-First-Out (LIFO) principle
used for function calls, recursion, and managing program execution.
peek or top
return the value of the top element without removing it
use of rooted tree
to represent family trees or file
systems on a computer’s hard drive
how are collision handled using rehashing
finding an available
position by moving to the next position until an available one is found.
