1、软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 18及答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 阅读下列说明以及图示 (如图 1所示 )，回答问题 1 3。【说明】 某大学准备开发一个学生课程注册系统，学生可以使用该系统查询新学期将开设的课程和讲课教师情况，选择自己要学习的课程进行登记注册，并可以查询成绩单；教师可以使用该系统查询新学期将开设的课程和选课学生情况，并可以登记成，绩单；注册管理员使用该系统进行注册管理，包括维护教师信息、学生信息和课程信息等。 在每个学期的开始，学生可 以获得该学期的课程目录表，课程目录表列出每门课程的所有信息，诸如基本信息、教师、
2、开课系和选课条件等。 新学期开始前两周为选课注册时间，在此期间学生可以选课注册，并且允许改变或取消注册申请，开学两周后注册管理员负责关闭课程注册。每个学生可以选择不超过 4门课程，同时指定 2门侯选课程以备主选课程未选上。每门课程最多不能超过 10人，最少不能低于 3人，低于 3人选课的课程将被取消。一旦学生的注册过程完毕，注册系统将有关信息提交收费系统以便学生付费。如果在实际注册过程中名额已满，系统将通知学生在提交课程表之前予以更改。 在学期结束时，学生可以存取系统查看电子成绩单。由于学生成绩属于敏感信息，系统必须提供必要的安全措施以防非法存取。 【用例图】【时序图】 注释 1：学生打算注册
3、新的课程。 注释 2：一张这学期可选择的课程列表。 注释 3：显示一张为学生选课用的空白登记表。 1 在 UML中，用例代表一个完整的功能，如与角色通信、进行计算或在系统内工作等。请简要说明用例具有哪些的特征，并指出用例图中 (1) (3)处表示的内容。 2 协作图与时序图是同构的，二者表示的都是同样的系统交互活动，只是各自的侧重点不同而已。根据题目提 供的信息，指出协作图中 (4) (8)处表示的内容。 3 UML采用 5个互联的视图来描述软件系统的体系结构，即用例视图 (Usecase View)、设计视图 (Design View)、进程视图 (Process View)、实现视图(Im
4、plementation View)和展开视图 (Deployment View)。系统模型中每一个视图的内容是由一些图来描述的， UML中包含用例图、类图、对象图、状态图、时序图、协作图、活动图、组件图、分布图等 9种图。对整个系统而言，其功能由用例图描述，静态结构由类图和对象 图描述，动态行为由状态图、时序图、协作图和活动图描述，而物理架构则是由组件图和分布图描述。请分别指出用例图、类图、对象图、状态图、时序图、协作图、活动图、组件图、分布图的作用。4 阅读下列说明和算法，回答问题 1和问题 2。【说明】 算法 2-1是用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号
5、或者右括号，则给出相应的提示信息，如下所示： 文件 提示信息 (1+2) abc) 缺少对应左括号：第 2行，第 4列 (def)gx) 缺少对应左括号：第 3行，第 10列 (h) ij)(k (1ml) 缺少对应右括号：第 5行，第 4列；第 4行，第 1列 在算法 2-1中， stack为一整数栈。算法中各函数的说明见表 4。【算法 2-1】将栈 stack 置空，置 EOF为 false ch - nextch(); while( not EOF) k - kind(CH); if(k= (1) ) push( (2) );push( (3) ); elseif(k= (4) ) if
6、(not empty() pop( ) ;pop( ); else 显示错误信息 (缺少对应左括号或右括号 )； 显示 行号 row；显示列号 col； endif endif ch - nextch( ); endwhile if(not empty() 显示错误信息 (缺少对应左括号或右括号 )； while(not empty() row - pop() ; col - pop(); 显示行号 row; 显示列号 col; endwhile endif 为了识别更多种类的括号，对算法 2-1加以改进后得到算法 2-2。算法 2-2能够识别圆括号、方括号和花括号 (不同类型的括号不能互相匹
7、配 )。改进后，函数 kind(char ch)的参数及其对应的返回值见表 5。 【算法 2-2】 将栈 stack置空，置 EOF为 false ch -nextch()； while(not EOF) k -kind(ch)； if( k 0) if( 判断条件 1 ) push(5);push(6);push(7); elseif( 判断条件 2 and 判断条件 3 ) pop() ;pop() ;pop(); else 显示行号 row； 显示列号 col； endif endif ch - nextch();endwhileif(not empty( ) ) 显示错误信息 (缺少对
8、应左括号或右括号 )； while( not empty( ) ) pop( ); rowpop( ); colpop( ); 显示行号 row；显示列号 col； endwhileendif 4 请将【算法 2-1】和【算法 2-2】中 (1) (7)处补充完整。 5 请从下面的选项中选择相应的判断逻辑填补【算法 2-1】中的 “判断条件 1”至 “判断条件 3”。注意，若 “判断条件 2”的逻辑判断结果为假，就无需对 “判断条件 3”进行判断。 (a)字符是括号 (b)字符是左括号 (c)字符是右括号 (d)栈空 (e)栈不空 (f)栈顶元素表示的是与当前字符匹配的左括号 (R)栈顶元素表
9、示的是与当前字符匹配的右括号 6 阅读下列说明，回答问题 1问题 4。【说明】 某超市的销售业务由一个销售业务管理系统进行管理，该系统每完成一次交易都需要提供顾客发票，其格式见表 6所示。 对于这样一个销售业务管理系统，分别给出了以下两种关系数据库的设计 (下划线表示主关键字 ) 设计一： 顾客 Customer(顾客代码 Cno，姓名 name，住址 address，联系电话 phone) 收银员 Salesman(收银员代码 Sno，身份证号 idno，姓名 name，住址 address，联系电话 phone) 商品 Merchandise(商品代码 Mno，商品名称 Mname，价格
10、price) 发票 Invoice(发票号码 Ino，交易日期 Idate，顾客代码 Cno，收银员代码 Sno，商品代码 Mno，单价 unitpfice，数量 amount) 设计二： 顾客 Customer(顾客代码 Cno，姓名 name，住址 address，联系电话 phone) 收银员 Salesman(收银员代码 Sno，身份证号 idno，姓名 name，住址 address，联系电话 phone) 商品Memhandise(商品代码 Mno，商品名称 Mname，价格 price) 发票 Ivoice(发票号码Ino，交易日期 Idate，顾客代码 Cno，收银员代码 Sn
11、o) 发票明细 Invoicedetail(发票号码 Ino，商品代码 Mno，单价 unitprice，数量 amount) 6 设计一的关系模式 Invoice最高满足第几范式 ?为什么 ?设计一和设计二哪个更加合理 ?为什么 ? 7 根据设计二中关系模式，以下 SQL语句是用于 “建立 2005年 1月期间 每张发票的发票号，交易日期，交易商品件数和交易总金额的视图 ”的不完整语句，请填补其中的空缺。 CREATE VIEW Invoice -total(1) SELECT Invoice. ino, ldate,(2)， (3) FROM Invoice, lnvoicedetail
12、WHERE(4)AND ldate BETWEEN 2005-01-01AND 2005-01-31 GROUPBY(5)； 8 根据设计二中关系模式，以下 SQL语句是用于 “查询从未售 出的商品信息 ”的不完整语句，请填补其中的空缺。 SELECT Mno, Mname, price FROM Merchandise(1) WHERE(2) (SELECT(3) FROM lnvoicedetail WHERE A. Mno=lnvoicedetail. Mno)； 9 设计二中关系 Merchandise中由属性 price表示商品价格，关系 lnvoicedetail中的属性 unit
13、price也表示商品价格。两个是否有必要同时存在 ?为什么 ? 10 阅读下 列函数说明，将应填入 (n)处的字句写在对应栏内。 【函数 1说明】 函数 compare(SqList A, SqList B)的功能是：设 A=(al， ， am)和 B=(b1， ， bn)均为顺序表， “比较 ”，两个顺序表 A和 B的大小。设 A 和 B 分别为 A和 B中除去最大共同前缀后的子表 (例如， A=(y， x， x， z， x， z)， B=(y， x， x， 2， y， x，x， z)，则两者中最大的共同前缀为 (y， x， x， z)，在两表中除去最大共同前缀后的子表分别为 A=(x， z
14、)和 B=(y， x， x， z)。若 A=B=空表，则 A=B；若 A=空表，而 B空表，或者两者均不为空表，且 A的首元小于 B首元，则 A B：否则A B。 提示：算法的基本思想为：若相等，则 j+1，之后继续比较后继元素；否则即可得出比较结果。显然， j的初值应为 0，循环的条件是 j不超出其中任何一个表的范围。若在循环内不能得出比较结果，则循环结束时有 3种可能出现的情况需要区分。 【函数 1】 int compare ( SqListA, SqList B) /若 A B，则返回 -1；若 A=B，则返回 0：若 A B，则返回 1 j =0; while(i (1) else (
15、2); if(A. length = B. length) return(0); else if(A. length B. length)return(-1); else return(1) /compare /函数 1的时间复杂度是 (3)。 【函数 2说明】 函数 exchanse_L(SLnk L， int m)的功能是：用尽可能少的辅助空间将单链表中前 m个结点和后 n个结点的互换。即将单链表 (a1、 a2 ， am， b1， b2， ， bn)改变成 (b1， b2， ， bn， a1， a2， ， am， )。 【函数 2】 void exchange_L(SLink k=1；
16、while( k m+k; if( (6) /以指针 ha记 a1结点的位置 L - next = p - next; /将 B1结点链接在头结点之后 p - next = NULL; /设 am的后继为空 q=(7); /令 q指向 b1结点 while(q- next)q =(8); /查找 bn结点 q- next=(9); /将 a1结点链接到 bn结点之后 /函数 2的时间复杂度是 (10)。 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 11 阅读下列程序说明和 C代码，将应填入 (n)处
17、。 【程序 5说明】 著名的四色定理 指出任何平面区域图均可用四种颜色着色，使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过四种颜色的着色方案。 程序中用 1 4表示四种颜色。要着色的 N个区域用 0 N-1编号，区域相邻关系用 adj矩阵表示，矩阵的 i行 j列的元素为 1，表示区域 i与区域 j相邻；矩阵的 i行 j列的元素为 0，表示区域 i与区域 j不相邻。数组 color用来存储着色结果，colori的值为区域 i所着颜色。 【程序 5】 #include stdio.h #define N 10 void output(int color)/*输出一种着色方案 */
18、 int i； for(i=0； i N； i+) printf(“%4d“， colori)； printf(“n“)； int back (int * ip， int color)/*回溯 */ int c=4； while(c=4) if(*ip =0)return 0； (*ip)； c=(1)； color*ip=-1； return c； /*检查区域 i，对 c种颜色的可用性 */ int colorOk(int i， int c， int N， int color int j； for(j=0； j i； j+) if(2) return 0； return 1； /*为区域
19、i选一种可着的颜色 */ int select (int i， int c， int adjN， int color) int k； for(k=c； k =4； k+) if(colorOK(3) return k； return 0； int coloring(int adjN)/*寻找各种着色方案 */ int colorN， i， c， cnt； for(i=0； i N； i+)colori =-1； i=c=0； cnt=0； while(1) if(c=(4)=0) c=back( public： List()list=NULL； void reverseList()； void
20、 multiplyList(List L1， List L2)； void createList()； ； void List:createList() |tem * p， * u， *pre； int exp； doubte quot； list=NULL； while(1) cout “输入多项式中的一项 (系数、指数 )： “ endl； cin quot exp： if(exp 0)break； /指数小于零，结束输入 if(quot=0)continue； p=list； while(2) /查找插入点 pre=p； p=p- next; if(p!=NULL&exp=p- exp)
21、 p- quot+=quot； continue； u=(3)； if(p=list) list=u； else pre- next=u； u- next=p； void List： reverseList() |tem*p， *u； if(list=NULL)return； p=list- next； list- next NULL； while(p! NULL) u=p- next； p- next=list； list=p； p=u； void List： multiplyList(List L1， List L2) |tem*pLI， *pL2， *u； int k， maxExp；
22、double quot； maxExp=(4)； L2.reverseList()； list NULL； for(k=maxExp； k =0； k-) pL1=L1.list； while(pL1!=NULL&pL1- exp k)pL1=pL1- next； pL2 L2.list； while(pL2!=NULL&(5) pL2=pL2- next； quot=0.0； while(pL1!=NULL&pL2!=NULL) if(pL1- exp+pL2- exp=k) (6)； pL1=pL1- next； pL2=pL2- next； else if(pL1- exp+pL2- e
23、xp k) pL1=pL1- next； else pL2=pL2- next； if(quot!=0.0) u=new |tem(quot， k)； u- next=list； list=u； reverseList(： )； L2.reverseList()： void main() ListL1， L2， L； cout “创建第一个多项式链表 n“； L1.createList()； cout “创建第二个多项式链表 n“； L2.createList()； L.multiplyList(L1， L2)； 13 【 说明】 下面是一个 Applet程序，其功能是根据给出的小时，分钟和秒
24、数计算相等的秒数，即将 1分钟化为 60秒，依此类推。要求建立一个时间类，时间参数均作为类的成员变量，并且给出换算时间的方法，也作为这个类的成员函数，可以供外部对象进行调用。同时还需要在输出窗口中显示换算结果，并且将结果写到out3_3.txt文件中，本题给出确定的时间为 4小时 23分 47秒，要求换算成以秒做单位的时间。 程序运行结果如图 11所示。 import java.io.*； import java.awt.*； impOrt java.applet.*； /* applet code=ex7_7.class width=800 height=400 /applet */ pub
25、lic class ex7_7 extends APPlet public void paint (Graphics g) int nSum； class myTime7_7 public int h； public int m； public int s； public int out； public int caculateSecond() (1)； return out； myTime7_7 objTime7_7=new myTime7_7()； ObjTime7_7. h=4； ObjTime7_7.m=23； ObjTime7_7.s=47； nSum=objTime7_7. (2)
26、； g.drawString(“时： “+objTime7_7.h， 20， 30)； g.drawString(“分：“+objTime7_7.m， 20， 50)； g.drawString(“秒： “+objTime7_7.s， 20， 70)； g.drawString(3)； try FileOutputStream fos7_7=new FileOutputStream(“out7_7.txt“)； BufferedOutputStream bos7_7=new BufferedOutputStream(fos7_7， 1024)； PrintStream ps7_7=new Pr
27、intStream(bos7_7，false)； SyStem.setOut(ps7_7)； System.out.println(4)； ps7_7. close()； catch(|OException ioe) (5) (ioe)； ex7_7.htm| HTML HEAD TITLE ex7_7 /TITLE /HEAD BODY appletcode=“ex7_7.class“width=800 height=400 /applet /BODY /HTML 软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 18答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 【
28、正确答案】 用例的特征如下：用例 总是由角色初始化；用例为角色提供值；用例具有完全性，即不管其内部是如何实现的，只有最终产生了返回角色的结果，用例的执行才能完毕。 (1)登记成绩 (2)查询成绩单 (3)关闭注册 2 【正确答案】 (4)create Schedule(5)display blank schedule()(6)get course offerings() (7)create with offerings()(8)add schedule(Schedule) 3 【正确答案】 1)用例图定义了系统的功能需求，它完全是从系统 的外部观看系统功能，并不描述系统内部对功能的具体实现。在
29、用例图中，角色代表触发系统功能的用户或其他系统，用例代表具体的功能描述。 2)类图描述系统的静态结构，表示系统中的类以及类与类之间的关系。 3)对象图描述了一组对象以及它们之间的关系，表示类的对象实例。 4)状态图表示一个状态机，强调对象行为的事件顺序。 5)时序图和协作图均表示一组对象之间的动态协作关系。其中，时序图反映对象之间发送消息的时间顺序，协作图反映收发消息的对象的结构组织。时序图和协作图是同构 【试题解析】 用例描述了它所代表的功能的 各个方面，即包含了用例执行期间可能发生的各种情况。用例和角色之间具有 “关联 ”的连接关系，表示什么角色与该用例进行通信。在 UML 语言中，用例用
30、一个椭圆图形和名称表示。 在本题中，我们通过题目说明可以识别以下用例： 1与教师有关的用例 1)选择课程 选择所教的课程，并获得学生名册。 2)登记成绩 在学期结束时，提交学生的课程成绩。 2与学生有关的用例 1)注册课程 在学期开始进行选课注册，允许在一段时间内更改或删除，课程目录系统提供当前学期的所有可选课程列表。 2)查 看成绩单 学生可以查看以前学期的电子成绩单。 3与注册管理员有关的用例 1)维护课程信息 在系统中增加、修改和删除课程信息。 2)维护学生信息 在系统中增加、修改和删除学生信息。 3)维护教师信息 在系统中增加、修改和删除教师信息。 4)关闭注册 删除少于 3人的课程，
31、并由付费系统通知学生缴费。 4与安全性要求有关的用例 登录 使用此系统的人员需要进行登录，以验证其身份和权限。 发现和定义对象类应以问题域和系统责任为出发点，正确地运用抽象原则，尽可能全面地发现对象的因素 ，并对其进行检查和整理，最终得到系统的对象类。我们可以在用例模型的基础上，通过识别实体类、边界类和控制类，从而发现和定义系统中的对象类。识别上述对象类之后，通过建立交互图，将用例的行为分布到这些对象类中。时序图表示完成某项行为的对象类和这些对象类之间传递消息的时间顺序，其中，对象生命线是一条垂直的虚线，表示对象存在的时间；控制焦点是一个细长的矩形，表示对象执行一个所经历的时间段；消息是对象之
32、间的一条水平箭头线，表示对象之间的通信。协作图包含一组对象和以消息交换为纽带的关联，用于描述系统的行为是如何由系统的成 分合作实现的。 4 【正确答案】 (1)1(2)col(3)row(4)2(5)col(6)row(7)k 【试题解析】 (1)栈置空，置 EOF为 false，并从文件中读取第一个字符到 ch，然后进入循环，循环体执行一次处理一个 ch。进人循环，利用 kind函数算出 ch的类型 k。 (2)算法 2-1大致流程如下：当 k等于什么的时候把什么入栈；当 k等于什么的时候且栈不为空的时候出栈，如果栈为空，打印错误消息，如果都不是，则读取文件的下一个字符再次进入循环。由上看出
33、，人栈应是类型 k为 1，而出栈应该是类型 k为 2。在 (4)下面出栈时，并没有用到栈的内容。在此就有些人认为栈中的内容没什么用了，随便压个 ch，而且两个写的都是 ch。其实从逻辑上就可以理解这种解答，如果压的是同样的数据，又是在同一位置出栈，算法大可置用一个 push、 pop 就可以了。所以应该继续看后面的内容，以寻找正确的答案。当看到 “row -pop()； col -pop()； ”时，所有的疑惑就迎刃而解了，应把 row 和 col压入栈。由于是先弹出 row 后弹出 col，按栈的后进先出的规则，可知压入栈的是col，再压 row。 5 【正确答案】 判断条件 1:b 判断条
34、件 2:e 判断条件 3:f 【试题解析】 因为后面有 “pop()； row -pop()； col -pop()； ”，所以空 (5)应填col， (6)应填 row。又因为判断条件 1为真时需要人栈，所以判断条件 1应是判断字符是不是左括号，是就人栈，所以判断条件选 b。判断条件 2和 3是相关联的，当 2和 3都为真时，要进行出栈操作，因此要判断栈是否为空。由此可以得到待判断条件 2和 3中，有一个必定是用来判断栈是否为空的。可以用栈顶元素来确定当前括号是否和栈中压人括号是同一类型的。前提是左括号类型已经人栈了，且 在栈底，如果 (7)压入的是 k，即吻合。所以 (7)应填 k，这样判
35、断括号是否匹配的条件就可以确定了，如果当前 ch是右括号且当前栈顶的左括号类型与 ch 匹配，则匹配成功。应把 “栈不空 ”作为判断条件 2， “栈顶元素表示的是与当前字符匹配的左括号 ”作为判断条件 3。这样判断条件 2填 e，判断条件 3填 f。 6 【正确答案】 设计一中 Invoice最高满足第一范式。 根据题意可得出以下函数依赖： InoSno ， Cno， Idate 而关系 Invoice的主码是 Ino和 Mno。非主属性 Sno、 Cno和 Idate并非完全依赖于主码，因此关系 Invoice不满足第二范式，最高满足第一范式。 设计二更加合理。因为设计二解决了设计一中由于非
36、主属性不完全依赖于主码而造成的数据冗余等问题。 7 【正确答案】 (1)AS(2)SUM(amount)(3)SUM(unitpnce * amount) (4)Invoice. Ino=Invoicedetail. Ino(5)Invoice. Ino, Idate 或 Invoicedetail. Ino. Idate 8 【正确答案】 (1)A和 AS A (2)NOTEXISTS (3)* 9 【正确答案】 有必要。 Merchandise中由属性 price表示的是商品的当前价格，超市中的价格是有可能变动的，而关系 Invoicedetail中的属性 unitprice表示的是在开具
37、发票时该商品的单价。 【试题解析】 设计一中根据题意可得出以下函数依赖： InoSno ， Cno， ldate 而关系 Invoice的主码是 Ino和 Mno。非主属性 Sno、 Cno和 Idate并非完全依赖于主码，因此关系 Invoice不满足第二范式，最高满足第一范式。 关系 Invoice的设计的不合理在于该关系中将发票的单值属性 (发票号码 Ino ，交易日期 Idate，顾客代码 Cno，收银员代码 Sno)和多值属性 (商品代码 Mno ，单价 unitprice，数量 amount)混合在一个关系中，造成关系 Invoice的冗余异常、修改异常和删除异常。而设计二则将设计
38、一中关系 Invoice分解，使得发票的单值属性和多值属性分开，避免了异常。因此，设计二明显比设计一要好。 问题 2是要建立 2005年 1月期间每张发票的发票号，交易日期，交易商品件数和交易总金额的视图。 首先建立视图的格式为 CREATE VIEW视图名 AS视图定义，因此 (1)空的答案为 AS。 本查询是从 Invoice 和 Invoicedetail 两个关系中查询，两关系的连接条件是两关系的 Ino相等，因此 (4)空的答案是 Invoice. Ino=Invoice- detail.Ino。 统计每张发票的信息需要按发票将数据分组，也就是按发票号 Ino分组，但因为查询关系 I
39、nvoice和 Invoicedetail都有属性 Ino。为了避免二义性，所以分组属性是 Invoice. Ino或者是 Invoieedetail. Ino。因为在包含聚合运算的 Select子句中，只有在 Group By 子句中出现的属性才能在 SELECT 子句中以非聚合形式出现，而 SELECT 子句中有非聚合形式的属性 Idate出现，所以 (5)空的答案是 Invoice. Ino. Idate或 Invoicedetail. Ino. Idate。 需要查询的是每张发票的交易商品件数和交易总金额。交易商品件数是发票商品数量的总和，因此 (2)空的答案是 SUM(amount)
40、。交易总金额是每条交易商品明细中每条记录商品金额的总和，每 条记录商品金额是 unitprice*amount，因此 (3)空的答案是 SUM(unitprice*a- mount)。 问题 3是查询从未售出的商品信息。 SQL 语句中有两种格式为表或视图取别名： “表名 AS别名 ”或 “表名 别名 ”。由题中可以看出 Merchandise 的别名是 A，因此填空 (1)的答案是 A或者 AS A。 要查询 “从未出售 ”的商品，也就是要查询的商品在交易记录中不存在，因此 (2)空的答案是 NOT EXISTS。 Merchandise 中由属性 price表示的是商品的当前价格 ，超市中
41、的价格是有可能变动的，而关系 Invoicedetail 中的属性 unitprice表示的是在开具发票时该商品的单价。如果缺少其中任意一个，将导致商品单价不能进行调整，否则，当商品的单价发生变化时，销售历史中的商品价格就随着发生变化。 10 【正确答案】 (1)A. length(2)j+(3)O(Min(A. length， B. length) (4)m(5)p- next(6)p(7)L- next (8)q- next(9)ha(10)O(ListLength(L) 【试题解析】 函数 1中，算法要求对两个顺序表进行 “比较 ”，是一种 “引用型 ”操作，因此在算法中不应该破坏已知表
42、。按题目中的规定，只有在两个表的长度相等，且每个对应元素都相同时才相等；否则，两个顺序表的大小主要取决于两表中除去最大公共前缀后的第一个元素。因此，比较两表的大小不应该先比较它们的长度，而应该设一个下标变量 i同时控制两个表，即对两表中 “位序相同 ”的元素进行比较。 上述算法中只有一个 while循环，它的执行次数依赖于待比较的顺序表的表长，因此，算法的时间复杂度为 O(Min(A. length， B. length)。 函数 2中，对链表来说， “插入 ”和 “删除 ”仅需修改指针即可完成，并且由于前 m个元素之间和后 n个元素之间的链接关系都不需要改变，则算法的实际操作为： 先从链表中
43、删除 (a1， a2， ， am)，然后将 (b1， b2， ， bn)链接到头结点之后，再将 (a1， a2， ， am)链接到 bn。之后。算法的时间复杂度为O(ListLength(L)。 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 11 【正确答案】 (1)color*ip(2)adjij!=0 & colorj=c (3)i， k， adj， color(4)select(i， c+1， adj， color) (5)colori=c 【试题解析】 (1)Back()函数将 color数组
44、中紧邻 *ip位置的，颜色值为 4的一个连续区域的元素赋值为 -1。 (2)colorOK()判断区域 i对其之前的所有区域是否可以着色 c。该句是检查 i的相邻区域是否已有颜色为 c的。 (3)这是 colorOK的参数列表。 Select为区域 i选择一种颜色，使用 colorok 函数对各种颜色 (值为 c 4的一种，不一定是所有颜色 )分别进行检查。 (4)Coloring()函数寻找各种着色方案。它先从区域 0开始，检查颜色，并着色 (着色的顺序总是从小色值的颜色开始的 )。当发现某一区域无法着色时，就使用 back()函数，将该区域之前的一个连贯区域进行洗色 (对应 color数组
45、中赋值为 -1)并回溯，并从回溯后的位置，重新开始进行颜色检查和赋色，但使用的色值比该位置洗色前的颜色值更大。若所有区域均已着色，则输出该着色方案。然后，使用 back 函数，重新进行着色。当所有颜色方案均已找到后，函 数结束。 (5)该句对区域 i赋颜色 c。 c为之前 select函数所选出的可以用的颜色。 12 【正确答案】 (1)quot=_quot； exp=_exp； next=NULL； (2)p!=NULL & exp p- exp (3)new Item(quot， exp) (4)L1.1ist- exp+L2.list- exp (5)pL1- exp +pL2 - ex
46、p k (6)qnot+=pL1- quot*pL2- quot 【试题解析】 程序主要由类 Item和 List 组成，其中类 Item定义多项式中的项，由三个私有成员组成分别是：系数 quot、指数 exp 和指向多项式的下一项的指针next，该类定义了一个构造函数，其作用是创建系数为 _quot、指数为 _exp 的项，即创建类 Item的一个对象，因此 (1)处应该填 “quot=_quot； exp=_exp；next=NULL”。类 List定义了多项式的操作，数据成员 list是多项式链表的链头指针，类成员函数 creatlist()的功能是创建按照指数降序链接的多项式，创建的方
47、法是不断将新的项插入到链表的合适位置上。若链表中存在一项 p，其指数 大于待插入项的指数，则待查入项为 p的前驱。该成员函数在链表上遍历，直到找到满足上述条件的项；若链表中不存在这样的项，那么待插入项称为新的链尾。因此 (2)处应填 “p!=NULL & exp p- exp”； (3)处应填 “new I- tem(quot， exp)”，根据读入的指数和系数创建要插入的项。若链表中存在指数与待插入项指数相等的项则合并同类项。 成员函数 multiplyList (List L1， List L2)计算多项式 L1和 12的乘积。首先计算了 L1和翅的乘积多项式的最高幂次，即多项式 L1和
48、U的最高此项的指数之和。由于多项式 L1和 12是按照指数的降序排列的，两个多项式的第一项分别是最高幂项，这两项的指数之和就是乘积多项式的最高次幂，因此 (4)处填 “L1.list-exp+L2.list- exp”。 为了实现系数的乘积求和计算，当多项式 L1 从幂次高至幂次低逐一考虑各项的系数时，多项式 L2应从幂次低至幂次高的顺序考虑各项的系数，以便将两多项式所有幂次和为 k 的两项系数相乘后累计。由于是单链表，所以成员函数先将其中多项式 L2的链接顺序颠倒，计算完成之后，再将多项式 12的链接顺序颠倒，即恢复 原来的链接顺序。乘积多项式从高次幂系数至 0次幂系数的顺序逐一计算。 为求 k次幂这一项的系数，对于 L1的考查顺序是从高次幂项至最低次幂项，而对于 L2的考查相反。首先跳过多项式 L1中高于 k次幂的项，设低于 k 次幂的项最高次幂是 j次幂；对于多项式 L2，跳过低于 k-j次幂的项，因此 (5)处应该填“pL1- exp+pL2- exp k”。
