2009~2023軟件設計師下午試卷

2009年~20232009200920092009（14:00～16:30150分鐘7115752009年上半年全國計算機技術與軟件專業(yè)技術資格（水平）（參看下表試題一（15分1（8分E1至E4的名稱和數(shù)據(jù)存儲D1至D4的名2（7分試題二（15分， ：部門（部門編號，部門名稱，位置分布，聯(lián)系電話，（a））員工（員工編號，員工姓名，崗位，電話號碼，工資，（b）經理（（c），任職時間）1（6分2-112、341:1、1:nm:n。2（6分3（3分的實體是（1）2-1中的員工存在（2）聯(lián)系（填寫聯(lián)系類型試題三（15分某銀行計劃開發(fā)一個自動存提款機模擬系統(tǒng)（ATMSystem。系統(tǒng)通過讀卡器Console（OperatorStartupShutdown（Session（PIN（Transaction從ATM卡賬戶取款（Withdraw向ATM卡賬戶存款（Deposit（Transfer進行驗證。若個人驗證碼錯誤，則轉個人驗證碼錯誤處理（InvalidPINProcess。每個事UML3-1所示，一次會話的序列圖（不考慮驗證）3-2所示。1（7分3-1A1A2所對應的參與者，U1U3所對應的用SessionInsertCard、InvalidPINProcessTransfer）2（6分3（2分3-1中用例U3Withdraw、Deposit試題四（15分到其他各頂點的最短路徑之和最小。算法首先需要求出每個頂點到其它任一頂點的最短路為??={1,2,?,??}，??=

為權重矩陣。設??(??)為從頂點??到頂點??的權重。當k=0時，不存在中間頂點，因此??(0)=

；當??>0

有的中間頂點均屬于集合{1,2??}????(??)=??(???1若中間頂點不包括頂點??，則??(??)=??(???1)

??(??)=

??=

)??>

