阅读下列函数说明和c代码，将应填入（n)处的字句写在对应栏内。

【说明】

函数void rcr(int a[]，int n，int k)的功能是：将数组a中的元素s[0]～9[n-1]循环向右平移k个位置。

为了达到总移动次数不超过n的要求，每个元素都必须只经过一次移动到达目标位置。在函数rcr中用如下算法实现：首先备份a[0]的值，然后计算应移动到a[0]的元素的下标 p，并将a[P]的值移至a[0]；接着计算应移动到a[p]的元素的下标q，并将a[q]的值移至 a[p]；依次类推，直到将a[0]的备份值移到正确位置。

若此时移动到位的元素个数已经为n，则结束；否则，再备份a[1]的值，然后计算应移动到a[1]的元素的下标p，并将a[p]的值移至9[1]；接着计算应移动到a[p]的元素的下标q，并将a[q]的值移至a[p]；依次类推，直到将a[1]的备份值移到正确位置。

若此时移动到位的元素个数已经为n，则结束；否则，从a[2]开始，重复上述过程，直至将所有的元素都移动到目标位置时为止。

例如，数组a中的6个元素如图1(a)所示，循环向右平移两个位置后元素的排列情况如图1(b)所示。

void rcr( int a[] ,int n,int k)

{ int i,j,t,temp,count;

count =0; /*记录移动元素的次数*/

k=k%n;

if((1)){ /*若k是n的倍数,则元素无须移动;否则,每个元素都要移动*/

i=0

while(count＜n) {

j=i;t=i;

temp =a[1]; /*备份a[i]的值*/

/*移动相关元素，直到计算出a[i]应移动到的目标位置*/

while((j=(2))! =i){

a[t]=a[j];

t=(3);

count++;

}

(4)= temp;count ++;

(5);

}

}

}

【说明】

某公司的用品采购流程如下所述。

(1)由营业部门提出需求用品清单。

(2)将需求用品清单交采购部门建立采购采买单据。

(3)采购部门建立采购采买单据后，交财务部门，向财务部申请款项，预支定金。

(4)财务部建立应付帐款单据后，核支款项。

(5)采购部门再收到款项后，进行采买。

(6)采买完成，执行：

①发票核剩余款项交财务部，即由财务部门处理。

②用品点交营业部门发放，即由营业部门处理。

(7)进行财务结算处理，执行：

①采购部门：采购单据结案。

②财务部门：帐款冲销结案。

【问题】

完成下面的UML活动图对象流分析，1～11为活动，设计此采购活动的流程。

【说明】

设有一个带表头结点的双向循环链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次L.Locate(x)操作时，令元素值x的结点的访问频度 freq加1，并将该结点前移，链接到现它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。

【函数】

void Locate( int &x)

{ ＜结点类型说明＞

* p =first -＞ next;

while(p!=frist&&(1))P=P-＞next;

if(p! =first) /*链表中存在x*/

{(2);

＜结点类型说明＞

* current = P; /*从链表中摘下这个结点*/

Current -＞ prior -＞ next = current -＞ next;

Current -＞ next -＞ prior = current -＞ prior;

P = current -＞ prior; /*寻找重新插入的位置*/

While(p! =first &&(3))p=p-＞prior;

Current-＞ next =(4); /*插入在P之后*?

Current -＞ prior = P;

P -＞ next -＞ prior = current;

P-＞next=(5);

}

else printf("Sorry. Not find! \n"); /*没找到*/

}

【说明2.1】

L为一个带头结点的循环链表。函数deletenode(LinkList L, int c)的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。

【函数2.1】

LinkList deletenode(LinkList L, int c)

{

LinkList Lc,p,pre;

pre=L;

p=(1);

Lc=(LinkList)malloc(sizeof(ListNode) );

Lc-＞next=Lc

while(p!=L)

if(p-＞data＞c)

{

(2);

(3);

Lc-＞next=p;

p=pre-＞next;

}

else

{

pre=p;

p=pre-＞next;

}

return Lc;

}

【说明2.2】

递归函数dec_to_k_2(int n, int k)的功能是将十进制正整数n转换成k＜2≤k≤9)进制数，并打印。

【函数2.2】

dec_to_k_2(int n, int k)

{ /*将十进制正整数n转换成k(2≤k≤9)进制数*/

if(n!=0)

{

dec_to_k_2((4),k);

printf("%d",(5));

}

}

【说明】

所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。

