96年C题精解.doc

试题9（1996年试题5）阅读以下程序说明和C程序，将应填入程序中_(n)_处的字句，写在答卷的对应栏内。【程序说明】本程序是一个简单的计算器模拟程序。对任意给定的正确四则运算表达式，程序计算其结果值并输出。表达式中运算分量为无正负号整数，运算符为+、_、*、/，圆括号按常规配对，表达式以字符=结束。函数getach()为获取表达式的一个合法自负，并将字符存入变量curch；函数指针树组func是为了统一加减乘除计算而设置的。【程序】#include int add(int x,int y)return x+y;int sub(int x,int y)return x-y;int mul(int x,int y)return x*y;int div(int x,int y)return x/y;int (*func)()=add,sub,mul,div;int num,curch;char chtbl=+-*/()=;char corch=+-*/()=0123456789;int getach() int i;while(1) curch=getchar();if(curch=EOF) return -1;for(i=0;corchi&curch!=corchi;i+);if(i=0&curch=0&curch=9;getach()num=_;return -1;elsefor(i=0;chtbli;i+)if(chtbli=curch) break;if(i=5) return x1;i=getid();if(I=4) x2=cal(); else x2=num;op2=getid();while(_) i=getid();if(i=4) x3=cal(); else x3=num;if(op1/2=0)&(op2/2=1)x2=(*funcop2(x2,x3);else x1=_;x2=x3;_;op2=getid();return _(x1,x2);void main() int value;printf(Please input an expression:n);getch();while(curch!=) value=cal();printf(The result is : %dn,value);printf(Please input an expression:n);getach();解析本程序是一个简单的计算器模拟程序，对值得任给的正确的四则运算表达式，程序计算其结果值并输出。程序由一个主程序和数个子程序组成。主程序的功能比较简单。输入一个表达式，计算其结果并输出，然后输入下一个表达式。4个计算子程序add、sub、mul、div和输入字符子程序getach都很简单，这里不再浪费笔墨。 getid子程序的功能是判断刚才输入的字符是操作数不是运算符。程序使用了一个if语句，若读入的字符是0到9之间的，则是操作数，那么继续将该操作数全部读进来（因为操作数也是以字符方式读进来的，因此一个操作数需要分为多个字符读进来，然后再装配成一个操作数），并将其值保存至全局变量num中。读入字符的顺序是先高位后低位，因此读入的数字字符要按照由高位到低位的顺序依次转化为一个数，所以填空（1）的答案为num*10+curch-0。若读入的字符不是数字，那么要判断一个是哪个运算符，不同的运算符返回不同的值。cal子程序是本题的关键所在。它比较复杂，使用了递归算法。它的功能是：首先判断已经输入的字符，若是（则根据括号优先的原则，先递归调用自己，求出括号里的表达式的值，否则是操作数（本程序无查错功能，假定所输入的都是正确的四则运算表达式，这样一个表达式的开头不是括号就肯定是操作数），将其值从全局变量num赋给x1。接着读入一个运算符，若运算符是）或，则完成一级运算，返回结果x1。读入第2个操作数，同上，若读入的字符是（，则根据括号优先的原则，先递归调用自己，求出括号里的表达式的值，否则将其值赋给操作数x2。然后读入第2个运算符。下一步的操作应当是先读入第3个操作数，再根据op1和op2的优先级决定进行运算op1还是op2，并将计算结果作为操作数x1或x2，继续后计算。循环的结束条件是遇到）或，说明一对括号内的计算完成整个计算结束。因此，填空（2）的答案为op2=0)&(op25) 或 op25 或 op2=5)（3）(*funcop1(x1, x2)（4）op1=op2（5）(*funcop1)试题10（1996年试题7）阅读下列程序说明和C程序，将应填入程序中(n)处的字句，写在答卷纸的对应栏内。【程序说明】本程序先从文件读入各考生的准考证号（设为整型数）及成绩，并将其存放在一棵检索二叉树上，二叉树的结点的键值是成绩，二叉树每个节点带一链表，链表结点存放取得该成绩的考生的准考证号。然后，程序按中序遍历检索二叉树，从高到底分输出结果，使每行输出某成绩及其取得该成绩的各考生的准考证号。【程序】#include typedef struct idnodeint id;struct idnode *next;IdNode;typedef struct marknodeint mark;IdNode *head;struct marknode left,right;MarkNode;char fname=sp07.datmain() int id,mark;MarkNode *root=null;FILE *fp=fopen(fname,r);if(!fp)printf(file %s open error.n,fname);exit(0);while(!feof(fp)fscanf(fp,%d%d,&id,&mark);btree(&root,id,mark);fclose(fp);print(root);btree() IdNode *ip;MarkNode *mp=mpptr;if(_)if(mark=mp-mark) addIdNode(_,id);else if(markmp-mark) btree(&mp-left,id,mark);else btree(&mp-right,id,mark);else mp=(MarkNode *)malloc(sizeof(MarkNode);mp-mark=mark;mp-left=mp-right=NULL;_addIdNode(&mp-head,id);_addIdNode(IdNode *ipp,int id) IdNode *ip=ipp;if(_) addIdNode(_,id);elseip=(IdNode *)malloc(sizeof(IdNode);sp-id=id;ip-next=NULL;_print(MarkNode *mp) IdNode *ip,ip0;if(mp)print(mp-left);printf(%6d: t,mp-mark);ip=mp-head;while(ip)printf(%6d: t,ip-id);ip0=ip;ip=ip-next;free(ip0);printf(n);print(mp-right);free(mp); 解析本程序着重考查对检索二叉树、链表的基本操作及双重指针的用法等知识点的掌握。二叉树或者为空，或者由一个根结点加上左子树和右子树（互不相交的两棵二叉树）组成。检索二叉树左子树的每一个结点的值都小于（或大于根结点的值，右子树的每一个结点的值都大于（或小于）根结点的值，其左子树和右子树也是检索二叉树。双重指针是指向指针的指针，它的值是一个指针的地址。大致浏览一个程序，程序主要由一个主程序和3个函数btree、addidNode、print组成。主程序的功能比较简单。打开一个文件，循环读出文件中的每一条记录，并将该记录的内容存放在一棵检索二叉树上，所有的记录读完以后，再将该检索二叉树打印出来。程序最重要的地方是在函数btree中，btree的功能是将一个新的标点插入检索二叉树中，它有3个参数，mpptr是检索二叉树的根结点，id和mark是从数据文件中读入的准考证号和成绩。检索二叉树的插入算法是若二叉树的根结点为空，则创建一个根结点，给其赋上相应初值，否则判断根结点的键值与所给的值的大小。结果可能有3种：所给值大小根，则递归检索根的左子树，即在左子树上插入新的结点；所给值等于根结点值，结点已存在；所给值小于结点值，则递归检索根的右子树，即在右子树上插入新的结点。 根据检索二叉树的插入算法，分析btree的算法。题中if(1) else 的结构，对应于检索二叉树的插入算法中判断根结点是否为空的算法。因而填空（1）应为mp!=NULL。若根结点不空，则：若所给mark与根结点的mark值相等，就需要在根结点的id链表上增加一个结点，调用函数addidNode实现这一功能，因此，填空（2）所在的语句为addidNode(&mp-head,id)；若所给mark大于根结点的mark值，则需要将该记录插入在根结点的左子树上，递归调用函数btree实现这一功能；若所给mark小于根结点的mark值，则需要将该记录插入在根结点的右子树，递归调用函数btree实现这一功能。若根结点为空，则创建一个根结点，给其赋上相应初值，赋给其mark值，初始化其左右子树为空，初始化其id链表为空，所以填空（3）答案为mp-head=NULL。此时，插入工作id尚未完成，该考生尚未保存，再调用函数addldNode将该考生的id插入到该结点的id链表中。最后，应将临时指针mp赋回给根结点，所以填空（4）的答案为*mpptr=mp。函数addidNode与btree有些类似，该函数也是一个递归函数，它与btree的不同在于它是在一个线性链表上操作，而btree是在一个检索二叉树上操作。addIdNode的功能是在一个链表尾部插入一个结点。它的算法也是先判断结点是否为空，若不空，则需递归在其next结点上插入，所以函数addidNode中填空（5）的答案为ip!=NULL，（6）的答案为addIdNode(&p-next,id)，即将结点插入到当前链表的下一结点所带链表的后面；若为空，则需要新建一结点，初始化其next为空，赋给其id值。若ip为空，并将临时指针ip赋回给原来的指针，所以填空（7）的答案为*ipp=ip。程序最后根据已经建好