问答题[说明]设有一张学生成绩表scores存放在Access数据库Student中，其中包括学生编号、姓名以及各科目考试成绩。下面的应用程序利用ADOData和DataGrid控件实现了对成绩数据的基本管理，其操作包括：(1)添加新记录：单击“添加”按钮，光标将指向最后一条数据记录，在其后编辑好新的数据记录后，再单击“更新”按钮，该数据即被加入成绩表；(2)删除记录：单击“删除”按钮将删除当前所指记录，其后的数据记录依次上移；(3)更新记录：直接编辑某条已有记录，再单击“更新”按钮将更新成绩表；(4)记录排序：选中单列字段后，单击“排序”按钮，记录集将按该字段升序排列。程序的运行界面为：在开发过程中，数据库连接对象使用了名为Adodc1的ADOData控件，数据显示区域使用了名DataGnd1的DataGrid控件，界面上从左到右各操作按钮分别取名为CmdAdd、CmdDel、CmdUpdate、CmdRefresh、CmdSort和CmdExit。[VisualBasic代码]Dimconn,database,tableAsStringPrivateSubForm_Load()database="E:/Student.mdb"’设置要访问的数据库conn="Provider=Microsoft.Jet.OLEDB.4.0;DataSouse="&databaseAdodc1.ConnectionString=conn’设置连接字符串table="scores"Adode1.{{U}}(1){{/U}}=table’设置所要访问的数据表SetDataGrid1.{{U}}(2){{/U}}=Adodc1EndSubPrivateSubCmdAdd_Click()’“添加”按钮的单击事件响应过程Adodc1.Recordset.{{U}}(3){{/U}}EndSubPrivateSubCmdDel_Click()’“删除”按钮的单击事件响应过程Adodc1.Recordset.DeleteAdodc1.Reeordset.MoveNextEndSubPrivateSubCmdUpdate_Click()’“更新”按钮的单击事件响应过程Adode1.Reeordset.UpdateBatchadAffectAllEndSubPrivateSubCmdRefresh_Cliek()’“刷新”按钮的单击事件响应过程Adodc1.RefreshEndSubPrivateSubCmdSort_Cliek()’“排序”按钮的单击事件响应过程IfDataGrid1.SelStartCol＜0OrDataGridl.SelStartCol{{U}}(4){{/U}}DataGrid1.SelEndColThenMsgBox“请选择某一字段(列)!”ExitSubEndIfAdodc1.RecordSource="SELECT*FROM"&table&"orderby"&_DataGrid1.Columns({{U}}(5){{/U}}).DataFieldAdodc1.RefreshEndSubPrivateSubCmdExit_Click()’“退出”按钮的单击事件响应过程EndEndSub

问答题[说明] Kruskal算法是一种构造图的最小生成树的方法。设G为一无向连通图，令T是由G的顶点构成的于图，Kmskal算法的基本思想是为T添加适当的边使之成为最小生成树：初始时，T中的点互相不连通；考察G的边集E中的每条边，若它的两个顶点在T中不连通，则将此边添加到T中，同时合并其两顶点所在的连通分量，如此下去，当添加了n-1条边时，T的连通分量个数为1，T便是G的一棵最小生成树。 下面的函数void Kruskal(EdgeType edges[],int n)利用Kruskal算法，构造了有n个顶点的图 edges的最小生成树。其中数组father[]用于记录T中顶点的连通性质：其初值为father[i]=-1 (i=0,1,…,n-1)，表示各个顶点在不同的连通分量上；若有father[i]=j，j＞-1，则顶点i，j连通；函数int Find(int father[],int v)用于返回顶点v所在树形连通分支的根结点。[函数]#define MAXEDGE 1000typedef struct int v1; int v2;EdgeType;void Kruskal(EdgeType edges[],int n) int father[MAXEDGE]; int i,j,vf1,vt2; for(i=0;i＜n;i+ +) father[i]=-1; i=0; j=0; while(i＜MAXEDGE vf2=Find(father,edges[i].v2); if( (2) ) (3) =vf1; (4) ; printf("%3d%3d/n",edges[i].v1,edges[i].v2); (5) ; int Find(int father[],int v) int t; t=v; while(father[t]＞=0) t=father[t]; return(t);

