上海交通大学：《程序设计基础》课程教学资源（习题集）05年期末习题_Solution for Practice Final 1

Handout #37 CS106A 2002 Dec.30,2002 Alex Khomenko Practice Final Solutions Problem 1:Strings. static char curptr NULL; /global state variable * char *strtok(char *str,char delim) int i; if(str =NULL)str curPtr; if(strcmp(str,"")==0)return (NULL); for(i=0;i<strlen(str);i++) { if(str[i]=delim) { str[i]=\0'; curptr str +i 1; return(str); curptr "" return(str); Problem 2:Arrays (a) void MakeHistogram(int pict[SIZE][SIZE],int hist [N_COLORS]) { int i,ji for (i=0;i<N COLORS;i++) hist[i]0; for (i 0;i SIZE;i++) for (j=0;j<SIZE;j++) hist[pict[i][j]]++; for (i=0;i<N COLORS;i++) printf("&d",hist[i]); printf("\n"); } (b) for (i =0;i<N PICTS;i++) MakeHistogram(knownData[i],histograms [i]);

Handout #37 2002 Dec. 30, 2002 Alex Khomenko Practice Final Solutions Problem 1: Strings. static char curPtr = NULL; /* global state variable */ char *strtok(char *str, char delim) { int i; if(str == NULL) str = curPtr; if(strcmp(str, "") == 0) return(NULL); for(i = 0; i < strlen(str); i++) { if(str[i] == delim) { str[i] = '\0'; curPtr = str + i + 1; return(str); } } curPtr = ""; return(str); } Problem 2: Arrays (a) void MakeHistogram(int pict[SIZE][SIZE], int hist[N_COLORS]) { int i, j; for (i = 0; i < N_COLORS; i++) hist[i] = 0; for (i = 0; i < SIZE; i++) for (j = 0; j < SIZE; j++) hist[pict[i][j]]++; for (i = 0; i < N_COLORS; i++) printf(" %d", hist[i]); printf("\n"); } (b) for (i = 0; i < N_PICTS; i++) { MakeHistogram(knownData[i], histograms[i]); CS106A

2 }

2 }

3 (c) int BestMatch(int unknown [SIZE][SIZE],int histograms [N_PICTS][N_COLORS]) int score [N_PICTS],hist [N_COLORS]; int i,best 0; MakeHistogram(unknown,hist); for (i =0;i<N_PICTS;i++) score [i]Compare(histograms [i],hist); for (i 1;i N PICTS;i++) if (score[i]score[best]) best =i; return best; int Compare(int h1[N_COLORS],int h2[N_COLORS]) int score 0,i; for (i=0;i<N COLORS;i++) score +abs(h1[i]-h2[i]); return score;

3 (c) int BestMatch(int unknown[SIZE][SIZE], int histograms[N_PICTS][N_COLORS]) { int score[N_PICTS], hist[N_COLORS]; int i, best = 0; MakeHistogram(unknown, hist); for (i = 0; i < N_PICTS; i++) score[i] = Compare(histograms[i], hist); for (i = 1; i < N_PICTS; i++) if (score[i] < score[best]) best = i; return best; } int Compare(int h1[N_COLORS], int h2[N_COLORS]) { int score = 0, i; for (i = 0; i < N_COLORS; i++) score += abs(h1[i] - h2[i]); return score; }

4 Problem 3:Function trace STACK HEAP main e' 6 mika schuey n '1 david mika schuey mika schuey mika 1' schuey mika schuey mika schuey Rubens jean jos 6 hello\0 johnny there\0 6 howyalldoin?\0 Orphaned! Ouch\0 Ralf eddie heinz marc pedro

4 Problem 3: Function trace STACK HEAP n david main mika schuey mika schuey mika schuey mika schuey mika schuey mika schuey jean jos Rubens johnny i eddie heinz Ralf marc pedro 6 6 hello\0 there\0 6 howyalldoin?\0 'e' 'l' 'l' Ouch\0 Orphaned!

5

5

6 Problem 4:Useful Pointers (a) shelfT *FindBook(string name,shelfT shelves []bool *found) { int i; shelfT *shelf; shelf Getshelf(name,shelves); *found FALSE; for (i=0;i shelf->nTitles;i++) if (StringEqual(name,shelf->titles[i])) *found TRUE; return shelf; } (b) void AddBook(string name,shelfT shelves[]) int i; string *newList; shelfT *shelf; bool found; shelf FindBook(name,shelves,&found); if (found) printf("We already have a copy of &s\n",name); return; newList GetBlock((shelf->nTitles 1)*sizeof(string)); for (i=0;inTitles;i++) newList[i]shelf->titles[i]; newList [i]name; if (shelf->titles !NULL) FreeBlock(shelf->titles); shelf->titles newList; shelf->nTitles++; printf("&s added to the collection\n\n",name); (c) void ShowBooks(shelfT *shelves) int i,j; for (i=0;i N SHELVES;i++) for (j=0;jnTitles;j++) printf("8s\n",*((shelves i)->titles j));

