读流程图写程序

[说明]

假定用一个整型数组表示一个长整数，数组的每个元素存储长整数的一位数字，则实际的长整数m表示为：

m=a[k]×10k-2+a[k-1]×10k-3+…+a[3]×10+a[2]

其中a[1]保存该长整数的位数，a[0]保存该长整数的符号：0表示正数、1表示负数。注：数组下标从0开始。

流程图(图4-1)用于计算长整数的加(减)法。运算时先决定符号，再进行绝对值运算。对于绝对值相减情况，总是绝对值较大的减去绝对值较小的，以避免出现不够减情况。注，此处不考虑溢出情况，即数组足够大。这样在程序中引进两个指针pA和pB，分别指向绝对值较大者和较小者。而对绝对值相加,情况，让pA指向LA，pB指向LB，不区分绝对值大小。pA±pB可用通式pA+flag*pB来计算，flag为+1时即对应pA+pB，flag为-1时即对应pA-pB。需特别注意的是，对于相减，不够减时要进行借位，而当

最高位借位后正好为0时，结果的总位数应减1；对于加法，有最高进位时，结果的总位数应加1。

流程图中涉及的函数说明如下：

(1)cmp(int *LA，int *LB)函数，用于比较长整数LA与LB的绝对值大小，若LA绝对值大于LB绝对值则返回正值，LA绝对值小于LB绝对值返回负值，相等则返回0。

(2)max(int A，int B)函数，用于返回整数A与B中较大数。

另外，对流程图中的写法进行约定：(1)“：=”表示赋值，如“flag：=LA[0]+LB[0]”表示将“LA[0]+LB[0]”的结果赋给flag，相当于C中的赋值语句：“flag=LA[0]+LB[0]；”；(2)“：”表示比较运算，如“flag：1”表示flag与1比较。

(1)

[说明]

当一元多项式中有许多系数为零时，可用一个单链表来存储，每个节点存储一个非零项的指受和对应系数。

为了便于进行运算，用带头节点的单链表存储，头节点中存储多项式中的非零项数，且各节点按指数递减顺序存储。例如：多项式8x5-2x2+7的存储结构为：

流程图图3-1用于将pC(Node结构体指针)节点按指数降序插入到多项式C(多项式POLY指针)中。

流程图中使用的符号说明如下：

(1)数据结构定义如下：

define EPSI 1e-6

struct Node{ /*多项式中的一项*/

double c； /*系数*/

int e； /*指数*/

Struct Node *next；

}；

typedef struct{ /*多项式头节点*/

int n； /*多项式不为零的项数*/

struct Node *head；

}POLY；

(2)Del(POLY *C，struct Node *p)函数，若p是空指针则删除头节点，否则删除p节点的后继。

(3)fabs(double c)函数返回实数C的绝对值。

[图3-1]

(1)

阅读以下说明和流程图(如图1所示)，回答问题1至问题4，将答案写在答卷的对应栏内。

【说明】

本流程图是将中缀表示的算术表达式转换成后缀表示。如中缀表达式

(A-(B*C+D)*E)/(F+G))

的后缀表示为

ABC*D+E*-FG+/

为了方便，假定变量名为单个英文字母，运算符只有+、-、*、/(均为双目运算符，左结合)，并假定所提供的算术表达是非空且语法是正确的。另外，中缀表示形式中无空格符，但整个算术表达式以空格符结束。流程图中使用的符号的意义如下：

数组IN［］存储中缀表达式；

数组POLISH［］存储其后缀表达式；

数组S［］是一个后进先出栈；

函数PRIOR(CHAR)返回符号CHAR的优先级，各符号的优先级见表2：

【问题1】

填充流程图中①的判断条件。

【问题2】

写出子程序A的功能，并顺序写出实现该功能的操作

【问题3】

写出子程序B的功能，并顺序写出实现该功能的操作。

【问题4】

中缀表达式

(A+B-C*D)*(E-F)/G

经该流程图处理后的输出是什么？

【流程图】

图1

[说明]

分糖果问题是一个经典问题。问题描述如下：幼儿国有n(＜20)个孩子围成一圈分糖果，老师先随机地发给每个孩子若干颗糖果，然后按以下规则调整：每个孩子同时将自己手中的糖果分一半给坐在他右边的小朋友；如共有8个孩子，则第1个将原来的一半分给第2个，第2个将原有的一半分给第3个……第8个将原来的一半分给第1个，这样的平分动作同时进行；若平分前，某个孩子手中的糖果是奇数颗，则必须从老师那里要一颗，使他的糖果变成偶数。小孩人数和每个小孩的初始数由键盘输入。经过多少次调整，使每个孩子手中的糖果一样多，调整结束时每个孩子有糖果多少颗，在调整过程中老师又新增发了多少颗糖果。

[C程序]

include ＜stdlib.h＞

include ＜stdio.h＞

bool allequall (int child[], int n ) //判断各小孩子手中的糖果是否相等

{

for ( int i=0; i＜n-1; i++)

if (child[i]!=child[i+1] )

return false; //不相等返回假

return true; //相等返回真

}

const int MaxNum=20; //定义最大人数

//主函数

void main ( )

