自考算法设计分析复习题2

好老师在线资料中心查资料,比课程,找好老师!

自考算法设计分析复习题

第一章算法基础知识

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

答：

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

种描述。

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

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

答：

算法评估的方法：

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

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

健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生

莫名其妙的输出结果。

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

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

度量指标

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

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

答：

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

答：

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

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

中所需要的存储空间的大小。一般空间复杂度以最坏情况来分析。

5.试列举算法复杂度分别为。(n2)和O(nlog2n)的算法。并解释由阶。(n2)改进为

O(nlog2n)的根本原因是什么？例冒泡排序算法中，其空间复杂度为S(n)=O(n)顺序结构、

选择结构、循环结构。

1

答：

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

0(n2)

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

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

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

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

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

)

答：

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

intfact(intn){

)

答：

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

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

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

将；

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

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

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

2c[i][j]=0;for(k=l;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];时间复杂度为：O(n3)if(n<l)return1;

return(n*fact(n-l));else时间复杂度为：O(n)

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

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

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

如果野人的人数大于牧师的人数，那么牧师就有被吃掉的危险。试用伪码语言描述出一种

安全的渡河方案。

答：

算法分析

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

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

乙岸，0野人，0牧师；

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

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

乙岸，3野人，3牧师；

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

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

是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，

可以得出以下5个算符(按照渡船方向的不同，也可以理解为10个算符)：

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

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

FindNext(”)函数找出下一步可以进行的渡河操作中的最优操作,如果没有找到则返回其父节

点，看看是否有其它兄弟节点可以扩展，然后用Process(„)3用冒泡排序法按升序排序，其

算法描述为：输入10个相同类型的数放入一维数组a[10]中；进行n-l轮比较，用外循环

控制：for(i=0;i<9;i++);每轮比较n-i-1.次，用内循环控制：for(j=0;j<9-i;j++);每次用相邻两数

比较，若前面的数大，则交换两个数：if(aU]>a[j+l]),排序结束后，输出排好序的10个数。

则a[j]与a[j+l]交换；算法描述为：设果汁杯为a,酒杯为b,空杯为c；将果汁倒入空杯

c,即a-c;将酒倒入果汁杯，即b-a；将空杯c中的果汁倒入酒杯，即c-b。

函数递规调用FindNex",,),一级一级的向后扩展。

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

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

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

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

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

4、由于只是找出最优解，所以当找到某一算符(当前最优先的)满足操作条件后，不再搜

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

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

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

基本数据结构

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

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

_riverside//岸边状态类型

(

intwildMan;//野人数

intchurchMan;//牧师数

}RIVERSIDE;

typedefstruct_boat//船的状态类型

(

intwildMan;//野人数

intchurchMan;//牧师数

}BOAT;

typedefstruct_question//整个问题状态

(

RIVERSIDEriverSidel;〃甲岸

RIVERSIDEriverSide2;//乙岸

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

BOATboat;//船的状态

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

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

}QUESTION;

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

程序流程及具体设计

本文只找出了最优解，据我所知，本问题有三种解。如果真要找出这三种解，八_八，那就得

加强对链表的操作了，比如说自己写一个动态链表类，顺便完成一些初始化工作，估计看

起来会舒服些。

下面给出部分关键程序：

//主函数

intmain()

4

//初始化

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.wildMan=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->riverSidel.churchMan=pQuest->riverSidel.churchMan

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

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

3-pNew->riverSidel.churchMan;5++

pNew->side=(-l)*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)return

TRUE;//完成

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牧

BOOLFindNextfQUESTION*pQuest)

(

//基本规则

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

staticBOATboatstate[5];//5个算符

if(pQuest->side==-1)

(

boatState[0].wildMan=2;

boatstate[0].churchMan=0;

boatState[l].wildMan=1;

boatState[l].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

6

(

boatState[0].wildMan=0;

boatstate[0].churchMan=1;

boatState[l].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.wildMan+boatstate[j].wildMan*pQuest->side;

intnChurchManl=pQuest->riverSidel.churchMan+boatState[j].churchMan*pQuest->side;

intnWildMan2=3-nWildManl;

intnChurchMan2=3-nChurchManl;

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

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

(nWildMan2<=nChurchMan211nChurchMan2==0)&&

nWildManl>=0&&nChurchManl>=0&&nWildMan2>=0&&

nChurchMan2>=0){

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

if(pQuest->pPrev!=NULL)

7

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

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)

(

int

int*A=newint[n];

j=0;

k=3;

s=n;

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

A[i]=i+l;

while(j<n){

t=s;

s=0;

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

if(-k!=0)

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

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

)

)

)

deleteA;

)

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

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