问答题【说明】 本程序的功能是实现任意两个大整数的乘法运算，例如： 输入整数1：8934793850094505800243958034985058 输入整数2：234584950989689084095803583095820923 二者之积： 209596817742739508050978890737675662366433464256830959194834854876 8534 【C++代码】 #include＜iostream.h＞ const int MAXINPUTBIT=100; const int MAXRESULTBIT=500; class LargeNumber{ int i,j; int temp; int one[MAXINPUTBIT+1]; int onebit; //one的位数 int two[MAXINPUTBIT+1]; int twobit; //two的位数 int result[MAXRESULTBIT+1]; public: LargeNumber(); ~LargeNumber(); int inputone(); //出错返叫0，否则返回1 int inputtwo(); //同上 void multiplication(); //乘 void clearresult(); //清零 void showresult(); //显示 }; LargeNumber∷LargeNumber() { for(i=0;i＜=MAXINPUTBIT;i++) { one[i]=0; two[i]=0; } onebit=0; twobit=0; inputone(); inputtwo(); } LargeNumber∷～LargeNumber() { } int LargeNumber∷inputone() { char Number[MAXINPUTBIT+1]; cout＜＜"Please enter one:"; cin＞＞Number; i=0; j=MAXINPUTBIT; while(Number[i]!='/0') i++; onebit=i; for(i--;i＞=0;i--,j--) { if(int(Number[i])＞=48 //由字符转换为数字 else return 0; } return 1; } int LargeNumber∷inputtwo() { char Number[MAXINPUTBIT+1]; cout＜＜"Please enter two:"; cin＞＞Number; i=0; j=MAXINPUTBIT; while(Number[i]!='/0') i++; twobit=i; for(i--;i＞=0;i--,j--) { if(int(Number[i])＞=48 //由字符转换为数字 else return 0; } return 1; } void LargeNumber∷multiplication() //乘法 { clearresult(); int m; for(i=MAXINPUTBIT;i＞=0;i--) { temp=two[i]; for(j={{U}} (2) {{/U}},m=MAXINPUTBIT;m＞=0;m--,j--) { result[j]+=temp*one[m]; if(result[j]＞9) { result[j-1]+=result[j]/10; {{U}} (3) {{/U}}; } } } cout＜＜"one*two="; showresult(); } void LargeNumber∷showresult() { i=0; while(result[i]==0 if(i＞MAXRESULTBIT) cout＜＜"0"; //输出0 for(;i＜=MAXRESULTBIT;i++) cout＜＜{{U}} (4) {{/U}}; cout＜＜endl; } void LargeNumber∷clearresult() { for(i=0;i＜=MAXRESULTBIT;i++) {{U}} (5) {{/U}}; } void main() { LargeNumber a; a.multiplication(); }

问答题试题九阅读以下应用说明及VisualBasic程序代码，将应填入(n)处的字句写在答题纸的对应栏内。[应用说明9]本应用程序的运行窗口如下图所示：窗口中的三个文本框和两个按钮名称分别为Txt_salary、Txt_base、Txt_tax、Cmd_compute和Cmd_quit。运行时，文本框Txt_base中存放的是免税金额基数（应扣除的基本费用）。当用户在文本框Txt_salary中输入月收入（工资或薪金）并单击“计算”按钮Cmd_compute后，Txt_tax框中就显示计算所得的应纳税额。文本框Txt_base和Txt_tax在运行时不接受用户输入，Txt_base的内容以灰色显示。个人工资(或薪金)所得税是按照超额累进的税率来征收的，方法是：以每月收入总额减去免税金额基数后的余额作为该月的月应纳税所得额，再将应纳税所得额按相应级数采用相应的税率进行累进计算。目前的免税金额基数为800元，税率如下表所示：设一个人的月应纳税所得额为K(元)，用下面的公式计算其应缴纳的个人所得税额S(元)：若0＜K≤500，则S=K×5％；若500＜K≤2000，则S=500×5％+(K-500)×10％；若2000＜K≤5000，则S=500×5％+1500×10％+(K-2000)×15％；若5000＜K≤20000，则S=500×5％+1500×10％+3000×15％+(K-5000)×20％；...例如，某人某月工资总额为4100元，减去800元后，应纳税所得额为3300元，其应缴纳的个人所得税额为500*5％+1500*10％+1300*15％=370元。在开发过程中，需要编写的程序代码如下：[程序代码9]OptionBase0PrivateSubCmd_compute_Click()Dimpaylevel,taxPratepaylevel=Array(0,500,2000,5000,20000,40000,60000,80000,100000,1000001)taxPrate=Array(5,10,15,20,25,30,35,40,45)K=（1）S=0If(K>0)ThenForj=1To9If（2）ThenS=S+(paylevel(j)-paylevel(j-1))*taxPrate(j-1)/100ElseS=S+(（3）)*taxPrate(j-1)/100ExitForEndIfNextjEndIf（4）=Str$(S)EndSubPrivateSubCmd_quit_Click()EndEndSubPrivateSubForm_Load()Txt_tax.Text=""Txt_salary.Text=""Txt_base.Text=800Txt_tax.Locked=TrueTxt_base.Enabled=（5）EndSub

