Department of Computer Science

University of Illinois at Urbana-Champaign

Computer Science 101: Final Exam  (120 minutes)

 


Name:                                                                         NetID:
 

Lab Section:                                                                Date: Dec 13, 2005

 


No questions will be answered during this examination.  If you do not understand a question, read it again.  If you still do not understand it, make reasonable assumptions and write them down. (Points will be deducted if unreasonable assumptions are made.)
DO NOT CHEAT: Cheating includes not only copying from another person but also allowing someone to copy from you.  Anyone who copies or allows someone to copy will receive a score of zero.  So be defensive and protect your work.

 

This examination contains 10 pages including this page. Check that your copy is complete, and ask for a replacement if it is not. Do all your work on these pages. For your own protection, in case pages come apart, write your NetID at the TOP of each page before beginning work.

The number of points for a question is roughly proportional to the amount of time you may need for it. Don’t spend too much time on any one question.

Do not forget to sign the attendance list and to write your signature on the line below:

 

_______________________________________________________________________
(If your exam is misplaced and you did not sign the attendance list then you will receive a zero score for the exam.)

You may not use any electronic devices, book, notes or other references during this examination.

DO NOT WRITE IN THIS SPACE

Section

Possible Score

Score

Grader

1

15

 

 

2

18

 

 

3

10

 

 

4

12

 

 

5

18

 

 

6

15

 

 

7

12

 

 

8

10

 

 

9

12

 

 

10

8

 

 

11

12

 

 

12

18

 

 

13

12

 

 

14

12

 

 

15

12

 

 

16

20

 

 

17

16

 

 

18

18

 

 

Total

250

 

 

A

 

 

1.      The following program compiles and runs without errors.  Write the output of this program.

#include <stdio.h>
int g; /* Declaration of global g */
void f(int a[]) {
    g = a[0];
    a[0] = a[1];
    a[1] = g;
}
void main(void) {
    int b[2] = {3, 5};
    g = 1;        /* NOTE: g is not declared here */
    f(b);
    printf("%i %i %i \n", b[0], b[1], g );
}


_____________________________________________________________




2.      Complete the function named count below.  The function count takes no parameters and returns the total number of times it has been called. Hint: Use a static variable.
For example, when the following program is executed, it should produce the output,


x = 2 count = 3

#include <stdio.h>

      
int count(void);

void main(void){

int x;
  x = count();
  x = count();
  printf("x = %i count = %i \n", x, count());
}

/* write the code for the count function here */
int count(void) {

 

 

 

 

 

 

 

 


}

3.      The following program compiles and runs without error. Write the output of the program.

 

#include<stdio.h>

 

void swap(int* , int* );

 

void main(void){

  int x = 0;

  int y = 5;

  swap(&x, &y);

  printf("x = %d y = %d\n", x, y);

}

 

void swap(int* a, int* b){

  int* temp = a;

  *a = *b;

  *b = *temp;

}

 








 

4.      The following program compiles and runs without error.  Write the output of the program.

 

#include <stdio.h>

 

void main(void) {

 

  int x[] = {4, 8, 15, 16, 23, 42};

  int i;

  int *p1;

  int *p2;

 

  p1 = x;

  p2 = &p1[2];

  p2[3] = 1;

  p1[2] = 2;

  for(i = 0; i < 6; i++)

    printf("%d ", x[i]);

 

}

 

 

 

 

 

 

 

 

 

 

5.      The following program compiles and runs without errors.  Write the output of this program.

#include <stdio.h>

 

void swap1(int* a, int* b){

  int temp = *a;

  *a = *b;

  *b = temp;

}

 

 

void swap2(int* x){

  int temp = x[0];

  x[0] = x[1];

  x[1] = temp;

}

 

void swap3(int* a, int b){

  int temp = *a;

  *a = b;

  b = temp;

}

 

void main(void){

  int a[3]={1, 2, 3};

  int b[3]={1, 2, 3};

  int c[3]={1, 2, 3};

  int* ptr;

 

  swap3(&a[0], a[1]);

  printf("%d %d %d\n", a[0], a[1], a[2]);

  swap2(b);
      printf("%d %d %d\n", b[0], b[1], b[2]);
      ptr = &c[1];

  swap1(&ptr[0], &ptr[1]);

  printf("%d %d %d\n", c[0], c[1], c[2]);

}

 



 


_____________________________________________

 


_____________________________________________



_____________________________________________

 

 

 

 

 

6.      Fill in the blanks to complete the function swap below, to reverse the order of letters in a string.  For example, if the user typed “abcd”  as input then the output of the program would be “dcba”.  However your program should work for any length string that doesn’t include blanks(spaces).  

 

#include <stdio.h>

#include <string.h>

 

 

void swap(char* a, char* b){ /* swaps one character */

 

  char temp = ___________________ ;

  *a = ____________________ ;

  *b = ____________________ ;

}

 

void flip_string(char* str){

int i;

int len = strlen(str); /* determine the length of the string */

for(i = 0; i < len/2; i++)

    swap(&str[i], &str[len-i-1]);

}

 

void main(void){

  char str[1024];

  printf("Enter a string: ");

  scanf("%s", str);

  flip_string(str);

  printf(" %s \n", str);

}

 

 

 

 

