Name:CSE 303, Spring 2005, Final Examination7 June 2005Please do not turn the page until everyone is ready.Rules:• The exam is closed-book, closed-note, except for one side of one 8.5x11in piece of pap e r.• Please stop promptly at 4:20.• You can rip apart the pages, but please write your name on each page.• There are 90 total points, distributed unevenly among 8 questions (which all have multiple parts).• When writing code, style matters, but don’t worry about indentation.Advice:• Read questions carefully. Understand a question b e fore you start writing.• Write down thoughts and intermediate steps so you can get partial credit.• The questions are not necessarily in order of difficulty. Skip around.• If you have questions, ask.• Relax. You are here to learn.1Name:1. Consider this C program, which compiles without warning, but crashes when run:int factorial(int x) {if(x==1)return 1;return x * factorial(x-1);}int main(int argc, char**argv) {factorial(0);}(a) 3pts Looking at the source co de, why does the program crash?(b) 6pts What would happen if you used gdb to run this program? Without looking at the sourcecode, what gdb commands would you use? What would you be able to conclude?Solution:(a) It overflows the stack: factorial will call itself recursively billions of times (assume 32-bit ints)and there is not enough room for a stack that large. When the stack reaches inaccessible memory,a segmentation-fault occurs. factorial does not expect arguments less than 1.(b) gdb would detect the segmentation fault and allow inspection of the program’s state. Using thebacktrace command would show that the stack is full of thousands of recursive calls to factorial,indicating that the problem almost certainly a stack overflow resulting from the way factorialis written and/or called.2Name:2. Supp ose a C program includes this code, which includes a loop that is useless. Assume that x and yare valid pointers to legal strings (that end in ’\0’) .int f(char *x, char* y) {int i=0;for(; i < 10000000; ++i)strcmp(x,y);return 7;}In the 3 separate problems below, suppose you use gprof to profile this program. You must give adifferent answer for each problem.(a) 5pts The time samples from gprof show that the program s pends most of its time in strcmp,but removing the loop from f has no noticeable effect on performance. What is the most likelyexplanation?(b) 5pts The call counts from gprof show that strcmp is called much more than any other functionand 60% of the calls to strcmp come from f, but removing the loop from f has no noticeable effecton performance. What is the most likely explanation?(c) 3pts The time samples from gprof show that the program spends most of its time in strcmpand the call counts from gprof show that strcmp is called much more than any other functionand 60% of the calls to strcmp come from f, but removing the loop from f still has no noticeableeffect on performance. What is the most likely explanation?Solution:(a) Most of the calls to strcmp are from other sources. Perhaps f is never even called when theprogram runs.(b) Although strcmp is called a lot, it is not where the program spends most of its time. Perhaps afunction that is called relatively few times takes a long time to execute because it has long loops.(c) Some calls to strcmp take longer than others and the calls from f are relatively quick. Forexample, suppose the arguments to f are short (e.g., one-character long), but the other calls tostrcmp pass very long strings.3Name:3. Consider this type definition for trees of integers in C and 3 functions that allegedly deallo c ate thespace for a tree:#include <stdlib.h>struct Tree {int val;struct Tree * left;struct Tree * right;};void free_tree_1(struct Tree * t) {if(t == NULL)return;free(t);}void free_tree_2(struct Tree * t) {if(t == NULL)return;free(t);free_tree_2(t->left);free_tree_2(t->right);}void free_tree_3(struct Tree * t) {if(t == NULL)return;free_tree_3(t->left);free_tree_3(t->right);free(t);}(a) 8pts Explain which of the three functions is the best. Explain why the other two are not well-written.(b) 4pts Explain what assumption(s) the best function is implicitly making and how the function iswrong if the assumption(s) are violated.Solution:(a) The third function is best. The first creates space leaks if the tree’s children are not otherwisereachable. The second has dangling-pointer dereferences; technically you may not use t->leftor t->right after the object t p oints to is deallocated. The third function correctly frees thesubtrees and then frees the root no de.(b) In addition to assuming all the struct Tree * pointers point to live heap-allocated objects oftype struct Tree, the third function assumes the pointers actually form a tree. Put another way,it assumes that there is no sharing; all the pointers are unique. If two pointers in the alleged treepoint to the same struct Tree, then the function will attempt to deallocate the object twice,which is an error.4Name:4. Here are the contents of three files that together form a program:• a.c:void f(int* x, int* y) { *y = *x; }• a.h:#ifndef A_H#define A_Hvoid f(int*);#endif• b.c:#include <a.h>int main(int argc, char**argv) {int x;f(&x);return 0;}(a) 2pts Why is this program incorrect?(b) 4pts Will gcc -c a.c; gcc -c b.c; gcc a.o b.o create an executable a.out or will there becompiler errors? Explain.(c) 4pts To catch this program’s error, would it help to have a.c include a.h? Explain.(d) 4pts To catch this program’s error, would it help to use a Makefile that recompiles a.c and b.cwhenever a.h changes? Explain.Solution:(a) Because f expect two arguments, but main passes it only one.(b) It will create an executable. Each file is compiled separately and typechecks, but they makedifferent assumptions about how many arguments f takes. The linker will not catch this error forC code.(c) Yes, now compiling a.c will fail (or at least give a warning) because the definition for f does notmatch its earlier declaration.(d) No, rec ompiling a.c if a.h changes does not detect the error; compiling a.c will still succeed.5Name:5. Here are the contents of 4 files:• a.java: class A { static boolean f() { return true; } }• b.java:class B { public static void main(String[] args) {if(args.length < 3)A.f();} }• a.c: int f() { return 1; }• b.c:int f(); // declaration of function defined in another fileint main(int argc, char **argv) {if(argc < 3)f();return 0;}For each of the following
View Full Document
Unlocking...