（1）设计一个程序，将任何输入的字符串中的最长单词输出，并计算出其在字符串中的位置。（本题15分）
参考解法：
#include<stdio.h>
void main()
{
int i,count=0,pos=0,maxlen=0;
char ch;
char s[80] = "what are you doing";
//printf("input a string:");
//gets(s);
i = -1;
do
{
i++;
ch = s[i];
if((ch>='A' && ch<='Z') || (ch>='a' && ch<='z'))
{
count++;
}
else
{
if(count>maxlen)
{
maxlen = count;
pos = i-maxlen;
}
count = 0;
}
} while(s[i]!='\0');
printf("The max length word is \"");
for(i=0;i<maxlen;i++)
{
printf("%c",s[pos+i]);
}
printf("\" and it's position is %d.\n",pos+1);
}
（2）试采用递归函数实现将任意位数的整数转换为字符串输出，要求在主函数中输入整数并调用递归函数实现转换并输出结果，对于负数也能处理。（本题15分）
参考解法：
#include<stdio.h>
void numtostring(int n,char a[],int k)
{
if(k==0) return;
else
{
a[--k] = n%10 + 48;
n /= 10;
numtostring(n,a,k);
}
}
void main()
{
int n,m,k=0;
char a[100],sign=' ';
printf("Please input the number:");
scanf("%d",&n);
if(n<0) {sign = '-';n = -n;}
m = n;
while(m)
{
k++;
m /= 10;
}
a[k] = '\0';
numtostring(n,a,k);
printf("The number is :%c%s\n",sign,a);
}
（3）以顺序存储结构表示串，设计算法，求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。（本题20分）参考解法：
#include<stdio.h>
void maxsubstr(char s[],int &pos,int &len)
{
int i,j,k;
for(i=0;s[i]!='\0';i++)
{
j = i+1;
k = 0;
while(s[j]!='\0')
{
while(s[i+k]!='\0' && s[j+k]!='\0' && s[i+k]==s[j+k])
{
k++;
}
if(k>len)
{
len = k;
pos = i;
}
k = 0;
j++;
}
}
}
void main()
{
int i,pos=0,len=0;
char s[100];
printf("please input string :");
gets(s);
maxsubstr(s,pos,len);
for(i=0;i<len;i++)
{
printf("%c",s[pos+i]);
}
printf("\n");
}
时间复杂度:O(n^3)
（4）利用两个栈S1和S2模拟一个队列，写出入队和出队的算法（可用栈的基本操作）。
（本题20分）
参考解法：
void EnQueue(ElemType x)
{
ElemType e;
Stack s1,s2;
if((!StackEmpty(s1)) && (!StackEmpty(s2))) //如果两个栈都不为空则返回
return;
else if((!StackEmpty(s2)) && (StackEmpty(s1))) //如果s1栈为空，s2栈不为空
{
while(!StackEmpty(s2))
{
Pop(s2,e);
Push(s1,e);
}
}
Push(s2,x); //元素x入队列
}
void DeQueue(ElemType &x)
{
ElemType e;
if((!StackEmpty(s1)) && (!StackEmpty(s2))) //如果两个栈都为空
return;
else if((!StackEmpty(s2)) && (StackEmpty(s1))) //如果s1栈为空，s2栈不为空
{
while(!StackEmpty(s2))
{
Pop(s2,e);
Push(s1,e);
}
}
Pop(s1,x); //元素x出队列
}
（5）编写一算法，以完成在带头节点单链表M中第n个位置前插入元素X的操作。（本题20分）
参考解法：
typedef struct node
{
ElemType data;
struct node *next;
}LNode;
void Insert(LNode *h,int n,ElemType x)
{
int i=0;
LNode *p,*q;
p = h;
q = p->next;
while(q && i<n-1)
{
i++;
p = q;
q = p->next;
}
if(i<n-1) return;
q = (LNode *)malloc(sizeof(LNode));
q->data = x;
q->next = p->next;
p->next = q;
}
（6）编写一个利用二分法查找某值X是否存在于一组已知数据X1、X2、X3、……Xn中的程序。（本题20分）
参考解法：
#include<stdio.h>
#define N 5
void main()
{
char ch;
int i,e,pos,low,high,mid,flag=1;
int a[N];
for(i=0;i<N;i++) //在数组a中读取一组从小到大排列的数
{
printf("input %dst number:",i+1);
scanf("%d",&a[i]);
if(i>0)
{
if(a[i]<=a[i-1])
{
printf("input a number which is bigger than %d\n",a[i-1]);
i--;
}
}
}
while(flag)
{
for(i=0;i<N;i++)
printf("%d ",a[i]);
printf("\nWhich number you want to query?");
scanf("%d",&e);
pos = -1;
low = 0;
high = N-1;
while(low<=high)
{
mid = (low+high)/2;
if(a[mid]==e)
{
pos = mid;
break;
}
else if(a[mid]>e)
high = mid-1;
else
low = mid+1;
}
if(pos==-1) printf("*****Cant't find the element!*****\n");
else printf("*****The element's position is %d.*****\n",pos+1);
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