1. 10 pts

=>	stack: *
	output: CD
	
=>	stack: -
	output: CD*
	
=>	stack: -(
	output: CD*
	
=>	stack: -(+
	output: CD*AE
	
=>	stack: -(+*
	output: CD*AEF
	
=>	stack: -
	output: CD*AEF*+
	
=>	stack: -*
	output: CD*AEF*+H
	
=>	stack: NULL
	output: CD*AEF*+H*-

ANS:  CD*AEF*+H*-


2. 10 pts

listpointer reversal (listpointer p)
{
     listpointer  ptr, temp;
     
if( p )
     {
       ptr = p->link;
       p->link = NULL;
       while( ptr )
       {
          temp = ptr->link;
          ptr->link = p;
          p = ptr;
          ptr = temp;           
       }
     } 
     return p;   
}


3. 10 pts 


void levelOrder (treenode *root)
{
  int front=rear=0;
  treenode queue[MAX_QUEUE_SIZE];
  if (!root) return;  //empty tree
  addq(root);
  for(;;)
  {
    root=deleteq();
    if (root)
    {
      printf("%d", root->data);
      if (root->lchild)  //root has left child
        addq(root->lchild);
      if (root->rchild)  //root has right child
        addq(root->rchild);
    }
    else break;  //root is NULL
  }
}

4. 10分

int total(treenode *root)
{
  if(root->lchild==NULL&& root->rchild==NULL)
  {
     return 0;
  }
  if( root->lchild==NULL)
  {
     return total(root->rchild)+1;
  }
  else if( root->rchild==NULL)
  {
     return total(root->lchild);
  }
  else
     return total(root->rchild)+total(root->lchild);
}

5.
a. 


                A
               /  \
              B   I
             /   / \
            G   C   F
               / \
              D   E
                   \
                    H

b.

                A
               /  \
              B    I
             /    / \
            G    C   F
                / \
               D   E
                  /  
                 H



6. 
(a) 從array最左邊往右開始放stack elements(top element先放)，
    再從array最右邊往左放置另一stack elements(top element先放)
(b) n-1
(c) n0 = n2+1 
(d) 上界[log(n)+1] 或者 下界[log(n)]+1
(e) n 
(f)-a
insert: O(1); delete: O(n)
(f)-b
insert: O(n); delete: O(1)
(f)-c
insert: O(log(n)); delete: O(log(n))

7.
(a) 2pt

         58
        /  \
       21  33
      /
     14 

(b) 3pt

        33
       /  \
      21  14

(c) 2pt

        61
       /  \
     59    43
    /  \   /  \
   33  32 14   41
  /
 21

(d) 3pt

        59
       /  \
     33    43
    /  \   /  \ 
   21  32 14  41


8.
(a)				
                10
               /  \
              7   20
               \  / 
               9 15
					


(b)				
                10
               /  \
              7   20
             / \  / \
            3  9 15 25
             \   /
             5  14
              \
              6
			     	

(c)				
                10
               /  \
              7   20
             / \  / \
            3  9 15 25
             \   /
             6  14
			     

(d)
                10
               /  \
              6   20
             / \  / \
            3  9 15 25
                 /
                14

		       
(e)
                14
               /  \
              6   20
             / \  / \
            3  9 15 25




9.

BOTTOM UP:

void skew(treenode *root, int *longest, int *shortest)
{
   int llong, lshort, rlong, rshort;

   if (root == NULL) {
       *longest = 0;
       *shortest = 0;
       return;
   }

   skew (root->lchild, &llong, &lshort);
   skew (root->rchild, &rlong, &rshort);  

   if ( llong >= rlong )
      *longest = llong;
   else 
      *longest = rlong;

   if ( lshort < rshort )
      *shortest = lshort;
   else 
      *shortest = rshort;

   *longest = *longest + root->delay;
   *shortest = *shortest + root->delay;

}

TOP DOWN:

void skew(treenode *root, int *longest, int *shortest)
{
    static int accumulative_delay = 0;

    accumulative_delay += root->delay;

    if(root->lchild == NULL && root->rchild == NULL)
    {
        if(*longest < accumulative_delay)
            *longest = accumulative_delay;
        if(*shortest > accumulative_delay)
            *shortest = accumulative_delay;
    }
    else
    {
        if(root->lchild != NULL)
            skew(root->lchild, longest, shortest);
        if(root->rchild != NULL)
            skew(root->rchild, longest, shortest);
    }

    accumulative_delay -= root->delay;

    return;
}