CSCI 160: Fundamentals Practice

Are you ready for the CSCI 160 final exam?

The questions below test the majority of what you are expected to be able to do having completed CSCI 160. It is much longer than a final exam, and is not meant to be completed in a single sitting. It should probably take 8-12 hours to complete all sections of all questions, but it is excellent practice for the final exam and should give you a good indication of your abilities and state of preparation for the exam.

Try to complete the questions without using your notes or computer, just the C++ quick-reference sheet.

Once you have completed a section, go to the lab and check your answers by actually coding and debugging them - the practice is extremely valuable!

Preliminaries

For each of the questions below, provide a brief explanation and code example showing the difference between ...
  1. ... data types and data values
  2. ... variables and constants
  3. ... declared constants and literal values
  4. ... 'a' and "a"
  5. ... '3' and 3
  6. ... the = operator and the == operator
  7. ... =, +=, and ++
  8. ... variables and parameters
  9. ... "%d", "%f", and "%g" for printf/scanf
  10. ... "%c" and "%s" for printf/scanf
  11. ... boolean expressions and arithmetic expressions
  12. ... when the / operator represents integer division and when it represents floating point division
  13. ... integer division and modulo (%)
  14. ... top-tested loops and bottom-tested loops
  15. ... function calls, prototypes, and implementations
  16. ... pass-by-reference parameters and pass-by-value parameters
  17. ... when we do/do not use a return type of void for a function
  18. ... the & operator in a function's formal parameters, such as void f1(int &x) and its in the actual parameters as part of a function call, such as f2(&y);
  19. Show the output that would be produced by each of the following code segments:
    Code segment Output
    int x = 3;
x = x + 1;
x++;
printf("%d\n", x);

    

    bool a = true;
bool b = false;
bool c = a;
bool d = !a;
if (a) {
   printf("a is true\n");
} else if (!a) {
   printf("a is not true\n");
} else {
   printf("neither is true\n");
}
if (a && b) {
   printf("a and b are true\n");
}
if (a || b) {
   printf("a or b is true\n");
}
if ((a && b) || (!c)) {
   printf("ugh, that was true\n");
}

    

    




Part 1: basic coding


 
Write four complete C++ programs as follows:

    
   
  1.  A program that prompts the user to enter a single integer
           whose value is in the range 2 to 100 (inclusive),
           reads the value they enter, and then displays either
           "Correct" or "Incorrect" depending on whether or not
           the value they entered was actually in that range.

    















    
   
  2.  Re-write the program from part 1, but this time use a do-while loop to
           get the program to keep prompting/asking/checking until the
           user provides a valid response.

    




















    
   
  3.  Add a new section to the program from part 2: after they 
           have entered the valid integer, N, treat that as the number
           of floating point values you now need to read from the user,
           computing their sum as you go.  Display the sum once all the
           values have been entered.

    Example:
Please enter an integer in the range 2-100
4
Please enter your 4 numbers:
3.1
2.0
100.1
50.2
The sum of the values you entered is 155.4

    

    





























    
   
  4.  Expand the code you added in part 3, this time keeping track
           of the smallest value they have entered so far.  After each 
           value they enter, tell them what the smallest value so far is.
           Remember to still keep track of the sum of all the values as
           you go, and print that at the end.

    Example:
Please enter an integer in the range 2-100
4
Please enter your 4 numbers:
3.1
The smallest so far is 3.1
2.0
The smallest so far is 2.0
100.1
The smallest so far is 2.0
50.2
The smallest so far is 2.0
The sum of the values you entered is 155.4

    

    






























    



 

Part 2: program reading/comprehension I


(a) Study function f below, then answer questions 1-4.

int f(int a, int b)
{
   int result = 0;
   for (int i = 1; i <= b; i++) {
       result = result + a;
   }
   return result;
}



    
   
  1.  What value does f(2,3) return?

    

    
   
  2.  What value does f(4,1) return?

    

    
   
  3.  What value does f(3,3) return?

    

    
   
  4.  What basic math operation does this function compute?

    


    



(b) Now study function p below (which uses the function f
above) then answer questions 1-5.

int p(int x, int y)
{
   int result = 1;
   for (int j = 1; j <= y; j++) {
       result = f(result, x);
   }
   return result;
}



    
   
  1.  What value does p(2,1) return?

    

    
   
  2.  What value does p(2,2) return?

    

    
   
  3.  What value does p(2,3) return?

    

    
   
  4.  What value does p(2,4) return?

    

    
   
  5.  What basic math operation does this function compute?

    


    



(c) Now study functions f1, f2, and f3 below,
then answer questions 1-4.