问答题【说明】 链表和栈对象的共同特征是：在数据上执行的操作与在每个对象中实体存储的基本类型无关。例如，一个栈存储实体后，只要保证最后存储的项最先用，最先存储的项最后用，则栈的操作可以从链表的操作中派生得到。程序6-1实现了链表的操作，程序6-2实现了栈操作。 import java.io.*; class Node //定义结点 private String m_content; private Node m_next; Node(String str) m_content=str; m_next=null; Node(String str,Node next) m_content=str; m_next=next; String getData() //获取结点数据域 return m_content; void setNext(Node next] //设置下一个结点值 m_next=next; Node getNext() //返回下一个结点 return m_next; ) 【程序6-1】 class List Node Head; List() Head=null; void insert(String str) //将数据str的结点插入在整个链表前面 if(Head==null) Head=new Node(str); else (1) void append(String str) //将数据str的结点插入在整个链表尾部 Node tempnode=Head; it(tempnode==null) Heed=new Node(str); else white(tempnode.getNext()!=null) (2) (3) String get() //移出链表第一个结点，并返回该结点的数据域 Srting temp=new String(); if(Head==null) System.out.println("Errow! from empty list!") System.exit(0); else temp=Head.getData(); (4) return temp; 【程序6-2】 class Stack extends List void push(String str) //进栈 (5) String pop() //出栈 return get();

问答题阅读以下说明和C++代码，填补C++代码中的空缺(1)～(6)，将解答写在答题纸的对应栏内。[说明]已知某公司按周给员工发放工资，其工资系统需记录每名员工的员工号、姓名、工资等信息。其中一些员工是正式的，按年薪分周发放(每年按52周计算)；另一些员工是计时工，以小时工资为基准，按每周工作小时数核算发放。下面是实现该工资系统的C++代码，其中定义了四个类：工资系统类PayRoll，员工类Employee，正式工类Salaried和计时工类Hourly,Salaried和Hourly是Employee的子类。

