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 < 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
-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 <stdio.h> #include <string.h> #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 <stdio.h> #include <string.h> #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