填空题 阅读下列函数说明和C代码，将应填入{{U}} (n) {{/U}}处的字句写在对应栏内。 [说明] HufTman树又称最优二叉树，是一类带权路径长度最短的树，在编码中应用比较广泛。 构造最优二叉树的Huffman算法如下： ①根据给定的n各权值{W1，w2，…，wn)构成n棵二叉树的集合F={T1，T2，…，Tn}，其中每棵树Ti中只有一个带权为wi的根节点，其左右子树均空。 ②在F中选取两棵根节点的权值较小的树作为左右子树，构造一棵新的二叉树，置新构造二叉树的根节点的权值为其左右予树根节点的权值之和。 ③从F中删除这两棵树，同时将新得到的二叉树加入到F中。 重复②③，直到F中只剩一棵树为止。 函数中使用的预定义符号如下： #define INT MAX 10000 #define ENCODING LENGTH 1000 typedef enum(none，left_child，right_child) Which； /*标记是左孩子还足右孩子*/ typedef char Elemtype； typedef struct TNode{//Huffman树节点 Elemtype letter； int weight； //权值 int parent； //父节点 Which sigh； char *code； //节点对应编码 }HTNode，*HuffmanTree； int n； char coding[50]；//储存代码 [函数] void Select(HuffmanTree HT，int end，int *sl，int *s2) /*在0～END之间，找出最小和次小的两个节点序号，返吲S1、S2*/ { int i； int min 1=INT_MAX； int min 2=INT_MAX； for(i=0；i＜=end；i++){/*找最小的节点序号*/ if(({{U}} (1) {{/U}})＆＆(HT[i].weight＜minl)){ *s1=i； min 1=HT[i].weight； } } for(i=0；i＜=end；i++){/*找次小节点的序号*/ if((HT[i].parent==0)＆＆({{U}} (2) {{/U}}) ＆＆(min 2＞HT[i].weight)){ *s2=i； min 2=HT[i].weight； } } } void HuffmanTreeCreat(HuffmanTree＆HT)/*建立HUFFMAN树*/ { int i； int m=2*n-1； int s1，s2； for(i=n；i＜m；i++){ Select({{U}} (3) {{/U}})； HT[s1].parent=i； HT[s2].parent=i； HT[s1].sigh=left child； HT[s2].sigh=right child； HT[i]．weight={{U}} (4) {{/U}}； } } void HuffmanTreeEncoding(char sen[]，HuffmanTree HT) { /*将句子进行编码*/ int i=0； int j； while(sen[i] !='＼0'){ for(j=0；j＜n；j++){ if(HT[j].letter==sen[i])(/*字母吻合则用代码取代*/ strcat(coding，{{U}} (5) {{/U}})； break； } } i++； if (Sen [1]==32) i++； } printf("/n%s"，coding)； }

填空题[问题2] 各个事务的内部结构如下所示。若事务不施加任何锁，则有多少可能的调度。T1: R1 ( Get A into t1 ;t1: = t1 + 1 ); U1 ( Update A from t1 );T2: R2 ( Get A into t2 ;t2: = t2 * 2); U2 ( Update A from t2);T3:1t3 ( Get A into t3; display t3 ); U3 ( Update A from 1 );

