New version page

UW CSE 303 - Study Notes

Documents in this Course

9 pages

10 pages

10 pages

13 pages

12 pages

19 pages

13 pages

11 pages

18 pages

13 pages

14 pages

9 pages

6 pages

20 pages

7 pages

4 pages

2 pages

15 pages

3 pages

3 pages

15 pages

17 pages

8 pages

4 pages

2 pages

15 pages

8 pages

10 pages

4 pages

2 pages

13 pages

13 pages

11 pages

8 pages

8 pages

17 pages

13 pages

7 pages

2 pages

2 pages

17 pages

6 pages

5 pages

18 pages

18 pages

8 pages

8 pages

12 pages

14 pages

14 pages

8 pages

8 pages

18 pages

18 pages

2 pages

3 pages

15 pages

11 pages

15 pages

3 pages

6 pages

2 pages

2 pages

20 pages

3 pages

18 pages

4 pages

26 pages

8 pages

11 pages

7 pages

18 pages

22 pages

11 pages

2 pages

15 pages

17 pages

13 pages

13 pages

15 pages

15 pages

3 pages

19 pages

11 pages

18 pages

13 pages

11 pages

3 pages

4 pages

5 pages

9 pages

4 pages

22 pages

10 pages

15 pages

11 pages

18 pages

2 pages

5 pages

33 pages

11 pages

24 pages

2 pages

19 pages

22 pages

2 pages

3 pages

12 pages

2 pages

20 pages

3 pages

15 pages

12 pages

12 pages

7 pages

18 pages

12 pages

33 pages

Load more
Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

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
Download Study Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Unlocking...
Sign Up

Join to view Study Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?