printf("Continue or Not?<Y/N>?");
        ch = getchar();
        getchar();
        if(ch=='n' || ch == 'N')
            flag = 0;
    }
}

（7）试设计一个算法解决地图着色判断问题。设一地图有n个区域（例如省）。用不多于4种
颜色对这些区域进行着色，着色应满足的要求是相邻的区域具有不同的颜色。你的算法以一
种着色方案（即哪一个区域着什么颜色）为输入，算法对该着色方案进行考察，若满足着色
要求，则输出true,否则输出false。（本题20分）
①用C语言描述你为解决问题而设计的数据结构（逻辑结构，存储结构）。数据结构的设计
应考虑对问题的清楚描述和算法的效率；
②用C语言写出你的算法。算法应简洁、高效。对算法中的参数、变量、语句做必要的注释，
以增加可读性；
③简单分析你的算法的空间开销和时间开销。

参考解法：
//    _ _ _ _ _ _
//   |_A_|_B_|_C_|
//   |_D_|_E_|_F_|
//   |_G_|_H_|_I_|
//<1>分别用1,2,3...,9表示A、B、C...I九个区域的编码
//<2>为了保证程序中数据的索引号与逻辑的索引号相同，N = 9 + 1，即N为区域个数加1
//<3>现在找任意两个区域之间的邻接关系relation[N][N]，如果两个数区域相邻，则用1表示，否则用0表示
//relation[i][j]的值表示i区域和j区域是否相邻，如果值为1，表示相邻；若为0，表示不相邻。
//<4>同时建立数组a[N]用来存储N个区域分别使用的颜色索引号。
//<5>MapColor(int a[],int n)函数用来存储第n个区域的颜色：先检验前n－1个区域，查看哪些区域与第n个区域
//相邻，则第n个区域不能使用与其相邻区域的颜色，完成第n个区域后，再对第n+1个区域进行操作。
//<6>print()函数用于将起色方案打印输出，并记录总共方案数目。其中的打印格式应根据具体情况
//以不同格式打印输出。
//  |_A_|_B_|_C_|_D_|_E_|_F_|_G_|_H_|_I_|
//A |_0_|_1_|_0_|_1_|_1_|_0_|_0_|_0_|_0_|
//B |_1_|_0_|_1_|_1_|_1_|_1_|_0_|_0_|_0_|
//C |_0_|_1_|_0_|_0_|_1_|_1_|_0_|_0_|_0_|
//D |_1_|_1_|_0_|_0_|_1_|_0_|_1_|_1_|_0_|
//E |_1_|_1_|_1_|_1_|_0_|_1_|_1_|_1_|_1_|
//F |_0_|_1_|_1_|_0_|_1_|_0_|_0_|_1_|_1_|
//G |_0_|_0_|_0_|_1_|_1_|_0_|_0_|_1_|_0_|
//H |_0_|_0_|_0_|_1_|_1_|_1_|_1_|_0_|_1_|
//I |_0_|_0_|_0_|_0_|_1_|_1_|_0_|_1_|_0_|

#include<stdio.h>
#define N 10
int relation[N][N] = {0,0,0,0,0,0,0,0,0,0,
                      0,0,1,0,1,1,0,0,0,0,
                      0,1,0,1,1,1,1,0,0,0,
                      0,0,1,0,0,1,1,0,0,0,
                      0,1,1,0,0,1,0,1,1,0,
                      0,1,1,1,1,0,1,1,1,1,
                      0,0,1,1,0,1,0,0,1,1,
                      0,0,0,0,1,1,0,0,1,0,
                      0,0,0,0,1,1,1,1,0,1,
                      0,0,0,0,0,1,1,0,1,0};
int count = 0;

void print(int a[])
{
    int i;
    count++;
    printf("The %dst method:\n",count);
    for(i=1;i<N;i++)
    {
        printf("%d ",a[i]);
        if(i%3==0)printf("\n");
    }
    printf("\n");

}

void MapColor(int a[],int n)
{
    int i;
    int color[5] = {0,1,1,1,1};
    if(n==N)    print(a);
    else
    {
        for(i=1;i<n;i++)
        {
            if(relation[n][i])
            {
                color[a[i]] = 0;
            }
        }
        for(i=1;i<5;i++)
        {
            if(color[i])
            {
                a[n] = i;
                MapColor(a,n+1);
            }
        }
    }
}

void main()
{
    int a[N];
    a[1] = 1;
    MapColor(a,2);
    if(count>0)
        printf("True\n");
    else
        printf("False\n");
}

（8）已知一棵树的边的结合为
{(I,M),(I,N),(E,I),(B,E),(B,D),(C,B),(G,J),(G,K),(A,G),(A,F),(H,L),(A,H),(C,A)},
试画出这棵树，并回答下列问题：（本题20分）
①哪个是根节点？
②哪些是叶子节点？
③树的深度是多少？
④写出该树的前序遍历序列
参考答案：
C
--A
----F
----G
------J
------K
----H
------L
--B
----D
----E
------I
--------M
--------N
①The root is :C.
②The leaf Nodes are :F、J、K、L、D、M、N.
③The depth of the tree :5.
④PreOrder :CAFGJKHLBDEIMN
南京师范大学2005年研究生入学考试试题-科目名称：C语言程序设计（含数据结构）
（1）设A和B是两个顺序表，其元素按从小到大的顺序排列。编写一个将A和B中相同元素组成
一个新的从大到小的有序顺序表C的算法，并分析算法的时间复杂度。（本题15分）
参考算法：
#include<stdio.h>
#define N 80
void merge(char a[],char b[],char c[])
{
    int i=0,j=0,k=0;
    while(a[i] != '\0') i++;
    while(b[j] != '\0') j++;
    i--;
    j--;
    while(i>=0 && j>=0)
    {
        if(a[i]==b[j])
        {
            c[k++] = a[i];
            i--;
            j--;
        }
        else if(a[i]>b[j])
            i--;
        else
            j--;
    }
    c[k] = '\0';
}
void main()
{
    char a[N],b[N],c[N];
    printf("input string a:");
    gets(a);
    printf("input string b:");
    gets(b);
    merge(a,b,c);
    puts(c);
}

（2）若线性表用单链表（带表头结点）作为存储结构，写出其就地逆置算法。（本题15分）
参考算法：
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
    int data;
    struct node *next;
}LNode;
void convert(LNode * &h)
{
    LNode *p,*q;
    p = h->next;
    h->next = NULL;
    while(p)
    {
        q = p->next;
        p->next = h->next;
        h->next = p;
        p = q;
    }
}
void print(LNode *h)
{
    h = h->next;
    while(h)
    {
        printf("%d ",h->data);
        h = h->next;
    }