CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  1. #1
    Join Date
    Sep 2007
    Posts
    55

    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.

  2. #2
    Join Date
    Aug 1999
    Location
    <Classified>
    Posts
    6,882

    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
  •  





Click Here to Expand Forum to Full Width

Featured