Question 1. (pointer and structures)

What is the output of the following program?

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct sample{
   int a;
   int b;
   char name[21];
};

void print_struct (const struct sample *p){
   printf("a : %d\nb : %d\nname : %s\n", p->a, p->b, p->name);
}

int main(){
   struct sample * p = malloc(sizeof(struct sample)*2);
   struct sample *q;
   p->a=10;
   p->b=11;
   strcpy(p->name,"cs240");
   print_struct(p);
   (p+1)->a=12;
   (p+1)->b=13;
   strcpy((p+1)->name,"midterm");
   print_struct((p+1));
   q = (p+strlen((p+5%2)->name)%2);
   print_struct(q);
   return 0;
}

Answer:

a : 10
b : 11
name : cs240
a : 12
b : 13
name : midterm
a : 12
b : 13
name : midterm


The key to answering this question is realizing that (a) the region
allocated by malloc is partitioned to contain space for two 'sample'
structures, and that (b) the expression (p+1)->a refers to the second of
these structures.  Thus, the first printf prints the first structure, the
second prints the second (whose contents are assigned by structure
manipulating expressions involving (p+1)); the third printf refers to the
second structure as well, since the value of (p+strlen((p+5%2)->name)%2) =
p+strlen((p+1)->name)%2 = p+strlen("midterm")%2 = p+1.

================================================================

Question 2. (casts)

What is the output of the following program?

#include <stdio.h>
int main()
{
   char array[10] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'};
   char *cptr = (char *)&array;
   int *iptr = (int *)&array;

   cptr += 2;
   iptr += 2;

   printf("%c\n", *cptr);
   printf("%c\n", *(char *)iptr);

   cptr = (char *)(((int *)cptr) + 1);
   iptr = (int *) (((char *)iptr) + 1);

   printf("%c\n", *cptr);
   printf("%c\n", *(char *)iptr);
}

Answer:

c
i
g
j

cptr is a pointer to an array of characters named array.  The assignment
cptr+=2 sets the pointer to character 'c' defined in this array.  On the
other hand, iptr treats 'array' as a collection of integers; the assignment
iptr+=2 thus has iptr index 8 bytes into the array, or the character i.
cptr is subsequently cast to an integer and incremented by 1 (i.e., 4 bytes)
which now has it pointing to g; conversely, iptr is cast to a character
pointer, and incremented by 1 which now has it pointing to j.  

================================================================

Question 3. (pointers)


What are the values of i,j,ptr, *ptr, pptr, and **pptr after
executing the following (write '?' if the value is unknown):

int i = 5, j = 10;
int *ptr;
int **pptr;

ptr = &i;
pptr = &ptr;
*ptr = 3;
**pptr = 7;
ptr = 8; 
**pptr = 9;
*ptr = &i;
*ptr = 2

Answer:

i = 7
j = 10
ptr = address 8
*ptr = 2
**pptr = 2

ptr initially points to 5, and pptr points to ptr, so **pptr has the value
5.  The assignment **pptr thus changes i to 5. The effect of the assignment
ptr = 8 is unspecified since it assigns ptr to memory location 8 which may
not be a valid accessible location; it would thus be acceptable to say that
ptr has value '?'.  Assuming the location is defined, however, the
subsequent assignments would have the location finally get the value 2.  If
you wrote '?' for the value of ptr, then *ptr and **pptr would have value
'?' as well.  Both solutions are acceptable.

================================================================

Question 4. (unions)

Please complete the following program to correctly output a student's grades.

The output should be:
Chemistry: 72/100
Computer Science: 100/100
Underwater Basket Weaving: F



#define PASS_FAIL 1
#define STANDARD 2

typedef union {
       int points; /* out of 100 */
       char pf;    /* 'P' for pass, 'F' for fail */
} grade;

typedef struct {
       int type;
       char name[50];
       grade g;
} course;

void printGrades(course *courses, int numCourses)
{
       int i;
       for(i = 0; i < numCourses; i++)
               if(__________________________________)
                       printf("%s: %i/100\n", courses[i].name, courses[i].g.points);
               else
                       ____________________________________________________________
}

int main()
{
       course cArray[3];

       strcpy(cArray[0].name, "Chemistry");
       strcpy(cArray[1].name, "Computer Science");
       strcpy(cArray[2].name, "Underwater Basket Weaving");

       ________________________
       ________________________
       ________________________

       cArray[0].g.points = 72;
       cArray[1].g.points = 100;
       cArray[2].g.pf = 'F';

       printGrades(cArray, 3);
}

Answer:

#include <stdlib.h>
#include <stdio.h>

#define PASS_FAIL 1
#define STANDARD 2

typedef union {
       int points; /* out of 100 */
       char pf;    /* 'P' for pass, 'F for fail */
} grade;

typedef struct {
       int type;
       char name[50];
       grade g;
} course;

void printGrades(course *courses, int numCourses)
{
       int i;
       for(i = 0; i < numCourses; i++)
	 if (courses[i].type == 2)
            printf("%s: %i/100\n", courses[i].name, courses[i].g.points);
	 else  printf("%s: %c\n", courses[i].name, courses[i].g.pf);
}

int main()
{
       course cArray[3];

       strcpy(cArray[0].name, "Chemistry");
       strcpy(cArray[1].name, "Computer Science");
       strcpy(cArray[2].name, "Underwater Basket Weaving");

       cArray[0].type = 2;
       cArray[1].type = 2;
       cArray[2].type = 1;

       cArray[0].g.points = 72;
       cArray[1].g.points = 100;
       cArray[2].g.pf = 'F';

       printGrades(cArray, 3);
}