应用贪婪法求解该问题。程序先计算由各点构成的所有边的长度(作为边的权值)，按长度大小对各边进行排序后，按贪婪准则从排序后的各边中选择边组成回路的边，贪婪准则使得边的选择按各边长度从小到大选择。

函数中使用的预定义符号如下：

define M 100

typedef struct{/*x为两端点p1、p2之间的距离，p1、p2所组成边的长度*/

float x;

int p1, p2;

}tdr;

typedef struct{/*p1、p2为和端点相联系的两个端点，n为端点的度*/

int n, P1, p2;

}tr;

typedef struct{/*给出两点坐标*/

float x,y;

}tpd;

typedef int tl[M];

int n=10;

【函数】

float distance(tpd a,tpd b);/*计算端点a、b之间的距离*/

void sortArr(tdr a[M], int m);

/*将已经计算好的距离关系表按距离大小从小到大排序形成排序表，m为边的条数*/

int isCircuit(tr[M], int i, int j);

/*判断边(i, j)选入端点关系表r[M]后，是否形成回路，若形成回路返回0*/

void selected(tr r[M], int i, int j);/*边(i,j)选入端点关系表r*/

void course(tr r[M], tl 1[M]);/*从端点关系表r中得出回路轨迹表*/

void exchange(tdr a[M], int m, int b);

/*调整表排序表，b表示是否可调，即是否有边长度相同的边存在*/

void travling(tpd pd[M], int n, float dist, t1 locus[M])

/*dist记录总路程*/