问答题【说明】 本程序的功能是实现任意两个大整数的乘法运算，例如： 输入整数1：8934793850094505800243958034985058 输入整数2：234584950989689084095803583095820923 二者之积： 209596817742739508050978890737675662366433464256830959194834854876 8534 【C++代码】 #include＜iostream.h＞ const int MAXINPUTBIT=100; const int MAXRESULTBIT=500; class LargeNumber int i,j; int temp; int one[MAXINPUTBIT+1]; int onebit; //one的位数 int two[MAXINPUTBIT+1]; int twobit; //two的位数 int result[MAXRESULTBIT+1]; public: LargeNumber(); ~LargeNumber(); int inputone(); //出错返叫0，否则返回1 int inputtwo(); //同上 void multiplication(); //乘 void clearresult(); //清零 void showresult(); //显示 ; LargeNumber∷LargeNumber() for(i=0;i＜=MAXINPUTBIT;i++) one[i]=0; two[i]=0; onebit=0; twobit=0; inputone(); inputtwo(); LargeNumber∷～LargeNumber() int LargeNumber∷inputone() char Number[MAXINPUTBIT+1]; cout＜＜"Please enter one:"; cin＞＞Number; i=0; j=MAXINPUTBIT; while(Number[i]!='/0') i++; onebit=i; for(i--;i＞=0;i--,j--) if(int(Number[i])＞=48 //由字符转换为数字 else return 0; return 1; int LargeNumber∷inputtwo() char Number[MAXINPUTBIT+1]; cout＜＜"Please enter two:"; cin＞＞Number; i=0; j=MAXINPUTBIT; while(Number[i]!='/0') i++; twobit=i; for(i--;i＞=0;i--,j--) if(int(Number[i])＞=48 //由字符转换为数字 else return 0; return 1; void LargeNumber∷multiplication() //乘法 clearresult(); int m; for(i=MAXINPUTBIT;i＞=0;i--) temp=two[i]; for(j= (2) ,m=MAXINPUTBIT;m＞=0;m--,j--) result[j]+=temp*one[m]; if(result[j]＞9) result[j-1]+=result[j]/10; (3) ; cout＜＜"one*two="; showresult(); void LargeNumber∷showresult() i=0; while(result[i]==0 if(i＞MAXRESULTBIT) cout＜＜"0"; //输出0 for(;i＜=MAXRESULTBIT;i++) cout＜＜ (4) ; cout＜＜endl; void LargeNumber∷clearresult() for(i=0;i＜=MAXRESULTBIT;i++) (5) ; void main() LargeNumber a; a.multiplication();

问答题试题六 阅读下列函数说明和C 函数，将应填入 （n） 处的字句写在答题纸的对应栏内。 [函数6 说明] 函数DelA_InsB(LinkedList La,LinkedList Lb,int key1,int key2,int len)的功能是：将线性表A 中关键码为key1 的结点开始的len 个结点，按原顺序移至线性表B 中关键码为key2的结点之前，若移动成功，则返回0；否则返回-1。线性表的存储结构为带头结点的单链表，La 为表A 的头指针，Lb 为表B 的头指针。单链表结点的类型定义为： typedef struct node { int key; struct node *next; }*LinkedList; [函数6] int DelA_InsB(LinkedList La,LinkedList Lb,int key1,int key2,int len) { LinkedList p,q,s,prep,pres; int k; if (!La->next||!Lb->next||len next; prep = La; while ( p p = p->next; } if (!p) return -1; /*表A 中不存在键值为key1 的结点*/ q = p; k = 1; while (q k++; } if (!q) return -1; /*表A 中不存在要被删除的len 个结点*/ s = Lb->next; （3） ; while (s s = s->next; } if (!s) return -1; /*表B 中不存在键值为key2 的结点*/ （4） = q->next; /*将表A 中的len 个结点删除*/ q->next = （5） ; pres->next = p; /*将len 个结点移至表B*/ return 0; }

问答题【说明】 下面代码里，instr是一个抽象类，它被两个子类wind和rain分别实现，而brass又继承了wind类，并覆盖了play方法。 【程序】 {{U}} (1) {{/U}}class instr{ {{U}} (2) {{/U}}Void play(); } class wind{{U}} (3) {{/U}}instr{ void play(){System.out.println("wind play!");} } class rain extends instr { void play(){System.out.println("rain play!");} } class brass extends{{U}} (4) {{/U}}{ void play(){System.out.println("brass play!"));} } public class music{ static void tuneAll(instr e[]){ for(int i=0;i＜e.length;i++) e[i].play(); } public{{U}} (5) {{/U}}void main(String[]args){ instr orch[]=new instr[3]; int i=0; orch[i++]=new wind(); orch[i++]=new rain(); orch[i++]=new brass(); tuneAll(orch); } }

