This copy has answers displayed.

Read and fill in this page now.
Do NOT turn the page until you are told to do so.

Your name:
Your login name:
Your lab section day and time:
Your lab t.a.:
Name of the person sitting to your left:
Name of the person sitting to your right:

Problem 0

Total:

/20

Problem 1

Problem 2

Problem 4

Problem 3

Problem 5

This is an open-book test. You have approximately fifty minutes to complete it. You may consult any books, notes, or other paper-based inanimate objects available to you. To avoid confusion, read the problems carefully. If you find it hard to understand a problem, ask us to explain it. If you have a question during the test, please come to the front or the side of the room to ask it.

This exam comprises 10% of the points on which your final grade will be based. Partial credit may be given for wrong answers. Your exam should contain six problems (numbered 0 through 5) on six pages. Please write your answers in the spaces provided in the test; in particular,we will not grade anything on the back of an exam page unless we are clearly told on the front of the page to look there.

For solutions involving C code, you are allowed to use any function in the stdio or string libraries. Assume that the lines

#include <stdio.h>

#include <string.h>

precede your code.

A couple of students are taking the exam Monday morning. Please don't post any newsgroup items about the exam until then.

Relax--this exam is not worth having heart failure about.

Problem 2 (5 points, 15 minutes)

Write a C function named resultOfInsert that, given a string s , a character c , and a position k between 0 and strlen(s) , inclusive, returns the string that results from inserting c into s at position k . For example,

resultOfInsert ("abcd", '_', 2)

should return the string "ab_cd" . The insertion should not change the argument string. You may use any functions declared in <string.h> . You don't need to do any error checking.

char *resultOfInsert (char *s, char c, int k) {

malloc call is worth 2 points, 1 for trying it and 1 for getting it right.

everything else is worth 3 points: -1 for each error, like off-by-one, forgetting terminating 0, using = for ==, forgetting to return something

Solution code:

char *resultOfInsert (char *s, char c, int pos) {

char *rtn = (char *) malloc (strlen(s)+2);

int k;

for (k=0; k<pos; k++) {

rtn[k] = s[k];

}

rtn[pos] = c;

for (k=pos; k<=strlen(s); k++) {

rtn[k+1] = s[k];

}

return rtn;

}

Another solution:

for (k=0, j=0; k<=strlen(s); k++, j++) {

if (k==pos) {

rtn[j] = c;

j++;

}

rtn[j] = s[k];

}

Problem 3 (3 points, 9 minutes)

Consider the following C program.

#include <string.h>

int main ( ) {

char oneName[10] = "xxxxxxxxx";

char* anotherName;

anotherName = oneName;

strcpy (anotherName, oneName);

oneName[1] = 'O';

return 0;

}

Draw the box-and-pointer diagram that represents the oneName and anotherName arrays and their contents after executing this segment.

oneName ----> |"xOxxxxxxx"| followed by null char

anotherName ---+

Anticipated errors: no sharing; only part sharing, no arrows, off-by-one indexing.

two copies of string => -3

anotherName nil => -3

anotherName points to last char of oneName string => -2

anotherName points to oneName, which points to char => -2

off by one on char assignment => -1

off by one on count of chars => -1

didn't show trailing null => -1

Problem 4 (5 points, 15 minutes)

Consider the storage layout below, which uses the boundary tags system from lab assignment 3.

"addresses"	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
contents	3 0 0 -2 3 -4 -7 -7 -7 -7 -4 -3 -13 -13 -13 -3 2 0 0 2

Part a

The layout provides enough information to determine the storage blocks represented, along with which blocks are allocated and which blocks are free. Provide this information below by specifying the start and end address of each block, including the boundary tag information. (For example, at the start of the program there is one free block that starts at "address" 1 and ends at "address" 20.)

start "address"	end "address"	allocated or free?
1	5	free
6	11	alloc
12	16	alloc
17	20	free

3 points: -1 each error

Part b

The layout above is incorrectly structured. What's wrong with it?

The two free blocks aren't linked.

2 points; -1 for a vague but possibly correct answer, or for something wrong in addition to the right answer.

Problem 5 (3 points, 5 minutes)

Suppose that the label names marks the beginning of an array of strings. In MIPS assembly language, this might appear as follows:

names: .word starting address of first string

.word starting address of second string

...

Give a MIPS assembly language program segment that loads the fourth character of the second string into register $t0 . For example, if the array contains the strings "mike" , "clancy" , "dave" , and "patterson" , this character would be the 'n' in "clancy" . Assume that there are at least two strings in the array and at least four characters in the second string.

A three-line solution is sufficient. You may use any registers you want.

la $t1,names

lw $t2,4($t1) # get the pointer to the 2nd string

lb $t0,3($t2) # get the 4th character

Also correct:

lw $t2,names+4 # get the pointer to the 2nd string

lb $t0,3($t2) # get the 4th character

-1 each error, e.g. wrong load, wrong offset, 1-based indexing