自考算法设计分析复习题

第一章算法基础知识

1.简单描述算法的定义以及算法的特性。

答：

•算法是指解决那些适合于计算机实现的问题的方法或过程，即对特定问

题求解步骤的一种描述。

•算法具有5个特性：输入性、输出性、确定性、有穷性和可行性。

2.简述算法评估的方法与度量指标。

答：

•算法评估的方法：

正确性：算法应满足具体问题的需求；

可读性：算法应该好读，以有利于读者对程序的理解；

健壮性：算法应具有容错处理，当输入为非法数据时一，算法应对其作出反应,

而不是产生莫名其妙的输出结果。

效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过

程中所需要的最大存储空间。一般这两者与问题的规模有关。

•度量指标

算法的时间复杂度和空间复杂度。

3.算法的三种基本结构是什么？

答：

顺序结构、选择结构、循环结构。

4.举例说明什么是算法的空间复杂度？

答：

一个算法所占用的存储空间包括算法自身、算法的输入、算法的输出及实现

算法的程序在运行时所占用空间的总和。对于一个算法空间复杂度的衡量主要考

虑的是算法在运行过程中所需要的存储空间的大小。一般空间复杂度以最坏情况

来分析。

例冒泡排序算法中，其空间复杂度为S(n)=O(n)

5.试列举算法复杂度分别为0(一)和O(nlo&n)的算法。并解释由阶0(/)改进为

0(nlogzn)的根本原因是什么？

答：

•如：快速排序的平均时间复杂度为O(nlog2n)；冒泡排序的时间复杂度为

0(n2)

•一般情况下一个算法的时间复杂度考虑的只是对于问题规模n的增长

率，此时只需计算出它关于n的增长率或阶即可。nlog2n的值比n2

的值小，值越小效率越高，由阶0(r?)改进为O(nlogzn)提高了时间效率。

6.给出下面算法的时间复杂度

for(i=l;i<=n;++i)

for(j=l;j<=n;++j){

c[i][j]=0;

for(k=l;k<=n：++k)

c[i][j]+=a[i][k]*b[k][j];

)

答：

时间复杂度为：0(r)

7.给出下面算法的时间复杂度

intfact(intn){

if(n<l)

return1;

else

return(n*fact(n-1));

答：

时间复杂度为：0(n)

8.利用伪码语言描述：求两个正整数m和n的最大公约数的算法。

答：

用辗转相除法求最大公约数，其算法描述为：

输入两个正整数放入变量m和n中；

将；

进入循环,循环控制条件为r不等于0;

若满足，则将n值送入m中，将r值送入n中，将ni对n求余的结果放入变

量r中；

若不满足，则n为最大公约数，输出最大公约数n。

9.利用伪码语言描述：将保存在数组中的若干元素从小到大进行排序的算法。

答：

用冒泡排序法按升序排序，其算法描述为：

输入10个相同类型的数放入一维数组a[10]中；

进行n-1轮比较,用外循环控制：for(i=0;i<9;i++);

每轮比较n-iT次,用内循环控制:for(j=0;j<9-i;j++);

每次用相邻两数比较，若前面的数大，则交换两个数：if(a[j]>a[j+l]),

则a[j]与a[j+l]交换；

排序结束后，输出排好序的10个数。

10.利用伪码语言描述：将两个分别装有果汁和酒的杯子进行互换的算法。

答：

算法描述为：

设果汁杯为a,酒杯为b,空杯为c；

将果汁倒入空杯c,即a-c;

将酒倒入果汁杯，即b-a；

将空杯c中的果汁倒入酒杯，即c~b。

11.有三个牧师和三个野人过河，只有一条能装下两个人的船，在河的任何一方

或者船上，如果野人的人数大于牧师的人数，那么牧师就有被吃掉的危险。试用

伪码语言描述出一种安全的渡河方案。

答：

•算法分析

先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸：

初始状态：甲岸，3野人，3牧师；

乙岸，0野人，0牧师；

船停在甲岸，船上有0个人；

目标状态：甲岸，0野人，0牧师；

乙岸，3野人，3牧师；

船停在乙岸，船上有0个人；

整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状

态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算

符，根据题目要求，可以得出以下5个算符(按照渡船方向的不同，也可以理解

为10个算符)：

渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师

算符知道以后，剩下的核心问题就是搜索方法了，本文采用深度优先搜索，通过

一个FindNext(…)函数找出下一步可以进行的渡河操作中的最优操作，如果没

有找到则返回其父节点，看看是否有其它兄弟节点可以扩展，然后用Process(•­•)

函数递规调用FindNext（…）,一级一■级的向后扩展。

搜索中采用的一些规则如下：

1、渡船优先规则：甲岸一次运走的人越多越好（即甲岸运多人优先），同时野人

优先运走；

乙岸一次运走的人越少越好（即乙岸运少人优先），同时牧师优先运走；

2、不能重复上次渡船操作（通过链表中前一操作比较），避免进入死循环；

3、任何时候河两边的野人和牧师数均分别大于等于0且小于等于3；

4、由于只是找出最优解，所以当找到某一算符（当前最优先的）满足操作条件

后，不再搜索其兄弟节点，而是直接载入链表。

5、若扩展某节点a的时候，没有找到合适的子节点，则从链表中返回节点a的

父节点b,从上次已经选择了的算符之后的算符中找最优先的算符继续扩展b。

•基本数据结构

仔细阅读问题，可以发现有些基本东西我们必须把握，例如：每时刻河两岸野人

牧师各自的数目、船的状态、整个问题状态。所以我们定义如下几个数据结构：

typedefstruct_riverside//岸边状态类型

{

intwiIdMan;//野人数

intchurchMan;//牧师数

}RIVERSIDE;

typedefstruct_boat//船的状态类型

（

intwiIdMan;//野人数

intchurchMan;//牧师数

}BOAT;

