LAST NAME: __________________________
FIRST NAME: __________________________
CIT 593: Introduction to Computing Systems Final Exam
Instructions: Write your name on every page of this exam. Complete all problems in the space provided. You may use the back pages of the exam, but make certain you label your work. This exam will be scanned into gradescope; if your work isn’t clear or I cannot read your handwriting, you are less likely to receive partial credit. This is a closed-notes exam, calculators are NOT allowed.
Copyright By PowCoder代写 加微信 powcoder
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:
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”?
All the steps of the Von-Neumann loop are done in 1 cycle of the clock.
5) A line from a Makefile reads:
clang program5_swap.c program5.o -o program5
An example of: Linking
__’A’________
___x41________
011 = +3,
It cannot happen if the two addends have different signs.
_#65__________
___#-63_________
If the two addends have the same sign and the sum has a different sign than the
addends, an overflow has occurred
LAST NAME: __________________________ FIRST NAME: __________________________
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?
Control/Status register – tell if devices is ready or has data to be transferred
Data Register – actual data to/from I/O device
Electronics – convert digital from control/status/data regs to I/O devices electrical
My_array1 is an actual array held entirely on the stack
My_array2 is actually a pointer, that holds a memory address to a location on the heap.
They both work like arrays, but only 1 of them is an array
Since my_array1 is on the stack, it is an automatic variable, so once it is out of scope, its
memory is de-allocated. My_array2 is a dynamic variable, so its memory will be
allocated until the programmer calls free().
9) What is a hashtable in C?
10) What are the advantages/disadvantages of a linked list over an array in C?
Linked list is dynamic in its length, arrays are not
Linked list can grow/shrink at runtime, arrays cannot
Linked list can be re-ordered easily by re-arranging pointers, arrays cannot
Linked lists are more difficult to search than arrays.
An associative array where the incoming data is mapped to the proper storage location
within the array.
An array (bucket holder) of linked lists with a hashing function to determine where data
should fit.
LAST NAME: __________________________ FIRST NAME: __________________________
Part II – CMOS and Logic
(15 points) Given the following CMOS gate, answer the following questions:
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.
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,…
ABCY 0001 0011 0101 0111 1001 1011 1101 1110
LAST NAME: __________________________ FIRST NAME: __________________________ 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.
Y=(A’B’C’)+(A’B’C)+(A’BC’)+(A’BC)+(AB’C’)+(AB’C)+(ABC’)
e) From steps (a)-(d), what logic function does this circuit actually perform?
3-input NAND gate: Y=(ABC)’
LAST NAME: __________________________ FIRST NAME: __________________________
Part III – Assembly/C
2) (10 points) For the questions in this section, assume memory has the following contents:
Memory before code is run: Address Contents Comment
X4000 #1 x
X4004 …… X7FFC a X7FFC
Memory after code is run:
Contents Comment
In addition, this code is to be referenced in parts (a) and (b) below:
int* a = &x ;
while (*a != 0) {
*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 any way 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).
;; int* a = &x
CONST R7 x00
HICONST R7 x40
ADD R0 R7 #0
; R0 = x4000 (&x)
; if *a-0=0, end
; R1 = the value at R0 (*a)
; Left shift R1 by 1 (<<1)
; Store shifted number at R0 (*a = shifted number)
;; while(*a != 0)
WHILE_LOOP
LDR R1 R0 #0
CMPI R1 #0
BRz END_WHILE
;; a+A+DD R0 R0 #1 ;; *a = (*a) << 1 LRD R1 R0 #1 SLL R1 R1 #1 STR R1 R0 #0
JMP WHILE_LOOP ; Loop
LAST NAME: __________________________ FIRST NAME: __________________________
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 letters ay. 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 function so we 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.
int stringPig (char *word)
int i = 1;
if (word == NULL) return (-1) ;
char first = word[0] ; if (first == '\0') return (-1) ;
while (word[i] != '\0') { word[i - 1] = word [i];
word[i - 1] = first; word[i] = 'a'; word[i + 1] = 'y'; word[i + 2] = '\0'; return (0) ;
#include
int main () {
char my_word [8] = “Hello” ;
stringPig (my_word) ;
printf (“my_word in pig latin is %s”, my_word) ;
LAST NAME: __________________________ FIRST NAME: __________________________
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”.
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 function so we 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.
#include
char* strShift (char* string, int shift) {
if (string == NULL) return NULL ; for (int i = 0 ; i < shift; i++) { } string++ ;
return string;
int main () {
int n = 1 ;
char* my_word = “Hello” ;
my_word = strShift (my_word, n) ;
printf (“my_word shifted %d places = %s”, n, my_word) ;
LAST NAME: __________________________ FIRST NAME: __________________________
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 ;
} 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.
Address X7FFD X7FFE X7FFF
Contents Comment X7FFF ind
b) What will this code print out to the screen? X7FFF, x7FFF, 125
LAST NAME: __________________________ FIRST NAME: __________________________ 6) (10 points) In the following example, you may assume malloc() always succeeds.
typedef struct customer_s {
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 ;
node->next = head ;
return (node);
void delete_list (customer* head) { customer* node = NULL ;
while (head != NULL) {
node = head ;
head = node->next ;
free (node) ;
int main() {
customer* head_node ;
= add_to_list ( head_node, 123, “Tom”);
= add_to_list ( head_node, 456, “Bob”);
delete_list ( head_node) ;
return 0 ; }
a) The above code compiles, but it segfaults whenever delete_list() is called. Explain why the segfault occurs.
Head_node is actually on the stack. When delete_list() attempts to “Free” it, a segfault 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.
When add_to_list() is called, we did not update the head node of the linked list!
c) Fix the errors in the above code to address the problems in parts (a) and (b)
LAST NAME: __________________________ FIRST NAME: __________________________
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’s stack frame:
Temporaries, arguments to callees
Local variables
Caller’s frame pointer
Return address
Return value
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 (in appropriate format) of the global/static, stack, heap regions of memory, R5, R6, and R7 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 line x0006.
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 ;
would be loaded into program memory at address: x001E
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.
#include
#include
#include
char* my_strdup (char* dest, char* src) {
dest = malloc (strlen(src) + 1) ;
strcpy (dest, src) ;
return (dest) ;
int main (int argc, char** argv) {
char* source = “Tom” ;
char* destination = NULL ;
destination = my_strdup (destination, source) ; printf (“%s\n”, destination) ;
return 0 ; }
LAST NAME: __________________________ FIRST NAME: __________________________
LC4 – Global Memory:
x2000 X2001 X2002 X2003 X2004 X2005 X2006 X2007 X2008 X2009 X200A X200B X200C
LC4 – Heap Contents:
Comment argv[0] argv[0][0] argv[0][1] argv[0][2] argv[0][3] argv[0][4] argv[0][5] argv[0][6] argv[0][7] source[0] source[1] source[2] source[3]
Address Contents
X4000 ‘T’ X4001 ‘o’ X4002 ‘m’ X4003 ‘\0’
Destination[0] Destination[1] Destination[2] Destination[3]
LC4 – Stack Contents:
X7FF4 X7FF5 X7FF6
X7FF8 X7FF9
X7FFA X7FFB X7FFC X7FFD X7FFE X7FFF
x7FFB x7FF9 X4000
X, then x4000 NULL then x4000 x2009 NULL, then X4000 x2009 x0000 x0007 X
main()’s FP main()’s RA my_strdup()’s RV
my_strdup arg: *dest
my_strdup arg: *src
main()’s Local var: *destination
main()’s Local var:*source USER_START’s FP USER_START’s RA main()’s RV
argc **argv
There is 1 error in main(), what is it?
Free() was never called on the malloc()’d memory.
R6 R7 (e.c.)
LAST NAME: __________________________ FIRST NAME: __________________________
x2000 X2001 X2002 X2003
Address Contents Comment X4000 X4001 argv[0] X4001 ‘.’ argv[0][0] X4002 ‘/’ argv[0][1] X4003 ‘a’ argv[0][2] X4004 ‘.’ argv[0][3] X4005 ‘o argv[0][4] X4006 ‘u’ argv[0][5] X4007 ‘t’ argv[0][6] X4008 ‘\0’ argv[0][7] X4009 ‘T’ Destination[0] X400A ‘o’ Destination[1] X400B ‘m’ Destination[2] X400C ‘\0’ Destination[3]
Comment source[0] source[1] source[2] source[3]
X7FF4 X7FF5 X7FF6
X7FF8 X7FF9
X7FFA X7FFB X7FFC X7FFD X7FFE X7FFF
x7FFB x7FF9 X4009
ALTERNATE SOLUTION – IF ARGV is on HEAP
LC4 – Global Memory:
LC4 – Heap Contents:
LC4 – Stack Contents:
X, then x4009 NULL, then x4009 x2000 NULL, then X4009 x2000 x0000 x0007 X
main()’s FP main()’s RA my_strdup()’s RV
my_strdup arg: *dest
my_strdup arg: *src
main()’s Local var: *destination
main()’s Local var:*source USER_START’s FP USER_START’s RA main()’s RV
argc **argv
There is 1 error in main(), what is it?
Free() was never called on the malloc()’d memory.
(3.5 points) The following code shows a TRAP, a TRAP_WRAPPER, and the C-Code that calls the wrapper. The TRAP should print out 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———————————— OS_ADSR_ADDR .UCONST xFE04 ; status reg for ASCII display OS_ADDR_ADDR .UCONST xFE06 ; control reg for ASCII display
Missing Instr. 1 = LC R1, OS_ADSR_ADDR
LDR R1, R1, #0
BRzp TRAP_PUTS ; check to see if ASCII display is available
Missing Instr. 2 = LC R1, OS_ADDR_ADDR
LAST NAME: __________________________ FIRST NAME: __________________________
LDR R2, R0, #0
STR R2, R1, #0
ADD R0, R0, #1
; load character from string into R2
; if char is NULL, exit
; write character from R2 to display
; advance pointer to next char in string EXIT Missing Instr. 3 = BRnzp TRAP_PUTS
——————–FILE: lc4_stdio.asm—————————– .FALIGN
;; prologue
ADD R5, R6, #0
;; function body
LDR R0, R5, #3
;; epilogue
ADD R6, R5, #0
ADD R6, R6, #3
STR R7, R6, #-1
LDR R5, R6, #-3
LDR R7, R6, #-2
; set R5 = R6 (the new frame pointer)
; get arguments to TRAP_PUTS
; assume TRAP_PUTS is at x03 on vector table
; reset stack to what it was before function body
; reduce the size of the stack
; store return value on stack
; restore base pointer
Missing Instr. 4 = STR R7, R6, #-2 Missing Instr. 5 = STR R5, R6, #-3 Missing Instr. 6 = ADD R6, R6, #-3
; restore return address ———————-FILE: main.c ———————–
void lc4_puts (char* string) ; /* function declaration for lc4_puts */
int main()
char my_string [] = {‘T’, ‘o’, ‘m’, ‘\0’} ; (Missing Instr. 7)
lc4_puts (my_string) /* call lc4_puts() properly */ }
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com