本程序输入列表,生成一棵 M 叉树,并由 M 叉树输出列表。假定输入无错误。

[程序4]

#include〈stdio.h〉

#include〈stdlib.h〉

#define M 3

typedef struct node{ char val;

        struct node *subTree[M];

        } NODE;

char buf[255] ,*str = buf

NODE *d = NULL

NODE *mackTree( ) /*由列表生成M叉树*/

{ int k; NODE *s ;

    s = __(1)__

    s -> val = *str++ ;

    for ( k = 0 ; k < M ; k++ ) s-> subTree[k] = NULL ;

    if(*str='( '){

        k = 0;

        do { str++;

            s -> subTree[k] = __(2)__ ;

            if ( *str == ')' ) { str++; break ; }

            k = k+l ;

        } while ( __(3)__ );

    }

    return s ;

}

void walkTree( NODE *t ) /*由 M 叉树输出列表*/

{ int i ;

    if t != NULL ) {

        __(4)__

        if ( t -> subTree[0] == NULL ) return ;

        putchar ( '( ' ) ;

        for ( i = 0 ; i < m ; i++) {

            __(5)__ 

           if ( i! = M - l && t -> subTree[i+l] != NULL )

                putchar ( ', ' ) ;

        }

        putchar ( ') ' ) ;

    }

}

void main( )

{ printf( "Enter exp:" ) ;

    scanf( "%S" , str ) ;

    d = makeTree() ;

    walkTree( d ) ; putchar( '\n') ;

}

试题五

阅读下列程序说明和C代码,将应填入__(n)__处的字句写在答题纸的对应栏内。

[程序5说明]

著名的四色定理指出任何平面区域图均可用四种颜色着色,使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过四种颜色的着色方案。程序中用 1～4 表示四种颜色。要着色的 N 个区域用 0～N一1编号,区域相邻关系用 adj[][] 矩阵表示,矩阵的 i 行 j 列的元素为 1 ,表示区域 i 与区域 j 相邻；矩阵的 i 行 j 列的元素为 0 ,表示区域 i 与区域 j 不相邻。数组 color[] 用来存储着色结果, color[i] 的值为区域 i 所着颜色。

【程序5】

#include〈stdio.h〉

#define  N 10

void output(int color[])/*输出一种着色方案*/

{ int i ;

    for ( i = 0 ; i < N ; i++ ) 

        printf( "%4d" , color[i] ) ;

    printf( "\n" ) ;

}

int back( int *ip ,int color[] ) /*