Week 10 Tutorial — Quacks, Recursion, Binary Search Trees

  1. The implementation of a quack using a linked list uses the data structure:

    // from quackLL.c
struct _node {
   int data;
   struct _node *next;
};

    The implementation of a quack using an array uses the data structure: 

    // from quackAR.c
struct _node {
   int array[HEIGHT];
   int top;
};

    We see in both cases that the data that can be stored must be integers, so only(?) integers can be pushed and popped. How can we push and pop characters using casting?

  2. A stack can be used to check whether opening and closing brackets: '(' and ')', '[' and ']', '{' and '}', are balanced in given text. For example, the following are all balanced:

    (a+b)*c

    (a[i]+b[j])*c[k]

    void f(char a[], int n) {int i; for(i=0;i<n;i++) a[i] = (a[i]*a[i]*a[i])*(i+1); return;}

    ([{}]) ([{}]) ([{}]) ([{}]) ([{}]) ([{}])

    ((())){{[]}{()()()}}(()){{}}

    Examples of text that is not balanced:

    a(a+b*c

    a(a+b]*c

    a[i]+b[j]*c[k])

    ((]())

    ((())){{[]}{(()()}}(()){{}}

    Sketch an algorithm that uses a stack to determine whether given text contained balanced brackets. Consider in particular the following cases, and show how your algorithm works for these:

    1. mismatched kind of bracket: e.g. (]
    2. missing opening bracket: e.g. ())
    3. missing closing bracket: e.g. (()

  3. A function to free a linked list is:

    void freeList(NodeT *head) {
   NodeT *cur = head;
   while (cur != NULL) {
      NodeT *tmp;
      tmp = cur->next;
      printf("free node %d\n", cur->data);
      free(cur);
      cur = tmp;
   }
}

    1. If a linked list consists of the nodes: 
      1 --> 2 --> 3 --> 4
      what will be the result of calling freeList with this list?
    2. Rewrite this as a recursive function, ensuring the nodes are freed in the same order.
    3. Change the recursive function to free nodes in the opposite direction.
    4. What is the essential difference between the two?

  4. Assume the following data structure that defines a binary tree:

    typedef struct node *Tree;
struct node {
   int data;
   Tree left;
   Tree right;
};

    Traversing a tree is often done in one of three standard orders: prefix, infix or postfix
    1. Which of these is the only suitable order to free all elements in a tree?
    2. Write a function with signature void freeTree(Tree t) that will free all memory associated with a tree t

  5. Design an algorithm to recursively sum all elements of a BST.