Midterm Examination – 2 – Sample Questions-Introduction to Algorithms and Programming

60-141-01 Introduction to Algorithms and Programming
Winter 2017
Midterm Examination # 2 – Sample Questions

Question 1. [ 13 marks ]
Answer each part of this question. Each part is independent of the other parts.
A. Assume the following declarations: [ 2 marks ]
int X = 3, Y = 4 ;
char M[100] ;
Write a single C language statement that places the string “The sum of 3 + 4 = 7” into the array M and which refers directly to the variables X and Y. Your answer must also be correct in any case where the values assigned to X or Y are modified so that a different sum is involved. You may use any C library functions in your answer.
sprintf( M, “The sum of %d + %d = %d”, X, Y, X+Y ) ;

B. Assume that A and B are 4-bit storages. A contains the bits 0011, while B contains the bits 0101. What are the results of applying the following operators to A and B? [ 3 marks ]
A 0011                        0011                          0011
B 0101                        0101                          0101
A & B = 0001            A | B = 0111             A ^ B = 0110

C. Write C language statements to (i) define a union that contains members X (int), S (a 6 character string) and Y (float), (ii) define a data type called XYSunion_t based on your definition, (iii) define and initialize a variable XYS of type XYSunion_t. [ 4 marks ]
union XYS_union {
int X ; // If first, initialize to 0
char S[6] ; // If first, initialize to ‘\0’
float Y ; // If first, initialize to 0 or 0.0
} ; // Define union
typedef union XYS_union XYSunion_t ; // Define type
XYSunion_t XYS ; // Define variable
XYS.X = 0 ; // Init. variable

D. Write a single C language statement that outputs (to stdout) the number of bytes in the array defined by: long int A[100];
Your answer must work on any computer that supports the C language. [ 1 mark ]
printf( “%d”, 100*sizeof(long int) ) ; // OR as below
printf( “%d”, 100*sizeof long int ) ;

E. Assume that P1 and P2 are two char * type pointers, each pointing to a different character in the same string, so that the character pointed to by P1 occurs before the character pointed to by P2. Write a single C language statement that outputs (to stdout) the number of characters between P1 and P2. As an example, for the string “ABCDE”, if P1 points at ‘A’ and P2 points at ‘E’, then the output would be 3 (i.e. the length of the substring “BCD”). [ 1 mark ]
printf( “%d”, P2 – P1 – 1 ) ;

F. Assume the following declarations:
int N ;
char * S ; Assuming only that S points to a valid string, write a single C language statement that determines the length of the string, storing the final result in N. [ 2 marks ]
for( N=0; *S != ‘\0’; N++ ) ; // OR as below
N = strlen( S ) ;

Question 2. [ 6 marks ]
Write a complete function definition for the function StrPBrk() that conforms to the function prototype, expected behavior and assumptions stated below.
char * StrPBrk( const char * S1, const char * S2 );
The purpose is to locate the first occurrence in S1 of any character found in S2, and returns a pointer to that position in S1. If no character in S2 is found in S1, a NULL value is returned. It is assumed that both S1 and S2 are valid strings. If either S1 or S2 is an empty string, the value NULL is returned.
You must not use any C library functions in your answer.
ANSWER:
char * StrPBrk( const char * S1, const char * S2 )
{
int k ;
char * T1, * T2 = NULL ;
for( T1 = S1 ; *T1 != ‘\0’ ; T1++ )
for( T2 = S2 ; T2 != ‘\0’ ; T2++ )
if( *T2 == *T1 ) return T1;
return NULL ;
}

Question 3. [ 6 marks ]
Write a complete function definition for the function StrCat() that conforms to the function prototype, expected behavior and assumptions stated below.
void StrCat( char * S1, const char * S2);
The purpose is to copy string S2 to a position immediately following the string S1, thereby forming a single string. Note that the original ‘\0’ delimiter in S1 is overwritten by the first character in the S2 string, so that only one delimiter occurs at the end of the modified S1 string. Assume that both S1 and S2 are valid strings, either or both may be empty, and the storage allocated to S1 is sufficient to hold the result.
You must not use any C library functions in your answer.
ANSWER:
void StrCat( char * S1, const char * S2)
{
char * T ;
for( T = S1, T != ‘\0’ ; T++ ) ; // Locate end of S1
for( ; S2 != ‘\0’ ; S2++, T++ ) // Copy S2 to S1
*T = *S2 ;
*T = ‘\0’ ; // Delimit the final string
return ;
}

