THE UNIVERSITY OF WESTERN ONTARIO
Computer Science 211a Final Examination – Fall 2003
THE UNIVERSITY OF WESTERN ONTARIO
LONDON CANADA
COMPUTER SCIENCE 211a
FINAL EXAMINATION
6 DECEMBER 2003
3 HOURS
Closed book.
No calculators or
electronic devices of
any kind.
A sheet of reference
notes is provided.
135 marks in total
Part I — Multiple choice, True/False – Choose the best answer from the choices given. Circle your answer on the paper, and fill in the answer on the Scantron form.
1. [1 mark] You can forward your future email by creating a .forward file in your home directory of your unix account.
a) True
b) False
2. [1 mark] You may login your unix account remotely.
a) True
b) False
3. [1 mark] linux is an operating system that is very similar to the unix operating system.
a) True
b) False
4. [1 mark] grep is a unix utility.
a) True
b) False
5. [1 mark] cd $HOME will change to a subdirectory $HOME of your current directory.
a) True
b) False
6. [1 mark] It is possible to use a question mark in a unix file name.
a) True
b) False
7. [1 mark] A unix hard link is a pointer to another file, and deleting the original file will invalidate the hard link.
a) True
b) False
8. [1 mark] You have to compile a shell script before you can run it.
a) True
b) False
9. [1 mark] gdb is a database management system that manages your C source codes.
a) True
b) False
10. [2 marks] Suppose a file filex has permission -rw—xr–. Which of the following statements is correct?
a) The group user cannot read and write filex.
b) The owner can read and write filex.
c) The accessibility to filex also depends on the permission of the directory where the file is located.
d) All users can see the file name by using the ls command.
11. [1 mark] What does the command ls */* do?
a) List all the files in current working directory.
b) List all files whose names contain a / symbol.
c) List all the files in all the subdirectories of the current working directory.
d) List all the files described in both a) and c).
12. [1 mark] The following is a portion of a program:
{
int x=3;
f(&x);
printf(“%d”, x);
}
Assume that f() is a well-behaved function, What will be printed out by the printf statement?
a) 3
b) x
c) the return value of the function call f(&x)
d) %d
e) the answer is unknown because the function call may change the value of x.
13. [1 mark] Which of the following is not a correct prototype of a C function?
a) int max(int *x, int *y);
b) int max(int x, int y);
c) void max();
d) int max(int &x, int &y);
14. [1 mark] The following is a portion of a program:
{
int x = 3;
x = f(&x);
printf(“%d”, x);
}
Assume that f() is a well-behaved function, What will be printed out by the printf statement?
a) 3
b) x
c) the return value of the function call f(&x)
d) %d
e) the answer is unknown because the function call may change the value of x.
15. [2 marks] The following is a portion of a C program:
{
int **z, *y, x=5;
z = &y;
y = &x;
(*z)++;
(*y)++;
printf(“%d”, x);
}
What will be printed out by the printf statement?
a) 5
b) 6
c) 0
d) The result is not predictable.
e) %d
16. [1 mark] The following is a portion of a C program:
{
char a[] = “unix&c”;
char *p = a;
p = &p[3];
printf(“%c”, *(p+1));
}
What will be printed by printf?
a) n
b) i
c) x
d) &
e) c
17. [2 marks] The following is a portion of a C program:
struct book{
float price;
char title[100];
};
int main(){
struct book x, y;
x.price = 3.5;
strcpy(x.title,“Unix Handbook”);
y = x;
puts(y.title);
return 0;
}
What is the output of the puts statement?
a) Unix Handbook.
b) Unix Handbook followed by very many whitespace characters.
c) The program is wrong because the \0 is missing at the end of the string “Unix Handbook”
d) The program is wrong because y.title is not initialized.
18. [2 marks] The following is a portion of a C program:
int main(){
int x,y;
x=0; y=3;
printf(“%d”, ((x>y)?(x++):(y++)) );
}
What will be printed out?
a) 1
b) 2
c) 3
d) 4
e) There is a parenthesis missing at the line of the printf statement.
19. [2 marks] The following is a portion of a C program:
{
int x,y,count=0;
for(x=0,y=5; (x++)<=(--y); count++);
printf(“%d”, count);
}
What is the output of the printf statement?
a) 1
b) 2
c) 3
d) 4
e) None of the above
20. [2 marks] The following is a portion of a C program:
struct book{
char * title;
};
int main(){
struct book ary[2];
ary[0].title = (char *) malloc(100);
strcpy(ary[0].title, “unix&c”);
*(ary+1) = *ary;
ary[1].title[4] = ‘\0’;
puts(ary[0].title);
}
What will be printed out?
a) uni
b) unix
c) unix&c
d) ary[1].title[4]=’\0’ will create a problem because we did not allocate memory for ary[1].title.
21. [2 marks] The following is a portion of a C program:
{
short x = -1;
for (;x--;);
printf(“%d”, x);
}
What will be printed?
a) 0
b) -1
c) -2
d) The for loop is an infinite loop and nothing is going to be printed.
e) The integer value overflow error message will be printed.
22. [2 marks] The following is a portion of a C program:
{
int x, count=0;
for(x=0; x<4; x++){
count += (x%2)?1:x;
}
printf(“%d”, count);
}
What is the output of the printf statement?
a) 6
b) 5
c) 4
d) 3
e) 2
23. [2 marks] The following is a portion of a C program:
{
int ary[5];
char *p, *q;
p = (char*) (&ary[1]);
q = (char*) (&ary[3]);
printf (“%d”, q-p);
}
What is the output?
a) Program is wrong because you cannot point a char * pointer to an int array element.
b) Program is wrong because you cannot subtract a pointer from another.
c) Unpredictable because ary is not initialized.
d) The value depends on sizeof(int) for the computer platform being used.
24. [1 mark] A Bourne shell script can be invoked with at most 9 positional parameters.
a) True
b) False
25. [1 mark] The shell script variable $# has its value decreased by 1 each time the shell script program executes the shift command.
a) True
b) False
26. [1 mark] The shell script variable $* holds a list of all the files in the current working directory.
a) True
b) False
27. [1 mark] All variables inside a shell script program are stored as strings.
a) True
b) False
28. [1 mark] A colon (“:”) on a line by itself is a unix command that does nothing.
a) True
b) False
29. [2 marks] The following Bourne shell script will fail to run properly because of a syntax error:
#!/bin/sh
word=””
# word is the empty string
if test –z $word
then
echo “Empty string”
else
echo “Non-empty string”
fi
a) True
b) False
Part II – Put your answers in the space provided on the question paper.
30. [20 marks] Shell commands: Provide shell command lines to perform the following tasks. You are allowed to use pipelines to link several commands together.
a) [1 mark] Print the current working directory.
Answer: .
b) [2 marks] Copy a file /home/bma/filex to the current working directory
Answer: .
c) [2 marks] Change to your home directory
Answer: .
d) [2 marks] Print all the lines in filex that contain the keyword 1234.
Answer: .
e) [2 marks] Compile all the .c files in your current directory, but do not generate the executable file.
Answer: .
f) [3 marks] In sh, set the value of variable x to be the name of the current system. (Hint: You may need command hostname.)
Answer: .
g) [1 mark] Make a module specified at the tag debug in the makefile in your current directory.
Answer: .
h) [3 marks] Remove a subdirectory of the current working directory and all the files in it. The subdirectory’s name is junk. And you are required to run the command in the background.
Answer: .
i) [4 marks] Write only the second line of filex to filey.
Answer: .
31. [10 marks] revstr is supposed to be a function that reverses a null character ended string that is stored in a char array. The parameter str points to the char array that stores the string. The function will change the content of the char array to reverse the string. The return value of the function is a pointer that is equal to the parameter str. The main function calls revstr and then prints the reversed string to the standardoutput.
However, there are many syntax errors and bugs that may cause runtime errors and/or make the program perform differently than intended. Try to fix all of the errors by writing the correct statements in the corresponding lines at the right. Do not fix anything that is correct, even if it is ugly coding.
#include
__________________________________________
#include
__________________________________________
char * revstr(char * str){
__________________________________________
int n, len;
__________________________________________
char ch;
__________________________________________
len = strlen(&str[0]);
__________________________________________
for ( n=0; n
puts(“Invalid Choice”);
}
}
return _________________;
}
b) [7 marks] Finish the program by filling in the blanks. The program reads all integers provided as command line parameters, sums them up, and print out the sum value. (Hint: argv[0] is the program name and should be excluded from the integer list.)
#include ____________________________
#include ____________________________
int main(int argc, char * argv[]){
int n, x, sum;
for (__________________________________________________){
x = atoi(____________________________);
sum = ____________________________;
}
printf (____________________________);
return 0;
}
c) [9 marks] Write a function that finds the second largest int value in an array. The return value should be a pointer to that int element. The array contains size elements, where size no less than 2.
int * secondLargest( int * ary, int size ){
33. [27 marks] This question makes use of the LinkedList ADT used with Assignment 5. the function prototypes for LinkedList are included on the sheet of reference notes handed out with the exam.
a) [6 marks] Recall that the function initializeList() requires that a LinkedList actually exist in order for it to be initialized. Write a new function of type void, called createList, that actually allocates a new LinkedList dynamically and initializes it to the empty list. The new list must be returned to the calling module through the function’s parameter list. (You must supply the parameter list.)
void createList ( ) {
b) [4 marks] Write a function called compareList that compares the two LinkedLists pointed to by parameters a and b, and that returns zero if the two lists are of the same size, a negative value if a is shorter than b, and a value greater than 0 if a is longer than b.
int compareList (LinkedList *a, LinkedList *b) {
c) [3 marks] Suppose that a C program contains the declaration
LinkedList arr[2000];
Show how to use the qsort() function from stdlib.h in order to sort the elements of arr by their lengths. Your solution may use your function from part b).
d) [4 marks] Suppose that the elements in a binary tree are LinkedLists. Provide a C typedef for a type TreeNode that can be used to build such a binary tree.
e) [10 marks] Suppose that a binary search tree ADT uses your TreeNodes from part d) in order to build trees. Complete the function addToTree, whose job is to insert an element into a binary search tree. (The function header for addToTree is given below.) The basic algorithm for inserting into a binary search tree is:
If the tree t is empty
Then build a new node containing LinkedList ll and return a reference to
this node
Else
If ll is “smaller” than the LinkedList inside t
Then insert ll into the left subtree of t recursively
Else insert ll into the right subtree of t recursively
Return a reference to the tree root
You may use your function from part b) in your solution.
TreeNode * addToTree( TreeNode *t, LinkedList *ll ) {
34. [18 marks]
a) [4 marks] Describe in words what the following Bourne shell script does:
#!/bin/sh
for k in *
do
if [ -f $k ]
then
n=”`echo $k | grep the `”
if [ -n “$n” ]
then
echo $k
fi
fi
done
b) [4 marks] Describe in words what the following Bourne shell script does:
for k in $*
do
if grep $k the > /dev/null
then
echo $k
fi
done
c) [10 marks] Write a Bourne shell script called calculate that accepts a list of parameters that form an arithmetic expression, and that computes an prints the value of that expression. The normal algebraic rules do not apply: operations are performed in the order they occur from left to right in the expression. For example:
calculate 3 + 7 \* 4
yields the result 40
calculate 6 – 2 \* 11 \/ 5 + 1
yields the result 9
The list of parameters can be arbitrarily long. Assume that there are no errors in the parameter list.
[Rough work only – This page will not be marked]
NAME: _______________________________________�
STUDENT NUMBER: ___________________________
Question
Part I. ________
Part II
30. ________
31. ________
32. ________
33. ________
34. ________
TOTAL
_________
PAGE
1