6 Problem 4: Useful Pointers (a) shelfT *FindBook(string name, shelfT shelves[], bool *found) { int i; shelfT *shelf; shelf = GetShelf(name, shelves); *found = FALSE; for (i = 0; i nTitles; i++) if (StringEqual(name, shelf->titles[i])) *found = TRUE; return shelf; } (b) void AddBook(string name, shelfT shelves[]) { int i; string *newList; shelfT *shelf; bool found; shelf = FindBook(name, shelves, &found); if (found) { printf("We already have a copy of %s\n", name); return; } newList = GetBlock((shelf->nTitles + 1) * sizeof(string)); for (i = 0; i nTitles; i++) newList[i] = shelf->titles[i]; newList[i] = name; if (shelf->titles != NULL) FreeBlock(shelf->titles); shelf->titles = newList; shelf->nTitles++; printf(" %s added to the collection\n\n", name); } (c) void ShowBooks(shelfT *shelves) { int i, j; for (i = 0; i nTitles; j++) printf("%s\n", *((shelves + i)->titles + j));

7 printf ("\n"); }

7 printf(" \n"); }

8 Problem 5:Data Structures (a) 1. char dbPtr->categories->products[3]->name[0] 2. double &(db.stores->items[5].product->price) 3. storeT dbptr->customers[5].visited[3] 4. Error (db.customers 1)->bought[4].price 5· itemT (&db)->stores [4].items [2] 6. char dbptr->products->description +7 1 Error db.customers [db->nCustomers]->idNum 8. productT * &(dbPtr->stores[27].items[3].product) 9. Error dbptr->products[5]->name 10. categoryT (*dbPtr).categories[2] (b) customerT *FindCustomer(int id,databaseT *dbptr) int i; for(i=0;i dbptr->nCustomers;i++) if(dbPtr->customers[i].idNum =id) return(&(dbPtr->customers[i])); return(NULL); (c) bool IsBigSpender(customerT *curCust) double sum; int i; sum 0; for(i=0;inBought;i++) sum +curCust->bought [i]->price; return((sum curCust->nBought)>THRESHOLD);

8 Problem 5: Data Structures (a) 1. char dbPtr->categories->products[3]->name[0] 2. double * &(db.stores->items[5].product->price) 3. storeT * dbPtr->customers[5].visited[3] 4. Error (db.customers + 1)->bought[4].price 5. itemT (&db)->stores[4].items[2] 6. char * dbPtr->products->description + 7 7. Error db.customers[db->nCustomers]->idNum 8. productT ** &(dbPtr->stores[27].items[3].product) 9. Error dbPtr->products[5]->name 10. categoryT (*dbPtr).categories[2] (b) customerT *FindCustomer(int id, databaseT *dbPtr) { int i; for(i = 0; i nCustomers; i++) { if(dbPtr->customers[i].idNum == id) return(&(dbPtr->customers[i])); } return(NULL); } (c) bool IsBigSpender(customerT *curCust) { double sum; int i; sum = 0; for(i = 0; i nBought; i++) sum += curCust->bought[i]->price; return((sum / curCust->nBought) > THRESHOLD);

9

9 }

10 (d④ productT *RecommendRandomProduct(int id,databaseT *dbptr) customerT *cust; storeT *store; int i,j; cust FindCustomer(id,dbptr); if(cust =NULL)return(NULL); if(IsBigSpender(cust)) { for(i=0;inVisited;i++) store cust->visited[i]; for(j =0;jnItems;j++) if(store->items[j].nAvail >0) return(store->items[j].product); } /no suitable product found * return (NULL);

10 (d) productT *RecommendRandomProduct(int id, databaseT *dbPtr) { customerT *cust; storeT *store; int i, j; cust = FindCustomer(id, dbPtr); if(cust == NULL) return(NULL); if(IsBigSpender(cust)) { for(i = 0; i nVisited; i++) { store = cust->visited[i]; for(j = 0; j nItems; j++) { if(store->items[j].nAvail > 0) return(store->items[j].product); } } } /* no suitable product found */ return(NULL); }