CS 180 Exam Three Terms and Concepts
Concepts from previous exam such as:
- program components, variables, data types and how to choose
them, various arithmetic operations, ways to control formatting of
output, if-then-else statements, relational and logical operators,
loops, functions, including pass-by-value and pass-by-reference
parameters
Chapter 7
- arrays: various ways to declare and initialize arrays,
distinguishing type of index (always
unsigned
,
use size_t
) versus type of data (anything you want,
often int
or double
so far), access
elements by position, size fixed at compile time, importance of
bounds checking
- range-based for loop: aka the foreach loop, loops through
array of values automatically, use a reference variable to modify elements of
the array
- whole array assignment & comparison: only way is
item by item, usually using a loop
- common array algorithms: print contents, sum contents,
compute average, find min/max, find position of min/max or some
arbitrary element
- parallel arrays: same position used for data about the
same entity, but stored in different arrays, perhaps of different
types
- arrays as function parameters: generally always
pass-by-reference, need to pass the size separately, should
be
const
if array is unchanged in function
- multi-dimensional arrays: relevant to lots of real-world
situations, double-subscripting for two-dimensional arrays, nested
for loops are especially helpful, you need to have a mental image of
the data to know how to use the array, use dimension parameter names
to help with this, passing multi-dimensional arrays as parameters,
must specify all dimensions except the leftmost
- array problems: static size, size must be known at
compile time, arrays don't know their size, lack of bounds
checking
- vectors: from the Standard Template Library (STL), how to
declare, how to initialize, how to add values
(
.push_back
), use
of size_t
, .size()
to determine
size, .at(index)
to access elements, always pass by
reference or const
reference
Chapter 8
- searching: linear search is pretty much the only option
for unsorted data, usually implemented with a
while
loop, main operation is comparison, return position of matched
element or size (as opposed to -1) to indicate item is not
found, analysis: requires n/2 comparisons on average when
item is found,
n comparisions when item is not found
- binary search: useful for searching sorted lists, know
the algorithm, be able to specify what elements are examined during
a binary search, be familiar with implementation, analysis:
takes log (base 2) of n comparisons, cuts search space in half at
each step, know powers of 2
- sorting: put values in an array (or vector) in
nondecreasing order, understand Bubble sort and Selection sort
algorithms and be able to work through them yourself, understand how
code works, be familiar with
swap
function
Chapter 9
- variable addresses: be familiar with address operator (&)
and
sizeof
operator
- pointer variables: variable to hold an address, similar
to, but different from reference variables, declaring a pointer
(
int *pointer = &value;
), usually draw memory
pictures with pointers as arrows to address they point to,
dereference a pointer using * operator
- pointers and arrays: array names are const pointers, can
use them as pointers or use standard array syntax, pointer
arithmetic allows code to dereference the next address
using
pointer + 1
syntax, compiler does this because it
knows the size of things, can compare pointers, pointers can be
passed as parameters
- dynamic variable allocation: compile time variables are
allocated from the runtime stack, dynamically allocated variables
are allocated from the heap,
new
operator is
used for dynamic allocation, new
returns the address of
the allocated memory, so pointer variable is necessary, normally
involves dynamic allocation of arrays whose size is determined at
allocation time
- memory management:
new
operator allocates
memory, delete
operator deallocates memory, it is
important that every new
must eventually be followed by
a delete
, otherwise your program has a memory
leak