答：

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

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

序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按“

后进先出“的规则进行操作，而队列必须按“先进先出”的规则进行操作。

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

多的约束和限定，故又称为限定性的线性表结构。栈只允许在表尾一端进行插入和删除；

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

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

答：

include"stdafx.h"

include"stdlib.h"

include"stdio.h"

#defineN8

typedefstructstack{

intI;

intJ;

intstep;〃步数

stack*next;

}STACK;

STACK*top;

STACK*lnitStack()

(

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

top->next=NULL;

top->step=0;

returntop;

9

)

voidpush(inti,intj)

(

STACK*p;

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

P->l=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->l；

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'&&a[i-l][j]!='Y'){

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

a[i]U]='X';

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

push(ij);

i=i-l;

continue;

}

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

a[i]U]='X';

push(ij);

i=i+l;

continue;

if(a[i][j-l]!='X'&&a[i][j-l]!=Y){〃左a[i]U]='X';

push(ij);

j=j-l；

continue;

)

if(a[i][j+l]!='X'&&a[i][j+l]!=Y){〃右a[i]D]='X';

push(i,j);

j=j+l；

continue;

)

〃四个方向都不通

a[i]U]='Y';

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

s=pop(i,j);

if(⑸

return0;

)

return1;

intmain(intargc,char*argv[])

(

chara[N][N]={X,X,X,X,X,X,X,X,\'xyEyo'/oyxysyxyx'A

'xyxyoyxyoyxyxyxw'xyoyo'/oyoyxyovxw

'xyxvxyxyo;'oyoyx'A'xyoyoyoyoyxyxyxw

iwl)wlIwllyllyllylIwiIwl1.

'xyxvxyxyo'/xvxyx'A八，八，A，八，八，A，八，八/，

intiJJOJO;

InitStackf);

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

11

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

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

iO=i;

jO=j；

)

)

ints;

s=ok(aJOJO);

if(!s){

printf("迷宫走不通，

exit(O);

)

printf("%d步可以走出迷宫”,top・>step);

while(top->next){

pop(i,j)；

a[i]U]='*'；

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

printf("\n");

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

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

a[i]U]='O'；

printf("%c",a(i][j]);

return0;

)

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

以按顺时针方向向东、东南、南、西南、西、西北、北和东北八个方向上进行搜索，编程

求出所有可能的路径。

答：

#include<stdio.h>

include<stdlib.h>

#defineMAXSIZE50

#defineERROR-1

#defineOK0

#defineFALSE0

#defineTRUE1

typedefenum{RIGH]DOWN,LEF[UP}Direction;

typedefenum{YES,NO}MarkTag;

12

typedefstructposition{〃迷宫中位置的坐标

intx;

inty;

}Position;

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

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

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

Directiondi;〃栈元素的类型

}SEIemType;

typedefstruct{

SEIemType*elem;

inttop;

}Stack;

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

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

S->elem=(SEIemType*)malloc(MAXSIZE*MAXSIZE*sizeof(SEIemType));if(!S->elem)

returnERROR;

S->top=0;

returnOK;

)

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

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

returnERROR;

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

returnOK;

)

intPop(Stack*S,SEIemTypee){〃栈顶元素出栈，由e带回栈顶元素if(S->top<=0)

returnERROR;

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

returnOK;

)

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

if(S.top==0)

returnTRUE;

returnFALSE;

13

}