給出了任意兩個頂點之間的最短路徑，即對所有????∈????(??)表示頂點??到頂點??的最短路徑。1（12分（62（3分1中偽代碼的時間復雜度為（7）（Ο符號表示試題五（15分閱讀下列說明和C函數(shù)代碼，將應填入（n）InOrder()借助棧實現(xiàn)二叉樹的非遞歸中序遍歷typedefstructBtNodeElemTypedata;/*節(jié)點的數(shù)據(jù)域，ElemType的具體定義省略*/structBtNode*lchild*rchild**/}BtNode,InOrder()中，用棧暫存二叉樹中各個節(jié)點的指針，并將棧表示為不含頭節(jié)點typedefstructStNode{/*BTreeelem; /**/structStNode*link;【CintInOrder(BTree /*BTree /*ptrStNode*q; /*q*/StNode*stacktop=NULL;/*初始化空棧的棧頂指針stacktop*/ptr=root; /*ptr*/while((1)||stacktop!=NULL){while(ptr!=NULL)q=(StNode*)malloc(sizeof(StNode));if(q==NULL)return-1;q->elem=(2)stacktopq;/*stacktop*/ptr=(3);/*進入左子樹*/q=(4) /* /*visit是訪問節(jié)點的函數(shù)，其具體定義省略*/ptr=(5); /*進入右子樹*/ /*return}試題六（15分C++代碼，將應填入（n）classMatrixclassImageImp{virtualvoiddoPaint(Matrixm0classWinImp:publicImageImp{voiddoPaint(Matrixm*Windows*classLinuxImp:publicImageImp{voiddoPaint(Matrixm*Linux*classImage{voidsetImp(ImageImp*imp){(1)=imp;virtualvoidparseFile(stringfileName)=(2)classBMP:publicImage{voidparseFile(stringfileName)BMP(3)classGIF:publicImageclassJPEG:publicImagevoidmain()Windowsdemo.bmpImage*image1=(4)ImageImp*imageImp1=(5)(6)105種操作系統(tǒng)，不考慮類Matrix，若采用橋接設計模式則至少需要設計（7）個類。試題七（15分Java代碼，將應填入（n）【JavaclassMatrixabstractclassImageImppublicabstractvoiddoPaint(Matrixm)classWinImpextendsImageImpclassLinuxImpextendsImageImpabstractclassImagepublicvoidsetImp(ImageImpimp)(1)=publicabstractvoidparseFile(StringfileName);protected(2)imp;classBMPextendsImagepublicvoidparseFile(StringfileName)BMP(3)classGIFextendsImageclassJPEGextendsImagepublicclassjavaMainpublicstaticvoidmain(String[]args)windowsdemo.bmpImageimage1=(4)ImageImpimageImp1=(5)(6)105種操作系統(tǒng)，不考慮類Matrix，若采用橋接設計模式則至少需要設計（7）個類。2009200920092009（14:00～16:30150分鐘7115752009年下半年全國計算機技術與軟件專業(yè)技術資格（水平）（參看下表試題一（15分CCMS。如果信用卡申請被銀行接受，CCMS將記錄該客戶的基本信用卡激活。信用卡客戶向CCMS提交激活請求，用信用卡號和密碼激活該信用卡。激活操作結束后，CCMS將激活通知發(fā)送給客戶，告知客戶其信用卡是否被成功激CCMS查詢并核實其交易信息（包括信用卡交易記錄及交易額。 0層數(shù)據(jù)流1（3分1-1中的E1?E32（3分1-1（注：數(shù)3（5分1-2（注：數(shù)據(jù)流4（4分試題二（15分\huse1123.o123等信息。地址薄中一個聯(lián)系人只能屬于一個用4種，分別表示郵件是屬于收件箱、發(fā)件箱、己發(fā)送箱和廢件箱。一封郵件可以發(fā)送給多 ：地址簿（（a）12，3）郵件（（b）間附件（（c），附件號，附件文件名，附件大小1（5分E-R2-1所示，請指出地址簿與用戶、電子郵件帳號與郵2（4分3（6分2中給出的地址簿、郵件和附件關系模式的主鍵，如果關系模式存在試題三（15分某企業(yè)為了方便員工用餐，為餐廳開發(fā)了一個訂餐系統(tǒng)（COS：CafeteriaOrderingSystemUML進行建模。系統(tǒng)的頂層用例圖和一次訂餐的活3-13-2所示。 1（2分3-1中A1A22（8分3（4分4（1分試題四（15分0-1背包問題可以描述為：有??個物品，對??=1,2??，第??個物品價值為????????（????和????為非負數(shù)，背包容量為??（??為非負數(shù)

????????≤其中，????∈{0,1}，????=0表示第??個物品不放入背包，????=1表示第??個物品放入背包。0-1背包問題，請?zhí)畛湎旅鎮(zhèn)未a中（1）~（4）處空缺。判斷并剪枝那些即使擴展了也不能得到最優(yōu)解的結點?，F(xiàn)在假設已經設計了BOUND(??,??,??,??)函數(shù)，其中??、??、??和??分別表示當前已經獲得的價值、當前背包的1（8分（42（7分1/0分別表示選擇/不選擇對應物品。除了根結點之外，每個左孩子結點旁邊的上下兩（5）（6）對于上述實例，若采用窮舉法搜索整個解空間，則搜索樹的結點數(shù)為（7）了上述回溯法，搜索樹的結點數(shù)為（8）。試題五（15分C++代碼，將應填入（n）#include<list>#include<iostream>#include<string>usingnamespaceclassAbstractFile{stringnamevoidprintName(){cout<<name;virtualvoidaddChild(AbstractFile*file)=virtualvoidremoveChild(AbstractFile*file)=virtuallist<AbstractFile*>*getChildren()=classFile:publicAbstractFile{File(stringname){(1)=name;voidaddChild(AbstractFile*file){return;}voidremoveChild(AbstractFile*file){return;}(2)*getChildren(){return(3);classFolder:publicAbstractFile{list<AbstractFile*childListFolder(stringname){(4)=name;voidaddChild(AbstractFile*file){childList.push_back(file);}voidremoveChild(AbstractFile*file){childList.remove(file);}list<AbstractFile*file>*getChildren(){return(5);}voidmain()構造一個樹形的文件/AbstractFile*rootFolder=newFolder("c:\\");AbstractFile*compositeFolder=newFolder("composite");AbstractFile*windowsFolder=newFolder("windows");AbstractFile*file=newFile("TestComposite.java");試題六（15分Java代碼，將應填入（n）【Javaimportjava.util.ArrayList;importjava.util.List;(1)classAbstractFileprotectedStringpublicvoidprintName(){System.out.println(name);}publicabstractbooleanaddChild(AbstractFilefile);publicabstractbooleanremoveChild(AbstractFilefile);publicabstractList<AbstractFile>getChildren();classFileextendsAbstractFilepublicFile(Stringname){=name;publicbooleanaddChild(AbstractFilefile){returnfalse;}publicbooleanremoveChild(AbstractFilefile){returnfalse;}publicList<AbstractFile>getChildren(){return(2);}classFolderextendsAbstractFile{privateList<AbstractFile>childList;publicFolder(Stringname){=this.childList=newpublicbooleanaddChild(AbstractFilefile){returnchildList.add(file);publicbooleanremoveChild(AbstractFilefile){returnchildList.remove(file);public(3)<AbstractFile>getChildren(){return(4);publicclassClientpublicstaticvoidmain(String[]args)創(chuàng)造一個樹形的文件/AbstractFilerootFolder=newFolder("c:\\");AbstractFilecompositeFolder=newFolder("composite");AbstractFilewindowsFolder=newFolder("windows");AbstractFilefile=newFile("TestComposite.java");privatestaticvoidprintTree(AbstractFileifile){List<AbstractFile>children=ifile.getChildren();if(Children==null)return;for(AbstractFilefile:Children)(5)試題七（15分閱讀以下說明和C程序，將應填入（n）n（n1000）1，2，3，…，nA的鐵軌上；一旦車廂駛入B方向鐵軌就不能再回到車站，如下圖所示，其中Station為棧結1000節(jié)車廂。下面的C程序判斷能否從BvoidInitStack(STACK*s)voidPush(STACK*sinte)1voidPop(STACK*s)1intTop(STACKs)：返回非空棧的棧頂元素值，棧中元素數(shù)目不變intIsEmpty(STACKs)10【C#include/**/intmain(){STACKstation;intstate[1000];int /*intbeginijmaxNo;/*maxNoA*/scanf("%d",：");if(n<1)return-1;/*state[*/for(i=0;i<n;i++)scanf("%d",(1)*maxNo=/*state[i*/for(i=0;i<n;){if(2)*if(state[iTop(station)**/print("%d",Top(station));i++;}elseif((3))return1;}elsebegin=(4)for(j=begin+1;j<=state[i];j++){Push(&station,j);else**/begin=maxNo;for(j=begin;j<=state[i];j++){Push(&station,j);maxNo=(5)return0;2010201020102010（14:00～16:30150分鐘6115752010年上半年全國計算機技術與軟件專業(yè)技術資格（水平）（參看下表試題一（15分，1（3分1-1中的實體E1?E32（3分1-2中的數(shù)據(jù)存儲D1?D33（6分1-2中加工PP1-2還缺失了兩條數(shù)據(jù)流，請給出這兩條數(shù)據(jù)流的起4（3分試題二（15分2-1所示。2-2所示。2-3所示。：開課情況（（1），授課學期實驗（（2），實驗類型，難度，學時，安排周次實驗計劃（（3），實驗時間，人數(shù)）實驗員（（4），級別學生（（5），姓名，年齡，性別實驗成績（（6），實驗成績，評分實驗員1（6分2（6分3（3分試題三（15分3-1給出了售票機的面板示系統(tǒng)采用面向對象方法開發(fā)，使用UML進行建模。系統(tǒng)的頂層用例圖和類圖分別如3-23-3所示。 1（5分3-2中A1A2所對應的參與者，U1所對應的用例，以（12（7分3-3中缺少的C1?C4所對應的類名以及（3）?（6）處3（3分試題四（15分閱讀下列說明和C130的頂點，將其放入拓撲序列中，同時從圖中刪除該頂點以（2int*TopSort(LinkedDigraphG)G中的頂點進行拓撲排序，返回拓撲序列中的頂點編號序列，若不能完成拓撲排序，則返回空指針。其中，圖G中的1v1，v2，…，vnG采用鄰接表表示，其數(shù)據(jù)類型#defineMAXVNUM50 typedefstructArcNode intadjvex; structArcNode*nextarc; typedefstructAdjList{ charvdata; ArcNode typedefstructLinkedDigraph{ intn; AdjList TopSort中用到了隊列結構（Queue的定義省略int*TopSort(LinkedDigraphG)ArcNode /*臨時指針QueueQ; /*臨時隊列,保存入度為0的頂點編號*/intk=0; /*臨時變量,用作數(shù)組元素的下標*/intj=0,w=0;/*臨時變量,用作頂點編號*/int*topOrder,/*topOrder=(int/*GinDegree=(intif(!inDegree||!topOrder)return(1)*forj1jG.nj**/topOrder[j]=0;inDegree[j]=0;forj1jG.nj*G*/for(p=G.Vhead[j].firstarc;p;p=p->nextarc)inDegree[p->adjvex]+=forj1jG.n;j*G0*/if(0==inDegree[j])EnQueue(&Q,j);while(!isEmpty(Q))(2)*隊頭頂點出隊列并用wtopOrder[k++]=/*w1（w及從該頂點出發(fā)的弧的操作）*/for(p=G.Vhead[w].firstarc;p;p=p->nextarc){(3)-=if(0==(4))EnQueue(&Q,p-}/*for}/*whileif((5))returnreturn}/*TopSort1（9分（1）~（52（2分4-1所示的有向圖GTopSort3（4分ne，那么用鄰接表存儲該圖時，實現(xiàn)上述拓TopSort的時間復雜度是（6）。若有向圖采用鄰接矩陣表示（4-14-3所示，且TopSort中有關鄰接表的操作修改為針對鄰接矩陣的操作，那么對于有??個頂點、??條弧的有向無環(huán)圖，實現(xiàn)上述拓撲排序算法的時間復雜度是（7）試題五（15分C++代碼，將應填入（n）5-1所示。SubSonicFlySuperSonicFly分別描述亞音速飛行和超音速飛行的行VerticalTakeOffLongDistanceTakeOff分別描述垂直起飛與長距離起飛的行為。#include<iostream>usingnamespacestd;classFlyBehaviorpublic:virtualvoidfly()=classSubSonicFly:publicFlyBehaviorpublicvoidfly(cout亞音速飛行！endlclassSuperSonicFly:publicFlyBehaviorpublicvoidfly(cout超音速飛行！endlclassTakeOffBehaviorpublic:virtualvoidtakeOff()=classVerticalTakeOff:publicTakeOffBehaviorpublicvoidtakeOffcout垂直起飛！endlclassLongDistanceTakeOff:publicTakeOffBehavior{publicvoidtakeOffcout長距離起飛！endlclassAirCraft{protected:(1)(2)publicvoidfly(){(3);voidtakeOff(){(4);classHelicopter:publicAirCraft{public:Helicopter()flyBehavior=new(5)takeOffBehavior=new(6)(7)if(!flyBehavior)deleteif(!takeOffBehavior)delete試題六（15分Java代碼，將應填入（n）6-1所示。SubSonicFlySuperSonicFly分別描述亞音速飛行和超音速飛行的行VerticalTakeOffLongDistanceTakeOff分別描述垂直起飛與長距離起飛的行為。【JavainterfaceFlyBehavior{publicvoidfly();classSubSonicFlyimplementsFlyBehaviorpublicvoidfly(System.out.println("亞音速飛行！classSuperSonicFlyimplementsFlyBehaviorpublicvoidfly(System.out.println("超音速飛行！interfaceTakeOffBehavior{publicvoidtakeOff();classVerticalTakeOffimplementsTakeOffBehaviorpublicvoidtakeOffSystem.out.println("垂直起飛！classLongDistanceTakeOffimplementsTakeOffBehaviorpublicvoidtakeOff(System.out.println("長距離起飛！abstractclassAirCraft{protected(1);protected(2)publicvoidfly(){(3);publicvoidtakeOff(){(4);classHelicopter(5)publicHelicopter(){flyBehavior=new(6);takeOffBehavior=new(7)2010201020102010（14:00～16:30150分鐘6115752010年下半年全國計算機技術與軟件專業(yè)技術資格（水平）（參看下表試題一（15分1-201（3分1-1中的實體E1?E32（3分1-2中的數(shù)據(jù)存儲D1?D33（9分1-2中處理（加工）P1和P2除加工P1P21-21條數(shù)據(jù)流，請給出其起點試題二（15分2-1所示。：業(yè)主（（1），姓名，房屋面積，工作單位，聯(lián)系電話）員工（（2），姓名，出生年月，性別，住址，聯(lián)系電話，職務，密碼部門（（3），部門名稱，部門電話）收費標準（（4）收費信息（（5），收費類型，收費金額，員工號1（8分2（5分，2-1中的實體、聯(lián)系和聯(lián)系的類型。3（2分試題三（15分7UML3-1所示。1（8分2（4分3-23-2S1?S4所對應的狀態(tài)名以及（7）?（10）處所對應的遷移（transition）名。3（3分試題四（15分閱讀下列說明和C13對于n個元素的關鍵字序列{??1??2????}{????≤????≤

{????≥????≥

其中，??=1,24-1是一個大頂堆的例子。index下面將C代碼中需要完善的三個函數(shù)說明如下：maxHeapInsert(Akey)key插入到大頂堆A的最后位置，再將A調#definePARENT(i)i/2typedefstructarray{int*int_arrayintarray_sizeint }【CintheapMaximum(ARRAY*A){return(1);intheapExtractMax(ARRAY*A){intmax;max=A-(2)A->array_size--heapify(AA->array_size0)returnintmaxHeapInsert(ARRAY*A,intkey){inti,*p;if(A->array_sizeA->capacityp=(int*)realloc(A->int_array,A->capacity*2*sizeof(int));if(!p)return-1;A->int_array=A->capacity=2*A-A->array_size++;i=(3);while(i>0&&(4))A->int_array[i]=A->int_array[PARENT(i)];i=PARENT(i);(5)return1（10分（52（3分CheapMaximum、heapExtractMaxmaxHeapInsert的時間復雜度的緊致上界分別為（6）、（7）、（8）（O符號表示。3（2分10插入到堆A={15,13,9,5,12,8,7,4,0,6,2,1}中,maxHeapInsertA中的第（9）個位置（1始試題五（15分C++代碼，將應填入（n）Company為抽象類，定義了在組織結構圖上添加（Add）和刪除（Delete）分公#include<iostream>#include<list>#include<string>usingnamespaceclassCompanyprotectedstringpublicCompany(stringname){(1)=name;(2)(3)classConcreteCompany:publicCompany{private:list<(4)>publicConcreteCompany(stringname):Company(name){}voidAdd(Company*c){(5).push_back(c);}voidDelete(Company*c){(6).remove(c);classHRDepartment:publicCompany{public:HRDepartment(stringnameCOmpant(nameclassFinanceDepartment:publicCompany{public:FinanceDepartment(stringnameCompany(namevoidmain()ConcreteCompany*rootnewConcreteCompany("北京分公司");root->Add(newHRDepartment("總公司人力資源部"));ConcreteCompany*compnewConcreteCompany("上海分公司");comp->Add(newHRDepartment("上海分公司人力資源部"));(7)ConcreteCompany*comp1newConcreteCompany("南京辦事處");comp1->Add(newHRDepartment("南京辦事處人力資源部"));(8)試題六（15分Java代碼，將應填入（n）Company為抽象類，定義了在組織結構圖上添加（Add）和刪除（Delete）分公【Javaimport(1)CompanyprotectedStringpublicCompany(Stringname){(2)=name;publicabstractvoidAdd(CompanycpublicabstractvoidDelete(Companyc)classConcreteCompanyextendsCompanyprivateList<(3)>children=newArrayList<(4publicConcreteCompany(Stringname){super(name);}publicvoidAdd(Companyc){(5).add(c);}publicvoidDelete(Companyc){(6).remove(c);classHRDepartmentextendsCompanypublicHRDepartment(Stringname){super(name);classFinanceDepartmentextendsCompanypublicFinanceDepartment(Stringname){super(name);publicclassTestpublicstaticvoidmain(String[]args)ConcreteCompanyrootnewConcreteCompany("北京總公司");root.Add(newHRDepartment("總公司人力資源部"));root.Add(newFinanceDepartment("總公司財務部"));ConcreteCompanycompnewConcreteCompany("上海分公司");comp.Add(newHRDepartment("上海分公司人力資源部"));comp.Add(newFinanceDepartment("上海分公司財務部"));(7)ConcreteCompanycomp1newConcreteCompany("南京辦事處");comp1.Add(newHRDepartment("南京辦事處人力資源部"));comp1.Add(newFinanceDepartment("南京辦事處財務部"));(8)2011201120112011（14:00～16:30150分鐘611575（參看下表試題一（15分1-201（3分1-1中的實體E1?E32（4分1-2中的數(shù)據(jù)存儲D1?D43（6分4（2分說明實體E1E3試題二（15分：倉庫信息（（1），倉庫位置，倉庫容量供應情況（（2），服裝質量等級）采購訂單（（3）采購訂單明細（（4）1（6分2（6分3（3分2-1進行修改，畫出修改后的實體間聯(lián)系和聯(lián)系的類型。試題三（15分currentactive（selected現(xiàn)采用面向對象方法開發(fā)該圖形編輯器，使用UML進行建模。構建出的用例圖和類圖3-13-2所示。1（4分3-1中U1和U2所對應的用例，以及（1）和（2）處所對2（8分3（3分試題四（15分閱讀下列說明和C131000000?5之間。排序算??，將410434應1098個位置上。算法具體的步驟為：1：統(tǒng)計每個元素值的個數(shù)?！綜RR6anvoidsort(intn,inta[],intb[]){intc[R],i;for(i=0;i<(1);i++)c[i]=for(i=0;i<n;i++){c[a[i]]=(2);for(i=1;i<R;i++){c[i]=(3);for(i=0;i<n;i++){b[c[a[i]]-1]=(4);c[a[i]]=c[a[i]]-1（8分（42（4分根據(jù)C代碼，函數(shù)的時間復雜度和空間復雜度分別為（5）和（6）（3（3分根據(jù)以上C代碼，分析該排序算法是否穩(wěn)定。若穩(wěn)定，請簡要說明（試題五（15分C++代碼，將應填入（n）5-1中的甜點菜單。類Menultem表示菜單中的菜式。#include<iostream>#include<list>#include<string>usingnamespaceclassMenuComponent{protected:stringname;publicMenuComponent(stringname){this->name=name;}stringgetName(){returnname;}(1) virtualvoidprint(0classMenuItem:publicMenuComponent{private:doubleprice;publicMenuItem(stringname,double:MenuComponent(name){this->price=price;doublegetPrice(){returnprice;voidadd(MenuComponent*menuComponentreturnvoidprint()cout<<""<<getName()<<","<<getPrice()<<classMenu:publicMenuComponent{private:list<(2)>menuComponents;publicMenu(stringname):MenuComponent(name)voidadd(MenuComponent*menuComponent(3)voidprint()cout<<"\n"<<getName()<<"\n"<<endl;std::list<MenuComponent*>::iteratoriter;for(iter=menuComponents.begin();iter!=menuComponents.end();iter++(4)-voidmain()MenuComponent*allMenus=newMenu("ALLMENUS");MenuComponent*dinerMenu=newMenu("DINERMENU");Menuallmenus->add(dinerMenu)dinerMenu(5)- 試題六（15分Java代碼，將應填入（n）6-1中的甜點菜單。類Menultem表示菜單中的菜式?！綣avaimport(1)MenuComponentprotectedString(2)publicabstractvoidprint()publicStringgetName(){returnname;classMenultemextendsMenuComponent{privatedoubleprice;publicMenuItem(Stringname,doubleprice){=name;this.price=price;publicdoublegetPrice(){returnprice;publicvoidadd(MenuComponentmenuComponentreturn;添加新菜單publicvoidprint(){System.out.print(""+getName());System.out.println(","+getPrice());classMenuextendsMenuComponentprivateList<MenuComponent>menuComponents=newpublicMenu(Stringname){=name;publicvoidadd(MenuComponentmenuComponentmenuComponents.(3)publicvoidprint(){System.out.print("\n"+getName());System.out.println(","+ Iteratoriterator=menuComponents.iterator();while(iterator.hasNext()){MenuComponentmenuComponent=(4)classMenuTestDrivepublicstaticvoidmain(Stringargs[]){MenuComponentaIIMenus=newMenu("ALLMENUS");MenuComponentdinerMenu=newMenu("DINERMENU”);allMenus.add(dinerMenu)dinerMenu(5)2011201120112011（14:00～16:30150分鐘611575（參看下表試題一（15分1（3分使用說明中的術語，給出圖中E1?E32（2分使用說明中的術語，給出圖中D1?D23（6分4（4分1-21-31-3中數(shù)據(jù)流試題二（15分：員工（員工號，姓名，職位，電話號碼，工資，（a）客戶（（b），單位名稱，通信地址，所屬省份，聯(lián)系人，聯(lián)系電話，銀行賬號托運申請（（c），貨物名稱，數(shù)量，運費，出發(fā)地，目的地）安排承運（（d），裝貨時間，到達時間，業(yè)務員1（5分2（8分3（2分補充）2-1所示的實體聯(lián)系圖，請給出修改后的實體聯(lián)系圖和關系模式。試題三（15分系統(tǒng)中存儲了特定區(qū)域的道路交通網(wǎng)的信息。道路交通網(wǎng)由若干個路段（Road的。在某些地理坐標點上安裝了訪問控制（AccessControl）（Card3種行駛卡。常規(guī)卡（RegularCard）有效期（ValidPeriod）為一年，可單次卡都是預付卡（PrepaidCard，需要客戶（Customer）預存一定的費用。等信息。在到達行程終點時，系統(tǒng)根據(jù)行駛的里程數(shù)和所持卡的里程單價（UnitPrice）計（Invoice3-13-2所示。1（4分2（8分3-2C1?C6所對應的類名以及（2）?（3）處3（3分根據(jù)說明中的描述，給出RoadSegment、Trajectory和Card試題四（15分閱讀下列說明和C代碼，將應填入（n）nm個不同的供應商處購得。供應商j供應的部件iwij和價格cijcc的最小重首先定義解空間。解空間由長度為n（cc（cc【C下面是該算法的Ci0n-1intn=3;intm=3;intcc=intw[3][3]={{1,2,3},{3,2,1},{2,2,intc[3][3]={{1,2,3},{3,2,1},{2,2,intbestW=8;intbestC=intbestX[3]={0,0,0};intcw=0;intcp=intx[3]={0,0,intbacktrack(inti){intj=0;intfound=ifin1**/bestW=cw;bestC=for(j=0;j<n;j++)(1)returnif(cpcc**/found=1;for(j=0;(2);j++)/*ij(3)cw=cw+cp=cp+if(cpcc&&(4)*if(backtrack(i+1)){found=1;/*回溯cw=cw-(5)試題五（15分C++代碼，將應填入（n）采用狀態(tài)（State）5-2所示的類圖。其中類State為抽象類，定義了投幣、退幣、出紙巾等方法接口。類SoldState、SoldOutState、NoQuarterState和HasQuarterState5-14種狀態(tài)：售出紙2元錢。#include<iostream>usingnamespacestd;classTissueMachineclassState{public:virtualvoidinsertQuarter(0virtualvoidejectQuarter(0virtualvoidturnCrank(0按下“出紙巾”virtualvoiddispense0/*SoldOutState、NoQuarterState、HasQuarterState、SoldState*TissueMachine*tissueMachineclassTissueMachine{(1)*soldOutState,*noQuarterState,*hasQuarterState,*soldState,intcountpublicTissueMachine(intnumbers);voidsetState(State*state);State*getHasQuarterState();State*getNoQuarterState();State*getSoldState();State*getSoldOutState();intgetCount();voidNoQuarterState::insertQuarter(){tissueMachin->setState((2));voidHasQuarterState::ejectQuarter(){tissusMachin->setState((3));voidSoldState::dispense()if(tissueMachine->getCount()>0){tissueMachine->setState((4)}elsetissueMachine->setState((5)試題六（15分Java代碼，將應填入（n）采用狀態(tài)（State）6-2所示的類圖。其中類State為抽象類，定義了投幣、退幣、出紙巾等方法接口。類SoldState、SoldOutState、NoQuarterState和HasQuarterState6-14種狀態(tài)：售出紙2元錢?！綣avaimportjava.util.*;interfaceState{publicvoid publicvoid publicvoid 按下“出紙巾”publicvoid classTissueMachine(1)soldOutState,noQuarterState,hasQuarterState,soldState,state=soldOutState;intcount0紙巾數(shù)publicTissueMachine(intnumbers**publicStategetHasQuarterState(){returnhasQuarterState;}publicStategetNoQuarterState(){returnnoQuarterState;}publicStategetSoldState(){returnsoldState;}publicStategetSoldOutState(){returnsoldOutState;}publicintgetCount(){returncount;}classNoQuarterStateimplementsState{TissueMachinetissueMachine;publicvoidinsertQuarter(){tissueMachine.setState((2));classHasQuarterStateimplementsState{TissueMachinetissueMachine;publicvoidejectQuarter(){tissueMachine.setState((3));classSoldStateimplementsState{TissueMachinetissueMachine;publicvoiddispense(){if(tissueMachine.getCount()>0){tissueMachine.setState((4)}elsetissueMachine.setState((5));2012201220122012（14:00～16:30150分鐘6115752012年上半年全國計算機技術與軟件專業(yè)技術資格（水平）（參看下表試題一（15分處理借閱。借閱者要借閱圖書時，系統(tǒng)必須對其身份（ID）進行檢查。通ID是否合法，若合法，則檢查借閱者在逾期未還圖書表中是否有逾期未還圖書，以及罰金1-201（4分1-1中的實體E1?E42（4分1-2中的數(shù)據(jù)存儲D1?D43（4分DFD建模時，需要對有些復雜加工（處理）進行進一步精化，繪制下層數(shù)據(jù)流圖。1-21層數(shù)據(jù)流圖中應分解為哪些加工？（使用說明中的4（3分試題二（15分2-2：病床護士（（1）手術室護士（（2）病人（（3），姓名，性別，地址，身份證號，電話號碼，入院時間診斷書（（4），診斷，診斷時間手術醫(yī)生安排（（5），醫(yī)生責任1（6分2（5分3（42-1進行修改，畫出補充后的實試題三（15分（Order（quantities（name（addresspayment（（volume（nameprice體積（cubicvolumedate發(fā)送要求（DeliveryTimeWindow運貨單（deliveryslip）上簽收。簽收后的運貨單最終需交還給訂單處理人員。3-13-2所示的類圖。1（5分3-1A1?A3U1?U2處所對應2（7分3（3分根據(jù)說明中的描述，將類C2和C3的屬性補充完整（屬性名使用說明中給出的英文詞試題四（15分閱讀下列說明和C13ABnABi個作業(yè)的時間分別為????和????。B上處理時間長。一臺處理機在某個時刻只能處理一個作業(yè)，而且作業(yè)處理是不可中斷的，n個作業(yè)被這兩臺處理機處理 m=min(∑ai,∑ p(x,y,k)=1表示前k個作業(yè)可以在AxB用時不超過y時間內處理完成，則p(x,y,k)=p(x?????,y,k?1)||p(x,y?????,k?1)（||表示邏輯或操作?！綜下面是該算法的Cp：三維數(shù)組，長度為(m1*(m1*(n1)（2）C#includeintn,inta[60],b[60],voidread(*輸入n、a、b,m,*voidschedule**/intx,y,k;for(x=0;x<=m;x++){for(y=0;y<=m;y++){(1)for(k=1;k<=n;k++)p[x][y][k]=0;for(k=1;k<=n;k++){for(x=0;x<=m;x++){for(y=0;y<=m;y++)if(x-a[k-1]>=0)(2)if((3)p[x][y][k]=(p[x][y][k]||p[x][y-b[k-1]][k-voidwrite(**/intx,y,temp,max=m;for(x=0;x<=m;x++){for(y=0;y<=m;y++){if((4))temp (5)if(temp<max)max=printf("\n%d\n",voidmain(){read();schedule();write();1（9分（1）~（52（2分根據(jù)以上C代碼，算法的時間復雜度為（6）（O符號表示3（4分優(yōu)解為（7）,最優(yōu)解的值（即最短處理時間）為（8）。最優(yōu)解用（x1x2x3,x4x5x6）表示其中若第iA上處理,則xi=1,否則xi=2（1,1,1,1,2,2）1,2,34A上處理,56B上處理。試題五（15分C++代碼，將應填入（n）#include<iostream>#include<string>usingnamespaceconstintESPRESSO_PRICE=25;constintDRAKROAST_PRICE=20;constintMOCHA_PRICE=10;constintWHIP_PRICE=8;classBeverage(1):stringpublic(2)(){returndescription;(3)classCondimentDecoratorpublicBeverage(4)classEspressopublicBeveragepublicEspresso(){description="Espresso";}intcost(){returnESPRESSO_PRICE;}classDarkRoastpublicBeveragepublicDarkRoast(){description="DardRoast";}intcost(){retrunDRAKROAST_PRICE;}classMochapublicCondimentDecoratorpublicMocha(Beverage*beverage){this->beverage=beverage;}stringgetDescription(){returnbeverage->getDescription()+intcost(){returnMOCHA_PRICE+beverage->cost();classWhippublicCondimentDecoratorpublicWhip(Beverage*beverage){this->beverage=beverage;}stringgetDescription(){returnbeverage->getDescription()+intcost(){returnWHIP_PRICE+beverage->cost();intmain()Beverage*beverage=newDarkRoast();beverage=newMocha((5));beverage=newWhip((6)cout<<beverage->getDescription()<<"￥"<<beverage->cost()<<endl;return0;DarkRoast,Mocha,Whip試題六（15分Java代碼，將應填入（n）【Javaimport(1)classBeverageStringdescription="UnknownBeverage";public(2)(){returndescription;}public(3)abstractclassCondimentDecoratorextendsBeverage(4)classEspressoextendsBeverageprivatefinalintESPRESSO_PRICE=publicEspresso(){description="Espresso";}publicintcost(){returnESPRESSO_PRICE;}classDarkRoastextendsBeverageprivatefinalintDARKROAST_PRICE=publicDarkRoast(){description="DarkRoast";}publicintcost(){rcturnDARKROASTPRICE;}classMochaextendsCondimentDecoratorprivatefinalintMOCHA_PRICE=publicMocha(Beveragebeverage){this.beverage=beverage;}publicStringgetDescription(){returnbeverage.getDescription()+",publicintcost(){returnMOCHA_PRICE+beverage.cost();classWhipextendsCondimentDecoratorprivatefinalintWHIP_PRICE=publicWhip(Beveragebeverage){this.beverage=beverage;}publicStringgetDescription(){returnbeverage.getDescription()+",publicintcost(){returnWHIP_PRICE+beverage.cost();publicclassCoffeepublicstaticvoidmain(Stringargs[]){Beveragebeverage=newDarkRoast();beverage=newMocha((5));beverage=newWhip((6)System.out.println(beverage.getDescription()+"￥"+DarkRoast,Mocha,Whip2012201220122012（14:00～16:30150分鐘6115752012年下半年全國計算機技術與軟件專業(yè)技術資格（水平）試題一（15分CrystalReports生成相關報表。1-20 1（4分1-1中的實體E1?E42（4分1-2中的數(shù)據(jù)存儲D1?D43（4分4（3分試題二（15分：員工（員工號，姓名，（a），聯(lián)系方式，工資會議申請（（b）策劃任務（（c），策劃內容，參與人數(shù)，要求完成時間）執(zhí)行策劃（（d），實際完成時間1（5分2（7分3（3分試題三（15分3%的折扣，現(xiàn)金支付沒有折扣。10%50%的賠償金。1（6分3-13-1中UC1?UC62（7分3-23-2中C1?C73（2分3-2進行怎樣的修改？（請用文字說明）試題四（15分閱讀下列說明和C13nCn{??1??2????}，且有????≤C(1≤i≤n)n個【Cs：數(shù)組，長度為n0b：數(shù)組，長度為n，b[i]i+10firstfitintfirstfit(){inti,j;k=for(i=0;i<n;i++){b[i]=0;for(i=0;i<n;i++)(1)while(C-b[j]<s[i]){j++;(2)k=k>(j+1)?k:(j+returnbestfitintbestfit(){inti,j,min,m,temp;k=0;for(i=0;i<n;i++){b[i]=0;for(i=0;i<n;i++){min=C;m=k+for(j=0;j<k+l;j++){temp=C-b[j]-s[i];if(temp>0&&temp<min)(3)m=(4)k=k>(m+1)?k:(m+return1（8分（42（4分根據(jù)說明和C（5）和（6）算法設計策略，時間復雜度分別為（7）和（8）（O符號表示。3（3分n=10，C=10，各個貨物的體積為{4273542362}。該實例在最先適宜和最優(yōu)適宜策略下所需的集裝箱數(shù)分別為（9）和（10）的情況，這兩種求解策略能否確保得到最優(yōu)解？（11）（能或否）試題五（15分C++代碼，將應填入（n）式設計該系統(tǒng)。以SQLServer和Access兩種數(shù)據(jù)庫以及系統(tǒng)中的數(shù)據(jù)庫表Department5-1所示。 #include<iostream>usingnamespacestd;classDepartment**classIDepartment{public(1)=(2)=classSqlserverDepartment:(3)publicvoidInsert(Department*department)cout<<"InsertarecordintoDepartmentinSQLDepartmentGetDepartment(intid)/*classAccessDepartment:(4)publicvoidInsert(Department*department)cout<<"InsertarecordintoDepartmentinDepartmentGetDepartment(intid)/*(5)public(6)=classSqlServerFactory:publicIFactory{public:IDEpartment*CreateDepartment(){returnnewSqlserverDepartment();classAccessFactory:publicIFactory{public:IDEpartment*CreateDepartment(){returnnewAccessDepartment();試題六（15分Java代碼，將應填入（n）式設計該系統(tǒng)。以SQLServer和Access兩種數(shù)據(jù)庫以及系統(tǒng)中的數(shù)據(jù)庫表Department6-1所示。 【JavaimportclassDepartment*代碼省略*interfaceIDepartment(1)(2)classSqlserverDepartment(3)publicvoidInsert(Departmentdepartment)System.out.println("InsertarecordintoDepartmentinSQLpublicDepartmentGetDepartment(intid)classAccessDepartment(4)publicvoidInsert(Departmentdepartment){System.out.println("InsertarecordintoDepartmentinACCESS!");publicDepartmentGetDepartment(intid)/*(5)(6)classSqlServerFactoryimplementsIFactory{publicIDepartmentCreateDepartment(){returnnewclassAccessFactoryimplementsIFactory{publicIDepartmentCreateDepartment(){returnnew2013201320132013（14:00～16:30150分鐘6115752013年上半年全國計算機技術與軟件專業(yè)技術資格（水平）（參看下表試題一（15分1-11-21-3所示分1（4分1-1中的實體E1?E42（7分DFD時，需要對有些復雜加工（處理）1-21-1中處311-31-23.12層數(shù)據(jù)流圖。1-2中加工P1、P2P31-21-3中缺少的數(shù)據(jù)流。3（4分1-3中的數(shù)據(jù)存儲D1?D4試題二（15分：廣告（廣告編號，銷售價格，（1）主持人（主持人工號，（2）插播單（（3），播出時間）調度單（（4））1（7分2（5分3（3分試題三（15分Web城市黃頁，公開發(fā)布該城市重要的組織或機構（以下統(tǒng)稱Internert的網(wǎng)絡用戶都可以搜索發(fā)布在城市黃頁中的信息，1（5分3-1A1A2處所對應的參與者，UC1UC2所對應2（7分3-2C1?C5所對應的類名（3-1中給出的類名）3（3分試題四（15分閱讀下列說明和C13m臺完全相同的機器運行ni所需的時間為????，要求確定【C下面是算法的Cjd[]md[i]i0開始count[]m0count[i]i運行的任務數(shù)schedulevoidscheduleinti,j,k,max=for(i=0;i<m;i++){d[i]=0;for(j=0;j<n;j++){s[i][j]=0;fori0imims[i][0]=(1)count[i]=for(2)in;i分配后nmintmin=d[0];k=0;forj1jmjif(min>d[j]){min=d[j];kjk(3)count[k]=count[k]+1;d[k]=d[k]+t[i];fori0imiif((4))max=1（8分（42（2分根據(jù)說明和C代碼，該問題采用了（5）算法設計策略，時間復雜度為3（5分m=3（0?2，n=7（0?6，各任務的運行時間為{1614,65432}0、12上運行的任務分別為（7）、（8）和（給出任務編號。從任務開始運行到完成所需的時間為（10）試題五（15分C++代碼，將應填入（n）#include<string>usingnamespacestd;classCloneable{public:(1)classWorkExperiencepublicCloneableprivatestringworkDate;stringcompany;publicCloneable*Clone()(2)obj->workData=this->workDate;obj->company=this->company;returnobj;classResumepublicCloneableprivatestringname;stringsex;stringage;WorkExperience*work;Resume(WorkExperience*work){this->work=(3)publicResume(stringname**voidSetPersonalInfo(stringsexstringage**voidSetWorkExperience(stringworkDate,stringcompany){/*Cloneable*Clone()(4)obj->name=this->name;obj->sex=this->sex;obj->age=this->age;returnobj;intmain()Resume*anewResume("張三");a->SetPersonalInfo("男a->SetWorkExperience("1998~2000""XXX公司")Resume*b=(5);a->SetWorkExperience("2001~2006""YYY公司");return0;試題六（15分Java代碼，將應填入（n）【JavaclassWorkExperience(1)CloneableprivateStringworkDate;privateStringcompany;publicObjectClone(){(2)obj.workDate=this.workDate;pany=pany;returnobj;classResume(3)CloneableprivateStringname;privateStringsex;privateStringage;privateWorkExperiencepublicResume(Stringname){=name;work=newprivateResume(WorkExperiencework){this.work=(4);publicvoidSetPersonInfo(stringsexstringage**publicvoidSetWorkExperience(stringworkDate,stringcompany){/*publicObjectClone(){Resumeobj=(5);returnclassWorkResumepublicstaticvoidmain(String[argsResumea=newResume("張三");a.SetPersonInfo("男","29")；SetWorkExperience("1998?2000""XXX公司Resumeb=(6)SetWorkExperience("2001?2006""YYY公司2013201320132013（14:00～16:30150分鐘6115752013年下半年全國計算機技術與軟件專業(yè)技術資格（水平）（參看下表試題一（15分1-101-211（2分1-1中的實體E1和E22（2分3（8分4（3分試題二（15分：