软件水平考试(中级)软件设计师下午(应用技术)试题模拟试卷47

如果您发现本试卷没有包含本套题的全部小题,请尝试在页面顶部本站内搜索框搜索相关题目,一般都能找到。
5

阅读以下说明和C代码,将应填入(n)处的字句写在对应栏内。

 [说明]

 下面程序用来将打乱的单词还原为原来的次序,比如将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( (1) ){

 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=(2);//临时存储

 reCompose(p,temp);//将temp重组

 q=&root;

 while((flag=(3))&&q !=NULL){

 if(flag<0){//搜索左子树

 q=q->lChiid;

 }else(//搜索右子树

 q=q->rChild;

 }

 }//while

 if(flag==0){//找到匹配的,保存下标

 return (4);

 }

 }

 if( (5) ){//查找失败

 printf("cant unscramble the following word:%s",temp);;

 return -1;

 }

 };

(1)

10

阅读以下说明和Java代码,将应填入(n)处的字句写在对应栏内。

 [说明]

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

 以下示例展示了Proxy(代理)模式,PrinterProxy类执行一些比较“轻”的方法——设置名称和取得名称,需要真正执行“重”的方法——真正打印——时才初始Print类。图6-1显示了各个类间的关系。

 [图6-1]

 [Java代码]

 //Printable.Java

 publiC (1) Printable{

 public abstract void setPrinterName(String name);

 public abstract String getprinterName();

 public abstract void print(String string);

 }

 //Printer.Java

 public class Printer implements Printable{

 private String name;

 public Printer(){

 System.out.println("正在产生Printer的对象实例");

 }

 public Printer(String name){

 this.name=name;

 heavyJob("正在产生Printer的对象实例("+name+")");

 public void setPrinterName(String name){

 this.name=name;

 public String getPrinterName(){

 return name;

 public void print(String string){

 System.out.println("===" +name+" ====");

 System.out.println(string);

 }

 }

 //PrinterProxy.Java

 public class PrinterProxy (2) Printable{

 private String name;

 private Printer real;

 public PrinterProxy(){}

 public PrinterProxy(String name){

 this.name=name;

 }

 public gynchronized void setPrinterName(String name){

 if( (3) ){

 real.setPrinterName(name);

 }

 this.name=name;

 }

 public String getprinterName(){

 return name;

 }

 public void print(String string){

  (4);

 real.print(string);

 }

 private synchronized void realize(){//产生真正的Printer对象

 if(real==null){

 real=(5);

 }

 }

 }

(1)

16

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

 [说明]

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

 以下示例展示了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)

20

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

 [说明]

 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(( (1) )&&(HT[i].weight<minl)){

 *s1=i;

 min 1=HT[i].weight;

 }

 }

 for(i=0;i<=end;i++){/*找次小节点的序号*/

 if((HT[i].parent==0)&&( (2) )

 &&(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( (3) );

 HT[s1].parent=i;

 HT[s2].parent=i;

 HT[s1].sigh=left child;

 HT[s2].sigh=right child;

 HT[i].weight=(4);

 }

 }

 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, (5) );

 break;

 }

 }

 i++;

 if (Sen [1]==32) i++;

 }

 printf("\n%s",coding);

 }

(1)

26

阅读以下说明和程序流程图,将应填入 (n) 处的字句写在对应栏内。

 [说明]

 假定用一个整型数组表示一个长整数,数组的每个元素存储长整数的一位数字,则实际的长整数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)