University of California Berkeley College of Engineering Department of Electrical Engineering and Computer Sciences Summer 2010 Instructor Paul Pearce CS61C 2010 07 16 Midterm After the exam indicate on the line above where you fall in the emotion spectrum between sad smiley Last Name Answer Key First Name Student ID Number Login cs61c Login First Letter please circle a b c d e f g h i j k l m Login Second Letter please circle a n b o c p d q e r f s g t h u i v j w k x l y m z The name of your LAB TA please circle Eric Tom Noah Alex Name of the person to your Left Name of the person to your Right All the work is my own and I have collaborated with no one 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 a Instructions Read Me Don t Panic This booklet contains 12 numbered pages including the cover page and MIPS reference guide Put all answers on these pages don t hand in any stray pieces of paper Please turn off all pagers cell phones beepers Remove all hats headphones Sit in every other seat Nothing may be placed in the no fly zone spare seat desk between students Question 0 1 point involves filling in the front of this page and putting your login on every sheet of paper You have 180 minutes to complete this exam The exam is closed book no computers PDAs calculators You are allowed 1 page of notes front and back A MIPS reference sheet has been provided as the last page of this handout You should rip it off 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 Minutes Points 0 1 1 1 15 39 2 20 20 3 25 50 4 15 20 5 20 25 6 25 35 Total 59 to review 180 190 Score 1 39 20 50 20 25 35 190 1 11 Login cs61c Answers Question 1 Where s the kitchen sink 39 pts 15 min Part 1 CS61C trivia True False Circle the correct answer in the right hand column a You must use the addu instruction to add unsigned numbers T F b You do not need to save volatile registers if your code doesn t call any subfunctions T F c You do not need to save volatile registers if they won t be modified by any subfunctions T F d We add a bias to floating point exponents to increase the range of values we can represent T F e The instructions srl and sra behave identically on positive 2 s complement numbers T F f There are situations where using first fit will cause less fragmentation than best fit T F g The size of a structure that contains only 2 ints and 1 char will be 9 bytes T F Fill in the blank neatly write your answer in the right hand column h How many things can you represent with N bits 2N i Suppose you are given N bits How many more bits would you need if we wished to triple the number of things we wanted to represent 2 j Assuming the following C code declaration char str Hello World 12 What will sizeof str return k Assuming the following C code declaration char str Hello World 4 What will sizeof str return l Assuming the following C code declaration char str Hello 0World 5 What will strlen str return Continued on next page 2 11 Login cs61c Question 1 Where s the kitchen sink Continued 39 pts 15 min Part 2 Number representation So far we have studied 4 different methods for representing integers using 32 bits These methods can be generalized to any number of bits Fill in the bit patterns for the following 4 bit numbers If there are multiple bit patterns for a given number write them all If no bit pattern exists to represent the given number write N A in the box don t leave it blank The first one has been done for you already 0 0000 Sign Magnitude 0000 1000 1 N A 1111 1001 N A Unsigned 15 One s Complement 0000 1111 1110 N A Two s Complement 0000 1111 N A Now fill in the decimal base 10 value for the following 4 bit numbers The first one has been done for you already Number with bit pattern 0b1100 Number closest to Number closest to Unsigned Sign Magnitude One s Complement Two s Complement 12 4 3 4 15 7 7 7 0 7 7 8 Part 3 Compiling Linking Loading Fill in the blanks to specify during what stage each action occurs Use abbreviations CO Compiling AS Assembly LI Linking LO Loading LI Jump labels are resolved AS Short branch labels are resolved LO The operating system handles this stage CO Code is translated from C MAL AS Code is translated from MAL TAL 3 11 Login cs61c Answers Question 2 Did somebody say Free Lunch 20 pts 20 min Consider the following 10 bit floating point format It contains the same fields sign exponent significand and follows the same general rules as the 32 bit IEEE standard denorms biased exponent non numeric values etc It simply allocates its bits differently Please answer the following questions and show all your work in the space provided We went ahead and got you started S EEE MMMMMM Number represented by 0x00 Bits in the Mantissa 6 a Exponent Bias 3 b Implicit exponent for denormalized s 2 c of Numbers between 2 n 8 0 128 2 8 1 256 d Largest number x such that x 5 5 Continued on next page 4 11 Login cs61c Question 2 Did somebody say Free Lunch Continued 20 pts 20 min S EEE MMMMMM Repeated so you don t need to flip back and forth e Difference between the two smallest positive values f Difference between the two largest non positive values g Number of NaN s h Using the above format what is the bit pattern for the floating point number closest to 14 4 5 11 2 8 1 256 2 3 1 8 126 0b0110110011 Login cs61c Answers Question 3 Don t lose your head 50 pts 25 min We ve created a simple doubly linked list out of nodes as defined below Each node contains a pointer to a struct pair The structures are defined as follows struct pair int x int y struct node struct node prev struct pair datum struct node next The first node has its prev field set to NULL The last node has its next field set to NULL a Fill in the code below to implement insert before The function inserts a node in …
View Full Document
Unlocking...