问答题阅读以下算法说明和C程序，根据要求回答问题1和问题2。【说明】【算法4-1】的功能是用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号而没有对应的左括号或者右括号，则给出相应的提示信息，如图1-18所示。在【算法4-1】中，slack为一整数栈。算法中各函数的说明如表1-11所示。{{B}}表1-11各函数的功能说明表{{/B}}{{B}}函数名{{/B}}{{B}}函数功能{{/B}}push(inti)将整数i压入栈stack中Pop()stack的栈顶元素出栈Empty()判断stack栈是否为空。若为空，函数返回1，否则函数返回0Nextch()读取文本文件中的下一个字符，并返回该字符的ASCII值，将字符所在的行号及字符在行中的位置分别存储到变量row和col中，若遇到文件结束符，则将变量EOF置为trueKind(charch)判断字符ch是左括号还是右括号，若是左括号，函数返回1：若是右括号，函数返回2；若两者都不是，函数返回0【算法4-1】将栈stack置空，置EOF为falseCh＜-nextch()；while(notEOF)　　k←kind(ch)；　　if(k=={{U}}　(1)　{{/U}}){　　　　push({{U}}　(2)　{{/U}})；　　　　push({{U}}　(3)　{{/U}})；}　　elseif(k=={{U}}　(4)　{{/U}})　　　　if(notempty()){　　　　　　pop()；　　　　　　pop()；)　　　　else{　　显示错误信息(缺少对应左括号或右括号)：　　显示行号row：显示列号col：)　　　　Endif　　Endif　　Ch＜-nextch()；endwhileif(notempty())　　显示错误信息(缺少对应左括号或右括号)：　　While(notempty()){　　row＜-pop()；　　col＜-pop()：　　显示行号row：显示列号col；)　　EndwhileEndif　　为了识别更多种类的括号，对【算法4-1】加以改进后得到【算法4-2】。【算法4-2】能够识别圆括号、方括号和花括号(不同类型的括号不能互相匹配)。改进后，函数kind(charch)的参数及其对应的返回值如表1-12所示。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　{{B}}表1-12函数kind(charch)的参数及其对应的返回值{{/B}}ch(){}[]其他返回值1234567【算法4-2】将栈stack置空，置EOF为falseCh＜-nextch()；while(notEOF){k＜-kind(ch)；if(k＞0)if(判断条件1){push({{U}}(5){{/U}})；push({{U}}(6){{/U}})；push({{U}}(7){{/U}})；}elseif(判断条件2and判断条件3){pop()；pop()；pop()；}else{显示错误信息(缺少对应左括号或右括号)；显示行号row；显示列号col；)endifendifch＜-nextch()；)endwhileif(notempty()){显示错误信息(缺少对应左括号或右括号)；While(notempty()){Pop()；row＜-pop()：col＜-pop()；显示行号row；显示列号col；))endwhileendif

问答题【说明】 本程序可以将字符串s1中出现的所有s2子串替换成s3，形成一个新串，但不破坏字符串s1。 【代码】 #include＜stdio.h＞ #include＜stdlib.h＞ #include＜string.h＞ char*replace(char *s1, char *s2,char *s3) { char *p, *q, *r, *s; int |2，|3, i=0; |2=strlen(s2); |3=strlen(s3); p=s1; while((p=strstr(p,s2))!=NULL) { i++; /* 统计s2串出现的次数*/ {{U}} (1) {{/U}}; } i={{U}} (2) {{/U}}; s=r=(char*)malloc(i); /*分配动态内存存放新字符串*/ p=s1; while(1) { q=strstr(p, s2); /* s2串是否在s1中出现，q是首次出现的位置*/ if(q!=NULL) { i=q-p; {{U}}(3) {{/U}}; r+=i; {{U}}(4) {{/U}}; r+=|3; p=q+|2; /*将指向s1串的指针移到s2子串出现的位置后， 为下一次循环做好准备*/ } else /*q为空，表示剩余的s1串中已经没有s2*/ { {{U}}(5) {{/U}}; break; /*终止循环*/ } } return(s); /*返回指向所形成的新串的指针*/ } void main() { char *a="sabcababde", *b="ab", *c="efg", *d; d=replace(a, b, c); printf("result=%s/n", d); free(d); }

问答题【说明】 对20个数进行排序，可以利用选择法，即从后19个比较过程中，选择一个最小的与第一个元素交换，依次类推，即用第二个元素与后18个进行比较，并进行交换。 【函数】 #define N 20 main() int i,j,min,tem,a[N]; printf("please input twenty num:/n"); for(i=0;i＜N;i) printf("a[%d]=",i); scanf("%d", printf("/n"); for(i=0;i＜N;i) printf(",",a[i]); printf("/n"); for(i=0; (1) ;i) min= (2) ; for(j= (3) ;j＜N;j++) if( (4) ) min=j; tem=a[i]; (5) ; a[min]=tem; printf("After sorted /n"); for(i=0;i＜N;i++) printf(",",a[i]);