void f1(int &m, int &n)
{
   int t = m;
   m = n;
   n = t;
}
void f2(int &a, int &b, int &c)
{
   if (a < b) { 
      f1(a,b); 
   }
   if (b < c) { 
      f1(b,c); 
   }
   if (a < b) { 
      f1(a,b); 
   }
}
void f3(int x, int y, int z)
{
   printf("%d, %d, %d\n", x, y, z);
   f2(x, y, z);
   printf("%d, %d, %d\n", x, y, z);
}



    
   
  1.  Show the precise output produced by the call f3(1,2,3); 

    


    
   
  2.  Show the precise output produced by the call f3(3,2,1); 

    


    
   
  3.  Show the precise output produced by the call f3(0,6,0); 

    


    
   
  4.  What is function f2 effectively doing to a, b, and c?

    


    



(d) As precisely as possible, show the complete output from
the following program:

#include <cstdio>

int x = 1;

int f1(int x);
void f2(int &x);

int main()
{
   printf("A: %d\n", x);
   int x = 2;
   printf("B: %d\n", x);
   x = f1(x);
   printf("C: %d\n", x);
   f2(x);
   printf("D: %d\n", x);
}

int f1(int x)
{
   x++;
   printf("E: %d\n", x);
   return x;
}

void f2(int &x)
{
   printf("F: %d\n", x);
   x = 6;
   for (int x = 4; x <= 4; x++) {
      printf("G: %d\n", x);
   }
   printf("H: %d\n", x);
   x++;
   printf("I: %d\n", x);
}





 

Part 3: types of loops


For each of the sections below, I provide either a code segment
using either a for loop, while loop, or do while loop.
Your job is to provide a equivalent code segments using the
other two kinds of loops.





for loop version

while loop version

do-while loop version


for (int x = 10; x > 5; x--) {
    printf(".");
}
printf("\n");





char inputChar;
do {
   printf("Enter any character\n");
   scanf("%c", &inputChar);
   printf("You entered \'%c\'\n", inputChar);
} while (inputChar != 'Q');



int x = 0;
int y = 10;
int z = 100;
int total = 0;
while (x < 5) {
   while (y <= z) {
      total = total + (y - x);
      y = y * 2;
   }
   x++;
}




Part 4: program reading/comprehension II


For each of the programs below, show as precisely as possible the
exact output the program would produce.



function

call and output

void f1(int n)
{
   int width = n;
   while (width > 0) {
      for (int i = 0; i < width; i++) {
          printf("x");
      }
      printf("\n");
      width--;
   }
}


call: f1(4);

void f2(int r, int c)
{
   for (int row = 0; row < r; row++) {
       for (int col = 0; col < c; col++) {
           if ((row == 0) || (row == r-1)) {
             printf("-");
           } else if ((col == 0) || (col == c-1)) {
             printf("|");
           } else if (col == row) {
             printf("*");
           } else {
             printf(" ");
           }
       }
       printf("\n");
   }
}

call: f2(5,5);

void f3(int n)
{
   for (int width = 1; width <= n; width++) {
       for (int i = 0; i < width; i++) {
           printf("y");
       }
       printf("\n");
   }
}

call: f3(3);

void f4(int n)
{
   f3(n-1);
   for (int i = 0; i < n; i++) {
       printf("*");
   }
   printf("\n");
   f1(n-1);
}

call: f4(3);



 

Part 5: array basics



    
   
  1.  Write a main routine that declares an array to
           hold 10 integers, gets the user to enter ten integer values
           (storing them in the array), then prints the array contents
           after all 10 values have been entered.

    
















    
   
  2.  Re-write the main routine from the program in part 1
           to call one function to fill in the
           array contents, and another to print them.  For both functions
           passing the array and the size as parameters.

    
































    
   
  3.  Write a complete program that declares an array to hold
           50 characters and uses getc to read 50 chars from the user,
           storing them in the array, and then uses a loop to print
           the 50 characters in the array one at a time.

    

















    

   
  4.  Write a complete program that declares an array to hold
           100 characters and uses fgets to read a line of input from
           the user, storing the content in the array,
           and then uses a single printf statement to print the array
           contents.

    














    

   
  5.  Write a length function that takes a null-terminated
           character array as a parameter and returns the length of the
           array (the number of characters that appear before the 
           null terminator).
           
    
           Add the function to your program from part 4, and have the
           main routine pass the character array to it, then display the
           length returned.

    
























    





Part 6: algorithms and implementation


For each of the sections below, either a code segment
or an algorithm is provided. 


