CS102

     
                                                                   (1 point) USER NAME: ___________________________

CS 102 Final Exam, May 1, 2008

(4 points) What is displayed by the code segments below? Please be careful!


  a. int a = 33, b = 15, c = 40;

     if(a < b || a < c)  {  
       if(b <= c && a != b)  a += b;
       else if(a == c)  a += c;
     }
     else a = b + c;
     cout << a << endl;



  b. a = 33; b = 15; c = 40;

     if(a == b || b < c)  {
       if(a > c)  
         a++;
     }
     else  a--;
     cout << a << endl;

(6 points) Rewrite the following as a functionally equivalent while loop.
(4 points) This question is about the binary search as shown in class.
How many probes will it take to find 19?

(6 points) Trace the code segment below and fill in the ASCII diagram with the indicated characters.


  char two_d [NROWS][NCOLS];    // NROWS and NCOLS are even global constants
  int row, col;
  
  // initialize array to blank spaces
  for(row = 0; row < NROWS; row++)
    for(col = 0; col < NCOLS; col++)
      two_d[row][col] = ' ';         // initilize to blanks

  // YOU TRACE THIS PART
  for(row = NROWS / 2; row < NROWS; row++)
    for(col = 0; col < NCOLS / 2; col++)
      two_d[row][col] = '*';


              0   1   2   3   4   5 
            -------------------------
         0  |   |   |   |   |   |   |   
            -------------------------
         1  |   |   |   |   |   |   |
            -------------------------
         2  |   |   |   |   |   |   |
            -------------------------
         3  |   |   |   |   |   |   |
            -------------------------
         4  |   |   |   |   |   |   |
            -------------------------
         5  |   |   |   |   |   |   |
            -------------------------

(4 points) What is the output from the following code segment?


int x = 628;          
cout <<  x / 10 % 10  <<  x % 10  <<  x / 100  << endl;

(4 points) You have int a[7] = {54, 35, 77, 41, 22, 62, 13};
Show the array elements after the first and second passes of selection sort as shown in class. ------------------------------------------- pass 1: | | | | | | | | ------------------------------------------- 0 1 2 3 4 5 6 ------------------------------------------- pass 2: | | | | | | | | ------------------------------------------- 0 1 2 3 4 5 6
(4 points)
a. What are the two things that malloc() does?
    1.
    2.

b. What are the two things that free() does?
    1.
    2.

(4 points) Fill in the new array values after the code segment is executed. Leave no blank array elements.


const int N = 8;
int i, A[N] = {0, 11, 22, 33, 44, 55, 66, 77};

for (i = 0; i < N-1; i++)      // notice: N-1
  A[i] = A[i+1];

             _________________________________________
             |    |    |    |    |    |    |    |    |
original A:  |  0 | 11 | 22 | 33 | 44 | 55 | 66 | 77 |
             |---------------------------------------|
                0    1    2    3    4    5    6    7

             _________________________________________
             |    |    |    |    |    |    |    |    |
     new A:  |    |    |    |    |    |    |    |    |
             |---------------------------------------|
               0    1    2    3    4    5    6    7

(6 points) Rewrite my_cmp() so it contains a single exit point. Declare any variables that you need.


int my_cmp (char *one, char *two)     // one and two are C-style strings
{
  int i;

  i = 0;
  while( 1 )  {
    if(one[i] < two[i])  return -1;
    if(one[i] > two[i])  return  1;
    if(one[i] == '\0')   return  0;
    i++;
  }
}

(4 points) You have the following code fragment. What is printed with the indicated input values?

cin >> x;
switch(x)  {   
    case 40:  x %= 6;  
    case 60:  x--;  x--;  break;
    case 80:  x += 100;  
    default:  if(x)  x = -x;
}
cout << x << endl;

  a) input: 40   _________

  b) input: 80   _________

(4 points) Rewrite as functionally equivalent code using if-else instead of the ? : operator.
```
  int x = 10, y = 1;
  cout << (x != y && x == 100 ? "yes\n" : "no\n");
```

(4 points) What (not how) does the following code do? Hint: Trace with input 123.


 int x, y;

 for(y = 0, cin >> x;              // expr1 
   x != 0;                         // expr2 
   y = x % 10 + y * 10, x /= 10);  // expr3, null body 

 cout << endl << y << endl;

(6 points) Examine the code below.
b. What is the value of the loop control variable when the loop terminates?

(3 points) Examine the code below and show what is printed.


  int a[8] = {60, 38, 43, 22, 71, 10, 47, 52}; 
  int *p; 

  for(p = a + 2; p < a + 8; p += 2) 
    cout << *p << "  "; 
  cout << endl;

(3 points) What is printed from the code segment below?


vector <int> list (10);
cout << "Number of elements in list:  " << list.size() << endl;

4 points) What gets printed?


#include <iostream>
using namespace std;
void trace(int, int *);

int main()
{
  int x = 43, y = 55, *ptr = &x, *q = &y;

  trace(x, q);
  cout << "In main:  " << *ptr << "  " << *q << endl;
}

void trace(int x, int *q)
{
  int y;

  y = 2;

  *q += y;
  y = x / 10;
  cout << "In trace:  " << y << "  " << *q << endl;
}

(4 points) Complete function read_it() to read values into integer vector v. Stop when either the vector is full or you reach eof. You may assume valid data.
```
vector  read_it(vector <int> v)
{

 

 

 










}
```

(5 points) Rewrite this recursive function using iteration.


int factorial(int n)
  {
    if (n == 0) return 1;
    return n * factorial(n-1);
  }

KEY

1a.  48    b.  33

2.  i = 0;  
    power = 1;
    while(i <= 6)  {
      cout << i << setw(4) << power << endl;
      i++; 
      power *= 2;
    }

3.  2

4.            0   1   2   3   4   5 
            -------------------------
         0  |   |   |   |   |   |   |   
            -------------------------
         1  |   |   |   |   |   |   |   
            -------------------------
         2  |   |   |   |   |   |   |   
            -------------------------
         3  | * | * | * |   |   |   |   
            -------------------------
         4  | * | * | * |   |   |   |   
            -------------------------
         5  | * | * | * |   |   |   |
            -------------------------

5.  286

6.  pass 1:  13  35  77  41  22  62  54
    pass 2:  13  22  77  41  35  62  54

7a. 1. malloc() allocates the requested amount of space from the heap, and
    2. malloc() returns the address of the allocated space. 

 b. 1. free() returns to the heap the space pointed to by its argument, and 
    2. the pointer is then undefined. 

8.  11  22  33  44  55  66  77  77

9.  int my_cmp (char *one, char *two)     
    {
      int i, result;
    
      i = 0;
      result = 999;
      while(result == 999)  {
        if(one[i] < two[i])  result = -1;
        else if(one[i] > two[i])  result =  1;
        else if(one[i] == '\0')   result =  0;
        i++;   cout << i << endl;
      }
      return result;
    }

10a.  2    b. -180

11. if(x != y && x == 100)  cout << "yes\n";
    else cout << "no\n";

12. It reverses the digits of x.

13a. It skips over leading blanks in the input.
  b. a non-blank character

14. 43  71  47

15. Number of elements in list:  10

16. In trace:  4  57
    In main:  43  57

17. vector  read_it(vector  v)
    {
      int i;

      for(i = 0; i < v.size() && !cin.eof(); i++)
        cin >> v[i];
      return v;
    }

18. int factorial(int n)
      {
        int fact = 1;

        while(n != 0)  {
          fact *= n;
          n--;
        }
        return fact;
      }