问答题【说明】 有n个整数，使其前面各数顺序向后移m个位置，最后m个数变成最前面的m个数。 【函数】 main() int number[20],n,m,i; printf("the total numbers is:"); scanf("%d", printf("back m:"); scanf("%d", for(i=0;i＜=n-1;i) scanf("%d,", (1) ; for(i=0;i＜=n-1;i) printf("%d,",number[i]); move(array,n,m) int n,m,array[20]; int *p,array_end; array_end= (2) ; for(p=array[n-1]; (3) ;p--) *p= (4) ; *array=array_end; m--; if(m＞0) (5) ;

问答题【说明】 下面待修改的C程序完成的功能是：对于给定的一个长正整数，从其个位数开始，每隔一位取一个数字(即取其个位、百位、万位等数字)，形成一个新的整数并输出。例如，将该程序修改正确后，运行时若输入“14251382”，则输出的整数为“4532”。 下面给出的C程序代码中有五个错误，请指出所有的错误。 【C程序代码】 01 #include ＜stdio.h＞ 02 03 int main() 04 { 05 long n, num; 06 int i; 07 08 do { 09 printf("请输入一个正整数："); 10 scanf("%ld", n); 11 }while(n ＜= 0); 12 k = 1; 13 for (i = 1; n ＞= 0; i++) { 14 if (i % 2 = 1) { 15 num= num+ (n % 10) * k; 16 k = k * 10; 17 } 18 n = n / 10; 19 } 20 printf("新数据为: %d /n",num); 21 return 0; 22 }

问答题【说明】该应用程序是用来修改文本框中的字体属性，其运行窗口如图4所示。窗口由1个标签(Labell)、1个文本框(txtPassage)和4个选择框(chkFont，chkltalic，chkSize，chkColor)组成。程序运行后，用户在文本框内输入一段文字，然后按需要单击各选择框，用以改变文本的字体、字型、颜色及大小。文本框的Mulitine属性已经设为True。当不选择“黑体”时，文字应是“宋体”。当不选择“大小16”时，字号为9。当不选择“紫色”时，字色为黑色。当不选择“斜体”时，文字采用正常字型。【程序代码】PrivateSubchkFontClick()If{{U}}(1){{/U}}ThentxtPassage.FontName="黑体"ElsetxtPassage.FontName="宋体"EndIfEndSubPrivateSub{{U}}(2){{/U}}()IfchkColor.Value=1ThentxtPassage.ForeColor=QBColor(13)ElsetxtPassage.ForeColor=QBColor(0)EndIfEndSubPrivateSubchkltalic_Click()Ifchkltalic.Value=1ThentxtPassage.Fontltalic={{U}}(3){{/U}}ElsetxtPassage.Fontltalic={{U}}(4){{/U}}EndIfEndSubPrivateSubchkSizeClick()If{{U}}(5){{/U}}ThentxtPassage.Font.Size=16ElsetxtPassage.Font.Size=9EndIfEndSub

问答题【说明】 该程序运行后，输出下面的数字金字塔 1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1 ...... 1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1 【程序】 #include ＜ stdio. h ＞ main ( ) char max, next; int i; for( max = '1'; max ＜= '9'; max + +) for(i=1;i＜=20- (1) ;++i) printf(" "); for(next = (2) ;next ＜= (3) ;next ++) printf(" %c" ,next); for(next= (4) ;next＞= (5) ;next--) printf(" %c" ,next); printf(" /n" );

问答题【说明】对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合{a,b,c,d}及其权值2、7、4、5，可构造如图6-15所示的最优二叉树，以及相应的结构数组Ht(如表6-14所示，其中数组元素Ht[0]不用)。{{B}}表6-14结构数组Ht{{/B}}{{B}}数组下标{{/B}}chweightparentlchildrchild1　a　2　5　0　02　b　7　7　0　03　c　4　5　0　04　e　5　6　0　05　6　6　1　36　11　7　4　57　18　0　2　6结构数组Ht的类型定义如下：#defineMAXLEAFNUM20structnode{charch;/*扫当前节点表示的字符，对于非叶子节点，此域不用*/Intweight；/*当前节点的权值*/intparent;/*当前节点的父节点的下标，为0时表示无父节点*/intlchild,rchild;/*当前节点的左、右孩子节点的下标，为0时表示无对应的孩子节点*/)Ht[2*MAXLEAFNUM];用“0”或“广标识最优二叉树中分支的规则是：从一个节点进入其左(右)孩子节点，就用“0”(或“1”)标识该分支，如图6-15所示。若用上述规则标识最优二叉树的每条分支后，从根节点开始到叶子节点为止，按经过分支的次序将相应标识依次排列，可得到由“0”、“1”组成的一个序列，称此序列为该叶子节点的前缀编码。例如，图6-15所示的叶子节点a、b、c、d的前缀编码分别是110、0、111、10。函数voidLeafCode(introot,intn)的功能是：采用非递归方法，遍历最优二叉树的全部叶子节点，为所有的叶子节点构造前缀编码。其中，形参root为最优二叉树的根节点下标；形参n为叶子节点个数。在函数voidLeafCode(introot,intn)构造过程中，将Ht[p].weight域用做被遍历节点的遍历状态标志。函数voidDecode(char*buff,introot)的功能是：将前缀编码序列翻译成叶子节点的字符序列，并输出。其中，形参root为最优二叉树的根节点下标；形参buff指向前缀编码序列。【函数4.1】char**HC;voidLeafCode(introot,intn){/*为最优二叉树中的n个叶子节点构造前缀编码，root是树的根节点下标*/intI,p=root,cdlen=0;charcode[20];Hc=(char**)malloc((n+1)*sizeof(char*));/*申请字符指针数组*/For(i=1;i＜=p;++I)Ht[i].weight=0;/*遍历最优二叉树时用做被遍历节点的状态标志*/While(p){/*以非递归方法遍历最优二叉树，求树中每个叶子节点的编码*/If(Ht[p].weight==0){/*向左*/Ht[p].weight=1;If(Ht[p].lchild!=0){p=Ht[p].lchild;code[cdlen++]='0';}elseif(Ht[p].rchild==0){/*若是叶子节点,则保存其前缀编码*/Hc[p]=(char*)malloc((cdlen+1)*sizeof(char));{{U}}(1){{/U}};strcpy(Hc[p],code);}}elseif(Ht[p].weight==1){/*向右*/Ht[p].weight=2;If(Ht[p].rchild!=0){p=Ht[p].rchild;code[cdlen++]='1';}}else{/*Ht[p].weight==2,回退/Ht[p].weight=0;p={{U}}(2){{/U}};{{U}}(3){{/U}};/*退回父节点*/}}/*while.结束*/}【函数4.2】voidDecode(char*buff,introot){intpre=root,p;while(*buff!='/0'){p=root;while(p!=0){/*存在下标为p的节点*/pre=p;if({{U}}(4){{/U}})p=Ht[p].lchild;/*进入左子树*/elsep=Ht[p].rchild;/*进入右子树*/elsebuff++;/*指向前缀编码序列的下一个字符*/}{{U}}(5){{/U}};printf("%c",Hr[pre].ch);}}

问答题【说明】 著名的四色定理指出任何平面区域图均可用4种颜色着色，使相邻区域着不同的颜色。以下C程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。该程序中用1～4分别表示4种颜色。要着色的N个区域用0～-1编号，区域相邻关系用adj[][]矩阵表示，矩阵的i行j列的元素为1，表示区域i与区域了相邻；矩阵的i行j列的元素为0，表示区域i与区域j不相邻。数组color[]用来存储着色结果，color[i]的值为区域i，所着颜色。 【C程序】 #include ＜stdio.h＞ #define N 10 void output(int color[]) /*输出一种着色方案*/ int i ; for ( i = 0 ; i ＜ N ; i++ ) printf( "%4d" , color[i] ) ; printf ("/n") ; int back(int *ip ,int color[] ) /*回溯*/ intc = 4 ; while ( c == 4 ) if ( *ip ＜= 0 ) return 0 ; -- (*ip) ; c = (1) ; color[*ip] =-1 ; return c ; /*检查区域i，对c种颜色的可用性*/ int colorOk(int i , intc , int [] [N] ,int color[ ] ) int j ; for (j = 0 ; j ＜ i ; j++ ) if ( (2) ) return 0 ; return 1 ; /*为区域i选一种可着色的颜色*/ int select (int i ,int c ,int adj [] [N] ,int color[ ] ) int k ; for(k = c ; k ＜= 4 ; k++ ) if( colorOK( (3) )) return k ; return 0 ; int coloring(int adj [] [N]) /*寻找各种着色方案*/ int color[N] , i , c , cnt ; for(i = 0 ; i ＜ N ; i++) color[i] =-1 ; i = c = 0 ; cnt = 0 ; while(1) if((c = (4) ) == 0 c = back( if( c == 0 ) return cnt; else (5) ; i++ ; if i == N) output(color); ++cnt ; c = back( else c = 0 ; void main()( int adj[N] [N] = 0,1,0,1,1,1,1,1,1,1, 1,0,1,1,0,1,1,1,1,0, 0,1,0,1,0,1,1,0,1,1, 1,1,1,0,1,1,0,0,1,1, 1,0,0,1,0,1,0,0,0,0, 1,1,1,1,1,0,1,0,0,1, 1,1,1,0,0,1,0,0,1,0, 1,1,0,0,0,0,0,0,1,1, 1,1,1,1,0,0,1,1,0,1, 1,0,1,1,0,1,0,1,1,0, ; printf("共有%d组解./n",coloring(adj));

问答题[函数2.1说明] 函数strcpy的功能是将字符串str2的内容复制到字符申str1。 [函数2.1] {{U}}(1) {{/U}}strcpy (char *slr1, const char *str2) { char * temp; while( * str2!='/0') *cp++ ={{U}} (2) {{/U}}; {{U}}(3) {{/U}}='/0'; return str1; } [函数2.2说明] 函数int strcmp(const char *str1, const char *str2)的功能是按字典序比较两个字符串str1和str2的大小。当str1＜str2时返回-1，当str1＞str2时返回1，否则返回0。 [函数2.2] int strcmp(const char *str1, const char *str2) { while( *str1= =* str2) { if(* s1= = {{U}}(4) {{/U}} ) return 0; s1++; {{U}}(5) {{/U}}; } if( *str1＜*str2) return -1; return 1; }

问答题[说明] 二叉树的二叉链表存储结构描述如下： lypedef struct BiTNode { datatype data; street BiTNode *lchiht, *rchild; /*左右孩子指针*/ } BiTNode, *BiTree; 下列函数基于上述存储结构，实现了二叉树的几项基本操作： (1) BiTree Creale(elemtype x, BiTree lbt, BiTree rbt)：建立并返回生成一棵以x为根结点的数据域值，以lbt和rbt为左右子树的二叉树； (2) BiTree InsertL(BiTree bt, elemtype x, BiTree parent)：在二叉树bt中结点parent的左子树插入结点数据元素x； (3) BiTree DeleteL(BiTree bt, BiTree parent)：在二叉树bt中删除结点parent的左子树，删除成功时返回根结点指针，否则返回空指针； (4) frceAll(BiTree p)：释放二叉树全体结点空间。 [函数] BiTree Create(elemtype x, BiTree lbt, BiTree rbt) { BiTree p; if ((p = (BiTNode *)malloc(sizeof(BiTNode)))= =NULL) return NULL; p-＞data=x; p-＞lchild=lbt; p-＞rchild=rbt; {{U}} (1) {{/U}}; } BiTree InsertL(BiTree bt, elemtype x,BiTree parent) { BiTree p; if (parent= =NULL) return NULL; if ((p=(BiTNode *)malloc(sizeof(BiTNode)))= =NULL) return NULL; p-＞data=x; p-＞lchild={{U}} (2) {{/U}}; p-＞rchild={{U}} (2) {{/U}}; if(parent-＞lchild= =NULL) {{U}}(3) {{/U}}; else{ p-＞lchild={{U}} (4) {{/U}}; parent-＞lchild=p; } return bt; } BiTree DeleteL(BiTree bt, BiTree parent) { BiTree p; if (parent= =NULL||parent-＞lchild= =NULL) return NULL; p= parent-＞lchild; parent-＞lchild=NULL; freeAll({{U}} (5) {{/U}}); return bt; }