Handout #36 CS106A 2002 Dec.30,2002 Alex Khomenko Practice Final Note:this practice exam is the actual exam from Autumn 00 at Stanford.Solutions to it will be distributed in electronic form as handout #37. Exam Instructions Answer each of the five questions included in the exam.Write all of your answers directly on the examination paper,including any work that you wish to be considered for partial credit. The examination is open-book,and you may make use of the text,handouts,or course notes.You may use any functions developed in the text or the handouts and need not rewrite the code;simply cite in a comment the function name,the source,and the page number.You may not use a computer of any kind. On header files:Don't worry about putting the necessary #include statements in your solutions.Just assume the required strlib,genlib,etc.header files are visible to you. On commenting:Comments regarding implementation are not 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 receive partial credit on a problem if they help us determine what you were trying to do,even if your code is wrong. On style:We will not require you to adhere to the strictest principles of good style for this exam, but a reasonable decomposition is expected. On time:You will have three hours to complete this exam.Budget your time and try to leave some time at the end to go over your work.If you run out of time on a problem,an English language "pseudocode"version may earn you partial credit. On function prototypes.You need not include function prototypes on any of the problems. I accept the letter and spirit of the honor code-I have not given or received aid on this exam Name (signed) Score Grader 1.Strings (15) 2.Arrays (15) 3.Function Trace (20) 4.Useful Pointers (20) 5.Data Structures (30) Total (100)
Handout #36 2002 Dec.30, 2002 Alex Khomenko Practice Final Note: this practice exam is the actual exam from Autumn 00 at Stanford. Solutions to it will be distributed in electronic form as handout #37. Exam Instructions Answer each of the five questions included in the exam. Write all of your answers directly on the examination paper, including any work that you wish to be considered for partial credit. The examination is open-book, and you may make use of the text, handouts, or course notes. You may use any functions developed in the text or the handouts and need not rewrite the code; simply cite in a comment the function name, the source, and the page number. You may not use a computer of any kind. On header files: Don't worry about putting the necessary #include statements in your solutions. Just assume the required strlib, genlib, etc. header files are visible to you. On commenting: Comments regarding implementation are not 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 receive partial credit on a problem if they help us determine what you were trying to do, even if your code is wrong. On style: We will not require you to adhere to the strictest principles of good style for this exam, but a reasonable decomposition is expected. On time: You will have three hours to complete this exam. Budget your time and try to leave some time at the end to go over your work. If you run out of time on a problem, an English language "pseudocode" version may earn you partial credit. On function prototypes. You need not include function prototypes on any of the problems. I accept the letter and spirit of the honor code— I have not given or received aid on this exam. Name (signed) __________________________________________________________ Score Grader 1. Strings (15) ______ ______ 2. Arrays (15) ______ ______ 3. Function Trace (20) ______ ______ 4. Useful Pointers (20) ______ ______ 5. Data Structures (30) ______ ______ Total (100) ______ CS106A
-2- Problem 1:Strings-strtok is your friend!(15 points) Function strtok is a function defined in string.h.It divides string into tokens by inserts\0' characters into the input string to turn it into several small strings instead of one large one.In this problem,you will implement a simplified version of this function.Here is the prototype: char *strtok(char *str,char delim); The first argument to the function is the string to be divided into tokens.The second argument is the character that serves as the delimiter between tokens.For example,we might make the call strtok ("Don't you love finals week?",') The second argument,which in this call is the space character,serves as the delimiter (i.e.,boundary) between the tokens. The function is supposed to retum the tokens to its caller.Since there can be lots of tokens in the string,the designers of C decided on the following scheme.When you call strtok as shown above, the first token is created by replacing the first occurrence of the delimiter with a'\o',and a pointer to the token is returned.The function also maintains an internal state (yes,you can use a global variable for this)that holds information about how far the search has proceeded. To get the next token,you then call the function with first argument NuLL,like this: strtok (NULL,'') This causes it to replace the next delimiter with'\o',return a pointer to the next token,and update its internal state.This process can be repeated to get the rest of the tokens,including the one that was the end of the original string.When there are no more tokens,the function returns NuLL. To be sure you understand how this works,consider the following code: token strtok (str,'); printf("号s\n",token)； while ((token strtok (NULL,''))!NULL) printf("&s\n",token); If str is the string "Don't you love finals week?",this code prints the following: Don't you love finals week? Originally the memory pointed to by str looked like this:
– 2 – Problem 1: Strings – strtok is your friend! (15 points) Function strtok is a function defined in string.h. It divides string into tokens by inserts '\0' characters into the input string to turn it into several small strings instead of one large one. In this problem, you will implement a simplified version of this function. Here is the prototype: char *strtok(char *str, char delim); The first argument to the function is the string to be divided into tokens. The second argument is the character that serves as the delimiter between tokens. For example, we might make the call strtok("Don't you love finals week?", ' ') The second argument, which in this call is the space character, serves as the delimiter (i.e., boundary) between the tokens. The function is supposed to return the tokens to its caller. Since there can be lots of tokens in the string, the designers of C decided on the following scheme. When you call strtok as shown above, the first token is created by replacing the first occurrence of the delimiter with a '\0', and a pointer to the token is returned. The function also maintains an internal state (yes, you can use a global variable for this) that holds information about how far the search has proceeded. To get the next token, you then call the function with first argument NULL, like this: strtok(NULL, ' '); This causes it to replace the next delimiter with '\0', return a pointer to the next token, and update its internal state. This process can be repeated to get the rest of the tokens, including the one that was the end of the original string. When there are no more tokens, the function returns NULL. To be sure you understand how this works, consider the following code: token = strtok(str, ' '); printf("%s\n", token); while ((token = strtok(NULL, ' ')) != NULL) printf("%s\n", token); If str is the string "Don't you love finals week?", this code prints the following: Don't you love finals week? Originally the memory pointed to by str looked like this:
-3- Don't you love finals week?\0 and now it looks like this: Don't\Oyou\0love\ofinals\Oweek?\0 The calls of strtok have mutilated the original string,and returned pointers to the tokens thus created.Note:the\o'characters are inserted as needed.It is not the case that the first call goes through and puts them all in the string Your job is to implement strtok as described above.Here are some ground rules(the real strtok is a little more general): ?You cannot use strlib.h functions on this problem. ?The first argument in the initial call is a pointer to a valid string. ?If the first argument is the empty string,the function returns NULL. ?The string neither starts nor ends with the delimiter. ?There are never two consecutive delimiters in the string ?If no delimiters are present in the first argument,the initial call returns the first argument and the next call returns NULL. ?You are allowed only one global variable,whose declaration you can write just above the code for the function: char *strtok(char *str,char delim)
– 3 – Don't you love finals week?\0 and now it looks like this: Don't\0you\0love\0finals\0week?\0 The calls of strtok have mutilated the original string, and returned pointers to the tokens thus created. Note: the '\0' characters are inserted as needed. It is not the case that the first call goes through and puts them all in the string. Your job is to implement strtok as described above. Here are some ground rules (the real strtok is a little more general): ?? You cannot use strlib.h functions on this problem. ?? The first argument in the initial call is a pointer to a valid string. ?? If the first argument is the empty string, the function returns NULL. ?? The string neither starts nor ends with the delimiter. ?? There are never two consecutive delimiters in the string. ?? If no delimiters are present in the first argument, the initial call returns the first argument and the next call returns NULL. ?? You are allowed only one global variable, whose declaration you can write just above the code for the function: char *strtok(char *str, char delim) {
-4- More space for the answer to Problem 1
– 4 – More space for the answer to Problem 1
-5- Problem 2:Arrays(15 points) This problem involves a simple method for identifying images.Suppose,for example,you were working on a videoconferencing system,and that you would like to automatically display the name of the person who is on camera.You could take a picture of each participant in the meeting in advance,so all you would need is some software to find the best match of those known images with the picture of the person who is on camera. Image recognition is,in general,a difficult task.But in the situation described,you are probably dealing with a small number of participants,and we are going to suggest a simple scheme that would probably work quite well. First let's say what an image is.For our purposes,we will assume that the result of digitizing an image is a two-dimensional array with sIze rows and sIze columns,where sIze is a #defined constant.We will call the images that we collect in advance our"known"data set,and we will assume that there are N_pIcrs images.Thus we could hold the known data in a three dimensional array declared as follows: int knownData[N PICTS][SIZE][SIZE]; As a refresher on three dimensional arrays,what this declaration says is that knownData is an array ofN pIcrs elements,each of which is a sIze x sIze two dimensional array.To put it another way,if i is an integer in the range o to N pIcrs -1,then knownData[i]is a two dimensional array that can be used anywhere such an array is expected. We also have to describe the two dimensional data that makes up the pictures.We will assume that our digitization process produces a color image,and that there are N coLoRs possible colors.Each picture is thus an array of sIze rows and sIze columns of integers in the range o to N coLoRs 1. Now we can discuss the matching process we will use.Our technique is based on the notion of a color histogram,which is just a tally of how many times each color appears in an image.Here is an example,assuming for simplicity that the images are 4 x 4 arrays and that there are 10 possible colors: Image Histogram 2 4 4 1 3 4 1 3 6 4 0312521200 5 5 7 0123456789 The histogram values are in the boxes,and the color numbers are written in below for reference. Thus the histogram tells us that color 1 appears 3 times in the image,color 4 appears 5 times,and that color 8 doesn't appear at all
– 5 – Problem 2: Arrays (15 points) This problem involves a simple method for identifying images. Suppose, for example, you were working on a videoconferencing system, and that you would like to automatically display the name of the person who is on camera. You could take a picture of each participant in the meeting in advance, so all you would need is some software to find the best match of those known images with the picture of the person who is on camera. Image recognition is, in general, a difficult task. But in the situation described, you are probably dealing with a small number of participants, and we are going to suggest a simple scheme that would probably work quite well. First let's say what an image is. For our purposes, we will assume that the result of digitizing an image is a two-dimensional array with SIZE rows and SIZE columns, where SIZE is a #defined constant. We will call the images that we collect in advance our "known" data set, and we will assume that there are N_PICTS images. Thus we could hold the known data in a three dimensional array declared as follows: int knownData[N_PICTS][SIZE][SIZE]; As a refresher on three dimensional arrays, what this declaration says is that knownData is an array of N_PICTS elements, each of which is a SIZE x SIZE two dimensional array. To put it another way, if i is an integer in the range 0 to N_PICTS – 1 , then knownData[i] is a two dimensional array that can be used anywhere such an array is expected. We also have to describe the two dimensional data that makes up the pictures. We will assume that our digitization process produces a color image, and that there are N_COLORS possible colors. Each picture is thus an array of SIZE rows and SIZE columns of integers in the range 0 to N_COLORS – 1. Now we can discuss the matching process we will use. Our technique is based on the notion of a color histogram, which is just a tally of how many times each color appears in an image. Here is an example, assuming for simplicity that the images are 4 x 4 arrays and that there are 10 possible colors: Image Histogram 2 7 4 4 1 3 4 4 1 3 6 4 0 3 1 2 5 2 1 2 0 0 1 5 5 7 0 1 2 3 4 5 6 7 8 9 The histogram values are in the boxes, and the color numbers are written in below for reference. Thus the histogram tells us that color 1 appears 3 times in the image, color 4 appears 5 times, and that color 8 doesn’t appear at all