1.   【流程图说明】
    下面的流程(如图1所示)用N-S盒图形式描述了在一棵二叉树排序中查找元素的过程，节点有3个成员：data, left和right。其查找的方法是：首先与树的根节点的元素值进行比较：若相等则找到，返回此结点的地址；若要查找的元素小于根节点的元素值，则指针指向此结点的左子树，继续查找；若要查找的元素大于根节点的元素值，则指针指向此结点的右子树，继续查找。直到指针为空，表示此树中不存在所要查找的元素。
  【算法说明】
  【流程图】
    将上题的排序二叉树中查找元素的过程用递归的方法实现。其中NODE是自定义类型：
     
    typedef struct node {
        int data;
        struct node * left;
        struct node * right;
    }NODE;
  【算法】
    NODE * SearchSortTree(NODE * tree, int e)
    {
        if(tree!=NULL)
        {
            if(tree-＞data＜e)
                  (4) 　;    //小于查找左子树
            else if(tree-＞data＜e)
                        ;    　//大于查找左子树
            else return tree;
        }
      return tree;
    }

1.     【说明】
    设M叉树采用列表法表示，即每棵子树对应一个列表，列表的结构为：子树根结点的值后跟用“()”括起来的各子树的列表(若有子树的话)，各子树的列表间用“，”分隔。例如，如下图所示的三叉树可用列表a(b(c,d),e,f(g,h,i))表示。
    本程序根据输入的列表生成一棵M叉树，并由M叉树再输出列表。
                         
    【函数】
    #include   
    #include   
    #define    M    3              /*三叉树*/
    typedef struct node{
        int val;
        struct node *subTree[M];
    }NODE;
    char buf[255], *str=buf;
    NODE *d=NULL;
    NODE *makeTree()    /*由列表生成M叉树*/
    {
        int k; NODE *s;
        s=        ;
        s-＞val=*str++;
        for(k=0;k＜M;k++)
            s-＞subTree[k]=NULL;
        if(*str=='(')
        {
            k=0;
            do{
                  str++;
                  s-＞subTree[k]=        ;
                  if(*str==')')
                  {
                      str++;
                      break;
                  }
                  k=k+1;
            }while(        );
        }
        return s;
    }
    void walkTree(NODE *t)      /*由M叉树输出列表*/
    {
        int i;
        if(t !=NULL)
        {
                    ;
            if(t-＞subTree[0]==NULL)
                    return;
            putchar('(');
            for(i=0;i＜M;i++)
            {
                        ;
                if(i !=M-1 && t-＞subTree[i+1]!=NULL)
                    putchar(',');
            }
            putchar(')');
        }
    }
    void main()
    {
        printf("Enter exp: ");
        scanf("%s",str);
        d=makeTree();
        walkTree(d);
        putchar('\n');
    }

  

(1)(NODE*)malloc(sizeof(NODE))
   (2)makeTree()
   (3)*str
   (4)putchar(t-＞val)
　 (5)walkTree(t-＞subTree[i])

[分析]
   本题考查在C语言中实现用列表表示M叉树。
   题目要求程序根据输入的列表生成一棵M叉树，并由M叉树再输出列表。题目中给出了列表与树的对应关系，从这种对应关系中我们可以看出，每个结点后紧跟的那层括号下结点的个数就是这个根结点的孩子个数，用列表表示得到的序列有点像树的先序遍历，因此，根据列表来生成M叉树时，应该是首先生成左子树，然后才依次往右的生成过程。下面来具体[分析]代码。
   第(1)空很明显是给变量s赋一个初值，从程序中可以知道，变量s是一个指向NODE型结点的指针变量，但程序中并没有给出这样的结点，那么此空应该是动态创建一个这样的结点。在C语言中，动态分配空间要用函数malloc()，因此，此空答案为(NODE*)malloc(sizeof(NODE))。
   第(2)空在循环体中，从程序中不难推断出此循环体的作用是由列表生成M叉树，此空是给s-＞subTree[k]这个指针数组赋值，这个数组中存放的是当前结点的孩子结点的指针，在树的生成过程中是根据列表来递归生成其对应的三叉树的，此空应该是递归调用生成结点的函数makeTree()。因此，此空答案为makeTree()。
   第(3)空是循环结束的判断条件，而这个循环的作用是根据列表来生成三叉树，只有列表的所有元素都被考虑了循环才结束。从程序中可以知道列表的元素存放在数组中，指针变量s廿指向这个数组，且在程序中对列表的操作都是通过指针变量str来实现的，因此，此空答案为*str。
   第(4)空在条件判断语句下面，此条件判断语句结果为真，说明当前取到的是结点，接下来应该把该结点的值写入列表中，从后面的程序我们很容易知道实现此功能的函数，因此，此空答案为putchar(t-＞val)。
   第(5)空在一个循环体下面，根据循环的条件，可以推断出这是对一个结点的所有孩子结点进行循环搜索。由M叉树生成列表可以说是由列表生成M叉树的逆过程，需要对树中的每个结点进行检索来生成列表，这里也要用到递归调用，而这个函数的当前检索的结点指针为t-＞subTree[i]。因此，此空答案为walkTree(t-＞subTree[i])。

 

