CS 61CSummer 2022Caroline, Justin, PeyrinMidtermPrint your name:,(last) (first)Print your student ID:You have 110 minutes. There are 5 questions of varying credit (100 points total).Question: 1 2 3 4 5 TotalPoints: 20 25 20 25 10 100For questions with circular bubbles, you may select only one choice.Unselected option (completely unfilled)Only one selected option (completely filled)For questions with square checkboxes, you may select one or more choices.You can selectmultiple squares(completely filled)Anything you write that you cross out will not be graded. Anything you write outside the answer boxeswill not be graded.If an answer requires hex input, make sure you only use capitalized letters! For example,0xDEADBEEFinstead of0xdeadbeef. Please include hex (0x) or binary (0b) prefixes in your answers unless otherwisespecified. For all other bases, do not add any prefixes or suffixes.Read the following honor code and sign your name.I understand that I may not collaborate with anyone else on this exam, or cheat in any way. I am awareof the Berkeley Campus Code of Student Conduct and acknowledge that academic misconduct will bereported to the Center for Student Conduct and may further result in, at minimum, negative points onthe exam.Sign your name:This content is protected and may not be shared, uploaded, or distributed.Page 1 of 21Q1 Potpourri (20 points)Q1.1 (6 points)Translate the following decimal numbers into 8-bit two’s complement, unsigned, andsign-magnitude representations in the table below.If a translation is not possible, please write "N/A". Write your final answer in hexadecimalformat, including the relevant prefix.Decimal Two’s Complement Unsigned Sign-Magnitude128N/A 0x80 N/A-120xF4 N/A 0x8CSolution:8-bit two’s complement numbers can represent numbers up to28− 1 = 127, so 128 cannot berepresented.128 = 27, so in unsigned representation, we have 0b1000 0000 = 0x80.Intuitively, an 8-bit sign-magnitude number can only use 7 bits to represent the number (leaving1 bit for the sign). A 7-bit unsigned number can represent numbers up to28− 1 = 127, so 128cannot be represented.12 in unsigned 8-bit binary is0b0000 1100. Since we want to represent -12 in two’s comple-ment binary, we’ll flip the bits:0b1111 0011, and add one:0b1111 0100. Converting to hex,we get 0xF4.Negative numbers cannot be represented as unsigned.An 8-bit sign-magnitude number uses 7 bits to represent the magnitude of the number. 12 inunsigned 7-bit binary is0b000 1100. Then we add the sign bit, which is0b1since we wantto represent a negative number. In total, we get 0b1000 1100, which is 0x8C in hex.Midterm (Question 1 continues. . .)This content is protected and may not be shared, uploaded, or distributed.Page 2 of 21 CS 61C – Summer 2022(Question 1 continued. ..)Q1.2 (2 points) Convert 83 to the following bases as an unsigned number. Remove any leading zeros.Binary Hex0b101 0011 0x53Solution:The nearest power of 2 below 83 is26= 64. The remainder is83− 64 = 19. The nearest powerof 2 below 19 is24= 16. The remainder is19−16 = 3. The nearest power of 2 below 3 is21= 2.The remainder is3 − 2 = 1 = 20. In total, we have26+ 24+ 21+ 20= 64 + 16 + 2 + 1 = 83.Converting this to unsigned binary gives us 0b101 0011.In hexadecimal, we can zero-pad to 8 bits (1 hex digit = 4 bits, so we need the bit length of thenumber to be a multiple of 4), which gives us 0b0101 0011. In hex, this is 0x53.Q1.3 (3 points)Which of the following representations have more than one representation of 0? Selectall that apply.(A) Two’s complement(B) Sign-magnitude(C) An IEEE-754 standard double-precision float(D) Bias notation(E) None of the aboveSolution:Two’s complement has one representation of zero. Intuitively, if you try to get a representationof "negative zero", flipping all the bits of0b0000...0000gives you0b1111...1111, andadding one gives you 0b0000...0000 again.Sign-magnitude has two representations of zero:0b0...0000(positive zero), and0b1...0000(negative zero).Floating point representation has two representations of zero: set all exponent and mantissabits to zero. Then you can set the sign bit to either 0 or 1, and both result in 0.Bias notation is unsigned representation with an offset. Unsigned representation has only onerepresentation of 0, so regardless of bias offset, there cannot be a second representation of 0.Midterm (Question 1 continues. . . )This content is protected and may not be shared, uploaded, or distributed.Page 3 of 21 CS 61C – Summer 2022(Question 1 continued. . . )Q1.4 (3 points) Which program resolves pseudoinstructions?(A) Assembler(B) Interpreter(C) Linker(D) Loader(E) None of the aboveSolution: Pseudoinstructions are resolved by the assembler in the process of convertinginstructions into machine code (raw bits).Q1.5 (3 points) Which program can output pseudoinstructions?(A) Assembler(B) Compiler(C) Linker(D) Preprocessor(E) None of the aboveSolution: Pseudoinstructions are part of assembly code. The compiler outputs assembly code.Q1.6 (3 points) Which program initializes registers to their default value?(A) Assembler(B) Compiler(C) Interpreter(D) Linker(E) None of the aboveSolution: None of these choices actually start and run the program, so they don’t initializeregisters.MidtermThis content is protected and may not be shared, uploaded, or distributed.Page 4 of 21 CS 61C – Summer 2022Q2 Trie, Trie Again (25 points)In this problem, we will be implementing a trie. A trie is a data structure that stores strings in a tree-likestructure, with each character in the string corresponding to a node. If two strings start with the samecharacters, the nodes for those characters will be shared between the two strings.For each character in the string, our trie will create an AlphaTrieNode struct with two fields:•A booleanlastthat indicates whether or not the character is the last character in a string. In thediagram, nodes with last set to true are shaded.•An arraynextof 26AlphaTrieNodepointers. Each element in thenextarray corresponds to alettera-z. Each array element is either a pointer to the node corresponding to that letter, orNULLif there is no node for that letter.CARThis trie on the left stores one word “car”.Thelastfield isfalsein the C and A nodes, andtruein theR node.In the C node,next[0]should hold the address of the A node,and next[1], next[2], ..., next[25] should all be NULL.CARLLOCWe want to insert “calloc” into the trie. Note that “car” and“calloc”