Computer Science II - Juniata College
Computer Science II
100 pts (out of 105)
Spring 2004 2/27/04
Name _____________________________
1. Match each data structure with one of the sets of characteristics on the right.
[10 pts]
a. ______ Array
b. ______ Stack
c. ______ Queue
d. ______ Record
e. ______ Set (mathematical)
A. Heterogeneous, linear, random access
B. Homogeneous, linear, LIFO
C. Homogeneous, linear, FIFO
D. Homogeneous, non-linear, random
E. Heterogeneous, non-linear, LIFO
F. Homogeneous, linear, sequential
G. Homogeneous, linear, random access
2. Rank the algorithm complexities from "fastest" to "slowest" (increasing dominance). 1 is fastest (good, low cost) and 6 is slowest (bad, high cost).
[5 pts]
|quadratic |exponential |linear |constant |logarithmic |O(n log n) |
| | | | | | |
3. For each of the cost functions below give the “best” big-O equivalence where n is the data set size and k is some constant not related to the size of data.
[8 pts]
_______ f(n) = 3n3 + 900n + 50
_______ f(n) = 17 + log2n + 5/n
_______ f(n) = 10n10 +8n
_______ f(n) = 2n2 + 5k7
4. For each of the data structure operations below, give the algorithm complexity running time cost. Choose from “constant”, “linear”, “quadratic”, and “logarithmic”
[7 pts]
a) ________________ retrieving the maximum value from a sorted list
b) ________________ searching a list with a binary search
c) ________________ adding an element to the end of an array (that physically still has room)
d) ________________ deep copying an array over to another array
e) ________________ inserting an element into the middle of a sorted array
f) ________________ popping an element from a stack
g) ________________ computing the sum of the squares of an array of doubles
5. Estimate the running times using the big-O notation for each of these code segments. The size of the data set is n.
[8 pts]
| |j=n; |
| |while(j>0){ |
|____________ |// 3 assignments |
| |j = j-2; |
| |} |
| |for (i=1; i ................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- programming contest preparation
- javascript texas a m university
- student lab 1 input processing and output
- computer science ii juniata college
- department of mathematics and statistics university of
- cs department home
- reminders for students
- python programming project university of south alabama
- technical publications
- list of experiments mait4us
Related searches
- igcse computer science workbooks pdf
- igcse computer science workbook
- igcse computer science workbook answer
- igcse computer science coursebook pdf
- computer science people
- what is computer science like
- computer science revision
- igcse computer science revision notes
- college computer science project ideas
- ideas for computer science project
- computer science projects for students
- computer science final project