intcreateMaze(char"filename,Position*startpos,Position*endpos){〃从文件filename读入

数据创建迷宫，由参数带回入口位置和出口位置FILE*fp;

inti,j,rows,cols,temp;

Positionstart,end;

fp=fopen(filename/'r");

if(!fp){

printfC'openfile%serror!\n",filename);

returnERROR;

)

if(!feof(fp)){

〃读入迷宫的行数和列数

fscanf(fp,"%d%d",&rows/&cols);

〃读入迷宫的入口位置

fscanf(fp/'%d%d",&start.x/&start.y);

〃读入迷宫的出口位置}

fscanf(fp/'%d%d"/&end.x/&end.y);

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

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

fscanf(fp,"%cT,&temp);

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

)

fclose(fp);

〃在迷宫四周加墙

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

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

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

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

*startpos=start;

*endpos=end;

returnOK;

)

intcanPass(Positioncurpos){

if(maze[curpos.x][curpos.y]=='0')

returnTRUE;

returnFALSE;

)

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

caseYES:maze[curpos.x][curpos.y]='.';break;〃路径标记caseNO:

maze[curpos.x][curpos.y]=,#*;break;〃死胡同标记}

14

)

PositionnextPos(Positioncurpos,Directiondir){

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

nextpos;

switch(dir){

caseRIGHT:nextpos.x=curpos.x;nextpos.y=curpos.y+l;break;caseDOWN:

nextpos.x=curpos.x+l;nextpos.y=curpos.y;break;caseLEFT:nextpos.x=curpos.x;

nextpos.y=curpos.y-l;break;caseUP:nextpos.x=curpos.x-l;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;

SEIemTypee;

intcurstep=l;

if(lnitStack(S)==ERROR)

returnFALSE;

curpos=start;

do{

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

markRos(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{

15

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^extPosfe.sea^e.di);

)

}

}while(!Empty(*S));

returnFALSE;

)

voidmain(void){

PositionstartPos^ndPos;

Stackpath;

SEIemTypee;

char*fname=,'in.txt";

if(createMaze(fname/&startPos/&endPos)==ERROR)return;

Solve(&path,startPos,endPos);

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

Pop(&path,&e);

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

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

字符的串。

答：

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

#defineStacksize100〃假定预分配的栈空间最多为100个元素typedefcharDataType;〃假

定栈元素的数据类型为字符

typedefstruct{

DataTypedata[StackSize];

inttop;

16

}SeqStack;

intlsHuiwen(char*t)

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

SeqStacks;

inti/len;

chartemp;

lnitStack(&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_Statlnfo

(

intnCode;〃代码行

intnSpace;〃空行

intnConment;〃注释行

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

intnEndConmentFlag;

intnLines;〃总行数

}Statinfo;

voidAnalyse(Statlnfo*psi,char*pLine)

17

/*------------对字符串进行分析的函数------------*//*--psi指向保存结果的结构

指针，pLine指向被分析字符串

〃总行数加1

psi->nLines++；

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

if(strcmp(strtmp,"")==0)

(

psi->nSpace++；

return;

)

charstrtmp[2];

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

stmcpy(strtmp,pLine,2);

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

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

if(strcmp(strtmpf,7*")==0)

psi->nEndConmentFlag=l;

〃StrFind(stringl,string2)函数，返回string2是否在stringl中的位置〃返回一1表示string2

不存在于stringl中

iffStrFindlpLine,"*/

psi->nEndConmentFlag=0;

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

if(psi->nEndConmentFlag)

psi->nConment++;

〃不是以"/*"开头，如果是以"〃"开头的注释，注释行数同样加1elseif(strcmp(strtmp,

7/")==o)

psi->nConment++;

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

else

psi->nCode++;

)

intStrFind(char*stringl/char*string2)

(

char*q=stringl;

q=strstr(q,string2);

18

if(q)

returnq-stringl;

else

return-1;

)

voidprint(Statlnfopsi)

(

printf(z/theresultsofanalysingprogramfile\"***.c\n:\n");printff^linesof

code:%d\n",psimCode);

printfj^lingsofcomments:%d\n”,psimComment);

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

printf(//code\tcomments\t\tspace\nw);

////

printf(%d%%\t%d%%\t\t%d%%\n/psi.nCode/psi.nLines/

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

//printfj^gradeA:excellentroutinexizestyle.\n");〃printf("gradeA:excellent

commentingstyle.'n");//printf("gradeA: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.编程统计文本单词的个数。基本要求如下：

19

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

的字符，初值设为false；

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

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

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

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

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

答：

include"stdio.h*'

main()

{charc,string[80];

inti,num=0,word=0;

FILE*fp=fopen(//file.txt7，rw)；

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

(

for(i=0;(c=string[i])!='\0';i++)

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

elseif(word==0)

{word=l;

num++;}

)

fclose(fp);

printf("Thereare%dwordintheline.\n",num);

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

链表中内容和比较次数。

答：

#include<stdio.h>

#include<stdlib.h>

typedefstructlist

(

intdata;

structlist*next;

}LIST;

voidmain()

(

LIST*head/*p,*q/*ln;

inti,j=l,num=O;

head=p=q=ln=NULL;

printf("lnputthe%dnumber:"J++);

scanf(”%d”,&i);

while(i!=-l)

20

(

if(head==NULL)

(

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

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

q>>data=i;

q->next=NULL;

head->next=q;

p=head->next;

)

else

(

ln=head;

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

{num++；

ln=p;

p=p->next;

)

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

q->data=i;

q->next=ln->next;

ln->next=q;

p=head->next;

)

printf("lnputthe%dnumber:",j++);

scanf(“％d”,&i);

)

p=head->next;

while(p!=NULL)

(

H

printf(%d"/p->data);

p=p->next;

)

printf("1btalcompara:%d\n”,num);

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

与5不能相连。

答：

publicclasstest

(

staticint[]a=newint[6];

publicstaticvoidsearch(intidx)

(

21

if(idx==6)

(

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

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

System.out.println("");

return;

)

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

(

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

continue;

if(idx!=l)

(

if((a[idx-l]==3&&i==5)11(a[idx-l]==5&&i==3))continue;

)

a[idx]=i;

search(idx+l);

)

)

publicstaticvoidmain(String[]args)

search(l);

10.编写一个简单的数学表达式解析程序。基本要求为：①能够解析用户输入的代数表达

式并求值；

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

答：

#defineStackjnit_size100

#defineStack_add10

include<iostream>

usingnamespacestd;

include<cstdlib>

include<cstring>

include<cctype>

include<cstdio>

typedefstruct{

char*base;

char*top;

intstacksize;

}SqStackl;

typedefstruct{

22

double*base;

double*top;

intstacksize;

}SqStack2;

voidlnitStack(SqStackl&S)

(

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

exit(l);

S.top=S.base;

S.stacksize=Stack_init_size;

return;

)

voidlnitStack(SqStack2&S)

(

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

exit(l);

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.base4S.stacksize+Stack_add)*sizeof(char));if(IS.base)

exit(l);

S.stacksize+=Stack_add;

*S.top++=e;

return;

)

voidPush(SqStack2&S,doublee)

(

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

(

S.base=(double

*)realloc(S.base4S.stacksize+Stack_add)*sizeof(double));if(IS.base)

exit(l);

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

23

S.stacksize+=Stack_add;

)

*S.top44-=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-l);

}

doubleGetlbp(SqStack2&S)

if(S.base==S.top)

return0;

return*(S.top-l);

boolln(charc)

(

if(c==V||c=='-J|c=='*J|C==71|c=='CI|c==，)'||c=='#'||c==，A，)

returntrue;

returnfalse;

)

doubletodouble(chars[])

(

doubleval,power;

inti=0,sign;

sign=(s[i]==',)？-1:1;

if(s[i]=='+'IIs[i]=='-')

24

i++；

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

(

val=val*10+(s[i]-'0')；

)

if(s[i]==7)

i++；

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

val=10.0*val+(s[i]-'01);power*=10;

)

returnsign*val/power;

)

doublepower(doublea,doubleb)

(

doubles=1.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，A':returnpower(a,b);

default:return0;

)

)

charPrecede(charmzcharn)

(

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

25

)；

charch[8]={'+','A')；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][j];

)

voidperfectfchars[])

(

charsl[100];

inti,j,n;

i=j=O;

if(s[O]=='-')

slU++]='O';

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

while(s[i])

(

if(s[i]=='->&&ln(s[i-l])&&s[i-l]!=,)')

sl[j++]='O';

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

)

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

)

slU]='\O'；

i=0;

while(sl[i])

s[i]=sl[i];

i++；

)

s[i]='\O';

)

doubleEvaluateExpression()

(

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

doublea,b;

inti,j=O,k=O;

chars[100];

gets⑸；

26

perfect(s);

SqStacklOPTR;〃寄存运算符

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

InitStack(OPTR);

InitStack(OPND);

Push(OPTR,'#');

while(sO]!='#'||GetTop(OPTR)!='#')

(

if(Hn(sUl))

(

i=0;

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

(

z[k][i++]=s[j++];

)

PushfOPND.todoublefztk]));

k++;

)

else

switch(Precede(GetTop(OPTR),s[j])){

case'<':Push(OPTR/s[j]);j++;break;

case'=':Pop(OPTR/x);j++；break;

case'>':Pop(OPTR,theta);

Pop(OPND,b);

Pop(OPND,a);

Push(OPND,Operate(a,theta,b));

break;

}

}

returnGetTop(OPND);

)

intmain()

(

primf(”％.2f\n”,EvahateExpression());

return0;

)

11.有一个多边形(N边形)，顶点上放整数，边上放"+”或“*”，要寻找一种逐次运算

合并的顺序，通过N-1次运算，使最后结果最大。

答：

programPolygon;｛“多边形"程序｝

var

｛输入、输出文件变量｝

27

n:integer;｛顶点个数｝

data:array[1..50]ofinteger;｛原始数据•顶点｝

sign:array[1..50]ofchar;｛原始数据■运算符｝

i,j,k,l:integer;｛辅助变量｝

t,s,p:integer;｛辅助变量｝

ans:setofL.50;｛可能达到最大值的第一次移动的边的序号｝

best:integer;｛当前最优解｝

minfmaxzarray[1..50,0..50]ofinteger;

｛动态规划表格，min[i川表示从第i个顶点开始，经过I个符号按合理运算所得的结果的最小

值；max与之类似，但为最大值｝

first:boolean;｛首次输出标志｝

procedureinit;｛初始化，读入原始数据｝

var

i:integer;

chxhar;

begin

readln(fl,n);

fori:=ltondo

begin

repeat

read(fl,ch);

untilcho;

sign[i]:=ch;｛sign[i]位于data回与其后顶点间｝

read(fl,data[i]);

end;

end;

begin

｛文件关联、打开｝

assign(fl,Polygon.in);

reset(fl);

assign(f2/Polygon.out);

rewrite(f2);

｛初始化｝

init;

｛赋初值｝

best:="maxint-l;

ans:=[];

fillchar(maxzsizeof(max),0);

28

fillchar(min,sizeof(min),0);｛数组初始化｝

forj:=ltondo

begin

max[j,O]:=data[j];

min[j,O]:=data[j];

end;｛初值是不经过运算(1=0)的值｝

forl:=lton-1do｛考虑长度由1到n-1｝

fork:=ltondo｛考虑起始点从1到n｝

begin

max[kj]:=-maxint-l;

min[kj]:=maxint;

fort:=0to1-1do｛考虑分开前半部分经过的运算数｝

begin

casesign[(k+t+l-l)modn+1]of｛考虑分开处的符号｝

t:｛为加法｝

begin

ifmax[k,t]+max[(k+t+l-l)modmax[k,l]:=max[k,t]+max[(k+t+l-l)mod

n+lj-t-l];

｛最大值更新｝

ifmin[k,t]+min[(k+t+l-l)modn+lj-t-l]<min[kj]min[k,l]:=min[k,t]+min[(k+t+l・l)mod

n+lj-t-l];

｛最小值更新｝

end;

x:｛为乘法｝

begin

forp:=lto4do

begin

casepof

1:s:=max[k/t]*max[(k+t+l-l)modn+l,l-t-l];

2:s:=max[k,t]*min[(k+t+l-l)modn+lj-t-l];

3:s:=min[k/t]*max[(k+t+l-l)modn+lj-t-l];

｛考虑四个乘积｝

4:s:=min[k/t]*min[(k+t+l-l)modend;

ifs>max[k,l]thenmax[k,l]:=s;

ifs<min[k,l]thenmin[k,l]:=s;｛更新最大最小值｝

end;

end;

end;

end;

end;

fori:=ltondo

ifmax[i/n-l]>bestthenbeginbest:=max[i,n-l];ans:=[i]endelseifmax[i,n-l]=bestthen

include(ans,i);｛更新全局的最大值｝29thenthen

writeln(f2,best);｛输出最大值｝

first:=true;

fori:=ltondo

ifiinansthen

begin

iffirstthenfirst:=false

elsewrite(f2,);

write(f2J);

end;

writeln(f2);｛输出首次被移动的边｝

close(fl);

close(f2)｛关闭文件｝

end.｛结束｝

12.正则表达式是一个个包含一般字符与广义字符的字符串。广义符包括：.代表任何字

符；

[C1-C2]代表任何位于cl和C2之间的字符(cl和c2是两个字符)；

[Acl-c2]代表任何不位于cl和C2之间的字符(cl和C2是两个字符)；*代表它之前的字

符可以出现任意多次，也可以不出现；

+代表它之前的字符可以出现任意多次且至少出现一次；

\代表它之后的任何一个字符应看作一般字符。

写一程序找出所给串中最左边的能够匹配所给正则表达式的子串。如果有多个子串能匹配

该正则表达式而且它们左边开始位置相同，则要求给出最长的子串。答：

programExpression_Match;｛正则表达式匹配程序｝

type

datatype=record｛预处理数据类型｝

st,ed:char;｛起始、结束字符｝

md:O..l;｛重复方式0：一次；1：。或多次｝

｛匹配方式0：不包含为匹配；1：包含为匹配｝

end;

var

fl,f2:text;｛文件变量｝

sl,s2:string;｛正则表达式串、待匹配串｝

str:string;

len:integer;｛正则表达式预处理后的“长度”｝

dd:array[1..80]ofdatatype;｛预处理结果｝

pro:array[0..80,0..80]ofboolean;｛动态规划数组｝

fr:array[0..80,0..80]ofbyte;

｛FR[川表示以第j个字符为尾的与前i项正则表达式匹配的最前端的字符位置｝

i,j,k,l:integer;｛辅助变量｝

ok:boolean;俄到标记｝

30

ha:boolean;

ans:integer;

bt,bj:integer;｛当前最优值的开始位置、长度｝

procedurepreprocess;｛预处理，生成规划的“正则表达式”表示｝var

ij,k：integer;

ch,c:char;

begin

i:=0;

j：=0;

whilei<length(sl)do

begin

inc(i);

casesl[i]of

begin｛处理)

inc(j);

dd[j].md:=0;

dd[j].mt:=l;

dd[j].st:=#O;

ddU].ed:=#255;

end;

*:dd[j].md:=l;｛处理…｝

+:｛处理)

begin

inc(j);

ddD]:=dd[j-l];

dd[j].md:=l;

end;

\:｛处理“\"｝

begin

inc(i);

inc(j);

dd[j].md:=0;

dd[j].mt:=l;

dd[j].st:=sl[i];

dd[j].ed:=sl[i];

end;

[:｛处理｝

begin

inc(i);

inc(j);

dd[j].md:=O;

dd[j].mt:=l;

31

ifsl[i]=Athenbegininc(i);dd[j].mt:=Oend;｛如果含“八”｝ifsl[i]=\theninc(i);

dd[j].st:=sl[i];

inc(i,2);

ifsl[i]=\theninc(i);

dd[j].ed:=sl[i];

inc(i);

end

else

begin｛处理一般字符｝

inc(j);

dd[j].st:=sl[i];

dd[j].ed:=sl[i];

dd[j].mt:=l;

dd[j].md:=O;

end;

end;

end;

len:=j

end;

begin

assign(fl,Match,in);

reset(fl);

assign(⑵Match,out);

rewrite(f2);｛文件关联、打开｝

whiletruedo

begin

readln(fl,sl);

ifsl=endthenbreak;｛如果为end串,跳出｝

readln(fl,s2);

preprocess;｛预处理｝

ok:=false;｛标记未找到｝

fillchar(pro,sizeof(pro),false);

fHlchar(pro[0],sizeof(pro[0]),true);

fillchar(fGsizeof(fr),0);

bt:=maxint;

bj:=O;

fori:=0toIength(s2)do｛赋初值｝

fr[OJ]:=i+l;

fori:=ltolendo｛分析前i项正则表达式｝

forj:=ltoIength(s2)do｛分析前j个字符｝

32

begin

ifdd[i].md=0then｛如果最后一个是一般字符｝

if(dd[i].mt=O)xor(s2[j]in[dd[i].st..dd[i].ed])｛如果匹配｝then

begin

pro[i,