CS paper 1.. Flashcards
Subroutines and stack frames
-Each time a subroutine Is called the program jumps to a different part
-Once subroutine completes program needs to return to where it left off
-Before program jumps off subroutines needs to know where to return to and restore values of any local variables and parameters when returning
-This is achieved with a stack frame
before calling subroutine (what system needs to do)
-construct stack frame
-add return address to stack frame
-add local variables to stack frame
-push completed stack from onto stack
data structures
stacks,queues,graphs,trees,
hash tables,dictionaries ,vectors
arrays
-variable that can contain more than one data item
-allocating a contiguous part of memory for the purpose of storing that data
-contiguous = data is stored together, 1 elements after the other
-starts at index 0
-static data structure
list vs array vs tuple
list: mutable,items can be changed or replaced, store
> 1 data type
array: mutable, items can be changed or replaced, only store 1 data type
tuple: immutable, items cannot be changed or replaced, store > 1 data type
File handling
Refers to the opening, closing, reading from and writing to files by program code
Binary file
-Contains records with many different data types
A 15 figure number will occupy 15 bytes in standard text, but it would take up less space stored as a pure binary number
Reading binary file is language specific but requires you to know the exact structure of the file e.g. field sizes
Static data structure
-Is fixed in size and cannot free up memory while program is running
-An array is suitable for storing a fixed number of items e.g. months of the year
-The disadvantage is that the size of the array has to be decided in advance And if items fill up, the array no more can be added
- Also memory, which has been allocated to the array cannot be reallocated
-But no pointers or ther data about structure needs to be stored
dynamic data structure
- Collection of data, in memory that can grow or shrink in size
-Does this with aid of the heap - Useful for implementing data structures, e.g. queues when the maximum size of data structure is not know
-Unused memory reallocated As required while program running
stack operation
-push(item) = add item
-pop() = remove item
-peek() =return top value without removing
-isEmpty()
-isFull()
queue
- First in first out, data structure
-New element added to end of queue
-back pointer, point to last item
-front pointer, poin tto first item
Queue operations
- enQueue(item) = add new item to rear of queue
- deQueue() = remove front item from queue and return it
- isEmpty() = test whether queue is empty
- isFull() = test whether queue is full
circular queues
- When Array Fills up and rear pointer points to last element (e.g. q[5]) It will be made to the first element, (q0), when next person joins queue
-Requires extra effort for programmer and less flexible than dynamic data structure
application of queues
-processer schelduling
-Transferring data between processor and printer spooling
-Performing breadth-first searches on graph data structures
adding item to stack
-check if stack is already full
-increment stack pointer so it points to next available space in array
-push (insert) new items
add items to queue
-Check if Q is already full
-Increment back pointer so it points to next available space in arrray
-Insert (enqueue) new item at position pointed by back pointer
graph
data structure consisting of nodes and edges
can have more then 2 edges and point to any vertex
graphs can be weighted with edges givena value
edges can:
point in 1 direction (directed)
not specify a direction (undirected)
adjacency matrix
-a table that shows the relationship between vertices in a graph
-checking for presence/absence of edge requires accessing corresponding element in matrix
-sparse graph with many nodes but few edges, most cells empty, and bigger graphs means greater potential for wasted memory
-If using static 2D array, it can be harder to delete/add nodes
Adjacency list
- a data structure that stores the relationship between vertices in a graph
-checking for presence/absence of edge requires traversing list of corresponding vertex (O(k) time)
-space efficient wat to implement sparsely connected graph
-much less memory used
graph applications
-mapping road networks for navigation systems
-storing social network data
-resource allocation in operating systems