The field named 'type' in structure course is used to properly discriminate
the union defined by grade.  Since the desired output requires that
Chemistry and Computer Science have a grade type based on points, and that
Underwater Basket Weaving has a grade type that is P/F, we simply need to
assign the respective instances of the structure in the array 'cArray' the
appropriate type value.  The #define declarations indicate that courses with
P/F should be assigned value 1 and standard grades should have value 2; this
is also consistent with the definition of printGrades that assumes
course structures whose type field has value 2 are associated with numeric
grades.

================================================================

Question 5. (malloc)


The strcatX function returns a new string by concatenating the two strings provided as arguments. 
Please fill in the missing lines.

char *
strcatX(const char *s1, const char *s2)
{
	char *s = malloc(________________________);
	__________________________
	__________________________
	return s;
}


Answer:

char *
strcatX(const char *s1, const char *s2)
{
	char *s = malloc(strlen(s1)+strlen(s2)+1);
	strcpy(s, s1);
	strcat(s, s2);
	return s;
}

Since we need to concatentate two input strings, the size of the resulting
string should be sum of the sizes of the two inputs; moreover, the first
part of this output string should contain the first string (hence, the
strcpy), and the second part of the output string can be constructed by
appending the second input to the end of the first (strcat).  Clearly, to
have this work properly, sufficient space to hold both strings must exist,
thus the need for the initial malloc.

================================================================

Question 6. (function pointers)

What is printed by the following program? Write '?' if it would print garbage.

#include <stdio.h>

void add(int *arg1, int *arg2) { *arg1 += *arg2; }

void mul(int *arg1, int *arg2) { *arg1 *= *arg2; }

void sub(int *arg1, int *arg2) { *arg1 -= *arg2; }

void (*getOp(int op))(int *, int *) { 
  switch(op) {
    case 0: return &add;
    case 1: return &mul;
    default: return &sub;
   }
}

int main() {
  int i;
  int x = 2, y = 3;

  for(i = 0; i < 4; i++) {
   getOp(i % 3)(&x, &y);
   printf("x = %d ... y = %d\n", x, y);
  }
}

Answer:

x = 5 ... y = 3
x = 15 ... y = 3
x = 12 ... y = 3
x = 15 ... y = 3

Looking at the definition of getOp, we see that it takes an integer
input op as an argument, and returns a function pointer that refers to
functions which take two integers as arguments, and which have no
defined return value.  In main, we call getOp 4 times with integer
values 0, 1, 2, and 0.  The first call invokes add which x and y (2
and 3), and stores the result in x, which results in 5 being printed.
The second call results in an invocation of mult, which multiples 5
and 3, resulting in 15.  The third call results in the default case
(&sub) being called from getOp, thus resulting in the evaluation of
15-3 = 12 being assinged to x.  Finally, the last call invokes add
again, resulting in x being assigned 12 + 3 = 15.


================================================================

Question 7. (code comprehension)

The following function takes as argument two strings hay and needle. The
function will return 1 if the string needle is contained in the string hay,
or 0 if hay does not contain the string needle. 

Please fill in the missing pieces.  NOTE: Your solution should NOT use any 
string functions such as strcpy, strlen etc.

int contains(char * hay, char * needle) 
{
	int i, j;
	
	// for all positions of hay
	i = 0;
        
        // Have not come to the end of string hay 
	while (________) {  

		// Check if at needle matches at this position in hay
		j = 0;
		while (hay[____] != 0 & needle[___] != 0 && ______________) {
			// Match this character. Go to next one
			__________;
		} 

		if (needle[j]==0) {
			// Found match
			return 1;
		}
                // perform search from next position in hay
		___________;
	}

	return 0;
}

int main(int argc, char **argv) {

	if (argc<3) {
		printf("Usage: contains hay needle\n");
		exit(1);
	}

	if (contains(argv[1], argv[2])) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
}

Answer:

#include <stdio.h>

int contains(char * hay, char * needle) 
{
	int i, j;
	
	// for all positions of hay
	i = 0;
	while (hay[i]!=0) {

		// Check if at this position i needle matches
		j = 0;
		while (hay[i+j] != 0 & needle[j] != 0 && hay[i+j]==needle[j]) {
			// Match this character. Go to next one
			j++;
		} 

		if (needle[j]==0) {
			// Found match
			return 1;
		}

		i++;
	}

	return 0;
}

int main(int argc, char **argv) {

	if (argc<3) {
		printf("Usage: conatins hay needle\n");
		exit(1);
	}

	if (contains(argv[1], argv[2])) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
}


We should continue to compare hay and needle as long as there are characters
in hay we've not examined, i.e., as long as hay[i] != 0 (and we already
haven't found a match).  Once we have a new position in hay, we need to
match characters pairwise between the two strings.  Given the index j
(initially 0) that represents the position in needle, the expression
hay[i+j] moves the comparison along string hay (and hay[i+j] !=0 makes sure
we've not reached the end of hay); the expression needle[j] != 0 checks that
we have not reached the end of needle; and, the check hay[i+j] = needle[j]
holds when the respective characters in the two strings match.  If the check
fails, we need to continue iterating, incrementing our position in hay
(i++).