For the sections where an algorithm
is provided, write an appropriate code segment that implements the
algorithm as closely as possible.


For the sections where a code segment is provided, write an algorithm
that concisely summarizes/describes what the code is doing.





Algorithm

Code



void shift(float arr[], int size, float fill)
{
   for (int pos = size-1; pos > 0; pos--) {
       arr[pos] = arr[pos-1];
   }
   arr[0] = fill;
}




gcd(x,y) computes the greatest common divisor of x and y
(the largest positive integer that evenly divides both)

put the larger of x and y is L
    and the smaller in S
repeat until S is 0:
   store a copy of S
   divide L by S, putting the remainder in S
   replace L with the earlier stored copy of S
return L




// lcm(x, y) computes the least common multiple of x and y,
//    using the gcd function defined above 
int lcm(int x, int y)
{
   return x * y / gcd(x,y);
}



fibonnaci(N)
   if N is less than 2
      return 1
   otherwise 
      return fibonnaci(N-1) + fibonacci(N-2)




int fib(int N)
{
   int prevFib = 1, currFib = 1;
   for (int n = 3; n <= N; n++) {
       int temp = currFib;
       currFib = currFib + prevFib;
       prevFib = temp;
   }
   return currFib;
}




 

Part 7: dynamic array allocation and use

Write a complete program that:

    
   
  1.  declares a float* variable to store an array address,
   
  2.  declares an int variable to store the size of the array,
   
  3.  asks the user what array size they want and reads the size
        they enter,
   
  4.  allocates an array of that many floats,
   
  5.  checks that the allocation succeeded,
        ending the program if it did not succeed
   
  6.  prompts the user to enter the specified number of values
        and stores them in the array,
   
  7.  prints the array contents,
   
  8.  deletes the array
































 

Part 8: iteration versus recursion


For each of the sections below, either a recursive function (a function
that calls itself) is provided or an iterative (non-recursive) 
function is provided.


For the sections where an iterative function
is provided, write an equivalent recursive version of the function.


For the sections where a recursive function is provided, write an 
equivalent iterative function. 





Recursive version

Iterative version

float getPositive()
{
   printf("Please enter a positive number\n");
   float val;
   scanf("%g", &val);
   if (val <= 0) {
      printf("%g is not positive, please try again\n", val);
      val = getPositive();
   }
   return val;
}


float sum(float arr[], int size)
{
   float total = arr[0];
   int pos = 1;
   while (pos < size) {
      total = total + arr[pos];
   }
   return total;
}



// binary search of part of a sorted array
int bsearch(float arr[], int lowPos, int hiPos, float target)
{
    int midPos = (lowPos + hiPos) / 2;
    int result;
    if (lowPos > hiPos) {
       result = -1;
    } else if (arr[midPos] == target) {
       result = midPos;
    } else if (arr[midPos] < target) {
       result = bsearch(arr, midPos+1, hiPos, target);
    } else {
       result = bsearch(arr, lowPos, midPos-1, target);
    }
    return result;
}




 

Part 9: structs 


Suppose we decide to use a struct to represent a fraction, 
with one (integer) field holding the denominator and another 
(also an integer) holding the numerator.



    

  1.  Write a definition for this new Fraction data type.

    




    

  2.  Write a main routine in which you create two Fraction variables,
   f1 and f2,
  and set appropriate values in the variable fields so that
   f1 represents 3/7 and f2 represents
   112/113

    














    

  3.  Write a function that takes a Fraction as a parameter
   and displays it in the form "%d/%d\n" with the numerator and denominator
   in the respective parts.  Have your main routine above call the function
   once to display f1 and once more to display f2.

    










    

  4.  Write a function that takes a Fraction as a
   pass-by-reference parameter and prompts the user to supply values
   for the numerator and denominator, then reads in the values the user
   supplies and sets the Fraction fields appropriately.

    











    

  5.  Re-write your main routine to call the function on f1 and then
   f2 to set their values instead of the initialization you used
   in step 2 above.

    















    

  6.  Create an array of 5 Fractions in your main routine,
   and use a for loop to call your function from step 5 to initialize
   each of them.  Once all 5 array elements have been initialized, use
   a second for loop to call your other function to print each of them.

    


















    



 

Part 10: switches and enumerated types 


Show the output from the following programs:





Program
Output


#include <cstdio>

void f(char c);

int main()
{
   f('x');
   f('H');
   f('q');
}

void f(char c)
{
   switch (c) {
      case 'q':  
         printf("quitting!\n");
         break;
      case 'h':
         printf("sorry, I have no help to give you!\n");
         break;
      default:
         printf("hmmm, I don\'t understand that\n");
         break;
   }
}