1.   【说明】
    函数move(int*a，int n)用于整理数组a[]的前n个元素，使其中小于0的元素移到数组的前端，大于0的元素移到数组的后端，等于0的元素留在数表中间。
    令a[0]～a[low-1)小于0(初始为空)；a[low]-a[i-1]等于0(初始为空)；a[i]～a[high]还未考察，当前考察元素为a[i]。a[high+1]～a[n-1]大于0(初始为空)。
  【函数】
    move(int*a ,int n)
    {
        int i,low,high,t;
        low=i=0;high=n-1;
        while(        )
        if(a[i]＜0)
        {　　　　
            t=a[i];a[i]=a[low];a[low]=t;
                    ;i++;
        }
        else if(        )
        {    t=a[i];a[i]=a[high];a[high]=t;
                    ;
        }
        else        ;
    }

1.  [说明]
    函数encode()和decode()分别通过参数传递实现对字符串的变换和复原，返回值均为处理以后的字符串长度。变换函数encode()顺序考察已知字符串的字符，按以下规则逐组生成新字符串：
        若已知字符串的当前字符不是数字字符，则复制该字符于新字符串中；
        若已知字符串的当前字符是一个数字字符，且它之后没有后继字符，则简单地将它复制到新字符串中；
        若已知字符串的当前字符是一个数字字符，并且还有后继字符，设该数字值为n，则将其后继字符重复复制n+1次到新字符串中；
        以上述一次变换为一组，在不同组之间另插入一个下划线‘_’用于分隔。
    例如：encode()函数对字符中26a3t2的变换结果为666_a_tttt_2。
    函数decode()用于经函数encode()处理的字符中，即复制不连续相同的单个字符，而将一组连续相同的字符(不超过10个)变换成一个用于表示重复次数的数字符和一个重复出现的字符，并在复原过程中掠过变换函数为不同组之间添加的一个下划线字符。
    注：假定调用变换函数encode()时的原始字符串中不包含下划线字符。
[函数]
int encode(char *instr,char *outstr)
{    char *ip, *op,c;
    int k,n;
    ip=instr;
    op=outstr;
    while ( * ip) {
        if(*ip＞='0'&&*ip＜='9'&&*(ip+l)) {
            n=*ip-'0'+1;
            c=        ;
            for (k=0;k＜n;k++) *op++=c;
        }
        else *op++=*ip;
                ;
        ip++;
    }
    if (op＞outstr)         ;
    *op='\0';
            ;
}
int decode(char *instr,char *outstr)
{  char *ip,*op,c;
    int n;
    ip=instr; op=outstr;
    while ( *ip) {
        c=*ip;
        n=0;
        while( *ip==c&&n＜10) {        ; n++; }
        if(n＞1) *op+ + ='0'+n-1;
        * op++=c;
        if(*ip=='_') ip++;
    }
    *op='\0';
            ;
}

1.  【说明】
    已知对某载客车辆(Car)进行类建模，如图5-1所示，其中类Engine表示发动机引擎，类Wheel表示车轮，类Body表示车身，类Driver表示司机，类Passenger表示乘客。

【C++代码】
    const int        ＝7；          //定义最多载客数
    const int MAX WHEELS＝5；    //定义最多轮胎数

    class Body{                //此处代码省略  }；    //车身类
    class Passenger{          //此处代码省略  }；    //乘客类
    class Wheel{              //此处代码省略  }；    //车轮类
    class Driver{      //司机类
    public：
      string name；//表示第几路公交车司机
      Driver(string driverName)：name(        ){}///构造函数
    }；
    class Engine{//引擎类
    public：
      string engineNo；//引擎编号
      Engine(string engineNo){        -＞engineNo＝engineNo；}//构造函数
    }；
    class Car{//汽车类
    protected：
      Engine * engine；    Driver * driver；    Body body；
      Wheel * wheels [MAX_WHEELS]；Passenger * passengers [MAX_PASSENGERS]；
    public：
      Car(Driver *driver){  //构造函数
        this-＞driver＝driver；
        engine＝new Engine("TX6536型号引擎")；
        for  (int index＝0；  index＜MAX WHEELS；index++){
            wheels[index]＝new Wheel()；
        }
        for(int index＝0；index＜MAX_PASSENGERS；index++){
            passengers[index]＝NULL；
        }
      }
      virtual ～Car(){//析构函数
        for( int index＝0；index＜MAX_WHEELS；index++)
          delete wheels[index]；
        delete         ；
      }
      int getPassengerNumber(){//获取车上乘客数量
          //此处代码省略
      }
      void getOnPassenger(Passenger * aPassenger){//乘客上车
          //此处代码省略
      }
      void run(){  //开车
          if(driver＝＝NULL){cout＜＜"司机尚未上车!"；  return；  }
          //此处代码省略
      }
    }；
    void main(){
      Driver driver("第五路公交车司机")；
      Car car(        )；
      Passenger passengers[MAX_PASSENGERS]；
      for(int index＝0；index＜MAX PASSENGERS；index ++)  //乘客上车处理
          car．getOnPassenger(&passengers [index])；
      car．run()；
    }