-
March 6th, 2008, 12:55 AM
#1
CS-315 Practice test
i didnt really know where to post this, but I figured alot of us are CS major or have taken upper level cs classes (or no stuff about them)
Ok so basically I have this practice online test for computer science.
preparing us for the real test: which is prolly alot of the same answers.
we dont have a book(there is no book for the class). so i figured i'd ask for help here...since he doesn't have a "KEY" to the actual real test....so
anyways here's the test
put into code format so it's easier to see
Code:
315f04-ex1-practice-a
315s08"Smith"
1)
provide the best rate of growth using the big-Oh notation for
1+2+...+n
I don't know.
O(n^2)
O(n)
O(n^3)
315s08"Smith"
2)
provide the best rate of growth using the big-Oh notation for
1 + 2 + 4 + ... + 2^n
I don't know.
O( 2^n)
O(n log n)
O(n)
O(n^2)
315s08"Smith"
3)
provide the best rate of growth using the big-Oh notation for the solution to the following recurrence
T(1) = 3
T(n) = T(n/2) + 6 for n>1
I don't know.
O(1)
O(n)
O(log n)
O(n log n)
315s08"Smith"
4)
provide the best rate of growth using the big-Oh notation for the solution to the following recurrence
T(1) = 1
T(n) = 2 T(n/2) + 6 for n>1
I don't know.
O( n log n)
O(n)
O(log n)
315s08"Smith"
5)
Recurrence that describes in the best way the number of
addition operations in the following program fragment is:
int example(A, int l, int r) { if (l == r) return 2;
return (A[l] + example(A, l+1, r);
}
I don't know.
T(1) = 1
T(n) = T(n-1) + 1 for n>1
T(1) = 1
T(n) = T(n/2) + 1 for n>1
T(1) = 1
T(n) = 2T(n/2) + 1 for n>1
315s08"Smith"
6)
The algorithm design paradigm that often leads to recursive algorithms is called:
I don't know.
iterative approach
optimization
divide and conquer
315s08"Smith"
7)
What is the the length of the sequence of a's outputted by the following program when called for n = 8?
question(int n)
{ if (n > 0) then
question(n-1);
cout << " a \n";
question(n-1);
}
I don't know.
8
511
255
1
315s08"Smith"
8)
What is the upper bound on the running time of the following fragment of a program, measured as the number of additions in a++?
for (i = 1; i <=n; i++)
for (j = n; j >=1; j--)
a++;
I don't know.
O(n)
O(n2)
O(n log n)
O(n3)
O(log n)
O(1)
315s08"Smith"
9)
What is the upper bound on the running time of the following fragment of a program, measured as the number of additions in a++?
for (i = 1; i <=n; i++)
for (j = 1; j <= n; j=2*j)
a++;
I don't know.
O(n3)
O(log n)
O(n)
O(1)
O(n log n)
O(n2)
315s08"Smith"
10)
What is the number of move operations in the recursive solution to Towers of Hanoi program for n rings?
I don't know.
2n-1
n
2n+1 -1
2n -1
315s08"Smith"
11)
How many multiplications are used to compute a128 using the fast exponentiation algorithm?
I don't know.
8
1
7
128
0
4
none of the listed
315s08"Smith"
12)
The GCD (Greatest Common Divisor) of two numbers a >= b can be computed with the Euclidean (Euclid) algorithm:
function gcd(a, b)
if b = 0 return a
else return gcd(b, a mod b)
For example, the values of arguments for a = 8, b = 5 while calling the above algorithm are:
a | b
-----
8 | 5
5 | 3
3 | 2
2 | 1
1 | 0
and the algorithm returns 1 since the last line above is a = 1, b = 0. The second to the last line is a = 2, b = 1.
Your question is: what is the second to the last line for gcd(34, 21)?
I don't know.
34,7
2,1
1,0
none of the listed
315s08"Smith"
13)
Is it true that if f(n)=O(n3) and g(n) = O(n3) then f(n)- g(n) = O(n3)?
I don't know.
never
sometimes
always
315s08"Smith"
14)
Is it true that if f(n)=O(n) and g(n) = O(log n) then f(n)*g(n) = O(n log n)?
I don't know.
false
true
315s08"Smith"
15)
If algorithm with T(n) = 3n takes 5 minutes to solve an instance of size 15, how long will it take to solve an instance of size 16?
I don't know.
125
15
10
45
none of the listed
315s08"Smith"
16)
Consider a recursive function:
void hh(int n, int a, int b)
{ if (n < 0) return;
hh(n-2, b, a);
cout << a << b;
hh(n-2, b, a);
}
In the following version, is the tail recursion removed correctly:
void hh(int n, int a, int b)
1: { if (n < 0) return;
hh(n-2, b, a);
cout << a << b;
n=n-2;
a = b;
b = a;
goto 1;
}
I don't know.
no
yes
what i have so far is.(dunno if their right tho.......) cause I could be way OFF (he's a hard teacher to understand so i proly am) but I figure I can check the answers with yall (this is just pracitice but it'll help if I have the real answers
1.o(n)
2.(o(2^n)
3.o(log(n)
4.o(n log n)
5.no clue
6.no clue
7.255
8.O(N^2)
9.O(log n)
10.2n-1
11.8
12.2,1
13.never
14.false
15.15
16.yes
thats just what i got....if anyone can give me any info....i'd be greatly appreciative. I have a feeling alot of mine are wrong, but I wanna get the practice test done.....so i can do well on the real test.
thx
Last edited by MercenaryFH; March 6th, 2008 at 01:35 AM.
-
March 7th, 2008, 08:07 AM
#2
Re: CS-315 Practice test
It's a practice test man, doesn't it show the answers after finishing it ?
Regards,
Ramkrishna Pawar
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|