University of California, Berkeley - College of EngineeringDepartment of Electrical Engineering and Computer SciencesInstructor: Scott BeamerSummer 2007CS 61C Midterm7/23/2007Last NameKeyFirst NameGradingSIDLogincs61c-First Letter of Logina b c dSecond letter of Logina b c d e f g h i j k l m n o p q r s t u v w x y zLab Time 101 102 103Name of the person to your leftName of the person to your rightAll the work is my own. I had no prior knowl-edge of the exam contents nor will I share the contents with others in CS61C who have not taken it yet. (please sign) Instruction•This booklet contains 7 numbered pages including the cover page. Put all answers on these pages (feel free to use the back of any page for scratch work); don’t hand in any stray pieces of paper.•Please turn off all pagers, cell phones & beepers. Remove all hats & headphones. Place your backpacks, laptops and jackets at the front. Sit in every other seat. Nothing may be placed in the “no fly zone” spare seat/desk between students.•Fill in the front of this page and put your name & login on every sheet of paper for Question 0.•You have 180 minutes to complete this exam. The exam is closed book, no computers, PDAs or calculators. You may use one pages (US Letter, front and back) of notes, plus the green reference sheet from COD 3/e.•There may be partial credit for incomplete answers; write as much of the solution as you can. We will deduct points if your solution is far more complicated than necessary. When we provide a blank, please fit your answer within the space provided. You have 3 hours...relax.Question012345TotalPoints1131616141575Score11316161415751/10Question 1: The CS61C Grab Bag (13pts, 20min)a)How many bits does it take to address N things? (hint: you may use the ceiling or floor function)ceil(log(N))b)Let: x = 0xfde7 z = 0x80d5i.What is x in binary?1111 1101 1110 0111ii.What is the value of x if it was interpreted as a 2’s Complement? (answer in decimal)-537iii.What is the encoding of the result of part ii in 1’s Complement? (answer in hex)fde6iv.Let x + y = z. Interpreting z as a sign-magnitude number, what 1’s Complement encoding of y will make this true? (answer in hex)0144!c) Match all the choices on the right with the most appropriate items on the left. Some choices will not be used, and others may be used more than once. If more than one choice on the right matches an item on the left, list all of those choices.K Next-fitA.238I Copying garbage collectionB.Makes request for memoryD, L LinkerC.Uses static predefined chunksF, J AssemblerD.Resolves jump statementsH Buddy Memory AllocationE.Converts C to MALB LoaderF.Resolves branch statementsE CompilerG.227A 256 GibiH.Can vary the size of chunksI.Wastes half the spaceJ.Makes the relocation tableK.Attempt to improve First-fitL.Makes executabled)Suppose you want to add a new pseudoinstruction to your assem-bler to operate on memory directly. The syntax of the instruction is: maddi register immediate (ie maddi $t2, 14) It will add the given immediate to the value in memory that the register holds the address for. You may assume that the absolute value of the immediate is less than 215. Write out what the instruc-tion to the right translates to in TAL.maddi $s0, 0xbeeflw $at, 0($s0)addi $at, $at, 0xbeefsw $at, 0($s0)Name:____________________________________ Login:____________________2/10Question 1 StandardPart a: 1pt all or nothingPart b (i-iv): 1pt each, all or nothing (4pts total)Part c: 0.5pts for each correct letter (5pts total) -0.5 pts for each wrong answer (but cap at 0, no negative)Part d: 3pts possible 3/3 for perfect 2/3 for slight error 1/3 for some knowledge shown (using memory) 0/3 for no clueQuestion 1 Common MistakesPart a: Thinking it is asking how many things N bits can represent (2N)Part b.iv: Done below x = -537 (part ii)! z = -213 (decoding sign magnitude)! x + y = z! =>! z - x = y! (-213) - (-537) = 324 = y! y = 0000 0001 0100 0100 (unsigned)! y = 0000 0001 0100 0100 (1’s Complement, positive so no change)! y = 0 1 4 4 = 0x144 Part d: Not using $at (it must be used when breaking up pseudoinstructions) Not using lw or sw (must be used to get to memory) !Name:____________________________________ Login:____________________3/10Question 2: The Matrix (16pts, 25min)In this problem you will help write some functions to deal with matrices in the mathematical sense. Our ultimate goal is to generate an add function for two matrices. You can use strlen and strcpy from string.h, but no other library functions (reference info on next page). For all of the following parts you may not need to use of all the variables declared, but you may not declare any additional variables. ! struct matrixStruct {! ! int *data;! ! char *name;! ! int numRows;! ! int numCols;! };! typedef struct matrixStruct *matrix;a) In one line of C complete the getElement function. You are guaranteed valid input, and you need to return the value in the matrix A at row r and column c. The matrix numbering starts with 0, so if r=0 and c=0 it is the upper left entry. int getElement(matrix A, int r, int c) {! ! 2pts possible! return (A->data)[c + r*(A->numCols)];! ! 1/2 for using r*c + c! (many possible ways)! ! ! ! ! 1/2 if missing A->data! ! ! ! ! ! ! ! ! 0 pts for A[r][c]! -0.5 pts for order of op error (1-array ref, 2-struct ref, 3-deref, 4-mult)}b) We want to generate a string that represents the name of the sum matrix. The string should be the name of A, concatenated with “ + “ (note the spaces before and after the ‘+’), and con-catenated with the name of B. You are guaranteed valid input. Complete getSumName.Example: ! A->name = “PB” B->name=”J” ! result of getSumName(A,B) = “PB + J”char* getSumName(matrix A, matrix B) {! ! 5pts possible! int newLength, i;! char *newName, *temp;1pt! newLength = strlen(A->name) + strlen(B->name) + 4;1pt! newName = (char*) malloc(sizeof(char) * newLength);1pt_/!temp = newName;! ! ! ! ! \!temp = strcpy(temp, A->name);!! -2 if didn’t move pointer1pt_/!temp += strlen(A->name);! ! -0.5 for each simple syntax error \!temp = strcpy(temp, " + ");! ! -1.5 major pointer error, but rest good1pt_/!temp+=3;! ! ! ! ! -2 set newName = A->name \ temp = strcpy(temp, B->name);!! -1 for no null character!! return
View Full Document
Unlocking...