Week 11 Tutorial — BSTs, Random Numbers

  1. For each of the following trees, state whether it could be a Binary Search Tree or not.

    a)     f           b)     f           c)      96
      /  \               /  \               /    \
     c    h             c    e             54     27
    /\   /             /\   /             / \    /
   a  e g             a  b d             13 53  26

d)     q           e)    b            f)     b
      /                 /                   / \
     m                 a                   a   b
    /\
   f  a

  2. Insert the values 10 20 5 30 15 28 24 26 in the given order into a Binary Search Tree.

    1. What is the height of the resulting BST?

    2. Show each of the trees after:
      • deleting node 5
      • deleting node 30
      • deleting node 20
      What is the height of the final BST?

  3. A program that simulates the tosses of a coin is as follows:

    #define NTOSSES 20
srandom(time(NULL));
int count = 0;
int i;
for (i=0; i<NTOSSES; i++) {
   int toss;
   toss = random()%2;     // toss = 0 or 1
   if (toss == 0) {
      putchar('H');
      count++;
   } else {
      putchar('T');
   }
}
putchar('\n');
printf("%d heads, %d tails\n", count, NTOSSES-count);

    Sample output is:

    HHTTTTHHTTTHHTHHHHHH
12 heads, 8 tails

    1. What could be the output if instead you were simulating the rolling of dice?
    2. What would an analagous program to simulate the repeated rolling of a die look like?

  4. If you were given a string, say "hippopotamus", and you had to select a random letter, how would you do this?

  5. If you have to pick a random number between 2 numbers, say i and j (inclusive), how would you do this? (Assume i<j.)

  6. Design an algorithm to reverse a linked list.