typedefstruct.question//整个问题状态

（

RIVERSIDEriverSidel;//甲岸

RIVERSIDEriverSide2;//乙岸

intside;//船的位置，甲岸为T,乙岸为1

BOATboat;//船的状态

_question*pPrev;//指向前一渡船操作

.question*pNext;//指向后一渡船操作

}QUESTION;

用QUESTION来声明一个最基本的链表。

•程序流程及具体设计

本文只找出了最优解，据我所知，本问题有三种解。如果真要找出这三种解，二工

那就得加强对链表的操作了，比如说自己写一个动态链表类，顺便完成一些初始

化工作，估计看起来会舒服些。

下面给出部分关键程序：

//主函数

intmain（）

//初始化

QUESTION*pHead=newQUESTION;

pHead->riverSidel.wildMan=3;

pHead->riverSidel.churchMan=3;

pHead->riverSide2.wildMan=0;

pHead->riverSide2.churchMan=0;

pHead->side=-1;//船在甲岸

pHead->pPrev=NULL;

pHead->pNext=NULL;

pHead->boat.wiIdMan=0;

pHead->boat.churchMan=0;

if(Process(pHead))

(

//........遍历链表输出结果

)

cout*”成功渡河。〃；

)

else

cout«〃到底怎样才能渡河呢？郁闷！〃<<endl;

//回收内存空间

while(pHead)

(

QUESTION*pTemp=pHead->pNext;

deletepHead;

pHead二pTemp;

)

pHead=NULL;

return0;

)

〃渡船过程，递规调用函数FindNext(.・.)

BOOLProcess(QUESTION*pQuest)

(

if(FindNext(pQuest))

(

QUESTION*pNew=newQUESTION;

pNew->riverSidel.wildMan=pQuest->riverSidel.wildMan+

pQuest->boat.wildMan*(pQuest->side);

pNew->riverSide1.churchMan=pQuest->riverSide1.churchMan+

pQuest->boat.churchMan*(pQuest->side);

pNew->riverSide2.wildMan=3-pNew->riverSidel.wildMan;

pNew->riverSide2.churchMan=3-pNew->riverSidel.churchMan;

pNew->side=(-1)*pQuest->side;

pNew->pPrev=pQuest;

pNew->pNext=NULL;

pNew->boat.wildMan=0;

pNew->boat.churchMan=0;

pQuest->pNext=pNew;

if(pNew->riverSide2.wildMan==3&&pNew->riverSide2.churchMan==3)

returnTRUE;//完成

returnProcess(pNew);

)

else

(

QUESTION*pPrev=pQuest->pPrev;

if(pPrev==NULL)

returnFALSE;//无解

deletepQuest;

pPrev->pNext=NULL;

returnProcess(pPrev);//返回其父节点重新再找

)

returnTRUE;

)