填空题[说明] 假设二叉树采用链式存储方式存储，编写一个后序遍历二叉树的非递归方式。 Void postorder (btree * B) { btree * stack [m0] , *p; int tag [m0], top =0; p=b; do { while (p! =NULL) { top+ +; {{U}}(1) {{/U}} tag [top] =0; p =p- ＞left; } if (top ＞0) { {{U}}(2) {{/U}} if (tag[top3 = =1) { {{U}}(3) {{/U}} print ("%d", p- ＞data); } if(top＞0) { {{U}}(4) {{/U}} tag [top] = 1; } } } while (p! = NULL && top ! =0) }

填空题[说明] 编写一个函数根据用户输入的偶对(以输入。表示结束)建立其有向图的邻接表。一个图的邻接表存储结构定义如下： # include ＜ stdio. h ＞ # define MAXVEX 30 struct edgenode { int adjvex; char info; struct edgenode * next; } struct vexnode { char data; struct edgenode * link; } typedef struct vexnode adjlist [MAXVEX]; 实现要求的函数如下: void creatadjlist ( adjlist g) { int i, j, k; street vexnode * s; for( k=1; k＜ =n; k+ +) { {{U}}(1) {{/U}} g [k]. link = NULL; } printf ( “输一个对：” ); scanf ("%d, %d", while{{U}} (2) {{/U}} { {{U}} (3) {{/U}} s- ＞adjvex =j; {{U}} (4) {{/U}} g [i].link =s; {{U}} (5) {{/U}} } }

填空题[问题1] 该关系模式满足2NF吗?为什么?

填空题[问题1] 通过该程序的算法用等价类设计测试用例，检查逻辑覆盖标准。

填空题[说明]欲开发一个绘图软件，要求使用不同的绘图程序绘制不同的图形。以绘制直线和圆形为例，对应的绘图程序如下表所示。不同的绘图程序DP1DP2绘制直线draw_a_line(x1,y1,x2,y2)drawline(x1,x2,y1,y2)绘制圆draw_a_circle(x,y,r)drawcircle(x,y,r)该绘图软件的扩展性要求，将不断扩充新的图形和新的绘图程序。为了避免出现类爆炸的情况，现采用桥接(Bridge)模式来实现上述要求，得到如下图所示的类图。某绘图软件类图[C++代码]classDP1{public:staticvoiddraw_aline(doublex1,doubley1,doublex2,doubley2){/*代码省略*/}staticvoiddrawa_circle(doublex,doubley,doubler){/*代码省略*/}classDP2(public:staticvoiddrawline(doublex1,doublex2,doubley1,doubley2){/*代码省略*/}staticvoiddrawcircle(doublex,doubley,doubler){/*代码省略*/}classDrawing{public:________;________;};classV1Drawing:publicDrawing{public:voiddrawLine(doublex1,doubley1,doublex2,doubley2){/*代码省略*/}voiddrawCircle(doublex,doubley,doubler){________;}};classV2Drawing:publicDrawing{public:voiddrawLine(doublexl,doubleyl,doublex2,doubley2>{/~~~~~~~/}voiddrawCircle(doublex,doubley,doubler){________;}classShape{publie:________;Shape(Drawing*dp){_dp=dp;}voiddrawLine(doublex1,doubley1,doublex2,doubley2){_dp-＞drawLine(x1,y1,x2,y2);}voiddrawCircle(doublex,doubley,doubler){_dp-＞drawCircle(x,y,r);}private:Drawing*_dp;classRectangle:publicShape{public:voiddraw(){/*代码省略*/}classCircle:publicShape{private:double_x,_y,_r;public:Circle(Drawing*dp,doublex,doubley,doubler):________{_x=x;_y=y;_r=r;}voiddraw(){drawCircle(_x,_y,_r);}};

填空题[说明]某灯具厂商欲生产一个灯具遥控器，该遥控器具有7个可编程的插槽，每个插槽都有开关按钮，对应着一个不同的灯。利用该遥控器能够统一控制房间中该厂商所有品牌灯具的开关，现采用Command(命令)模式实现该遥控器的软件部分。Command模式的类图如下图所示。Command模式类图[C++代码]classLight{public:Light(stringname){/*代码省略*/}voidon(){/*代码省略*/}//开灯voidoff(){/*代码省略*/}//关灯}:classCommand{public:________;}classLightonCommand:publicCommand{//开灯命令private:Light*light;public:LightonCommand(Light*light){this-＞light=light;}Voidexecute(){________;}};classLightoffCommand:publicCommand{//关灯命令private:Light*light;public:LightoffCommand(Light*light){this-＞light=light;}Voidexecute(){________;}};classRemoteControl{//遥控器private:Command*onCommands[7];Command*offCommands[7];public:RemoteControl(){/*代码省略/}voidsetCommand(intslotCommand*onCommand,Command*offCommand){________=onCommand;________=offCommand;}voidonButtonWasPushed(intslot){________:)voidoffButtonWasPushed(intslot){________:});intmain(){RemoteControl*remoteControl=newRemoteControl();Light*livingRoomLight=newLight("LivingRoom");Light*kitchenLight=newLight("kitchen");LightonCommand*IivingRoomLighton=newLightonCommand(livingRoomLight);LightoffCommand*livingRoomLightoff=newLightoffCommand(livingRoomLight);LightonCommand*kitchenLighton=newLightonCommand(kitchenLight);LightoffCommand*kitchenLightoff=newLightoffCommand(kitchenLight);remoteControl-＞setCommand(0,livingRoomLighton,livingRoomLightoff);remoteControl-＞setCommand(1,kitchenLighton,kitchenLightoff);remoteControl-＞onButtonWasPushed(0);remoteControl-＞offButtonWasPushed(0);remoteControl-＞onButtonWasPushed(1);remoteControl-＞offButtonWasPushed(1);/*其余代码省略*/return0;}

填空题[说明] 这是一个用户名校验程序，如用户名正确，即输出欢迎字样，否则，弹出警告窗并直接退出程序。下面是实现上述功能的程序，请填空。“Option Explicit”此语句的作用：强制显示声明 Dim UserName (2) As String Dim Flag As Boolean {{U}} (1) {{/U}} Private Sub Form _ Load( ) UserName (0) = "AA": UserName (1) = "BB": UserName(2) = "CC" Flag = False inputName = InputBox( “请输入名称：“,”身份确认”“,”) Dim i As Integer For i = 0 To False If inputName = UserName(i) Then {{U}}(2) {{/U}} End If Next i If{{U}} (3) {{/U}}Then MsgBox “用户身份确失败!退出应用”, vbOKOnly, “警告” End End If End Sub Private Sub Form_ Paint( ) {{U}}(4) {{/U}} End Sub

填空题阅读以下函数说明和Java代码，将应填入(n)处的字句写上。[说明]现有一个显示系统，要显示的图形有线Line、矩形Square，抽象出一个Shape类(接口)，有方法显示display()。需要新增图形Circle，又已知有类XXCircle实现了所需要实现的功能：显示displayIt()。为了继承自shape以提供统一接口，又不希望从头开发代码，希望使用XXCircle。这样将XXCircle作为Circle的一个属性，即Circle的对象包含一个XXCircle对象。当一个Circle对象被实例化时，它必须实例化一个相应的XXCircle对象；当Circle对象收到的做任何事的请求都将转发给这个XXCircle对象。通过这种称为Adapter模式，Circle对象就可以通过“让XXCircle做实际工作”来表现自己的行为了。图7-1显示了各个类间的关系。以下是JAVA语言实现，能够正确编译通过。[图7-1][Java代码]//Shape.java文件publicinterfaceShapepublic(1)voiddisplay();//XXCircle.jave文件publicclassXXCirclepublicvoiddisplayIt()//省略具体实现//Circle.java文件publicclassCircle(2)ShapeprivateXXCirclepcx=(3);publicvoiddisplay()pcx.displayIt()；//Factory.java文件publicclassFactorypublic(4)getShapeInstance(inttype)switch(type)case1：returnnewLine()；case2：returnnewSquare()；case3：returnnewCircle()；default：returnnull；//Main.java文件publicclassMainpublicstaticvoidmain(String[]args)inttype=1；Factoryfactory=newFactory()；Shapes;s=factory.(5)；if(s==null)System.out.println("Errorgettheinstance!");return；s.display();return；

填空题阅读以下说明和C++代码，将应填入(n)处的字句写上。[说明]现有一个显示系统，要显示的图形有线Line、矩形Square，抽象出一个Shape类(接口)，有方法显不display()。需要新增图形Circle，又已知有类XXCircle实现了所需要实现的功能：显示displayIt()。为了继承自shape以提供统一接口，又不希望从头开发代码，希望使用XXCircle。这样将XXcircle作为Circle的一个属性，即Circle的对象包含一个XXCircle对象。当一个Circle对象被实例化时，它必须实例化一个相应的XXCircle对象：Circle对象收到的做任何事的请求都将转发给这个XXCircle对象。通过这种称为Adapter模式，Circle对象就可以通过“让XXCircle做实际工作”来表现自己的行为了。图6-1显示了各个类间的关系。以下是C++语言实现，能够正确编译通过。[图6-1][C++代码]classShapepublic：(1)voiddisplay()=0;;classLine：publicShape//省略具体实现;classSquare：publicShape//省略具体实现;classXXCirclepublic：voiddisplayIt()//省略具体实现//省略其余方法和属性;classCircle：publicShapeprivate：XXCircle*pxc;public：Circle();voiddisplay();;Circle：：Circle()pxc=(2);voidCircle：：display()pxc-＞(3);classFactorypublic：(4)getshapeInstance(inttype)//生成特定类实例switch(type)case1：returnnewSquare;case2：returnnewLine;case3：returnnewCircle;default：returnNULL;;voidmain(intargc，char*argv[])if(argc!=2)cout＜＜"errorparameters!"＜＜endl;return;inttype=atoi(argv[1]);Factoryfactory；Shape*s=factory.(5);if(s==NULL)cout＜＜"Errorgettheinstance!"＜＜endl;return;s-＞display();deletes；return；

填空题[说明] 将一个正整数分解质因数。例如：输入90，打印出90=2*3*3*5。 main ( ) { int n, i; printf ( "/n please input a number: /n"); scanf ( "% d" , printf ( "%d =" ,n); for({{U}} (1) {{/U}}) { while({{U}} (2) {{/U}}) { if({{U}} (3) {{/U}}) { printf ("%d*",i); {{U}}(4) {{/U}} } else break; } } printf (“%d”，n)；}

填空题[问题3] 用SQL语言写出查询：查询年龄不在20～23岁(包括20岁和23岁)之间的学生的姓名，系别和年龄。

填空题 阅读以下说明和C代码，将应填入{{U}} (n) {{/U}}处的字句写在对应栏内。 [说明] 下面程序用来将打乱的单词还原为原来的次序，比如将rty还原为try。单词的原来次序存储于wordlist.txt文件中，原则上可用穷举法(rty对应的穷举为：rty、ryt、try、tyr、ytr、yrt)，但考虑到破译速度，采用如下方法。 注意到单词列表中不存在组成字符完全相同的单词(如Hack12与Hack21包含完全相同的字符)，因此将单词中的字符进行重组再进行比较，例如，try单词重组为rty(按ASCⅡ码顺序)，这样不管打乱的单词是什么顺序，只要是由r、t、y三个字母组成的均破译为try，大大提高破译速度。程序中借助二叉排序树以进一步提高查找效率，二叉排序树左子树(如果有)上的节点对应的值均小于根节点的值，右子树(如果有)上的节点对应的值均大于根节点的值。 函数中使用的符号定义如下： #define NumberofWords 1275//单词总数 #define MaxLength 10//最长单词所含字符数 char WordList[NumberofWords][MaxLength]；//存储单词列表 int cmp(Node *q，Node *p)；//q与p比较。p小，返回负值；P大返回正值：相等，返回0 typedef struct Node(//二叉树节点 char *eleLetters；//重组后的字符串 int index；//对应单词表中的下标 struct Node *lChiId，*rChiid；//左右子节点 }Node； [C代码] void reCompose(Node *p，char *temp) //重纰，亦即将temp字符串中的字符升序排序，存储于p节点中 //采用直接插入排序法 { char c； strcpy(p-＞eleLetters，temp)；// int len=strlen(temp)； int i，j，k； for(i=0；i＜len－1；i++){ k=i； for(j=i+1；j＜lan；j++){ if(p-＞eleLetters[j]＜P-＞eleLetters[k])k=J； } if({{U}} (1) {{/U}}){ C=P-＞eleLetters[i]； P-＞eleLetters[i]=P-＞eleLetters[k]； P-＞eleLetters[k]=c； }//if }//for }； int find(Node root，char *temp) //在二叉排序树root中查找与temp匹配的单词。 //若匹配返回相应单词在WordList中下标；若查找失败，返回-1 { Node *P，*q； int flag； P={{U}} (2) {{/U}}；//临时存储 reCompose(p，temp)；//将temp重组 q=root； while((flag={{U}} (3) {{/U}})＆＆q !=NULL){ if(flag＜0){//搜索左子树 q=q-＞lChiid； }else(//搜索右子树 q=q-＞rChild； } }//while if(flag==0){//找到匹配的，保存下标 return{{U}} (4) {{/U}}； } } if({{U}} (5) {{/U}}){//查找失败 printf("cant unscramble the following word：%s"，temp)；； return -1； } }；

填空题[说明] 打印输出10行杨晖三角形。形式如下： 杨晖三角形： 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 class yanghui { public static void main (String args [] ) { int i, j; {{U}} (1) {{/U}} int yanghui [] []; System. out. println( “杨晖三角形：” ); yanghui = new int [ yhleve1] []; for(i =0;i ＜ yanghui, length; i + + ) yanghui[i] = new int [i + 1]; {{U}}(2) {{/U}} for({{U}} (3) {{/U}}) { yanghui [i] [0] = 1; for(j = 1 ;j ＜ yanghui[i], length - 1 ;j + + ) yanghui[i] [j] = yanghui[i - 1] [j - 1] + yanghui[i - 1] [j]; yanghui[i] [yanghui[i]. length - 1 ] = 1; } for ( i=0; i ＜ yanghui. length; i + + ) { for(j =0;j ＜ yanghui[i]. length; j + + ) {{U}} (4) {{/U}} System. out. println( ); } } }

填空题[说明]若要在N个城市之间建立通信网络，只需要N-1条线路即可。如何以最低的经济代价建设这个网络，是一个网的最小生成树的问题。现要在8个城市间建立通信网络，其间拓扑结构如图所示，边表示城市间通信线路，边上标示的是建立该线路的代价。无向图用邻接矩阵存储，元素的值为对应的权值。考虑到邻接矩阵是对称的且对角线上元素均为0，故压缩存储，只存储上三角元素(不包括对角线)。现用Prim算法生成网络的最小生成树。由网络G=(V,E)构造最小生成树T=(U,TE)的Prim算法的基本思想是：首先从集合V中任取一顶点放入集合U中，然后把所有一个顶点在集合U里、另一个顶点在集合V-U里的边中，找出权值最小的边(u,v)，将边加入TE，并将顶点v加入集合U，重复上述操作直U=V为止。函数中使用的预定义符号如下：#defineMAX32768/*无穷大权，表示顶点间不连通*/#defineMAXVEX30/*图中顶点数目的最大值*/typedefstructintStartVex,StopVex;/*边的起点和终点*/floatweight;/*边的权*/Edge;typedefstructcharvexs[MAXVEX];/*顶点信息*/floatarcs[MAXVEX*(MAXVEX-1)/2];/*邻接矩阵信息，压缩存储*/intn;/*图的顶点个数*/Graph;[函数]voidPrimMST(Graph*pGraph,Edgemst[])inti,j,k,min,vx,vy;floatweight,minWeight;Edgeedge;for(i=0;i＜pGraph-＞n-1;i++)mst[i].StartVex=0;mst[i].StopVex=i+1;mst[i].weight=pGraph-＞arcs[i];for(i=0;i＜______;i++)/*共n-1条边*/minWeight=(float)MAX;min=i;/*从所有边(vx,vy)中选出最短的边*/for(j=i;j＜pGraph-＞n-1;j++)if(mst[j].weight＜minWeight)minWeight=______;min=j;/*mst[min]最短的边(vx,vy),将mst[min]加入最小生成树*/edge=mst[min];mst[min]=mst[i];met[i]=edge;vx=______;/*vx为刚加入最小生成树的顶点下标*//*调整mst[i+1]到mst[n-1]*/for(j=i+1;j＜pGraph-＞n-1;j++)vy=mst[j].StopVex;if______/*计算(vx,vy)对应的边在压缩矩阵中的下标*/k=pGraph-＞n*vy-vy*(vy+1)/2+vx-vy-1;elsek=pGraph-＞n*vx-vx*(vx+1)/2+vy-vx-1;weight=______;if(weight＜mst[j].weight)mst[j].weight=weight;mst[j].StartVex=vx;

填空题[说明]欲开发一个绘图软件，要求使用不同的绘图程序绘制不同的图形。以绘制直线和圆形为例，对应的绘图程序如下表所示。不同的绘图程序DP1DP2绘制直线draw_a_line(x1,y1,x2,y2)drawline(x1,x2,y1,y2)绘制圆draw_a_circle(x,y,r)drawcircle(x,y,r)该绘图软件的扩展性要求，将不断扩充新的图形和新的绘图程序。为了避免出现类爆炸的情况，现采用桥接(Bridge)模式来实现上述要求，得到如下图所示的类图。某绘图软件类图[Java代码]________Drawing{________；________；classDP1{staticpublicvoiddraw_aline(doublex1,doubley1,doublex2,doubley2){/*代码省略*/}staticpublicvoiddraw_a_circle(doublex,doubley,doubler){/*代码省略*/}};classDP2(staticpublicvoiddrawline(doublex1,doublex2,doubley1,doubley2){/*代码省略*/}staticpublicvoiddrawcircle(doublex,doubley,doubler){/*代码省略*/}};classViDrawingimplementsDrawing{public{/*代码省略*/}public{________;}classV2DrawingimplementsDrawing{public{/*代码省略*/}public{________;}};abstractclassShape{privateDrawing_dp;________Shape(Drawingdp){_dp=dp;}public{_dp.drawLine(x1,y1,x2,y2);}public{_dp.drawCircle(x,y,r);}classRectangleextendsShape{privatedoublex1,x2,_y1,_y2;publicRectangle(Drawingdp,doublex1,doubley1,doublex2,doubley2){/*代码省略*/}publicvoiddraw(){/*代码省略*/}};classCircleextendsShape{privatedouble_x,_y,_r;publicCircle(Drawingdp,doublex,doubley,doubler){/*代码省略*/}publicvoiddraw(){drawCircle(_x,_y,_r);}

填空题[说明]计算一个整数数组a的最长递增子序列长度的方法描述如下：假设数组a的长度为n，用数组b的元素b[i]记录以a[i](0≤i＜n”)为结尾元素的最长递增子序列的长度为；其中b[i]满足最优子结构，可递归定义为：[C代码]下面是算法的C语言实现。(1)常量和变量说明a:长度为n的整数数组，待求其最长递增子序列b:长度为n的数组，b[i]记录以a[i](0≤i＜n”)为结尾元素的最长递增子序列的长度，其中0≤i＜nlen:最长递增子序列的长度i,j:循环变量temp:临时变量(2)C程序#jnclude＜stdio,h＞mtmaxL(int*b,mtn){mtI,temp=0for(i=0;i＜n;i++){(b[i]＞temp)temp=b[i]returntemp;intmain(){intn,a[100],b[100],i,j,len;scanf("%d",for(i=0;i＜n;i++){scanf("%d",________:for(i=1;i＜n;i++){for(j=0,len=0;________;j++){if(________}Printf("len:%d\n",maxL(b,n))Primtf("\n")}

填空题[问题1]利用存在的依赖关系构造一个图书馆的对象模型。

填空题[问题3]使用ORDB的查询语言，分别写出下列查询的SELECT语句；1)检索每个学生的学习课程和成绩。2)检索至少有一门课程的求学地与籍贯在同一城市的学生的学号和姓名。