# 讲解 CIT 593: Introduction to Computing Systems Fall 2017 Final Exam辅导 R编程

CIT 593: Introduction to Computing Systems

Fall 2017

Final Exam

Part I – General Knowledge (20 points total)

Directions: Provide 1 to 2 sentence answers to the following questions:

1)   Convert the following binary #: 1000001, into the following forms:

ASCII:

Hex:

Decimal (if # is 8-bit unsigned):

Decimal (if # is 8-bit signed):

2)   What are the most positive and most negative #’s you can create using only 3-bits in 2C?

3)   How can one detect overflow in 2C binary addition?

4)   What does it mean for a CPU to be “single cycle”?

5)   A line from a Makefile reads:

clang program5_swap.c program5.o -o program5

What is this an example of: Assembling, Compiling, or Linking?

6)   Draw the Von-Neumann model for a CPU

7)   Draw the model for an I/O controller for a generic device.  Briefly indicate what the various parts are meant to do.

8)   What is the difference between these two variables: my_array1 and my_array2? int my_array1 [2]

my_array1[0] = 1;

my_array1[1] = 2;

int *my_array2 = malloc (sizeof(int)*2) ;

my_array2[0] = 1 ;

my_array2[1] = 2 ;

free(my_array2) ;

9)   What is a hashtable in C?

Part II - CMOS and Logic

1) (15 points) Given the following CMOS gate, answer the following questions:

a)   Using the inputs listed on the 4 instances of the above CMOS circuit below, replace the missing parts in the circuits below with either a wire or no wire and predict the output. Fill in the predicted output in the line next to the output Y.

b)   Create a truth table that lists all possible input combinations for the above CMOS circuit.

NOTE: your table inputs must be in binary and in ascending numeric order: 0,1,2,…

c)   Using your truth table from step (b), create a PLA that implements the truth table

d)   Write out the exact Boolean logic function expressed by your PLA.

e)   From steps (a)-(d), what logic function does this circuit actually perform?

Part III - Assembly/C

2) (10 points) For the questions in this section, assume memory has the following contents:

In addition, this code is to be referenced in parts (a) and (b) below:

int* a = &x ;

while (*a != 0) {

a++ ;

*a=(*a)<<1 ;

}

a)   Using the code shown above and the contents of memory shown in the above table entitled: “Memory before code is run”, fill in the table labeled: “Memory after code is run.”

b)   Translate the C-code on the last page into LC4-Assembly. You do not need to use the stack; you may simply use R0-R7 in anyway you’d like. However, you MUST follow the algorithm exactly (while loops, shift operators, etc). In addition, you must properly dereference pointers in Assembly (you may use the back of this page for more space) .

Part IV - Strings in C

3) (15 points) Write a C function named: “stringPig()” that takes as a parameter a C-string of

unknown length, containing a single word.  Your function should translate this string from English into Pig Latin. This translation is performed by removing the first letter of the string, appending it onto the end, and concatenating the lettersay. You can assume that the array contains enough space for you to add the extra characters.

For example, if your function is passed the string “Hello” after your function returns, the string should have the value: “elloHay”.  The first character of the string should be “e” .

a)   Write the C-function with the following specifications:

.    You must determine if returning data is necessary

.    You may not call other string functions in C (like strlen or strcat as an example)

.    Your function should not crash if the string passed in is NULL.

.    You must comment your functionsowe can grade it!

.    You may not use malloc() or any form of dynamic memory

b)   Write a main() function that will test your stringPig() and print its output to the screen. You must ensure that your main() and stringPig() have no memory leaks upon return.

4) (10 points) Write a C function named: “strShift()” that takes as a parameter a C-string of unknown length and an amount to shift the string by: n. Your function should shift the string n character’s to the left and return the result.

For example, if your function is passed the string “Hello” and n=1 after your function returns, the string should have the value: “ello”.  If n=2, after your function eturns the string should be: “llo” .

a)   Further specifications for writing the function:

. YOU MUST USE POINTER NOTATION ONLY (no [ ] operators)

.    You must determine if returning data is necessary

.    You may not call other string functions in C (like strlen or strcat as an example)

.    Your function should not crash if the string passed in is NULL.

.    You must comment your functionsowe can grade it!

.    You may not use malloc() or any form of dynamic memory

