CS106A Handout #36 Summer 2003 Aug7,2003 Practice Final Exam Schedule next week:Regular lectures Monday,August 11 and Tuesday,August 12; Battleship due on Wednesday,August 13 by 11am (one late day max may be used)-late assignments to box at Gates 160. Review session: TBA-Wednesday,August 13 or Thursday,August 14 at 11am Scheduled final: Friday,August 15,8:30-11:30AM,Location:TBA Check the class web site frequently for announcements! This handout is intended to give you practice solving problems that are comparable in format and difficulty to those which will appear on the final examination.A solution set to this practice examination will be available on next week. General instructions The instructions that will be used for the actual final look like this: Answer each of the questions given below.Write all of your answers directly on the examination paper,including any work that you wish to be considered for partial credit. Each question is marked with the number of points assigned to that problem.The total number of points is 100.We intend that the number of points be roughly comparable to the number of minutes you should spend on that problem.This leaves you with 80 minutes to check your work or to recover from false starts. In all questions,you may include functions or definitions that have been developed in the course,either by writing the #include line for the appropriate interface(if there is one) or by giving the name of the function and the handout number in which its definition appears.For example,if you write #include "strlib.h" in your answer,you can then use any of the functions implemented in strlib.c. The examination is open-book,and you may make use of any texts,handouts,or course notes.You may not,however,use a computer of any kind
CS106A Handout #36 Summer 2003 Aug 7, 2003 Practice Final Exam Schedule next week: Regular lectures Monday, August 11 and Tuesday, August 12; Battleship due on Wednesday, August 13 by 11am (one late day max may be used) – late assignments to box at Gates 160. Review session: TBA – Wednesday, August 13 or Thursday, August 14 at 11am Scheduled final: Friday, August 15, 8:30-11:30AM, Location: TBA Check the class web site frequently for announcements! This handout is intended to give you practice solving problems that are comparable in format and difficulty to those which will appear on the final examination. A solution set to this practice examination will be available on next week. General instructions The instructions that will be used for the actual final look like this: Answer each of the questions given below. Write all of your answers directly on the examination paper, including any work that you wish to be considered for partial credit. Each question is marked with the number of points assigned to that problem. The total number of points is 100. We intend that the number of points be roughly comparable to the number of minutes you should spend on that problem. This leaves you with 80 minutes to check your work or to recover from false starts. In all questions, you may include functions or definitions that have been developed in the course, either by writing the #include line for the appropriate interface (if there is one) or by giving the name of the function and the handout number in which its definition appears. For example, if you write #include "strlib.h" in your answer, you can then use any of the functions implemented in strlib.c. The examination is open-book, and you may make use of any texts, handouts, or course notes. You may not, however, use a computer of any kind
-2- Problem 1-Short answer (15 points) la)Suppose that the integer array 1ist has been declared and initialized as follows: #define NElements 5 int list[NElements]=10,20,30,40,50 } This declaration sets up an array of five elements with the initial values shown in the diagram below: list 10 20 30 40 50 Given this array,what is the effect of calling the function Mystery(list,NElements); if Mystery is defined as: void Mystery(int array[],int n) int i,tmp; tmp array[n -1]; for (i=1;i<n;it+){ array[i]array[i -1]; } array[o]tmp; Work through the function carefully and indicate your answer by filling in the boxes below to show the final contents of list: list
– 2 – Problem 1—Short answer (15 points) 1a) Suppose that the integer array list has been declared and initialized as follows: #define NElements 5 int list[NElements] = { 10, 20, 30, 40, 50 }; This declaration sets up an array of five elements with the initial values shown in the diagram below: list 10 20 30 40 50 Given this array, what is the effect of calling the function Mystery(list, NElements); if Mystery is defined as: void Mystery(int array[], int n) { int i, tmp; tmp = array[n - 1]; for (i = 1; i < n; i++) { array[i] = array[i - 1]; } array[0] = tmp; } Work through the function carefully and indicate your answer by filling in the boxes below to show the final contents of list: list
-3- 1b)Suppose that you have been assigned to take over a project from another programmer who has just been dismissed for writing buggy code.One of the functions you have been asked to rewrite has the following comment and prototype: /者 Function:InsertValue Usage:Insertvalue(value,array,n,max)i This function takes four parameters: ★ 1.A new value to be inserted in the array (value) 2.An integer array sorted in ascending order (array) 3.The effective size of the array (n) 4.The allocated size of the array (max) The effect of the function is to insert value at its proper position in the array.When the function returns,the new effective size of the array will be n+1.If there is no space for the value,the Insertvalue function generates an error message. */ void Insertvalue(int value,int array[],int n,int max); Unfortunately,the corresponding implementation is buggy and looks like this: void Insertvalue(int value,int array[],int n,int max) int i,pos; if (n max)Error("No space in array"); for (i=0;i<n;i++){ if (value array[i]){ pos i; break; } } for (i=pos;i<n;i++){ array[i +1]array[i]; array[i]value; Circle the bugs in the implementation and write a sentence or two explaining the precise nature of each problem you identify
– 3 – 1b) Suppose that you have been assigned to take over a project from another programmer who has just been dismissed for writing buggy code. One of the functions you have been asked to rewrite has the following comment and prototype: /* * Function: InsertValue * Usage: InsertValue(value, array, n, max); * ----------------------------------------- * This function takes four parameters: * * 1. A new value to be inserted in the array (value) * 2. An integer array sorted in ascending order (array) * 3. The effective size of the array (n) * 4. The allocated size of the array (max) * * The effect of the function is to insert value at * its proper position in the array. When the function * returns, the new effective size of the array will * be n+1. If there is no space for the value, the * InsertValue function generates an error message. */ void InsertValue(int value, int array[], int n, int max); Unfortunately, the corresponding implementation is buggy and looks like this: void InsertValue(int value, int array[], int n, int max) { int i, pos; if (n > max) Error("No space in array"); for (i = 0; i array[i]) { pos = i; break; } } for (i = pos; i < n; i++){ array[i + 1] = array[i]; } array[i] = value; } Circle the bugs in the implementation and write a sentence or two explaining the precise nature of each problem you identify
-4- 1c)Draw a memory diagram showing the structure of the memory that has been allocated at the indicated point in the following program: #include #include #include "genlib.h" #include "strlib.h" main ( string si char carray[5],*cptr; strcpy(carray,"abc"); cptr carray +1; *cptr++'x'; s Concat(carray,cptr)i Draw a diagram indicating the contents of memory at this point. Your diagram should include a separate box for each pointer and character cell used by the program.The values of pointer cells should be shown using arrows;the value of any character cells should be shown just by writing the character in the box.Your diagram should also make it clear whether each region of memory is allocated on the stack or the heap.For example,if a pointer variable p on the stack points to a heap cell containing the character 'A',you should indicate that situation using a diagram that looks like this: Stack Heap A Uninitialized memory locations should be left blank
– 4 – 1c) Draw a memory diagram showing the structure of the memory that has been allocated at the indicated point in the following program: #include #include #include "genlib.h" #include "strlib.h" main() { string s; char carray[5], *cptr; strcpy(carray, "abc"); cptr = carray + 1; *cptr++ = 'x'; s = Concat(carray, cptr); Draw a diagram indicating the contents of memory at this point. } Your diagram should include a separate box for each pointer and character cell used by the program. The values of pointer cells should be shown using arrows; the value of any character cells should be shown just by writing the character in the box. Your diagram should also make it clear whether each region of memory is allocated on the stack or the heap. For example, if a pointer variable p on the stack points to a heap cell containing the character 'A', you should indicate that situation using a diagram that looks like this: p Stack Heap A Uninitialized memory locations should be left blank
-5- Problem 2-Strings(15 points) When large numbers are written out on paper,it is traditional-at least in the United States-to use commas to separate the digits into groups of three.For example,the number one million is usually written in the following form: 1,000,000 To make it easier for programmers to display numbers in this fashion,implement a function string AddCommasToNumericstring(string digits); that takes a string of decimal digits representing a number and returns the string formed by inserting commas at every third position,starting on the right.For example,if you were to execute the main program main ( f string digits; while (TRUE){ printf("Enter a string of digits:") digits GetLine(); if (StringEqual(digits,"")break; printf("&s\n",AddCommasToNumericstring(digits)); } your implementation of the AddcommasToNumericstring function should be able to produce the following sample run: Enter a string of digits:17 17 Enter a string of digits:1001 1,001 Enter a string of digits:12345678/ 12,345,678 Enter a string of digits:999999999/ 999,999,999 Note that AddcommasToNumericstring takes a string rather than an integer.On some machines, the range of the type int may be too small to allow interesting examples.If you want to use this function with integers,you could always call Integerrostring before calling AddCommasToNumericstring
– 5 – Problem 2—Strings (15 points) When large numbers are written out on paper, it is traditional—at least in the United States—to use commas to separate the digits into groups of three. For example, the number one million is usually written in the following form: 1,000,000 To make it easier for programmers to display numbers in this fashion, implement a function string AddCommasToNumericString(string digits); that takes a string of decimal digits representing a number and returns the string formed by inserting commas at every third position, starting on the right. For example, if you were to execute the main program main() { string digits; while (TRUE) { printf("Enter a string of digits: "); digits = GetLine(); if (StringEqual(digits, "")) break; printf("%s\n", AddCommasToNumericString(digits)); } } your implementation of the AddCommasToNumericString function should be able to produce the following sample run: Enter a string of digits: 17 17 Enter a string of digits: 1001 1,001 Enter a string of digits: 12345678 12,345,678 Enter a string of digits: 999999999 999,999,999 Note that AddCommasToNumericString takes a string rather than an integer. On some machines, the range of the type int may be too small to allow interesting examples. If you want to use this function with integers, you could always call IntegerToString before calling AddCommasToNumericString
-6- Problem 3-Simple C(10 points) Your job is to write a program to calculate the integer quotient (i.e.,division in the style of C's/ operator applied to integers,which throws away any remainder)of two input values,which you may assume are both positive.You may not use the division operator.Instead,you need to simulate the division by repeated subtraction,counting the number of times the second input value can be subtracted from the first before the result goes negative.The output of this program is shown in the following sample run,which shows that the quotient of 50 divided by 15 is 3: Please enter a number to divided:50 Please enter a number to be divided into 50:15 The quotient is:3 Problem 4-Arrays(10 points) The last shall be first. -Matthew,20:15 Write a function RotateRight that takes two arguments-an array of values of type double and an integer indicating the effective size of that array-and that has the effect of shifting every element one position rightward toward the end of the array,with the exception of the last element,which gets moved to the initial position.For example,if the array values has the contents values 3.14 2.72 98.6 6.28 22.5 42.0 calling RotateRight(values,6); should shift the first five values one position to the right and move the value from the last position to the front,as follows: values 42.0 3.14 2.72 98.6 6.28 22.5
– 6 – Problem 3—Simple C (10 points) Your job is to write a program to calculate the integer quotient (i.e., division in the style of C’s / operator applied to integers, which throws away any remainder) of two input values, which you may assume are both positive. You may not use the division operator. Instead, you need to simulate the division by repeated subtraction, counting the number of times the second input value can be subtracted from the first before the result goes negative. The output of this program is shown in the following sample run, which shows that the quotient of 50 divided by 15 is 3: Problem 4—Arrays (10 points) The last shall be first. — Matthew, 20:15 Write a function RotateRight that takes two arguments—an array of values of type double and an integer indicating the effective size of that array—and that has the effect of shifting every element one position rightward toward the end of the array, with the exception of the last element, which gets moved to the initial position. For example, if the array values has the contents 3.14 2.72 98.6 6.28 22.5 42.0 values calling RotateRight(values, 6); should shift the first five values one position to the right and move the value from the last position to the front, as follows: 42.0 3.14 2.72 98.6 6.28 22.5 values Please enter a number to divided: 50 Please enter a number to be divided into 50: 15 The quotient is: 3
-7- Problem 5-Records (10 points) Although none of the many predicted disasters came to pass,there was considerable concern in 1999 about what would happen on January 1,2000,when the calendar year rolled over to the next century.The problem-which was commonly known as the millennium bug or the Y2K problem-comes from the fact that programmers (along with everyone else)have often used two digits to represent the year.Thus,the two-digit value 99 is intended to represent the year 1999. But what about the two-digit value 00?If programs assumed that it meant 1900,all sorts of trouble might arise. Suppose that you had been hired to rewrite various C programs to be less susceptible to Y2K errors.In these programs,dates are represented using the following structure: typedef struct int month,day,year; 】dateT; Your job is to write a function int DateCompare(dateT d1,dateT d2); which takes two dates,d1 and d2,and returns (in much the same manner as the function stringcompare),one of the following values: -1 if d1 comes before d2 0 if di and d2 represent the same date +1 if di comes after d2 To address the Y2K problem,two-digit year values between 0 and 49 should be interpreted as being in the 21st century,so that the year 01 corresponds to 2001.Year values between 50 and 99 should be interpreted as being in the 20th century,so that the year 97 represents 1997.Your function should interpret any value outside the range 0 to 99 as a complete year,so that if the year field contains the value 1942,that value is taken as the year 1942. As an example,suppose that the two records d1 and d2 have the following components, corresponding to the dates March 15,99 and January 1,00: dl d2 month day year month day year 15 99 00 Calling Datecompare(d1,d2)on these values should return-1,because the year value 00 in d2 is assumed to represent the year 2000.If d1 and d2 were instead dl d2 month day year month day year 5 00 5 1 2000 calling Datecompare (d1,d2)should return 0,because these values refer to the same date(May 1,2000)
– 7 – Problem 5—Records (10 points) Although none of the many predicted disasters came to pass, there was considerable concern in 1999 about what would happen on January 1, 2000, when the calendar year rolled over to the next century. The problem—which was commonly known as the millennium bug or the Y2K problem—comes from the fact that programmers (along with everyone else) have often used two digits to represent the year. Thus, the two-digit value 99 is intended to represent the year 1999. But what about the two-digit value 00? If programs assumed that it meant 1900, all sorts of trouble might arise. Suppose that you had been hired to rewrite various C programs to be less susceptible to Y2K errors. In these programs, dates are represented using the following structure: typedef struct { int month, day, year; } dateT; Your job is to write a function int DateCompare(dateT d1, dateT d2); which takes two dates, d1 and d2, and returns (in much the same manner as the function StringCompare), one of the following values: –1 if d1 comes before d2 0 if d1 and d2 represent the same date +1 if d1 comes after d2 To address the Y2K problem, two-digit year values between 0 and 49 should be interpreted as being in the 21st century, so that the year 01 corresponds to 2001. Year values between 50 and 99 should be interpreted as being in the 20th century, so that the year 97 represents 1997. Your function should interpret any value outside the range 0 to 99 as a complete year, so that if the year field contains the value 1942, that value is taken as the year 1942. As an example, suppose that the two records d1 and d2 have the following components, corresponding to the dates March 15, 99 and January 1, 00: 3 month 15 day 99 year d1 1 month 1 day 00 year d2 Calling DateCompare(d1, d2) on these values should return –1, because the year value 00 in d2 is assumed to represent the year 2000. If d1 and d2 were instead 5 month 1 day 00 year d1 5 month 1 day 2000 year d2 calling DateCompare(d1, d2) should return 0, because these values refer to the same date (May 1, 2000)
-8- Problem 6-Pointer tracing(10 points) Evaluate the following program by hand and show what output it produces: /* File:ptrtrace.c This file does nothing useful and exists only to test your understanding of pointers. */ #include #include #include "genlib.h" #include "strlib.h" /Private function prototypes static void Bizarre(int *pl,int *p2,int n); static int *Weird(int array[],int n); static void Checkpoint(int ckpt,int array[],int n); /Statically initialized arrays * static int a1[]={10,11,12,13,14}: static int a2[]={3,4,0,1,2}; /Main program main ( int i,*p; Checkpoint(0,al,5); Bizarre(al,a2,5); Checkpoint(1,al,5); p Weird(Weird(a2,2),4); Checkpoint(2,a2,5); static void Bizarre(int *pl,int *p2,int n) int *p3,*array; array p3 GetBlock(n sizeof(int)); while (n-->0){ *p3++=p1[*p2++]; while (p3--!=array)( p1[p3-array】=*p3;
– 8 – Problem 6—Pointer tracing (10 points) Evaluate the following program by hand and show what output it produces: /* * File: ptrtrace.c * ---------------- * This file does nothing useful and exists only to test your * understanding of pointers. */ #include #include #include "genlib.h" #include "strlib.h" /* Private function prototypes */ static void Bizarre(int *p1, int *p2, int n); static int *Weird(int array[], int n); static void Checkpoint(int ckpt, int array[], int n); /* Statically initialized arrays */ static int a1[] = { 10, 11, 12, 13, 14 }; static int a2[] = { 3, 4, 0, 1, 2 }; /* Main program */ main() { int i, *p; Checkpoint(0, a1, 5); Bizarre(a1, a2, 5); Checkpoint(1, a1, 5); p = Weird(Weird(a2, 2), 4); Checkpoint(2, a2, 5); } static void Bizarre(int *p1, int *p2, int n) { int *p3, *array; array = p3 = GetBlock(n * sizeof(int)); while (n-- > 0) { *p3++ = p1[*p2++]; } while (p3-- != array) { p1[p3 - array] = *p3; } }
-9- static int *Weird(int array[],int n) int *p,i; p array; for (i 1;i0)printf(",") printf("8d",array[i]); printf(")\n"); The checkpoint function does exactly what its comments say it does:display the contents of an array preceded by a checkpoint number.Thus,to answer this problem,all you have to do is show the output at each of the calls to checkpoint.The results of the first call are filled in as an example. Answer to problem 6: Checkpoint0:{10,11,12,13,14J Checkpoint 1: Checkpoint 2: (Space to show your scratch work appears on the following page)
– 9 – static int *Weird(int array[], int n) { int *p, i; p = array; for (i = 1; i 0) printf(", "); printf("%d", array[i]); } printf(" }\n"); } The Checkpoint function does exactly what its comments say it does: display the contents of an array preceded by a checkpoint number. Thus, to answer this problem, all you have to do is show the output at each of the calls to Checkpoint. The results of the first call are filled in as an example. Answer to problem 6: Checkpoint 0: { 10, 11, 12, 13, 14 } Checkpoint 1: Checkpoint 2: (Space to show your scratch work appears on the following page)
-10- Problem 7-C programming (15 points) Write a function void UntabifyFile(FILE *infile,FILE *outfile); which copies the entire contents of the input file to the output file,replacing any tabs in the input with enough spaces to reach the next tab stop,which are traditionally set at every eight spaces,as they were in MiniSim code.For flexibility,your version of untabifyFile must use the value of the constant rabstops to control the size of a tab stop.For MiniSim files,rabstops would be set as follows: #define TabStops 8 For Thetis programs,the value of rabstops would be changed to 4. Suppose,for example,that the input file contains the following lines,where the arrow symbol (→)represents a tab: start:◆INPUT◆x →OUTPUT◆x →HALT x:◆0 When you read in a line from the file,you need to go through that line character by character, looking for instances of the tab character,which is denoted in C as '\t'.When you find one. you need to replace it in the output by a sequence of spaces.The number of spaces is determined by figuring out how many characters you need to reach the next tab stop.If rabstops has the value 8,you need to add spaces until you reach the next column position divisible by 8. As an example,the first line in the input file is start:→input-x The s,t,a,r,t,and characters take up positions 1,2,3,4,5,and 6 on the line.The tab character that follows therefore corresponds to two spaces,because 8 is the next column divisible by 8.The characters I,N,P,U,and r take up positions 9,10,11,12,and 13.At this point the tab character requires three spaces to reach the next tab stop at 16. The completed output file looks like this,where the space character is indicated by the symbol-. start:-inputx halt x:0 Remember that you have to write only the untabifyFile procedure and not the surrounding main program.The main program takes care of opening and closing the files;your job is simply to copy data from the input file to the output file,replacing tabs with spaces as you go
– 10 – Problem 7—C programming (15 points) Write a function void UntabifyFile(FILE *infile, FILE *outfile); which copies the entire contents of the input file to the output file, replacing any tabs in the input with enough spaces to reach the next tab stop, which are traditionally set at every eight spaces, as they were in MiniSim code. For flexibility, your version of UntabifyFile must use the value of the constant TabStops to control the size of a tab stop. For MiniSim files, TabStops would be set as follows: #define TabStops 8 For Thetis programs, the value of TabStops would be changed to 4. Suppose, for example, that the input file contains the following lines, where the arrow symbol ( ) represents a tab: start: INPUT x OUTPUT x HALT x: 0 When you read in a line from the file, you need to go through that line character by character, looking for instances of the tab character, which is denoted in C as '\t'. When you find one, you need to replace it in the output by a sequence of spaces. The number of spaces is determined by figuring out how many characters you need to reach the next tab stop. If TabStops has the value 8, you need to add spaces until you reach the next column position divisible by 8. As an example, the first line in the input file is start: input x The s, t, a, r, t, and : characters take up positions 1, 2, 3, 4, 5, and 6 on the line. The tab character that follows therefore corresponds to two spaces, because 8 is the next column divisible by 8. The characters I, N, P, U, and T take up positions 9, 10, 11, 12, and 13. At this point the tab character requires three spaces to reach the next tab stop at 16. The completed output file looks like this, where the space character is indicated by the symbol . start: input x output x halt x: 0 Remember that you have to write only the UntabifyFile procedure and not the surrounding main program. The main program takes care of opening and closing the files; your job is simply to copy data from the input file to the output file, replacing tabs with spaces as you go