Week 13 Tutorial — Revision

The tutorial this week reviews some of the contents of the whole course. It illustrates the type of questions that might be asked in the Written Part of the final exam.

  1. (Data types) On a CSE workstation, what is the value of sizeof(x) when x is defined as:

  2. (Binary search trees) Consider the following pretty-printed BST:

    		1
	2
3
		4
			5
	6
		7

    Show the tree after the execution of each of the following operations: 

    delete(3); insert(3); delete(2);

    After which of these operation is the BST balanced?

  3. (C execution model, dynamic memory allocation) Consider the following program:

    // reads lines from a file and reverses them 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

int main(void) {
   FILE *file;
   char line[BUFSIZ], *reverse;

   file = fopen("textfile", "r");
   assert(file != NULL);
   while (fgets(line, BUFSIZ, file) != NULL) {
      reverse = (char *)malloc(sizeof(char)*strlen(line)+1);
      assert(reverse != NULL);

      char *i, *j = reverse;
      for (i = &line[strlen(line)]-1; i >= line; i--) {
         if (*i != '\n') {
            *j++ = *i;
         }
      }
      *j = '\0';
      printf("%s\n", reverse);
   }
   fclose(file);
   return EXIT_SUCCESS;
}

    1. Assume the following:

      • textfile  contains just one line 
        maps
      • the address of the object returned by malloc() is 0xff0000

      Consider the state of the program just before the fclose() statement. What is the value of each of the following expressions in this state:

      1. reverse[3]
      2. &reverse[3]
      3. j

    2. The program has memory leaks. Explain where this occurs and how it can be fixed.

  4. (Random numbers) Consider the following program:

    // simulates the roll of a roulette wheel as random number between 0 and 36
// accepts seed for random number generator as command line argument
#include <stdio.h>
#include <stdlib.h>

#define ROUNDS 10

int main(int argc, char **argv) {
   int val;
   if (argc==2 || sscanf(argv[1], "%d", &val)) {
      srandom(val);
      int i;
      for (i=0; i<ROUNDS; i++) {
         int toss = random()%36;                // toss = 0 ... 36
         printf("Winning number: %2d\n", toss);
      }
   }
   return EXIT_SUCCESS;
}

    1. The program has two bugs. Briefly describe their nature and how they can be fixed.

    2. What is the purpose of the instruction srandom(val)?

    3. Modify the program to simulate a roulette wheel with a double zero (an additonal pocket (outcome) displayed as "00").