//判断有否下一个渡河操作，即根据比较算符找出可以接近目标节点的操作

//算符共5个：1野/I牧/I野1牧/2野/2牧

BOOLFindNext(QUESTION*pQuest)

(

//基本规则

//渡船的优先顺序：甲岸运多人优先，野人优先；乙岸运少人优先，牧师优

先.

staticBOATboatState[5];//5个算符

if(pQuest->side==-1)

(

boatState[0].wiIdMan=2;

boatState[0].churchMan=0;

boatState[1].wildMan=1;

boatState[1].churchMan=1;

boatState[2].wildMan=0;

boatState[2].churchMan=2;

boatState[3].wildMan=1;

boatState[3].churchMan=0;

boatState[4].wildMan=0;

boatState[4].churchMan=1;

)

else

boatState[0].wildMan=0;

boatState[0].churchMan=1;

boatState[1].wildMan=1;

boatState[1].churchMan=0;

boatState[2].wildMan=0;

boatState[2].churchMan=2;

boatState[3].wildMan=1;

boatState[3].churchMan=1;

boatState[4].wildMan=2;

boatState[4].churchMan=0;

)

inti;//用来控制算符

if(pQuest->boat.wildMan==0&&pQuest->boat.churchMan==0)//初始

状态，第一次渡河时

i=0;//取算符1

else

{

for(i=0;i<5;i++)//扩展同一节点时;已经用过的算符不再用，按优先级

来

if(pQuest->boat.wildMan==boatState[i].wildMan&&

pQuest->boat.churchMan==boatState[i].churchMan)

break;

i++；

)

if(i<5)

(

intj;

for(j=i;j<5;j++)

(

intnWildManl=pQuest->riverSidel.wiIdMan+boatState[j].wildMan*

pQuest->side;

intnChurchMan1=pQuest->riverSidel.churchMan+boatState[j].churchMan

*pQuest->side;

intnWildMan2=3-nWildManl;

intnChurchMan2=3-nChurchMan1;

//判断本次操作的安全性，即牧师数量>=野人或牧师数为0

if((nWildManl<=nChurchMan1nChurchManl==0)&&

(nWildMan2<=nChurchMan2||nChurchMan2==0)&&

nWildManl>=0&&nChurchManl>=0&&nWildMan2>=0&&nChurchMan2>=0)

(

//本操作是否重复上次操作,注意方向不同

if(pQuest->pPrev!=NULL)

if(pQuest->pPrev->boat.wildMan==boatState[j].wiIdMan&&

pQuest->pPrev->boat.churchMan==boatState[j].churchMan)

continue;

)

break;//该操作可行，推出循环，只找出当前最优节点

)

)

if(j<5)

(

pQuest->boat.wildMan=boatState[j].wildMan;

pQuest->boat.churchMan=boatState[j].churchMan;

returnTRUE;

)

)

returnFALSE;

12.利用伪码语言描述收割白菜问题：菜园四周种了n棵白菜，并按顺时针方向

由1到n编号。收割时，从编号为1的白菜开始，按顺时针方向每隔两棵白菜

收割一棵，直到全部收割完毕。最后按收割顺序输出白菜的编号。

答:

数组A：存放白菜的编号。当白菜被收割后，从数组中删去相应元素

数组B：按收割顺序存放被收割白菜的编号

输入：白菜棵数n

输出：按收割顺序存放白菜编号的数组B[]

voidreap(intB[],intn)

