UM-SJTU Joint Institute Sample Midterm 2008 for Vg101 Introduction to Computer and Programming You Name (Printed): Student ID: General instructions You exam will be divided into two parts.A part on paper and the second one is on computer For the on paper exam,you directly write down your answers 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 50.We intend for the number of points to be roughly comparable to the number of minutes you should spend on that problem. Unless otherwise indicated as part of the instructions for a specific problem,comments will not be required on the exam.Uncommented code that gets the job done will be sufficient for full credit on the problem.On the other hand,comments may help you to get partial credit if they help us determine what you were trying to do. Total 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 for the paper test. For the computer part,you will be given a problem and you will need to design it,implement it, compile it,debug it and test it on computer.You need to summit your results to the ftp server specified in the problem description. THE UM-SJTU JI HONOR CODE I accept the letter and spirit of the honor code: "I have neither given nor received unauthorized aid on this examination,nor have I concealed any violations of the Honor Code. signature Date
UM-SJTU Joint Institute Sample Midterm 2008 for Vg101 Introduction to Computer and Programming You Name (Printed) : Student ID: General instructions You exam will be divided into two parts. A part on paper and the second one is on computer. For the on paper exam, you directly write down your answers 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 50. We intend for the number of points to be roughly comparable to the number of minutes you should spend on that problem. Unless otherwise indicated as part of the instructions for a specific problem, comments will not be required on the exam. Uncommented code that gets the job done will be sufficient for full credit on the problem. On the other hand, comments may help you to get partial credit if they help us determine what you were trying to do. 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 for the paper test. For the computer part, you will be given a problem and you will need to design it, implement it, compile it, debug it and test it on computer. You need to summit your results to the ftp server specified in the problem description. THE UM-SJTU JI HONOR CODE I accept the letter and spirit of the honor code: "I have neither given nor received unauthorized aid on this examination, nor have I concealed any violations of the Honor Code." signature Date
PartA:Paper part(You cannot use any programmable device) Problem 1-Short answer(30 points) la)Write out the results of the function mystery(10 points) 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 2030 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 tmp=array[n-1]; for (int 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 50 10 10 10 10
PartA: Paper part (You cannot use any programmable device) Problem 1—Short answer (30 points) 1a) Write out the results of the function mystery (10 points) 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 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 tmp = array[n -1]; for (int 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
1b)Debug as a compiler(20 points) 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: /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 the array is full,the insertValue displays an error message then quit. Unfortunately,the corresponding implementation is buggy and looks like this: void Insertvalue(int value,int array[],int n,int max)//n shoulb be &n(3 pts) { int i=0,pos; bool quit false; if (n>max) /should be n =max (4 pts) console.runTimeError("No space in array"); while (!quit &&i<n) if (value array[i]) /should be value array[i](4 pts) E pos =i; quit true; else i++; } for (i=pos;i<n;i++)//should be (i=n-1;i>=pos;i++)(6 pts) array[i 1]array[i]; } array[i]value; //missing n++;(3 pts) } Circle the bugs in the implementation and write a sentence or two explaining the precise nature of each problem you identify.You don't need to write the correct version:just pointing out the wrong one and gave some explains
1b) Debug as a compiler (20 points) 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: /* * 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 the array is full, the insertValue displays an error message then quit. */ Unfortunately, the corresponding implementation is buggy and looks like this: void InsertValue(int value, int array[], int n, int max) // n shoulb be &n (3 pts) { int i = 0, pos; bool quit = false; if (n > max) // should be n == max (4 pts) console.runTimeError("No space in array"); while (!quit && i < n) { if (value > array[i]) // should be value < array[i] (4 pts) { pos = i; quit = true; } else i++; } for (i = pos; i < n; i++) // should be (i = n-1; i >= pos; i++) (6 pts) { array[i + 1] = array[i]; } array[i] = value; // missing n++; (3 pts) } Circle the bugs in the implementation and write a sentence or two explaining the precise nature of each problem you identify. You don’t need to write the correct version; just pointing out the wrong one and gave some explains
Problem 2-Strings(20 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 int main (int argc,char *argv[]) { ifstream inFile; ConsoleT console; string digits; bool done false; if (argc ==2)inFile.open (argv[1]); while (!done) if (argc =2)inFile >digits; else digits console.readString ("Enter a string of digits:") if (digits =="exit")done true; else console.printLine (AddCommasToNumericString(digits),endl); inFile.close () your implementation of the AddCommasToNumericString function should be able to produce the following sample run: Enter a string of digits: string AddCommasToNumericString(string &digits) 17 17 if (digits.length ()<4)return digits; Enter a string of digits: for (int i digits.length ()-3;i>0;i-=3) 1001 digits.insert(i,1,); 1,001 return digits; Enter a string of digits: 12345678 12,345,678 Enter a string of digits: 999999999 999,999.999 Enter a string of digits: exit Note that AddCommasToNumericString takes a string rather than an integer
Problem 2—Strings (20 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 int main (int argc, char *argv[]) { ifstream inFile; ConsoleT console; string digits; bool done = false; if (argc == 2) inFile.open (argv[1]); while (!done) { if (argc == 2) inFile >> digits; else digits = console.readString ("Enter a string of digits: "); if (digits == "exit") done = true; else console.printLine (AddCommasToNumericString(digits), endl); } inFile.close (); } 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 Enter a string of digits: exit Note that AddCommasToNumericString takes a string rather than an integer
Problem 3-Pointer tracing (10 points) Evaluate the following program by hand and show what output it produces: void Bizarre (int pl[l,int p2[],int n); int *Weird(int array[,int n) int *Weird (int array[],int n); void Checkpoint (int ckpt,int arr[,int n); int *p,i; p=array; int al0={10,11,12,13,14}; for (i=1;i<n;++ inta20={3,4,0,1,2}; { ConsoleT console; if (*p<array[i]) int main() p=array +i; } int i,*p; } Checkpoint(0,al,5); (*p-; Bizarre (al,a2,5); return (p); Checkpoint(1,al,5); p=Weird (Weird (a2,2),4); Checkpoint(2,a2,5); void Checkpoint(int ckpt,int array,int n) void Bizarre(int p10,int p2[,int n) int i; console.printLine ("Checkpoint "ckpt,":{") int *p3,*array; for (i=0;i<n;i++) array p3 new int [nl; { while (n-->0) if (i>0)console.printLine ("") *p3++=pl[*p2++ console.printLine (array[i]); while (p3--!=array) pl[p3-array]=*p3; console.printLine (}\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: C:\Windows\system32\cmd.exe Checkpoint0:{10,11,12,13,14} Checkpoint0:(10,11,12,13,14) Checkpoint 1: Checkp0int1:(13,14,10,11,12) Checkpoint 2:3.2.0.1.2 Checkpoint 2: Press any key to continue···■
Problem 3—Pointer tracing (10 points) Evaluate the following program by hand and show what output it produces: void Bizarre (int p1[], int p2[], int n); int *Weird (int array[], int n); void Checkpoint (int ckpt, int arr[], int n); int a1[] = { 10, 11, 12, 13, 14 }; int a2[] = { 3, 4, 0, 1, 2 }; ConsoleT console; int 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); } void Bizarre(int p1[], int p2[], int n) { int *p3, *array; array = p3 = new int [n]; while (n--> 0) *p3++ = p1[*p2++]; while (p3--!= array) p1[p3 -array] = *p3; } int *Weird(int array[], int n) { int *p, i; p = array; for (i = 1; i < n; i++) { if (*p < array[i]) { p = array + i; } } (*p)--; return (p); } void Checkpoint(int ckpt, int array[], int n) { int i; console.printLine ("Checkpoint ", ckpt, ": { "); for (i = 0; i < n; i++) { if (i > 0) console.printLine (", "); console.printLine (array[i]); } console.printLine (" }\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: