问答题例如：设散列函数为Hash(Key)=Keymod7，记录的关键字序列为15,14,21,87,97,293,35,24,149,19,63,16,103,77,5,153,145,356,51,68,705,453，建立的散列文件内容如图所示。为简化起见，散列文件的存储单位以内存单元表示。函数InsertToHashTable(intNewElemKey)的功能是：将元素NewEIemKey插入散列桶中，若插入成功则返回0，否则返回-1。采用的散列函数为Hash(NewElemKey)=NewElemKey%P，其中P为设定的基桶数目。函数中使用的预定义符号如下：#defineNULLKEY-1/*散列桶的空闲单元标识*/#defineP7/*散列文件中基桶的数目*/#defineITEMS3/*基桶和溢出桶的容量*/typedefstructBucketNode/*基桶和溢出桶的类型定义*/intKcyData[ITEMS];structBucketNode*Link;BUCKET;BUCKETBucket[P];/*基桶空间定义*/[函数]intlnsertToHashTable(intNewElemKey)/*将元素NewElemKey插入散列桶中，若插入成功则返回0，否则返回-1*//*设插入第一个元素前基桶的所有KeyData[]、Link域已分别初始化为NULLKEY、NULL*/intIndex;/*基桶编号*/inti,k;BUCKET*s,*front,*t;(1);for(i=0;i＜ITEMS;i++)/*在基桶查找空闲单元，若找到则将元素存入*/if(Bucket[Index].KeyData[i]=NULLKEY)Bucket[Index].KeyData[i]=NewElemKey;break;if((2))return0;/*若基桶已满，则在溢出桶中查找空闲单元，若找不到则申请新的溢出桶*/(3);t=Bucket[Index].Link;if(t!=NULL)/*有溢出桶*/while(t!=NULL)for(k=0;k＜ITEMS;k++)if(t-＞KeyData[k]=NULLKEY)/*在溢出桶链表中找到空闲单元*/t-＞KeyData[k]=NewElemKey;break;/*if*/front=t;if((4))t=t-＞Link;elsebreak;/*while*//*if*/if((5))/*申请新溢出桶并将元素存入*/s=(BUCKET*)malloe(sizeof(BUCKET));if(!s)return-1;s-＞Link=NULL;for(k=0;k＜ITEMS;k++)s-＞KeyData[k]=NULLKEY;s-＞KeyData[0]=NewElemKey;(6);/*if*/return0;/*InsertToHashTable*/

问答题{{B}}试题1～试题4是必答题{{/B}}阅读以下关于住宅安全系统的技术说明，根据要求回答问题1～问题4。[说明]基于某嵌入式系统的住宅安全系统可使用传感器(如红外探头、摄像头等)来检测各种意外情况，如非法进入、火警和水灾等。房主可以在安装该系统时配置安全监控设备(如传感器、显示器、报警器等)，也可以在系统运行时修改配置，通过录像机和电视机监控与系统连接的所有传感器，并通过控制面板上的键盘与系统进行信息交互。在安装过程中，系统给每个传感器赋予一个ID编号和类型，并设置房主密码以启动和关闭系统，设置传感器事件发生时应自动拨出的电话号码。当系统检测到一个传感器事件时，就激活警报，拨出预置的电话号码，并报告关于位置和检测到的事件的性质等信息。住宅安全系统的顶层数据流图如图6-13所示，图6-14是住宅安全系统的第0层数据流图，图6-15是对住宅安全系统的第0层数据流图中加工4的细化图。

问答题[说明]某公司欲开发一个管理选民信息的软件系统。系统的基本需求描述如下：(1)每个人(Person)可以是一个合法选民(Eligible)或者无效的选民(Ineligible)。(2)每个合法选民必须通过该系统对其投票所在区域(即选区，Riding)进行注册(Registration)。每个合法选民仅能注册一个选区。(3)选民所属选区由其居住地址(Address)决定。假设每个人只有一个地址，地址可以是镇(Town)或者城市(City)。(4)某些选区可能包含多个镇；而某些较大的城市也可能包含多个选区。现采用面向对象方法对该系统进行分析与设计，得到如下图所示的初始类图。类图

问答题试题一（共15分）阅读以下说明和图，回答问题1至问题3.将解答填入答题纸的对应栏内。【说明】某时装邮购提供商拟开发订单处理系统，用于处理客户通过电话、传真、邮件或Web站点所下订单。其主要功能如下：（1）增加客户记录。将新客户信息添加到客户文件，并分配一个客户号以备后续使用。（2）查询商品信息。接收客户提交商品信息请求，从商品文件中查询商品的价格和可订购数量等商品信息，返回给客户。（3）增加订单记录。根据客户的订购请求及该客户记录的相关信息，产生订单并添加到订单文件中。（4）产生配货单。根据订单记录产生配货单，并将配货单发送给仓库进行备货；备好货后，发送备货就绪通知。如果现货不足，则需向供应商订货。（5）准备发货单。从订单文件中获取订单记录，从客户文件中获取客户记录，并产生发货单。（6）发货。当收到仓库发送的备货就绪通知后，根据发货单给客户发货；产生装运单并发送给客户。（7）创建客户账单。根据订单文件中的订单记录和客户文件中的客户记录，产生并发送客户账单，同时更新商品文件中的商品数量和订单文件中的订单状态。（8）产生应收账户。根据客户记录和订单文件中的订单信息，产生并发送给财务部门应收账户报表。现采用结构化方法对订单处理系统进行分析与设计，获得如图1-1所示的顶层数据流图和图1-2所示0层数据流图。注：名称使用说明中的词汇，起点和终点均使用图1-2中的符号或词汇。

问答题试题五(共15分)阅读下列说明和C++代码，将应填入____(n)____处的字句写在答题纸的对应栏内。[说明]现欲开发一个软件系统，要求能够同时支持多种不同的数据库，为此采用抽象工厂模式设计该系统。以SQLServer和Access两种数据库以及系统中的数据库表Department为例，其类图如图5-1所示。

问答题【问题 3】(2 分) 对于本题的作业处理问题，用图4-1 的贪心算法策略，能否求得最高收益？ (6) 。用贪心算法求解任意给定问题时，是否一定能得到最优解？ (7) 。

问答题试题四（共15分）阅读下列说明，回答问题1至问题2，将解答填入答题纸的对应栏内。【说明】0-1背包问题可以描述为：有n个物品，对i=1,2,···,n，第i个物品价值为vi,重量为wi(vi和wi为非负数），背包容量为W(W为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即,且总重量不超过背包容量，即,其中，xi∈{0,1},xi=0表示第i个物品放入背包。

问答题[说明] ①为类Circle增加一个构造函数，该函数有一个参数，并在构造时将该参数值赋给成员 radius。将该函数实现为一个非内联函数，并且使用参数列表的方式将类成员赋值。 ②为类Circle增加一个成员函数print()，使得可以输出有关圆的信息，比如下列程序 Circle c； c. SetRadius(5)； c. Print()； 将输出：The circle has radius of 5! ③完成友元函数void CompareR(Circle *c1，Circle *c2)的定义，在屏幕中输出c1与c2比较radius大小结果，要求使用if - else结构完成。 输出结果如下： The circle has radus of 5 ! The circle has radius of 10 ! cl ＜c2 源程序文件test7_3, cpp 清单如下: #include ＜ iostream, h ＞ class Circle { public: Circle( ) :radius(5) {} {{U}} (1) {{/U}} void SetRadius(int r) { radius = r; } int GetRadius() { return radius; } {{U}} (2) {{/U}} friend void CompareR(Circle * c1,Circle * c2); private: int radius; }; void CompareR(Circle * c! ,Circle * c2) { {{U}} (3) {{/U}} cout ＜＜ "c1 ＞ c2" ＜＜ endl; else if ( (c1 -＞ GetRadius( )) == (c2 -＞ GetRadius( ))) tout ＜ ＜"c1=c2' ＜ ＜ endl; else if ( (c1 -＞ GetRadius( )) ＜ ( c2 -＞ GetRadius( ))) cout ＜＜"c1＜c2" ＜＜endl; void main( ) Circle c1 c1. SetRadius(5) c1. Print( ) Circle c2(10); c2. Print( ) CompareR( }

问答题{{B}}试题1～试题4是必答题{{/B}}阅读以下某房屋租赁服务系统的技术说明和数据流图，根据要求回答问题1～问题4。[说明]某房屋租赁公司欲建立一个房屋租赁服务系统，统一管理房主和租赁者的信息，从而快速地提供租赁服务。该系统具有以下功能。(1)登记房主信息：对于每名房主，系统需登记其姓名、住址和联系电话，系统还将为其分配一个唯一的身份标识(ID)和密码，并将这些信息写入房主信息文件。(2)登记房屋信息：所有在系统中登记的房屋都有一个唯一的识别号(对于新增加的房屋，系统会自动为其分配一个识别号)。除此之外，还需登记该房屋的地址、房型(如平房、带阳台的楼房、独立式住宅等)、最多能够容纳的房客数、租金及房屋状态(待租赁、已出租)。这些信息都保存在房屋信息文件中。一名房主可以在系统中登记多个待租赁的房屋。(3)收取手续费：房主登记完房屋后，系统会生成一份费用单，房主根据费用单交纳相应的费用。(4)登记租赁者信息：所有想通过该系统租赁房屋的租赁者，必须首先在系统中登记个人信息，租赁者信息包括姓名、现住址、电话号码、出生年月、性别，以及系统分配的唯一身份标识(ID)和密码。这些信息都保存在租赁者信息文件中。(5)租赁房屋：已经登记在系统中的租赁者，可以得到一份系统提供的待租赁房屋列表。一旦租赁者从中找到合适的房屋，就可以提出看房请求。系统将安排租赁者与房主见面的时间和地点，并将见面信息(包含见面双方的基本信息)通知租赁者和房主。对于每次看房，系统会生成一条看房记录并将其写入看房记录文件中。(6)变更房屋状态：当租赁者与房主达成租房或退房协议后，房主向系统提交变更房屋状态的请求。系统将根据房主的请求，修改房屋信息文件。该房屋租赁服务系统的顶层数据流图如图5-10所示，图5-11是其第0层数据流图。

问答题[问题2] 根据题意，补充图2-5中缺失的联系和联系的类型，使其成为完善的实体联系图。其中，联系名分别取名为联系1，联系2，联系3，……。

问答题阅读下列算法说明和流程图，根据要求回答问题1～问题3。[说明]某机器上需要处理n个作业job1，job2，…，jobn，其中：(1)每个作业jobi(1≤i≤n)的编号为i，jobi有一个收益值P[i]和最后期限值d[i]；(2)机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；(3)job1～jobn的收益值呈非递增顺序排列，即p[1]≥p[2]≥…≥p[n]；(4)如果作业jobi在其期限之内完成，则获得收益p[i]；如果在其期限之后完成，则没有收益。为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图3-25是基于贪心策略求解该问题的流程图。(1)整型数组J[]有n个存储单元，变量k表示在期限之内完成的作业数，J[1..k]存储所有能够在期限内完成的作业编号，数组J[1..k)里的作业按其最后期限非递减排序，即d[J[1]]≤…≤d[J[k]]。(2)为了便于在数组J中加入作业，增加一个虚拟作业job0，并令d[0]=0，J[0]=0。(3)算法大致思想是：先将作业job1的编号1放入J[1]，然后，依次对每个作业jobi(2≤i≤n)进行判定，看其能否插入到数组J中。若能，则将其编号插入到数组J的适当位置，并保证J中作业按其最后期限非递减排列；否则不插入。jobi能插入数组J的充要条件是：jobi和数组J中已有作业均能在其期限之内完成。(4)流程图中的主要变量说明如下。i：循环控制变量，表示作业的编号；k：表示在期限内完成的作业数；r：若jobi能插入数组J，则其在数组J中的位置为r+1；q：循环控制变量，用于移动数组J中的元素。

问答题[说明2]在M阶B树中插入一个关键字时，首先在最接近外部节点的某个非叶子节点中增加一个关键字，若该节点中关键字的个数不超过M-1，则完成插入；否则，要进行节点的“分裂”处理。所谓“分裂”，就是把节点中处于中间位置上的关键字取出来并插入其父节点中，然后以该关键字为分界线，把原节点分成两个节点。“分裂”过程可能会一直持续到树根，若树根节点也需要分裂，则整棵树的高度增1。例如，在图1所示的B树中插入关键字25时，需将其插入节点e中。由于e中已经有3个关键字，因此将关键字24插入节点e的父节点b中，并以24为分界线将节点e分裂为e1和e2两个节点，结果如图2所示。函数Isgrowing(BTreeNode*root,ElemKeyTypeakey)的功能是：判断在给定的M阶B树中插入关键字akey后，该B树的高度是否增加，若增加则返回TRUE，否则返回FALSE。其中，root是指向该M阶B树根节点的指针。在函数Isgrowing中，首先调用函数SearchBtree查找关键字akey是否在给定的M阶B树中，若在则返回FALSE(表明无需插入关键字akey，树的高度不会增加)；否则，通过判断节点中关键字的数目考查插入关键字akey后该B树的高度是否增加。函数lsgrowing的代码如下：boolIsgrowing(BTreeNode*root,ElemKeyTypeakey){BTreeNode*t,*f;if(!SearchBtree(______){t=f;while(______){t=t→parent;}if(!t)returnTRUE;}returnFALSE;}

问答题试题二（15分）阅读下列说明和E-R图，回答问题1至问题3，将解答填入答题纸的对应栏内。[说明]某网上订书系统的E-R图(已消除了不必要的冗余)如图2-1所示（图中没有标出主码）。图中实体的说明如表2-1所示，相关属性说明如表2-2所示。一个顾客可以在同一天填写多张购书单，每张购书单上可填写多种图书，每种图书可以订购多本，bid相同的图书在同一张购书单上不能出现多次。注：为简化起见，不考虑信用卡号码泄漏所带来的安全性等问题。[图2-1]

问答题【说明】 本题将有向网(带权有向图)定义为类Adjacency WDigraph。类中的数据成员n表示有向网中的顶点数；a为带权邻接矩阵，用于存储有向网中每一对顶点间弧上的权值；c为二维数组，存储有向网中每一对顶点间的最短路径长度；kay为二维数组，存储最短路径，kay[i][j]=k表示顶点i到达顶点j的最短路径必须经过顶点k。类中的主要成员函数有： Input()：输入有向网的顶点数、各条弧及权值，建立带权领接矩阵a。若顶点i到顶点j有弧，则a[i][j]取弧上的权值，否则a[i][j]的值取NoEdge。 AllPairs()；用弗洛伊德(Floyd)算法求有向网中每一对顶点间的最短路径长度。 OutShortestPath (int i, int j：计算顶点i到顶点j的最短路径。 outputPath(int i, int j)：输出顶点i到顶点j的最短路径上的顶点。 Floyd算法的基本思想是递推地产生一个矩阵序列C0，C1，C2，…，Cn，其中C0是已知的带权邻接矩阵，a，Ck(i, j(0≤i，j＜)表示从顶点i到顶点j的中间顶点序号不大于k的最短路径长度。如果i到j的路径没有中间顶点，则对于0≤k＜n，有Ck(i,j)=C0(i,j)= a[i][j]。递推地产生C1，C2，…，Cn的过程就是逐步将可能是最短路径上的顶点作为路径上的中间顶点进行试探，直到为全部路径都找遍了所有可能成为最短路径上的中间顶点，所有的最短路径也就全部求出，算法就此结束。 【C++代码】#include ＜ iostream. h ＞#define NoEdge 10000// 当两个顶点之间没有边相连时，在邻接矩阵中用NoEdge表示void Make2DArray(int * * class AdjacencyWDigraph private int n; //有向网中的顶点数目 int* *a; //存储顶点间弧上的权值 int* *c; //存储计算出的最短路径长度 int* * kay; //存储求出的最短路径pubic: int Vertices( )const j return n; void AllPairs( ); void Input( ); //输入有向网的顶点数、各条弧及权值，建立邻接矩阵a void OutShortestPath(int i, int j); //计算顶点i到j的最短路径(试卷中未列出) ~ AdjacencyWDigraph ( ); //析构函数(试卷中未列出)private: void outputPath(int i, int j);;void AdjacencyWDigraph: :AllPairs( ) int i,j,k,t1,t2,t3; for(i=1;i＜=n; k++) for(j=1;j＜=n; ++j) c[i][j]= (1) ; kay[i][j]=0; for(k=1;k＜=n; k++) for(i=1;i＜=n; i++) if(i= =k) continue; t1=c[i][k]; for(j=1;j＜=n; j++) if(j==k||j==i) continue; t2 =c[k] [j]; t3 =c[i] [j]; if( t1 ! = NoEdge kay[i][j]= (3) ; //for //forvoid AdjacencyWDigraph:: outputPath(int i, int j) //输出顶点i到j的最短路径上的顶点 if(i==j) return; if(kay[i] [j]==0)cout＜＜j ＜＜"; else outputPath(i, (4) ); outputPath( (5) );void Adjacency WDigraph: :lnput( )int i,j,u,v,w,E; cout ＜＜ "输入网中顶点个数:";cin＞ ＞n; cout ＜＜ "输入网中弧的个数:"; cin＞ ＞E; Make2DArray (a, n+1, n+1); for(i=1;i＜=n; i++) for(j=1; j＜=n; j++) a[i][j]=NoEdge; for(i=1;i＜ =n; i++) a[i][i]=0; Make2DArray(c, n+1, n+1); Make2DArray(kay, n+1, n+1) for(i=1;i＜=E; i++)cout＜＜"输入弧的信息(起点终点权值); "; cin＞ ＞u＞ ＞v＞ ＞w; a[u][v] =w;void Make2DArray(int * * x=new int* [rows+1]; for(i=0;i＜rows+1;i ++ ) x[i]=new int [cols+1]; for(i=1;i＜= rows; i ++) for(j=1;j＜=cols; j++) x[i][j]=0;

问答题[说明]在一些应用场合中，需要对用户的输入数据进行检查监控。以下VisualBasic程序实现了对新添加到List列表的内容进行监控，拒绝向List列表添加重复信息。例如，在List列表中存在元素“a01001；a01002”，如果用户输入数据为“aOl001”或“a01002”，系统则弹出提示信息，拒绝将新数据加入List列表；如果用户输入的数据不同与List列表中的任何一个元素，则作为新元素加入List中。VisualBasic界面显示如图11-5所示。根据程序功能说明，完成程序代码。[代码1]BeginVB.FormForm1Caption=“List列表拒绝添加重复信息”//...窗体描述(略)BeginVB.CommandButtonCommand2Caption=“退出”//...窗体描述(略)EndBeginVB.CommandButtonommand1Caption=“添加”//...窗体描述(略)EndBeginVB.TextBoxText1//...窗体描述(略)EndBeginVB.ListBoxList1Height=1860ItemData="Form1.frx":0000Left=1020List="Form1.frx":0002TabIndex=0Top=525Width=2580EndBeginVB.LabelLabellBackStyle=0'TransparentCaption="请输入编号"//...窗体描述(略)EndEnd[代码2]AttributeVB_Name="Form1"AttributeVB_GlobalNameSpace=FalseAttributeVB_Creatable=FalseAttributeVB_PredeclaredId=TrueAttributeVB_Exposed=FalsePrivateSubForm_Load()Listl.AddItem"a01001"Listl.AddItem"a01002"EndSubPrivateSubCommand1Click()DimMyvalAsLongFori=0To(1)(2)If(3)ThenMsgBox"系统不允许重复输入，请重新输入"ExitSubEndIf(4)(5)EndSub

问答题【算法说明】下面是一段插入排序的程序，将R[k+1]插入到R[1...k]的适当位置。R[0]=R[k+1]；j=k；while(R[j]＞R[0])R[j+1]=R[j]；j--；R[j+1]=R[0]；【流程图】【测试用例设计】(while循环次数为0、1、2次)测试用例表

问答题[说明]散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录，当桶中已有m个同义词(散列函数值相同)的记录时，存放第m+1个同义词会发生“溢出”。此时需要将第m+1个同义词存放到另一个称为“溢出桶”的桶中。相对地，称存放前m个同义词的桶为“基桶”。溢出桶和基桶大小相同，用指针链接。查找指定元素记录时，首先在基桶中查找。若找到，则成功返回，否则沿指针到溢出桶中进行查找。例如，设散列函数为Hash(Key)=Keymod7，记录的关键字序列为15，14，21，87，96，293，35，24，149，19，63，16，103，77，5，153，145，356，51，68，705，453，建立的散列文件内容如图2-27所示。为简化起见，散列文件的存储单位以内存单元表示。函数InsertToHashTable(intNewElemKey)的功能是：若新元素NewElemKey正确插入散列文件中，则返回值0；否则返回值-1。采用的散列函数为Hash(NewElemKey)=NewElemKey%P，其中P设定基桶的数目。函数中使用的预定义符号如下。

问答题[问题2] 请在下列选项中选择合适的答案，填入图3-2的方框c至方框f。 B的公钥，B的私钥，摘要算法，A的私钥，A的公钥，会话密钥

问答题【说明】某供销系统接受顾客的订货单。当库存中某配件的数量小于订购量或库存量低于一定数量时，向供应商发出采货单；当某配件的库存量大于或等于订购量时，或者收到供应商的送货单并更新了库存后，向顾客发㈩提货单。该系统还可随时向总经理提供销售和库存情况表。该供销系统的分层数据流图中部分数据流和文件的组成如下：【文件】配件库存=配件名+规格+数量+允许的最低率库存量【数据流】订货单＝配件号+配件名+规格+数量+顾客名+地址提供单=订货单+金额采货单＝配件号+配件名+规格+数量+供应商名十地址送货单=配件号+配件名+规格+数量+金额假定顶层图是正确的，“供应商”文件已由其他系统生成。【数据流图】假定题中提供的顶层图是正确的，请回答下列问题：

问答题【问题1】 假设当前该旅馆各个房间的情况见表3。 序号i ROOM RANK NBED STATUS 1 101 3 4 0 2 102 3 4 1 3 201 2 3 0 4 202 2 4 1 5 301 1 6 0 当输入M=4，R=0时，该算法的输出是什么?