(

inti,j,k,s,t;

int*A=newint[n];

j=0;

k=3:

s=n;

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

A[i]=i+1;

while(j<n){

t=s;

s=0;

for(1=0;i<t;i++){

if(—k!=0)

A[s++]=A[i];/*未被收割的白菜*/

else{

B[j++]=A[i];k=3;/*被收割的白菜*/

)

)

)

deleteA;

第二章线性数据结构与算法

1.简述栈、队列的异同点。

答：

栈是限定只能在表的一端进行插入和删除操作的线性表。

队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。

栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于

基本操作的特殊性，栈必须按〃后进先出〃的规则进行操作，而队列必须按〃先进

先出〃的规则进行操作。

它们的主要区别是对插入和删除操作的〃限定〃。和线性表相比，它们的插入

和删除操作受更多的约束和限定，故又称为限定性的线性表结构。栈只允许在表

尾一端进行插入和删除；队列只允许在表尾一端进行插入，在表头一端进行删除。

2.利用栈实现老鼠走迷宫问题的求解。

答：

Sinclude"stdafx.h〃

Sinclude〃stdlib・h〃

#include"stdio.h"

#defineN8

typedefstructstack{

intI;

intJ;

intstep;〃步数

stack*next;

}STACK;

STACK*top;

STACK*InitStackO

(

top=(STACK*)malloc(sizeof(STACK));

top->next=NULL;

top->step=0;

returntop;

voidpush(inti,intj)

(

STACK*p;

p=(STACK*)malloc(sizeof(STACK));

p->I=i；

p->J=j：

p->next=top->next：

top->next=p;

top->step++;

)

intpop(int&i,int&j)

(

STACK*p;

if(top->next){

p=top->next;

top->next=p->next;

)

elseif(top->next==NULL)

return0;

i=p->I；

J=P->J：

top->step一;

return1;

)

intok(chara[][N],inti,intj)

(

while((i<N&&i>=0)&&(j<N&&j>=0)){

if(a[i][j]='S'){〃找到出口

break;

)

if(a[i-l][j]!='X'[j]!='Y'){

〃上边不是墙且不是死路，并旦没有走过则压栈

//经过该点则标记，否则在N000处会造成原路返回结果

push(i,j);

i=i-l；

continue;

if(a[i+l][j]!=X'&&a[i+l][j]!=，Y'){〃下

a[i][j]='X';

push(i,j);

i=i+l;

continue;

if(a[i][j-1]!='X'!='Y'){〃左

push(i,j);

j=j-l；

continue;

)

if(a[i][j+1]!='[j+1]!=Y'){〃右

a[i][j]=X);

push(i,j);

j=j+l；

continue;

)

〃四个方向都不通

//Y表示此路已经走过但是不通，否则会在该处造成无限循环

ints;

s=pop(i,j);

if(!s)

return0;

)

return1;

intmain(intargc,char*argv[1)

(

chara[N][N]={'X','X','X','X','X','X','X','X',\

'X','E','O','O','X','S','X','X',\

'X','X','O','X','O','X','X','X',\

'X','O','O','O','O','X','O','X',\

'X','X','X','X','O','O','O','X',\

'X','O','O','O','O','X','X','X',\

'X','X','X','X','O','X','X','X',\

，丫，，丫，，丫，，丫，，丫，，丫，，丫，，丫，\

A,A,AfA,A,A,AfAfj

inti,j,iO,jO;

InitStackO;

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

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

if(a[i][j]=='E'){

i0=i;

jO=j;

)

ints;

s=ok(a,iO,jO);

if(!s){

printf(〃迷宫走不通”)；

exit(0);

printf(/z%d步可以走出迷宫”,top->step);

while(top->next){

pop(i,j);

a[i][j]=

)

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

printf('\n");

for(j=0;j<N;j++){

if(a[i][j]=='Y')〃将Y还原

printf("枇"，a[i][j]):

)

)

return0;

3.对于老鼠走迷宫问题，如果迷宫的入口至出口路径可能存在多个，且在某一

位置老鼠可以按顺时针方向向东、东南、南、西南、西、西北、北和东北八个方

向上进行搜索，编程求出所有可能的路径。

答：

ttinclude<stdio.h>

#include<stdlib.h>

ttdefineMAXSIZE50

#defineERROR-1

#defineOK0

#defineFALSE0

#defineTRUE1

typedefenum{RIGHT,DOWN,LEFT,UP}Direction;

typedefenum{YES,NO}MarkTag;

typedefstructposition{〃迷宫中位置的坐标

intx;

inty;

}Position;

typedefstruct{〃当前位置在路径中的序号

intorder;〃当前位置在迷宫中的坐标

Positionseat;〃从当前位置走到下一位置的方向

Directiondi;〃栈元素的类型

}SElemType;

typedefstruct{

SElemType*elem;

inttop;

}Stack;

charmaze[MAXSIZE+2][MAXSIZE+2];〃用二维数组表示迷宫

intInitStack(Stack*S){〃创建一空栈

S->elem=(SElemType*)malloc(MAXSIZE*MAXSIZE*sizeof(SElemType));

if(!S->elem)

returnERROR;

S->top=0;

returnOK;

)

intPush(Stack*S,SElemTypee){〃元素e入栈

if(S->top>=MAXSIZE*MAXSIZE)

returnERROR;

S->elem[S->top++]=e;

returnOK;

)

intPop(Stack*S,SElemTypee){〃栈顶元素出栈，由e带回栈顶元素

if(S->top<=0)

returnERROR;

*e=S->elem[--S->top];

returnOK;

)

intEmpty(StackS){〃若栈为空，返回TRUE,否则返回FALSE

if(S.top==0)

returnTRUE;

returnFALSE;

)

intcreateMaze(char*filename,Position*startpos,Position*endpos){

//从文件filename读入数据创建迷宫，由参数带回入口位置和出口位置

FILE*fp;

inti,j,rows,cols,temp;

Positionstart,end;

fp=fopen(filename,z/rz/);

if(!fp){

printf(，zopenfile%serror!\nz，,filename);

returnERROR;

)

if(!feof(fp)){

fscanf(fp,z/%d%dz/,&rows,&cols);〃读入迷宫的行数和列数

fscanf(fp,/z%d%d，z,&start.x,&start.y);〃读入迷宫的入口位置

fscanf(fp,〃%d%d，z,&end.x,&end.y);〃读入迷宫的出口位置

)

for(i=l;i<=rows;i++)〃读入迷宫数据

for(j=l;j<=cols;j++){

fscanf(fp,z，%d，z,&temp);

maze[i][j]=48+temp;

)

fclose(fp);

〃在迷宫四周加墙

for(i=0,j=0;i<=rows+l;i++)maze[i][j]=，P;

for(i=0,j=cols+l;i<=rows+l;i++)mazeLi][j]=，1';

for(i=0,j=0;j<=cols+l;j++)mazeti][j]=，T;

for(i=rows+l,j=0;j<=cols+l;j++)maze[i][j]=，1';

*startpos=start;

*endpos=end;

returnOK;

)

intcanPass(Positioncurpos){

if(mazetcurpos.x][curpos.y]==，O')

returnTRUE;

returnFALSE;

)

voidmarkPos(Positioncurpos,MarkTagtag){〃为已走过的位置标记

switch(tag){

caseYES:mazetcurpos.x][curpos.y]='・';break;//路径标t己

caseNO:maze[curpos.x][curpos.y]二;break;//死胡同标t己

PositionnextPos(Positioncurpos,Directiondir){

〃根据当前的位置坐标和下一步要探索的方向dir求下一步要走的位置坐标

Positionnextpos;

switch(dir){

caseRIGHT:nextpos.x=curpos.x;nextpos.y=curpos.y+1;break;

caseDOWN:nextpos.x=curpos.x+1;nextpos.y=curpos.y;break;

caseLEFT:nextpos.x=curpos.x;nextpos.y=curpos.y-1;break;

caseUP:nextpos.x=curpos.x-1;nextpos.y=curpos.y;break;

)

returnnextpos;

)

DirectionnextDir(Directiondir){

switch(dir){〃按照RIGHTDOWNLEFTUP的次序进行路径探索

caseRIGHT:returnDOWN;

caseDOWN:returnLEFT;

caseLEFT:returnUP;

)

)

/*若迷宫中存在从入口start到出口end的通道，则求得一条存放在栈S中，并

返回TRUE,若不存在则返回FALSE*/

intSolve(Stack*S,Positionstart,Positionend){

Positioncurpos;

SElemTypee;

intcurstep=l;

if(InitStack(S)==ERROR)

returnFALSE;

curpos=start;

do(

if(canPass(curpos)){〃当前位置可以通过

markPos(curpos,YES);〃留下足迹

e.order=curstep;

e.seat=curpos;

e.di=RIGHT;

Push(S,e);

if(curpos.x==end.x&&curpos.y=end.y)

returnTRUE;〃找到从入口到出口的通道

curpos=nextPos(curpos,RIGHT);

curstep++;

else{

if(!Empty(*S)){〃当前位置不能通过

if(Pos(S,&e)==ERROR)

returnFALSE;

while(e.di==UP&&!Empty(*S)){

//4个方向都找不到通路，则回溯

curpos=e.seat;

markPos(curpos,NO);

if(Pop(S,&e)==ERROR)

returnFALSE;

)

if(e.di!=UP){〃4个方向还没有探索完

e.di=nextDir(e.di);

Push(S,e);〃换下一个方向探索

curpos=nextPos(e.seat,e.di);

)

)

}while(!Empty(*S));

returnFALSE;

)

voidmain(void){

PositionstartPos,endPos;

Stackpath;

SElemTypee;

char*fname=〃in.txt”;

if(createMaze(fname,ftstartPos,&endPos)==ERROR)return;

Solve(&path,startPos,endPos);

while(!Empty(path)){〃输出出口到入口的路径

Pop(&path,&e);

printf(〃(%d,%d)\n〃,e.seat,x,e.seat,y);

)

)

4.判断一个字符串是否是回文。回文是指从前向后顺读和从后向前倒读都一样

的不含空白字符的串。

答：

〃以下为顺序栈的存储结构定义

SdefineStackSize100〃假定预分配的栈空间最多为100个元素

typedefcharDataType;〃假定栈元素的数据类型为字符

typedefstruct{

DataTypedata[StackSize];

inttop;

}SeqStack;

intIsHuiwen(char*t)

{〃判断t字符向量是否为回文，若是，返回1,否则返回0

SeqStacks;

inti,len;

chartemp;

InitStack(&s);

len=strlen(t);〃求向量长度

for(i=0;i<len/2;i++)〃将一半字符入栈

Push(&s,t);

while(!EmptyStack(&s))

{//每弹出一个字符与相应字符比较

temp=Pop(&s);

if(temp!=S)return0;//不等则返回0

elsei++;

)

return1;//比较完毕均相等则返回1

)

5.读入一个程序，统计程序中代码、注释和空行数及函数的个数，并利用统计

信息分析评价该程序风格。基本要求如下：

①把Java程序文件按字符顺序读入源程序；

②边读入程序，边识别统计代码行、注释行和空行，同时还要识别函数的开始和

结束，以便统计其个数。

③程序风格分为代码、注释和空行三方面。每方面分A、B、C、D四个等级。

答：

〃用于保存统计信息的结构

typedefstruct_StatInfo

{

intnCode;〃代码行

intnSpace;〃空行

intnConment;〃注释行

〃〃/*〃开头的注释是否结束,0表示结束，1表示没有结束

intnEndConmentFlag;

intnLines;〃总行数

}Statinfo;

voidAnalyse(Statinfo*psi,char*pLine)

/*---------------------对字符串进行分析的函数---------------------*/

/*——psi指向保存结果的结构指针，pLine指向被分析字符串

"11111111-/

(

〃总行数加1

psi->nLines++;

〃如果是空行，则空行数加1

if(strcmp(strtmp,〃〃)二二0)

(

psi->nSpace++;

return;

)

charstrtmp[2];

〃读出每行头两个字符，以便比较

strncpy(strtmp,pLine,2);

〃发现〃/*〃则注释标识置为真，

〃如果没有发现〃/*:或在同一行中发现〃*/〃，则结构体注释标志置为假

if(strcmp(strtmp,〃/*〃)=0)

psi->nEndConmentFlag=l;

//StrFind(stringl,string2)函数，返回string2是否在stringl中的位置

//返回一1表示string2不存在于stringl中

if(StrFind(pLine,〃*/"))!=T)

psi->nEndConmentFlag=0;

〃如果是以〃/*〃开头的注释，则注释行数加1

if(psi->nEndConmentFlag)

psi->nConment++;

〃不是以〃/*〃开头，如果是以‘7/〃开头的注释，注释行数同样加1

elseif(strcmp(strtmp,〃〃〃)=0)

psi->nConment++;

〃两种注释都不是，则代码行数加1

else

psi->nCode++;

)

intStrFind(char*stringl,char*string2)

(

char*q=stringl;

q=strstr(q,string2);

if(q)

returnq-stringl;

else

return-1;

voidprint(Statinfopsi)

printf("theresultsofanalysingprogramfile\〃***.c、〃：\n");

printf("linesofcode:%d\n”,psi.nCode);

printf("lingsofcomments:%d\nn,psi.nComment);

printf("blanklines:%d\n\n”,psi.nSpace);

printf(ucode\tcomments\t\tspace\n??);

printf(u%d%%\t%d%%\t\t%d%%\nn,psi.nCode/psi.nLines,

psi.nComment/psi.nLines,psi.nSpace/psi.nLines);

//printf(ugradeA:excellentroutinexizestyle.\n");

//printf(ugradeA:excellentcommentingstyle.\n”);

//printf(ugradeA:excellentwhitespacestyle.\n");

)

voidmain()

(

charstrCppFile[256];

〃读取用户输入的C文件名的函数

GetFile(strCppFile);

FILE*fp;

fp=fopen(ff.GetFilePath(),〃r〃)；

if(fp==NULL)

return;

charbuf[1000];

Statinfopsi;

while(fgets(buf,1000,fp)!=NULL)

(

Analyse(&psi,buf);

)

fclose(fp);

〃向用户输出统计结果的函数

print(psi);

)

6.编程统计文本单词的个数。基本要求如下:

①从文本(字符串)的左边开始，取出一个字符；设逻辑量WT表示所取字符是

否是单词内的字符，初值设为false；

②若所取字符不是“空格”，“逗号”，“分号”或“感叹号”等单词的分隔符，再

判断WT是否为true,若WT不为true则表示新单词的开始，让单词数Nw=Nw+l,

让WT=true;

③若所取字符是“空格”，“逗号”，“分号”或“感叹号”等单词的分隔符，则表

示字符不是单词内字符，让WT=false；

④再依次取下一个字符，重复②③直到文本结束。

答：

Sinclude〃stdio.h〃

main()

{charc,string[80];

inti,num=0,word=0;

FILE*fp=fopen(afile.txt"，"r");

while(fgets(string,80,fp)!=NULL)

(

for(i=0;(c=stringEi])!=,\0J;i++)

if(c==，')word=0;

elseif(word==0)

{word=l;

num++;}

)

fclose(fp);

printf(zzThereare%dwordintheline.\nz，,num);

)

7.从键盘读入任意个整数，以从小到大的方式保存到链表中，并计算比较次数。

最后输出链表中内容和比较次数。

答：

#include<stdio.h>

#include<stdlib.h>

typedefstructlist

(

intdata;

structlist*next;

}LIST;

voidmain()

(

LIST*head,*p,*q,*In;

inti,j=l,num=0;

head=p=q=In=NULL;

printf('"Inputthe%dnumber:〃，j++);

scanf(〃%d〃，&i);

while(i!=-l)

if(head==NULL)

(

head=(LIST*)malloc(sizeof(LIST));

q=(LIST*)malloc(sizeof(LIST));

q->data=i;

q->next=NULL;

head->next=q;

p=head-〉next;

)

else

(

In=head;

while(p!=NULL&&p->data<i)

{num++;

In=p;

p=p->next;

)

q=(LIST*)malloc(sizeof(LIST));

q->data=i;

q->next=In->next;

In->next=q;

p=head->next;

}

printf(，zInputthe%dnumber:〃，j++);

scanf(〃%d〃,&i);

)

p=head->next;

while(p!=NULL)

(

printf(z，%d〃，p->data);

p=p->next;

}

printf(z，Totalcompara:%d\n，z,num);

)

9.现有1、2、3、4、5五个数字，要求输出所有不同的排列。要求：4不能在

第三位，3与5不能相连。

答：

publicclasstest

(

staticint[]a=newint[6];

publicstaticvoidsearch(intidx)

if(idx==6)

for(inti=l;i<a.length;i++)

System.out.print(a[i]);

System,out.printin(〃〃);

return;

)

for(inti=l;i<=5;i++)

(

if(i==4&&idx==3)

continue;

if(idx!=l)

(

if((a[idx-l]==3&&i==5)||(a[idx-l]==5&&i==3))

continue;

}

a[idx]=i;

search(idx+1);

)

)

publicstaticvoidmain(String[]args)

(

search(1);

10.编写一个简单的数学表达式解析程序。基本要求为:

①能够解析用户输入的代数表达式并求值；

②至少支持加减乘除及括号等运算符。

答：

#defineStack_init_size100

SdefineStack_add10

ttinclude<iostream>

usingnamespacestd;

#include<cstdlib>

#include<cstring>

#include<cctype>

#include<cstdio>

typedefstruct(

char*base;

char*top;

intstacksize;

}SqStackl;

typedefstruct(

double*base;

double*top;

intstacksize;

}SqStack2;

voidInitStack(SqStackl&S)

(

S.base=(char*)malloc(Stack_init_size*sizeof(char));

if(!S.base)

exit(1);

S.top=S.base;

S.stacksize=Stack_init_size;

return;

)

voidInitStack(SqStack2&S)

(

S.base=(double*)malloc(Stack_init_size*sizeof(double));

if(!S.base)

exit(1);

S.top=S.base;

S.stacksize=Stack_init_size;

return;

)

voidPush(SqStackl&S,chare)

(

if(S.top-S.base>=S.stacksize)

(

S.base=(char

*)realloc(S.base,(S.stacksize+Stack_add)*sizeof(char));

if(!S.base)

exit(1);

S.stacksize+=Stack_add;

)

*S.top++=e;

return;

)

voidPush(SqStack2&S,doublee)

{

if(S.top-S.base>=S.stacksize)

(

S.base=(double

*)realloc(S.base,(S.stacksize+Stack_add)*sizeof(double));

if(!S.base)

exit(1);

S.top=S.base+S.stacksize;

S.stacksize+=Stack_add;

)

*S・top++=e;

return;

)

boolPop(SqStackl&S,char&e)

(

if(S.base==S.top)

returnfalse;

e=*(一S.top);

returntrue;

)

boolPop(SqStack2&S,double&e)

(

if(S.base==S.top)

returnfalse;

e=*(--S.top);

returntrue;

)

charGetTop(SqStackl&S)

(

if(S.base==S.top)

return0;

return*(S.top-1);

)

doubleGetTop(SqStack2&S)

(

if(S.base==S.top)

return0;

return*(S.top-1);

)

boolIn(charc)

(

=，9

if(c=+'||c='」||c二二'*，||c二二,/"||c='('Hc二二')，||c='ft||c=-

)

returntrue;

returnfalse;

)

doubletodouble(chars[])

(

doubleval,power;

inti=0,sign;

sign=(s[i]=='-')?T:1;

if(sLi]=='+'||s[i]==)

i++；

for(val=0.0;isdigit(s[i]);i++)

(

val=val*10+(s[i]-'O');

)

if(s[i]==

i++;

for(power=1.0;isdigit(s[i]);i++)

(

val=10.0*val+(s[i]-'O');

power*=10;

)

returnsign*val/power;

)

doublepower(doublea,doubleb)

(

doubles=l.0;

for(inti=0;i<b;i++)

s=s*a;

returns;

)

doubleOperate(doublea,chartheta,doubleb)

switch(theta)

case'+':returna+b;

case'-':returna-b;

case)**:returna*b;

case'/':returna/b;

case""":returnpower(a,b);

default:return0;

)

)

charPrecede(charm,charn)

charPrior[8][8]={//算符间的优先关系

);

charch[8]={3,，-，，*；/；(，)，，#；

inti,j;

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

if(m==ch[i])

break;

for(j=0;j<8;j++)

if(n==ch[j])

break;

returnPrior[i]Lj];

)

voidperfect(chars[])

{

charsi[100];

inti,j,n;

i=j=0;

if(s[0]==-)

si[j++]='O'；

sl[j++]=s[i++];

while(sLil)

(

if(s[i]=-&&In(s[i-l!)&&s[i-l]!=')")

(

si[j++]='O';

sl[j++]=s[i++];

)

si[j++]=s[i++];

)

sl[j]=\0';

i=0;

while(si[i])

(

s[i]=sl[i];

i++；

)

s[i]='\0';

)

doubleEvaluateExpression()

(

charx,theta,z[100][20];

doublea,b;

inti,j=0,k=0;

chars[100];

gets(s);

perfect(s);

SqStacklOPTR;〃寄存运算符

SqStack2OPND;〃寄存操作数和操作结果

InitStack(OPTR);

InitStack(OPND);

PushSPTR,;

while(s[j]!=’#'|GetTop(OPTR)!=，#')

(

if(!In(sLj]))

(

i=0;

while(isdigit(s[j])||s[j]=='.')

(