{

tdr dr[M];/*距离关系表*/

tr r[M];;/*端点关系表*/

int i, j, k, h, m;/*h表示选入端点关系表中的边数*/

int b;/*标识是否有长度相等的边*/

k=0;

/*计算距离关系表中各边的长度*/

for(i=1;i＜n;i++){

for(j=i+1;j＜=n;j++){

k++;

dr[k].x=(1);

dr[k].p1=i;

dr[k].p2=j;

}

}

m=k;

sortArr(dr,m);/*按距离大小从小到大排序形成排序表*/

do{

b=1;

dist=0;

k=h=0;

do{

k++;

i=dr[k].p1;

j=dr[k].p2;

if((r[i].n＜=1)&&(r[j].n＜=1)){/*度数不能大于2*/

if((2)){

/*若边(i，j)加入r后形成回路，则不能加入*/

(3);

h++;

dist+=dr[k].x;

}else if((4)){

/*最后一边选入r成回路，则该边必须加入且得到解*/

selected(r,i,j);

h++;

&n

[说明]

函数Printprime(int UpBound)的功能是输出1到UpBound以内的全体素数。

[函数2.1]

void PrintPrime(int UpBound)

printf("2," );

for(i=3; i＜UpBound; i+ =2) {

int k = sqrt(i);

for(j=3; j＜= k;(1)) /*检查i是否有3到k以入的奇因数*/

if((2)) break;

fi((3)) printf("%d", i);

[函数2.2说明]

递归函数invert(int a[],int k)，int k)的功能是将数组a中的前k个元素逆置。

[函数2.2]

void invert(int a[ ], int k)

{ int t;

if ((4)) {

invert((5));

t=a[0];

a[0] =a[k-1];

a[k-l]=t;

}

}

[说明]

在一些大型系统中，大多数的功能在初始化时要花费很多时间，如果在启动的时候，所有功能(包括不用的功能)都要全面初始化的话，会导致应用软件要花很多时间才能启动。因此常将程序设计成到了实际要使用某种功能的阶段才初始化该功能。

以下示例展示了Proxy(代理)模式，PrinterProxy类执行一些比较“轻”的方法，需要真正执行“重”的方法时才初始化Print类。图5-1显示了各个类间的关系。

[图5-1]

[C++代码]

class Printable{

public：

virtual void setPrinterName(string name)=0；

virtual string getprinterName()=0；

virtual void print(string name)=0；

}；

class Printer：public Printable{

private：

string name；

public：

Printer(string name){

cout＜＜"正在产生Printer的对象实例"＜＜endl；

this－＞name=name；

}

void setPrinterName(string name){

this-＞name=name；

}

string getPrinterName(){

return name；

}

void print(string msg){

cout＜＜"======="＜＜name＜＜"==========="＜＜endl；

cout＜＜msg＜＜endl；

}

}；

class printerproxy ：public (1) {

private：

String name；

Printer *real；

public：

PrinterProxy(string name){

(2)=NULL；

this-＞name=name；

}

void setPrinterName(string name){

if((3))real-＞setPrinterName(name)；

this-＞name=name；

}

string getPrinterName(){

return name；

}

void print(string msg){

(4)；

real-＞print(msg)；

}

void realize(){

if(real==NULL)real=(5)；

}

}；

(1)

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

【说明】

函数move(int*a，int n)用于整理数组a［］的前n个元素，使其中小于0的元素移到数组的前端，大于0的元素移到数组的后端，等于0的元素留在数表中间。

令a［0］~a［low-1］小于0(初始为空)；a［low］~a［i-1］等于0(初始为空)；a［i］~a［high］还未考察，当前考察元素为a［i］。a［high+1］～a［n-1］大于0(初始为空)。

【函数】

move(int*a，int n)

{

int i，low，high，t；

low=i=0；high=n-1；

while( (1) )

if(a［i］<0)

{

t=a［i］；a［i］=a［low］；a［low］=t；

(2) ；i＋＋；

}

else if( (3) )

{t=a［i］；a［i］=a［high］；a［high］=t；

(4) ；

}

else (5) ；

}

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

【说明】

函数print(BinTreeNode*t；DateType ＆x)的功能是在二叉树中查找值为x的结点，并打印该结点所有祖先结点。在此算法中，假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。因为退栈时需要区分右子树。函数中使用栈ST保存结点指针ptr以及标志tag，Top是栈顶指针。

【函数】

void print(BinTreeNode*t；DateType ＆x){

stack ST；int i，top；top=0；∥置空栈

while(t!=NULL ＆＆t->data!=x‖top!=0)

{while(t!=NULL ＆＆ t->data!=x)

{

∥寻找值为x的结点

(1) ；

ST［top］．ptr=t；

ST［top］．tag=0；

(2) ；

}

if(t!=Null ＆＆ t->data==x){∥找到值为x的结点

for(i=1； (3) ；i＋＋)

printf("％d"，ST［top］．ptr->data)；}

else{

while( (4) )

top--；

if(top>0)

{

ST［top］．tag=1；

(5) ；

}

}

}

【说明】

函数int Toplogical(Linded WDipaph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE-网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下：

typedefstruct Gnode{ /* 邻接表的表结点类型*/

iht adjvex; /* 邻接顶点编号*/

iht weight; /* 弧上的权值*/

street Gnode *nextarc; /* 指示下一个弧的结点*/

}Gnode;

typedef struct Adjlist{ /* 邻接表的头结点类型*/

char vdata; /*顶点的数据信息*/

struct Gnode *Firstadj; /* 指向邻接表的第一个表结点*/

}Adjlist;

typedef street LinkedWDigraph{ /* 图的类型*/

int n, e; /* 图中顶点个数和边数*/

struct Adjlist *head; /*指向图中第一个顶点的邻接表的头结点 */

} LinkedWDigraph;

例如，某AOE-网如图5-1所示，其邻接表存储结构如图5-2所示。

【函数】

iht Toplogical(LinkedWDigraph G)

{ Gnode *p;

intj, w, top = 0;

iht *Stack, *ye, *indegree;

ye = (int *)malloe((G.n+1) * sizeof(int));

indegree = (int *)malloc((G.n+1)*sizeof(int)); /* 存储网中各顶点的入度*/

Stack = (int *)malloe((G.n+1)*sizeof(int)); /* 存储入度为0的顶点的编号*/

if(!ve||!indegree || !Stack) exit(0);

for (j = 1;j ＜= G.n;j++) {

ve[j] = 0; indegree[j]= 0;

}/*for*/

for(j= 1;j<=G.n;j++) { /* 求网中各顶点的入度*/

p = G.head[j].Firstadj;

while (p) {

(1); p = p→nextarc;

}/*while*/

}/*for*/

for (j = 1; j ＜= G.n; j++) /*求网中入度为0的顶点并保存其编号*/

if (!indegree[j]) Stack[++top] =j;

while (top ＞ 0) {

w=(2);

printf("%e ", G.head[w].vdata);

p = G.head[w].Firstadj;

while (p) {

(3);

if ( !indegree [p→adjvex])

Staek[++top] = p→adjvex;

if( (4))

ve[p→adjvex] = ve[w] + p→weight;

p = p→nextarc;

}/* while */

}/* while */ return (5); }/*Toplogieal*/