Exam (elaborations)
CPSC 1110 - Exam 2 Solved Correctly To Score A+
- Course
- Institution
CPSC 1110 - Exam 2 Solved Correctly To Score A+
[Show more]
Content preview
CPSC 1110 - Exam 2 Solved Correctly ToScore A+
Definition of array CORRECT ANSWERS Indexed data structure that holds a collection
of multiple variables of the same type in the same name
Array declaration CORRECT ANSWERS type name[size];
Initializer lists (4) CORRECT ANSWERS Values separated by commas, whole thing in
braces
Can omit size of array, it'll figure it out based on initializer list
If initializer list too short for array, the rest of the array will be initialized to 0
Can specify indices like [0] = 1
Do #define statements need a ; CORRECT ANSWERS No
What do variables contain without initialization CORRECT ANSWERS Garbage
What does array name refer to CORRECT ANSWERS Base address, a pointer to the
first element
What happens if you go too far in a row in a 2D array CORRECT ANSWERS It wraps
around to the next row
Address of an element in a 2D array CORRECT ANSWERS base + rowIndex *
(rowElements * elementSize) + colIndex * elementSize
How to declare strings CORRECT ANSWERS In quotes (automatically puts \0)
With initializer list (you need to put \0)
How to declare size for strings CORRECT ANSWERS # characters + 1 (for \0)
How to use strings w/ scanf CORRECT ANSWERS %s
Don't need & because the array name is a pointer
How to get string length CORRECT ANSWERS strlen() in string.h (doesn't count \0)
Multidimensional arrays syntax CORRECT ANSWERS array[rows][cols]
What happens if you refer to just 1 index of a 2D array CORRECT ANSWERS It'll give
you a row
, Bubble sort CORRECT ANSWERS Traverse array, bubble the largest value to the end
each time using pairwise comparisons. Then run again, but ignore the ith-last element
because it has to be in the correct place
Worst case scenario of bubble sort and complexity CORRECT ANSWERS Worst case:
Runs n-1 times (because after n-1 times, the first element HAS to be in the right spot
b/c everything else is)
O(n^2)
Possible improvement to bubble sort CORRECT ANSWERS If during a pass, nothing
was swapped, end early
What to use when swapping CORRECT ANSWERS Temp value to prevent data
destruction
Exchange sort CORRECT ANSWERS Sort of like bubble sort
For each element, it compares that to all elements above it, swapping if necessary.
After each pass, the ith element is in the right spot
Merge sort CORRECT ANSWERS Uses divide and conquer
Divide unsorted array into 2 halves recursively until subarrays contain only 1 element.
Merge the subarrays must picking the lesser of the first remaining elements from each
subarray. Repeat until all elements are sorted for the sub-problem. Then merge one
level higher until the entire array is sorted
Divide and conquer CORRECT ANSWERS Divide the problem in half recursively until
the problem is trivial, solve both halves, then combine
Complexity of merge sort CORRECT ANSWERS O(N*log2(N))
Selection sort CORRECT ANSWERS Find min value of unsorted part of list, swap it to
the place where it's supposed to go (last element of new sorted part). Repeat so the
nth-smallest element is at index n-1
Complexity of selection sort CORRECT ANSWERS O(n^2)
Insertion sort CORRECT ANSWERS Go through and put each element in its correct
spot in the beginning "sorted" part of the array. Basically, if a value is less than the max
of the sorted part, shift elements right until you find the correct place in the array and put
the value there
Dealing with array size CORRECT ANSWERS sizeof(array) returns size of array in
bytes (number of elements * size of type)
sizeof(array) / sizeof(type or array[0]) returns number of elements
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller ElevatedExcellence. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $11.99. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
79373 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now