b)   Write a main() function that will test your strShift () and print its output to the screen. You must ensure that your main() and strShift () have no memory leaks upon return.

Part V - Debugging in C

5) (5 points) Assume printf() exists on the LC4 and this code is compiled using LC4’s C- Compiler:

#include

int main() {

int apple ;

int *ptr ;

int **ind ;

ind = &ptr ;

*ind = &apple ;

**ind = 123 ;

ind++ ;

(*ptr)++;

apple++ ;

printf(“%p %p %d\n” ind, ptr, apple) ;

}

a)   Draw out the stack just after the apple++; executes. You do not need to show the

arguments, RV, RA, or FP in this listing of the stack. You may start your stack at address: x7FFF.

b)   What will this code printout to the screen?

6) (10 points) In the following example, you may assume malloc() always succeeds.

typedef struct customer_s {

int id ;

char* name ;

struct customer_s* next ;

} customer ;

customer* add_to_list (customer* head, int id, char* name) { customer* node = malloc(sizeof(customer));

node->id = id ;

node->name = name ;

return (node);

}

customer* node = NULL ;

free (node) ;

}

}

int main() {

return 0 ;

}

a)   The above code compiles, but itsegfaults whenever delete_list() is called.  Explain why thesegfault occurs.

b)   While the above code compiles, before delete_list() is called, the linked list never has more than 1 node.  Explain why that is the case.

c)   Fix the errors in the above code to address the problems in parts (a) and (b)

Part VI - Stack/Heap/TRAPS

7) (20 points) The following C function was compiled with the lcc compiler to run on PennSim.

For this question, a handy reference for you will be the following table that shows the calling convention in lcc for each function’sstack frame.

a)   Your job is to populate the table of the LC4’s memory on the next page for the program shown above. The table must show the addresses (in HEX) & contents (inappropriate format) of the global/static, stack, heap regions of memory, as well as registers: R5, and R6 right before the call to printf().  The following information will aid you in your task:

.    Assume the program is called “a.out” and executed as follows: ./a.out

.    Assume when main() was called, R5 was 0 and R6=x7FFE

.    Assume main() was called by USER_START using a JSR on linex0006 .

.    Assume the line #’s you see in the C-program are the locations in program memory where the corresponding assembly is loaded.  As an example:

[1E] char* destination = NULL ;

.    Assume stdio.h, stdlib.h, and string.h libraries exist on the LC4 and that each call to malloc() will succeed for this program.

.    Any values that cannot be determined must be marked with an X.

b)  There is 1 error in main(), what is it?

8) (3.5 points) The following code showsa TRAP,a TRAP_WRAPPER, and the C-Code that calls  the wrapper.  The TRAP should printout a null terminated string to the ASCII display. There are 7 missing instructions throughout the code below.  Fill in the missing instructions right   next to the missing instruction.

--------------------FILE: os.asm------------------------------------

.CODE

TRAP_PUTS

Missing Instr. 1 =

LDR R1, R1, #0

BRzp TRAP_PUTS   ; check to see if ASCII display is available

Missing Instr. 2 =

LDR R2, R0, #0    ; load character from string into R2

BRz EXIT          ; if char is NULL, exit

STR R2, R1, #0    ; write character from R2 to display

ADD R0, R0, #1   ; advance pointer to next char in string

Missing Instr. 3 =

EXIT

RTI

--------------------FILE: lc4_stdio.asm-----------------------------

.FALIGN

lc4_puts

;; prologue

Missing Instr. 4 =

Missing Instr. 5 =

Missing Instr. 6 =

ADD R5, R6, #0  ; set R5 = R6 (the new frame pointer)

;; function body

LDR R0, R5, #3  ; get arguments to TRAP_PUTS

TRAP x03        ; assume TRAP_PUTS is at x03 on vector table

;; epilogue

ADD R6, R5, #0   ; reset stack to what it was before function body

ADD R6, R6, #3  ; reduce the size of the stack

STR R7, R6, #-1 ; store return value on stack

LDR R5, R6, #-3 ; restore base pointer

LDR R7, R6, #-2 ; restore return address

RET

----------------------FILE: main.c -----------------------

void lc4_puts (char* string) ; /* function declaration for lc4_puts */

int main()

{

char my_string [] = ; (Missing Instr. 7)

lc4_puts (my_string) /* call lc4_puts() properly */

}