#include <cstdio>

enum CommandType { 
   Quit = 'Q', 
   Help = 'H', 
   Invalid = '*' 
};

void processCmd(CommandType cmd);

int main()
{
   CommandType c = Help;
   processCmd(c);
   c = Invalid;
   processCmd(c);
   processCmd(Quit);
}

void processCmd(CommandType cmd)
{
   switch (cmd) {
      case Quit:  
         printf("quitting!\n");
         break;
      case Help:
         printf("sorry, I have no help to give you!\n");
         break;
      default:
         printf("hmmm, I don\'t understand that\n");
         break;
   }
}





 

Part 11: searching and sorting 

Write functions that follow the algorithms described below


Algorithm
function



linear search of an array of floats,
   parameters: the array, its size, and the search target

for each position in the array
   if the target matches that array element
      return the current position
if no match was found
   return -1






bubblesort on an array of floats,
   parameters: the array, its size

repeat size-1 times:
   for positions 0 through size-2
       if the element in the current position
          is larger than the next element
          swap their positions in the array






selection sort on a null-terminated array of chars,
   parameters: the array

for positions p=0 through size-2
    smallest = the element in position p
    smallestpos = p
    for positions p+1 through size-1
        if the value in the current position
           is less than smallest, then
              set smallestpos equal to its position
              and set smallest equal to that value
        swap the values in positions p and smallestpos





 

Part 12: linked lists 


Suppose we want to represent a linked list of items where each item
contains a student number, that student's current g.p.a., and a pointer
to the next item in the list.


The definition we have chosen to use for an individual item is this:

struct StGPA {
   long   StuNum;
   float  GPA;
   StGPA* next;
}


To represent an entire list, we will have a struct that keeps track
of the front and back items in the list:

struct GPAList {
   StGPA* front;
   StGPA* back;
};


To manipulate the list, we have the following function prototypes:

// given a student number and a gpa,
//    allocate a StGPA item, fill in its fields,
//    and return a pointer to it
StGPA* create(int stnum, float gpa);

// initializes both fields of L to NULL
//   to represent an empty list
void init(GPAList &L);

// given a list and an item, insert the item at the back of the list
//    returning true if successful, false otherwise
bool insert(GPAList &L, StGPA* st);

// print all the student information currently in the list
void print(GPAList L);

// release all StGPA items in the list,
//    then reset L's fields to NULL
void release(GPAList &L);




(a) Write a main routine that declares a variable of type GPAList
to hold a list of student numbers and gpas, and make appropriate function calls
to initialize the list and then
insert the following student numbers and gpas (in this order)

555666777 4.1
567890123 2.3
666777888 3.1 


Add a call to print the list contents, and a call to release all the list contents.
























(b) Write an implementation of the create function,
the init function, and the print function.



 StGPA* create(int stnum, float gpa)














 void init(GPAList &L)














 void print(GPAList L)















 

Part 13: architecture and the fetch-decode-execute cycle 


Briefly describe the role of each of the following components in a basic
computer architecture:

    
  
  1.  The processor

    



    
  
  2.  Main memory

    



    
  
  3.  The bus

    



    
  
  4.  Secondary storage 

    



    
  
  5.  The memory cache

    


    


In your own words, briefly describe what the fetch-decode-execute cycle is,
and what happens in each of the key steps.












 

Part 14: software concepts 


In  your own words, briefly describe the meaning and significance of each of
the following concepts in a software development context:


    
   
  1.  Encapsulation

    


    
   
  2.  Abstract data types

    


    
   
  3.  Incremental development

    


    
   
  4.  Modularity

    


    
   
  5.  Top-down design

    


    
   
  6.  Software standards

    


    


 

Part 15: Testing and debugging 


Suppose someone has written a function that is supposed to
display times in the format hh:mm and
the function prototype is

 // given hours in the range 0..23 and minutes in the range 0..59
 // if both parameters are in range, this function
 //    displays the time in the format hh:mm
 // if any of the parameters are out of range, this function
 //    displays the message "invalid time supplied"
 void displayTime(int hours, int minutes);


Your task is to provide a compact list of test calls that could be
used to see if the function is working correctly, e.g.
displayTime(23,59);, displayTime(-1,-1);, etc.


Provide the list of calls and why those test values were chosen.

























 

Part 16: two-dimensional arrays 


One of our most commonly used two-dimensional arrays is the argv
array for command line arguments.  Complete the main routine shown below
so that it prints the second and second-to-last character of each
'word' in argv.

#include <cstdio>
int main(int argc, char *argv[])