Question 4. [ 8 marks ]
This question deals with tracing. For the C program below, show what output would be produced. Your answers must be stated precisely, accounting for proper formatting. It is highly recommended that you show your tracing work deriving the answers, neatly, within the space provided beside the program codes.
#include
#include
int main ( ) /* SHOW TRACE BELOW */
{
int L = 3, M = 4, N = 5 ;
float X=2.3456 ;
char S[] = “Spring flowers” ;
char *P, *Q ;
P = &S[2];
Q = strstr( S, ”low” ) ;
printf( “A1 = %s ** %5s\n”, Q, “low” ) ;
printf( “A2 = %.1f ** %5.2f\n”, X, X ) ;
printf( “A3 = %d ** %d\n”, Q-P, strlen(S) ) ;
printf( “%d\*%dn”, strchr(S,‘f’)-&S[1], M<N&&L>N-M ) ;
return 0 ;
}
Neatly, print the output, if any, that would be produced by the program above. Proper formatting is very important so a grid is provided – use one character per box. More than enough row and column boxes are provided and the first row is labeled for easier referencing of column spacing.

Question 5. [ 5 marks ]
This question deals with tracing. It is highly recommended that you show your tracing work deriving the answers, neatly, within the space provided beside the program codes.
Following are five (5) C statements. They are intended to be executed in the order shown. What, if anything, outputs (ie. prints) when each of the C statements is performed? If the statement contains an error, describe the error and indicate how to correct it. Assume that all required libraries have been included, and further assume the following variable definitions:
char S1[50] = “jack”, S2[50] = “ jill”, S3[50], *Sptr ;
Check carefully for formatting and spacing considerations.
(a) printf( “%c%s\n”, toupper( S1[0] ), &S1[1] ) ;
(b) printf( “%s\n”, strcpy( S3, S2 ) ) ;
(c) printf( “%s\n”, strcat( strcat( strcpy( S3, S1 ), “ and “ ), S2 ) ) ;
(d) printf( “%u\n”, strlen( S1 ) + strlen( S2 ) ) ;
(e) printf( “%u\n”, strlen( S3 ) ) ;

Jack
jill
jack and jill (note: 2 spaces between ‘and’ and ‘jill’)
9
14

Question 6. [ 15 marks ]
Write a complete C language function called fmerge() that takes two input lists and merges them together to form a third list which is outputted using call by reference (address). The prototype for the function is:
void fmerge( float *, float *, float * ) ;
It is assumed that the first and second arguments refer to arrays of float values. It is assumed further that each of these lists consists of float values that are greater than or equal to zero and that each list is sorted from smallest to largest value, and all values in each list are unique. It may occur, however, that a value is duplicated between the two input lists. Finally, it is assumed that each input list contains a negative value in its final position, used to indicate the end of the list (it is assumed that this delimiter value exists).
The output list (the third argument) is a pointer to an array of floats. Merge the two input lists so that the output list is sorted from smallest to largest, with no duplicates, and with a negative number used to end the list.

void fmerge( float *A, float *B, float *C )
{
int J=0, K=0, L=0 ;
while( A[J] >= 0 && B[K] >= 0 ) {
if( A[J] < B[K] ) C[L++] = A[J++] ; else if( A[J] > B[K] )
C[L++] = B[K++] ;
else {
C[L++] = A[J++] ;
K++ ;
}
}
for( ; A[J] >= 0 ; )
C[L++] = A[J++] ;
for( ; B[K] >= 0 ; )
C[L++] = A[K++] ;
C[L] = -1 ;
return ;
}