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.

Google Online Preview   Download