1. General C Programming:

A typical main program in C starts out with the declaration

void main(int argc, char *argv[])

a) In general, what determines the value of argc when the program runs(hint: it’s one greater than …)? {3}

The value of argc is the number of elements in argv (array of pointers to program name and arguments on command line), which is one greater than the number of parameters to the command (after shell substitutions). For example, the command

myprog a b c

would result in argc == 4.

b) Assume that the current working directory contains the following files:

monarchs.dat myprog myprog.c sealions.dat
seals.dat slugs.dat slugs.new walruses.dat

List the strings pointed to by argv when the following command is executed: {6}

myprog se*.dat s.lst

"myprog", "sealions.dat", "seals.dat", "s.lst"

The program name is always stored in argv[0]. The wildcard se*.lst expands to all files starting with "se" and ending with ".lst" (sealions.dat and seals.dat). Notice that non-wildcard parameters appear even if they don't match an existing file name, so s.lst will appear in argv (it might be an output file name, for instance). Common errors were omission of "myprog" and omission of "s.lst".

c) The following statement later in the program should call the Error function if the value of pointer variable point is NULL, but it never calls Error, even when point is NULL. Correct the statement so that it works properly: {3}

if ( point == NULL ) Error( "Pointer value is NULL" );

The statement as originally written sets point to the value NULL, rather than comparing to NULL. Since the value of the assignment is NULL which is 0, the condition is always false, and so Error is never called. This common programing error can be corrected by changing the assignment (=) to a comparison (==).

d) The C statement below is which one of the following (circle the correct answer): {3}
i) Declaration of a function which returns a pointer, or ii) Declaration of a pointer to a function

int (*myfunc)(double avg);

See the textbook section on list traversal, or the lecture notes, for more information.

2. Program Development:

a) Name two types of scaffolding commonly used in program development: {6}

Scaffolding is code inserted into a program to help with debugging (see textbook, pp. 24-26). The main types are stubs, drivers, and tracing (print statements).

b) What is the main feature of Glass Box testing which makes it more appropriate for testing individual functions or small sets of functions rather than large programs? {6}

Glass Box testing (pp. 28-29) tests all paths through a program. This is prohibitively expensive for large programs, but possible for smaller collections of code.

c) Give an example of some conceptual type and the corresponding implementation type for a simple (non-structured) Abstract Data Type (one word/phrase each): {3}

concept: examples: integer, real number

implementation: corresponding implementation types: int, float

One common error here was to not notice that the question asked for a non-structured ADT (see section 4.8).

d) When you’ve made changes to source and header files of a large software system, what software tool can you use to make sure that all of (and only) the appropriate source files get recompiled? {3}

Acceptable answers: gmake, make, GNUmakefile, Makefile. A common error was "gcc"; although gcc compiles the code, it doesn't do any checking to make sure you recompile all the routines affected by a change.

3. Stack Operations

You are to implement a stack whose entries contains integer values. The operation Push(v) pushes the integer value of v onto the stack. Pop(&x) stores the value from the top of the stack into integer variable x and pops the stack. On the grid below, fill in the state of the stack after each operation shown. For each stack entry, show the numerical value on the stack, not a variable name. Leave unused stack entries blank. {12}

								3
							3	3	3
		2		3		2	2	2	2
	9	9	9	9	9	9	9	9	9
5	5	5	5	5	5	5	5	5	5
(start)	Push(9)	Push(2)	Pop(&a)	Push(3)	Pop(&b)	Push(a)	Push(b)	Push(b)	Pop(&c)


Some students answers put the "top" of the stack at the bottom of the table, and vice versa. This was given full credit as long as the operations were correctly performed on the stack using that representation. In some cases the stack operations were confused with queue operations; see section 3.1 and the class notes for a review of stack operations. Remember that all stack operations are done from one end (the top), while a queue has a separate front and back (head and tail). Another common error was to enter variable names in the stack entries; the question explicitly asks for numeric values (again, see the examples done in class and in the textbook).

Dynamic Storage

a) Write the C declaration for a pointer variable named intarray which points to a dynamic array of elements of type int: {3}

int *intarray;

Note that the declaration "int intarray[]" is not a generally valid pointer variable; it's used only in function declarations.

b) Write an executable C statement to allocate storage for this array; numflt is an integer variable containing the number of elements to be allocated: {3}

Here are several valid ways to do it:

intarray = malloc( numflt * sizeof(int));
intarray = calloc( numflt, sizeof(int) );
intarray = malloc( numflt * sizeof(*intarray) );

c) While running, a C program has two sources of storage for non-permanent variables, the program stack and the heap. Describes briefly how a program can get memory for its use from each of these two areas: {6}

Heap: Explicit allocation through malloc or calloc

Stack: Declaration of local variables in functions (allocated automatically), including function parameters passed by value.

4. Complexity

For each of the following algorithms studied in class, what is the order of complexity of the number of operations required? Give values in terms of N, such as: constant, O(N), O(N²), O(N³), O(2^N), O(N!), etc.

a) Linear search for a value in an array with N entries {3} O(N), you compare N items

b) Computing the factorial of N using a simple loop to multiply the values 1 to N {3} O(N), you multiply N number together.

c) Generating all permutations of the integers from 1 to N {3} O(N!) (see section 5.6)

d) Adding an entry to the tail of a linked list of N items, if you only have a pointer to the head {3} O(N), you must traverse the entire list to add an entry.

e) Adding an entry to the tail of a linked list of N items, if you have pointers to the head and tail {3} O(1), constant, the tail pointer takes you directly to the location to add the new entry.

 

5. Linked and Contiguous Representations

1. Serve
2. Serve
3. Append('d')
4. Serve
5. Append('e')
6. Append('f')
7. Serve

Show the intermediate states of the queue by (lightly) crossing out entries as they are served, and entering appended values in the appropriate cells (if a value is both appended and then served, write it in when appended and then cross it out when served). Enter the final state of the queue indices and count in the box at right. {15}

Most problems with this question seem to be due to forgetting how a circular queue operates (it wraps around the end of the array). The queue variables (front, rear, count) contain integers, not queue entry values. The actual queue entries are stored in the queue entry array. See sec. 4.2 and the lecture notes for a review of circular queues.

 CMPS012B Spring '97 pages maintained by Mike Goss <goss@cse.ucsc.edu>

This page last updated 05/18/97