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=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 array[i]) // should be value = 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 ()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;i0) 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 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:
Part B:This part you need to do on computer. 1.Palindrome Checker (30)A palindrome is a word or phrase which is exactly the same if the letters in the word or phrase are reversed-for example the words pup, civic,radar,and racecar are all palindromes.For this problem you will write a program which checks whether a word or phrase entered is a palindrome.If the data entered is a palindrome,print"XXX is a palindrome!",otherwise print "XXX is Not a palindrome."Your checker should work for phrases as well as words,and should ignore spaces,punctuation,and upper/lower-case differences.Thus the phrase:"A man,a plan,a canal,Panama!"should be correctly identified as a palindrome. The program only tests a single word and then stops execution.If you want to check another word or phrase,you'll have to run the program again.Here is a screenshot showing the program in action: #include #include #include using namespace std; string preProcess(string str) string newString; for (int i=0,j=0;i<str.length ()i++) if (isalpha (str[i])) newString.append (1,tolower (str[i])); return newString; } bool IsPalindrome (string str) str preProcess (str); int i=0,j=str.length ()-1; bool equal true; while (equal &&i<j) equal str[i++]=str[j--]; return equal; } int main (int argc,char *argv[]) ConsoleT console; string str argc ==2 argv[1]:"A man,a plan,a canal,Panama!"; console.printLine (str,is "IsPalindrome (str)?"""NOT",a palindrome.\n"); return 0;
Part B: This part you need to do on computer. 1. Palindrome Checker (30) A palindrome is a word or phrase which is exactly the same if the letters in the word or phrase are reversed—for example the words pup, civic, radar, and racecar are all palindromes. For this problem you will write a program which checks whether a word or phrase entered is a palindrome. If the data entered is a palindrome, print “XXX is a palindrome!”, otherwise print “XXX is Not a palindrome.” Your checker should work for phrases as well as words, and should ignore spaces, punctuation, and upper/lower-case differences. Thus the phrase: “A man, a plan, a canal, Panama!” should be correctly identified as a palindrome. The program only tests a single word and then stops execution. If you want to check another word or phrase, you’ll have to run the program again. Here is a screenshot showing the program in action: #include #include #include using namespace std; int main (int argc, char *argv[]) { ConsoleT console; string str = argc == 2 ? argv[1] : "A man, a plan, a canal, Panama!"; console.printLine (str, " is ", IsPalindrome (str) ? "" : "NOT", " a palindrome.\n"); return 0; }
2.FileDraw(30)In this problem you write a program which draws Circles and Rectangle on screen,where the location,size,color and density of the Circles and Rectangles are read from a file.Suppose,for example,the following data is read: rectangle:5.993125.178617.332375.65564 Yellow0.5 circle:6.970141.561510.3273260 range0.8 rectangle:0.6079843.196931.348073.51565Gold0.3 The file will always consist of zero or more lines,where each line starts with either “circle'”or“rectangle''.The“circle”will be followed by the center of the circle, followed by the radius of the circle and its fill color and density.The "rectangle"will always be followed by the lower-left and upper-right points of the rectangle with each point represented by x and y coordinates.Assume that the program always reads a file named shapes.txt.You may also assume that all numeric values given will be doubles. For the test purpose,we have implement the main function for you.All you need is to write a function called readAndDraw (ifstream &inFile) int main (int argc,char *argv[]) r ifstream inFile (argc =2 argv[1]"shapes.txt"); readAndDraw (inFile,outFile); inFile.close O return O; } void readAndDraw ifstream &inFile double x,y,r,x1,y1,density; string shape,color; bool quit false; while (!quit &!inFile.eof () inFile >shape; if (shape ="circle:" L inFile >>x>>y>>r>>color >density; MyArcT circle (x,y,r,color,density); circle.draw () else if (shape =="rectangle:" inFile >>x>>y>>x1>>y1 >color >density; MyRectangleT rect(x,y,x1,y1,color,density); rect.draw(); else quit true;
2. FileDraw (30) In this problem you write a program which draws Circles and Rectangle on screen, where the location, size, color and density of the Circles and Rectangles are read from a file. Suppose, for example, the following data is read: rectangle: 5.99312 5.17861 7.33237 5.65564 Yellow 0.5 circle: 6.97014 1.56151 0.327326 Orange 0.8 rectangle: 0.607984 3.19693 1.34807 3.51565 Gold 0.3 The file will always consist of zero or more lines, where each line starts with either “circle” or “rectangle”. The “circle” will be followed by the center of the circle, followed by the radius of the circle and its fill color and density. The “rectangle” will always be followed by the lower-left and upper-right points of the rectangle with each point represented by x and y coordinates. Assume that the program always reads a file named shapes.txt. You may also assume that all numeric values given will be doubles. For the test purpose, we have implement the main function for you. All you need is to write a function called readAndDraw (ifstream &inFile) int main (int argc, char *argv[]) { ifstream inFile (argc == 2 ? argv[1] : "shapes.txt"); readAndDraw (inFile, outFile); inFile.close (); return 0; } void readAndDraw ( ifstream &inFile ) { double x, y, r, x1, y1, density; string shape, color; bool quit = false; while (!quit && !inFile.eof ()) { inFile >> shape; if (shape == "circle:") { inFile >> x >> y >> r >> color >> density; MyArcT circle (x, y, r, color, density); circle.draw (); } else if (shape == "rectangle:") { inFile >> x >> y >> x1 >> y1 >> color >> density; MyRectangleT rect (x, y, x1, y1, color, density); rect.draw (); } else { quit = true; } } }