7.      Fill in the blanks to complete the following function.  The function writeInteger should write the value of its integer parameter my_arg to the file "output.dat".  Assume that the call to fopen is successful.

 

void writeInteger(int my_arg) {

FILE * fptr;

fptr = fopen(________________,_______________);

             fprintf(_____________,______________,____________);


fclose(______________);

}

 

8.      Fill in the blanks in the code below.  Use malloc to dynamically allocate an array of 150 values of datatype double. Assume that the call to malloc succeeds.  Finally, release the memory allocated for the array.

 

double *ptr;

ptr = __________________________________; /* call malloc */
/* some code not shown here */

 

___________________________ ; /* release space used for array */

 

 

 

9.      Fill in the blanks to complete the function named get_copy .  This function takes an array of datatype double and an integer giving the length of that array as input. The function get_copy dynamically allocates an array of the same size and copies the values of the original array into the new array.

double * get_copy(double arr[], int length) {

 int i;

 double * copy;

   
 copy = malloc(________________________________________);

 
 for (i=0 ;  _____________________ ; i++ ) {



      ________________________ = arr[i] ;

 }

 return copy;

}

 

 

 

 

 

 

10.  The following program compiles and runs without errors.  Write the output of this program.

#include <stdio.h>

void main(void) {

    char * c = "Walk the Line";

    printf("%c ",c[3]);

    printf("%c ", *c);

}

 

 

 

 

 

 

 

 

11.  Write C code to define a new data type called book, a structure to store  information about books. It should have the following fields:

 

- title (string, max length 40 characters)

- author (string, max length 25 characters)

- number_of_pages (integer)

- price (floating point number)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

12.  Given the following structure definition:

  typedef struct {

      double x;

      double y;

} vector;

 

Write a function named norm that computes and returns the norm of a vector.  The input to

norm is a pointer to a vector.  Recall that the norm of a vector with values (x,y) is . 

You can use functions from the C math library.

 

double norm(vector *v) {

 

/*Write your code here */

 

 

 

 

 

 

 

 

 

 

 

 

 

}

Problems 13, 14, and 15 refer to the following structure and array:

 

typedef struct {

 

char name[100];

int width;

int height;

 

} photo;

photo album[1000];

 

13.  Fill in the blanks in following code fragment to read data for 1000 photos into the array album. The data will be read using Unix redirection from the file “input.dat”.  Below is an example of the file content for one photo(one row of the file “input.dat”):

 my trip to hawii;  100; 150


    Each row in the file “input.dat” has the same format, specifically,

 
 name; width; height

 where two semicolons (;) are used to separate the values.

int i;

for (i = 0; i < 1000 ; ++i)

scanf(_____________________________________________,


_______________,___________________,__________________);



 

14.  Fill in the blanks in the following function. We want qsort to sort an array of datatype photo in ascending order by the value in the name field.

 

int compare_photo_names(photo *a, photo *b) {

 

   return strcmp(____________________, _____________________);

}

 

 

 

 

15.  Fill in the blanks in the call to qsort to sort all 1000 elements of the array named album .

 

qsort (_______________________, __________________________ ,


______________________________, compare_photo_names);

     

16.  Parts a) and b) refer to the following structures:

typedef struct {

 char name[40]; /* the name of a student */

 float total;   /* the total score of a student */

} Student;

 

typedef struct {

 char name[4];/* name of a section, e.g. “AYA”, “AYB”, etc. */

 int num;     /* actual number of students in a section */

 Student students[30]; /* section quota is 30 students */

} Section;

 

Suppose that the CS 101 TAs store information about each student in each section of CS 101 in the following array:

 

Section sections[12];

 

where each Section is defined as above.

 

 

a)      Assuming that all twelve elements of the array named sections have been initialized with data, fill in the blanks to call the qsort function in order to sort the students within each section by their total score in descending order. You will use compare_totals as your “compare” function.  Assume that i has been declared as an integer variable.

 

for( i = 0 ; _________________; _______________)

qsort ( sections[i].students , ______________________________,

           _______________________, ______________________  );

 

 

b)      Fill in the blanks and then complete the following comparison function (for use with qsort above) in order to sort the students in each section by their total score in descending order.

 

int compare_totals( ___________________, __________________) {

 

/* write your code here */

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

}

17.  The following program compiles and runs without errors.  Write the output of this program.

#include <stdio.h>

 

int game(int x){

   if (x == 0)

     return 0;

   /* Hint: % gives the remainder,example 5%2 is 1 */

   if( (x % 2) != 0 )

     return 2 * game(x - 1);

   else

     return 1 + game(x - 1);

}

 

void main(void){

   printf("%i %i %i %i\n",game(0), game(1), game(2), game(4));

}


Output: _________________________________________________________________

 

 

 

  1. Fibonacci numbers are well-known in math and computer science. Each Fibonacci number is the sum of the two previous ones, yielding the sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ... . If we denote the nth Fibonacci number as Fn, then Fibonacci numbers are defined by the following set of equations:

F0 = 0, 
F1 = 1, 
Fn = Fn-1 + Fn-2   for n >= 2


Write a recursive function called fibonacci , which given a non-negative integer argument n