University of California Berkeley College of Engineering Department of Electrical Engineering and Computer Sciences Instructor Scott Beamer Summer 2007 CS 61C Midterm 7 23 2007 Last Name Key First Name Grading SID Login cs61cFirst Letter of Login a b c d Second letter of Login a b o c p d q n Lab Time e r f s 101 g t h u i v 102 j w k x l y m z 103 Name of the person to your left Name of the person to your right All the work is my own I had no prior knowledge 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 Question 0 1 2 3 4 5 Total Points 1 13 16 16 14 15 75 Score 1 13 16 16 14 15 75 1 10 Name Login Question 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 b Let i x 0xfde7 ceil log N z 0x80d5 What is x in binary 1111 1101 1110 0111 ii What is the value of x if it was interpreted as a 2 s Complement 537 answer in decimal iii What is the encoding of the result of part ii in 1 s Complement answer in hex fde6 iv 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 I D L F J H B E A Next fit Copying garbage collection Linker Assembler Buddy Memory Allocation Loader Compiler 256 Gibi A B C D E F G H I J K L 238 Makes request for memory Uses static predefined chunks Resolves jump statements Converts C to MAL Resolves branch statements 227 Can vary the size of chunks Wastes half the space Makes the relocation table Attempt to improve First fit Makes executable d Suppose you want to add a new pseudoinstruction to your assembler 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 instruction to the right translates to in TAL 2 10 maddi s0 0xbeef lw at 0 s0 addi at at 0xbeef sw at 0 s0 Name Login Question 1 Standard Part a 1pt all or nothing Part 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 clue Question 1 Common Mistakes Part 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 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 z x y 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 3 10 Name Login Question 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 concatenated 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 pointer 1pt temp strlen A name 0 5 for each simple syntax error temp strcpy temp 1 5 major pointer error but rest good 1pt temp 3 2 set newName A name temp strcpy temp B name 1 for no null character return newName 4 10 Name Login Question 2 continued The Matrix 16pts 25min c Now that we have helping functions lets write …
View Full Document
Unlocking...