数据库和C语言---省软件设计师培训指南-周力ppt课件

.,全国计算机技术与软件专业技术资格（水平）考试软件设计师培训指南,数据库及C语言部分辽宁省软考备考站专家组,.,培训内容,数据库知识数据库模型概念模式、外模式、内模式三级模式和两极映像数据的独立性,.,试题举例(2008年上半年软件设计师上午试题51、52）,.,培训内容,数据库知识数据模型数据模型：层次模型、网状模型、关系模型、面向对象模型关系模型数据模型的三要素,.,培训内容,数据库知识ER图E-R模型E-R图向关系模型转换的基本方法实体中主键、候选键、外键联系类型（1：1，1：n，m：n）属性（简单属性、复合属性、单值属性、多值属性、NULL属性、派生属性）,.,试题举例(2004年下半年软件设计师上午试题4244）,假定每一车次具有唯一的始发站和终点站。如果实体“列车时刻表”属性为车次、始发站、发车时间、终点站、到达时间，该实体的主键是（42）；如果实体“列车运行表”属性为车次、日期、发车时间、到达时间，该实体的主键是（43）。通常情况下，上述“列车时刻表”和“列车运行表”两实体型间（44）联系。（42）A车次B始发站C发车时间D车次，始（43）A车次B始发站C发车时间D车次，日期（44）A不存在B存在一对一C存在一对多D存在多对多,.,试题举例(2008年上半年软件设计师上午试题53、54）,设有职工EMP（职工号，姓名，性别，部门号，职务，进单位时间，电话），职务JOB（职务，月薪）和部门DEPT（部门号，部门名称，部门电话，负责人）实体集，一个职务可以由多个职工担任，但一个职工只能担任一个职务，并属于一个部门，部门负责人是一个职工。下图所示的a、b处的实体名分别为（53）；图中a、b之间为（54）联系。（53）ADEPT、EMPBEMP、DEPTCJOB、EMPDEMP、JOB（54）A1：1B1：*C*：1D*：*,.,培训内容,数据库知识规范化关系模式规范化的程度第一范式第二范式第三范式,.,试题举例(2007年下半年软件设计师上午试题53）,建立一个供应商、零件数据库。其中“供应商”表S（Sno，Sname，Zip，City）分别表示：供应商代码、供应商名、供应商邮编、供应商所在城市，其函数依赖为：Sno（Sname，Zip，City），ZipCity。“供应商”表S属于（53）。（53）A.1NFB.2NFC.3NFD.BCNF,.,试题举例(2007年上半年软件设计师上午试题55、56）,.,培训内容,数据库知识数据操作关系数据库、关系数据库模式关系模型的实体完整性、参照完整性、用户定义完整性5种基本的关系运算（并、差、笛卡尔积、投影、选择）的基本概念；扩展的关系运算中选择、投影、连接运算方法；扩展的关系运算中的除法、外联接方法的基本概念,.,试题举例(2007年下半年软件设计师上午试题51）,在数据库系统中，数据的完整性约束的建立需要通过数据库管理系统提供的（51）语言来实现。（51）A.数据定义B.数据操作C.数据查询D.数据控制,.,试题举例(2005年下半年软件设计师上午试题3334）,在关系代数运算中，关系S、SP和R如下表所示。若先（33），则可以从S和SP获得R。其对应的关系表达式为（34）。,.,试题举例(2005年下半年软件设计师上午试题3334）,（33）A对S进行选择运算，再与S进行自然连接运算B对S进行选择运算，再与SP进行自然连接运算，最后进行投影运算C对S和SP进行笛卡尔积运算，再对运算结果进行投影运算D分别对S和SP进行投影运算，再对运算结果进行笛卡尔积运算（34）A1=010(S)SPB1,3,4(1=010(S)SP)C2,3,4(1=010(S)SP)D2,3,4(SSP),.,试题举例(2007年下半年软件设计师上午试题54、55）,关系R、S如下图所示，RS可由（54）基本的关系运算组成，RS=（55）。,.,试题举例(2002年上半年软件设计师上午试题40、41）,关系R、S如下表所示，R(A1,A2(1=1000AND月工资=2WHERE部门号ISNOTNULL);,.,试题举例(2005年上半年软件设计师下午试题2）,【问题3】（3分）对于表1、表2示的“职员”和“部门”关系，请指出下列各行是否可以插入“职员”关系，为什么？【问题4】（4分）原来的“职员”关系模式存在什么问题？在不增加新关系模式的前提下，请给出修改后的“职员”和“部门”关系模式。,.,试题举例(2007年下半年软件设计师下午试题2）,阅读下列说明，回答问题1至问题4，将解答填入答题纸的对应栏内。【说明】某汽车维修站拟开发一套小型汽车维修管理系统，对车辆的维修情况进行管理。1对于新客户及车辆，汽车维修管理系统首先登记客户信息，包括：客户编号、客户名称、客户性质（个人、单位）、折扣率、联系人、联系电话等信息；还要记录客户的车辆信息，包括：车牌号、车型、颜色等信息。一个客户至少有一台车。客户及车辆信息如表2-1所示。,.,试题举例(2007年下半年软件设计师下午试题2）,2记录维修车辆的故障信息。包括：维修类型（普通、加急）、作业分类（大、中、小修）、结算方式（自付、三包、索赔）等信息。维修厂的员工分为：维修员和业务员。车辆维修首先委托给业务员。业务员对车辆进行检查和故障分析后，与客户磋商，确定故障现象，生成维修委托书。,.,试题举例(2007年下半年软件设计师下午试题2）,3维修车间根据维修委托书和车辆的故障现象，在已有的维修项目中选择并确定一个或多个具体维修项目，安排相关的维修工及工时，生成维修派工单。维修派工单如表2-3所示。,.,试题举例(2007年下半年软件设计师下午试题2）,4客户车辆在车间修理完毕后，根据维修项目单价和维修派工单中的工时计算车辆此次维修的总费用，记录在委托书中。根据需求阶段收集的信息，设计的实体联系图（图2-1）和关系模式（不完整）如下所示。图2-1中业务员和维修工是员工的子实体。,.,试题举例(2007年下半年软件设计师下午试题2）,【逻辑结构设计】客户(5)，折扣率，联系人，联系电话)车辆(车牌号，客户编号，车型，颜色，车辆类别)委托书(6)，维修类型，作业分类，结算方式，进厂时间，预计完工时间，登记日期，故障描述，总费用)维修项目(维修项目编号，维修项目，单价)派工单(7)，工时)员工(8)，工种，员工类型，级别),.,试题举例(2007年下半年软件设计师下午试题2）,【问题1】（4分）根据问题描述，填写图2-1中(1)(4)处联系的类型。联系类型分为一对一、一对多和多对多三种，分别使用1:1，1:n或1:*，m:n或*:*表示。【问题2】（4分）补充图2-1中的联系并指明其联系类型。联系名可为：联系1，联系2，。【问题3】（4分）根据图2-1和说明，将逻辑结构设计阶段生成的关系模式中的空(5)(8)补充完整。【问题4】（3分）根据问题描述，写出客户、委托书和派工单这三个关系的主键。,.,培训内容,C程序设计语言用C语言实现常用的数据结构与算法及应用程序迭代、穷举搜索递推、递归回溯贪心动态规划分治应用程序,.,试题举例(2008年下半年软件设计师下午试题五）,.,试题举例(2007年下半年软件设计师上午试题1、2）,.,试题举例(2005年上半年软件设计师下午试题四）,阅读以下说明和c程序，将应填入（n）处的字句写在答题纸的对应栏内。【说明】假设需要将N个任务分配给N个工人同时去完成，每个人都能承担这N个任务，但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案，在该方案中，为每个人分配1个不同的任务。程序中，N个任务从0开始依次编号，N个工人也从0开始依次编号，主要的变量说明如下：cij：将任务i分配给工人j的费用。taski：值为0表示任务i未分配。值为j表示任务i分配给工人j。workerk：值为0表示工人k未分配任务。值为1表示工人k已分配任务。mincost：最小总费用。,.,【程序】#include#defineN8*N表示任务数和工人数。*intcNN；unsignedintmincost：65535；*设置min的初始值，大于可能的总费用*inttaskNtempN，workerN；voidplan(intk，unsignedintcost)inti;if(（1）（5）；taskk=0；*if*/*plan*/,.,voidmain()inti,j；for(i=0；iN；i+)*设置每个任务由不同工人承担时的费用及全局数组的初值*workeri=0；taski=0；tempi=0；for(j=0；jN；j+)scanf(“d”，cij)；plan(0，0)；*从任务0开始分配*printf(“n最小费用=dn”，mincost)；for(i=0；iN；i+)printf(“TaskdisassignedtoWorkerdn”，i，tempi)；)*main*,.,试题举例(2007年下半年软件设计师下午试题四）,试题四(共15分)阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某机器上需要处理n个作业job1,job2,jobn，其中：(1)每个作业jobi(1in)的编号为i，jobi有一个收益值pi和最后期限值di；(2)机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；(3)job1jobn的收益值呈非递增顺序排列，即p1p2pn；(4)如果作业jobi在其期限之内完成，则获得收益pi；如果在其期限之后完成，则没有收益。为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图4-1是基于贪心策略求解该问题的流程图。,.,(1)整型数组J有n个存储单元，变量k表示在期限之内完成的作业数，J1.k存储所有能够在期限内完成的作业编号，数组J1.k里的作业按其最后期限非递减排序，即dJ1dJk。(2)为了方便于在数组J中加入作业，增加一个虚拟作业job0，并令d0=0，J0=0。(3)算法大致思想：先将作业job1的编号1放入J1，然后，依次对每个作业jobi(2in)进行判定，看其能否插入到数组J中，若能，则将其编号插入到数组J的适当位置，并保证J中作业按其最后期限非递减排列，否则不插入。jobi能插入数组J的充要条件是：jobi和数组J中已有作业均能在其期限之内完成。(4)流程图中的主要变量说明如下：i：循环控制变量，表示作业的编号；k：表示在期限内完成的作业数；r：若jobi能插入数组J，则其在数组J中的位置为r+1；q：循环控制变量，用于移动数组J中的元素。,.,.,【问题1】（9分）请填充图4-1中的空缺(1)、(2)和(3)处。【问题2】(4分)假设有6个作业job1,job2,job6；完成作业的收益数组p=(p1,p2,p3,p4,p5,