{

int Num=0;

int *child;

int *child1;

//构造两个相应大小的数组child代表小朋友现有的粮果数child1代表小朋友原来有的糖果数

int Tnum=0;

int i=0;

do{

printf ( "Pelase input the number of the children: ").,

scanf ( "%d",&Num );

if ( Num＞MaxNum )

printf ( "Error Number!!" );

} while ( Num＞MaxNum );

child=new int [Nmn];

child1=new int [Num];

for ( i=0; i＜Num; i++ ) //将数组赋值

{

printf ( "Input NO. %d child's candy numbers: ",i+1);

scanf ( "%d", &child[i] );

}

while ( (1) )

{

for (i=0; i＜Num; i++ )

{

if( (2) )

{

(3)

Tnum++;

}

}

for ( i=0; i＜Num; i++ )

child1[i]=child[i]; //将child1赋值用来记忆原来小朋友的粮果数

for ( i=0; i＜Nam; i++ )

(4)

for (i=0; i＜Num-1; i++)//用循环实现前一个小朋友粮果数加后一个小朋友粮果数的一半

{

child[i]/=2;

child[i]+=child 1 [i+1];

}

child[Num-1]/=2;

(5)

}

printf ( "每个同学最后分到糖果数目是%d\n", child[1]);

printf ( "老师分发出的糖果是%d\n", Tnum );

}

图12-7是一种解决问题的流程图，请根据该流程图将对应C代码(n)处补充完整。

【说明】

已知头指针分别为La和lb的有序单链表，其数据元素都是按值非递减排列。现要归并La和Lb得到单链表Lc，使得Lc中的元素按值非递减排列。程序流程图如下所示：

阅读下列说明和流程图，将应填入(n)的语句写在答题纸的对应栏内。

【流程图】

图1

下面的流程图描述了对16位二进制整数求补的算法。计算过程是：从二进制数的低位(最右位)开始，依次向高位逐位查看，直到首次遇到"1"时，停止查看。然后，对该"1"位左面的更高位(如果有的话)，逐位求反，所得的结果就是对原二进制数求补的结果。

例如：对二进制整数10111001 10101000求补的结果是01000110 01011000。

设16位二进制整数中的各位，从低位到高位，依次存放在整型数组BIT的BIT［1］～BIT［16］中。例如，二进制整数10111001 10101000存放在数组BIT后，就有BIT1［1］=0，BIT［2］=0，……，BIT［15］=0，BIT［16］=1。

流程图(如图1所示)中 (1) 处按"循环变量名：循环初值，增量，循环终值"格式描述。若流程图中存在空操作，则用NOP表示。

【流程图说明】

下图所示的流程图5.3用N-S盒图形式描述了数组Array中的元素被划分的过程。其划分方法；以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于Array[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。

【算法说明】

将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int Array[]，int low，int high)实现了上述流程图的划分过程并返回基准数在数组Ar ray中的下标。递归函数void sort(int Array[]，int L，int H)的功能是实现数组Array中元素的递增排序。

【算法】

void sort(int Array[]，int L，int H){

if (L＜H) {

k=p(Array，L，H)；/*p()返回基准数在数组Array中的下标*/

sort((4))；/*小于基准数的元素排序*/

sort((5))；/*大于基准数的元素排序*/

}

}

阅读下列说明和流程图，将应填入(n)的语句写在答题纸的对应栏内。

【流程图说明】

下面的流程(如图1所示)用N-S盒图形式描述了在一棵二叉树排序中查找元素的过程，节点有3个成员：data，left和right。其查找的方法是：首先与树的根节点的元素值进行比较：若相等则找到，返回此结点的地址；若要查找的元素小于根节点的元素值，则指针指向此结点的左子树，继续查找；若要查找的元素大于根节点的元素值，则指针指向此结点的右子树，继续查找。直到指针为空，表示此树中不存在所要查找的元素。

【算法说明】

【流程图】

将上题的排序二叉树中查找元素的过程用递归的方法实现。其中NODE是自定义类型：

typedef struct node{

int data；

struct node*left；

struct node*right；

}NODE；

【算法】

NODE*SearchSortTree(NODE*tree，int e)

{

if(tree!=NULL)

{

if(tree->data<e)

(4) ；∥小于查找左子树

else if(tree->data<e)

(5) ；∥大于查找左子树

else return tree；

}

return tree；

}

[说明]

下面的流程图(如图3所示)用N - S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为 low，上界为high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以4为基准数的划分过程如下：

[流程图]

[算法说明]

将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int A[]，int low，int hieh)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[]，int L，int H)的功能是实现数组A中元素的递增排序。

[算法]

void sort(int A[]，int L，int H) {

if (L＜H) {

k=p(A，L，R)； //p()返回基准数在数组A中的下标

sort((4))； //小于基准敷的元素排序

sort((5))； //大于基准数的元素排序

}

}

【说明】

(1)流程图描述某大型商店商品销售的数据处理流程。

(2)商店设有若干柜台，同一种商品可能在几个柜台上销售，各柜台每天提供一组日销售数据，其格式如下：

日期、柜台号、商品代码、销售数量、商品代码、销售数量……

(3)数据处理系统每日产生一份反映各柜台当日销售金额和商店日销售金额的“日销售金额报告”，必要时还产生一份“商品请购报告”，给出那些低于最低库存量的商品代码、商品名称、最低库存量和实际库存量。处理过程中产生存档的“日销售文件”和临时工作文件“日销售量文件”和“旧销售金额文件”。

(4)系统中所用到的数据均来自数据文件。

(5)流程图中的商品库存文件的记录已按关键字“商品代码”排序。

①指出商品库存文件的记录中必须包括哪些数据项?

②分别指出在日销售文件，日销售量文件和日销售金额文件的记录中至少应包括哪些数据项，同时不产生数据冗余?

③错误清单可能指出哪些错误?