《《问题解答专题》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《问题解答专题》PPT课件.ppt（103页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、问题解答专题问题解答专题基础题基础题2003p-1现在市场上有一款汽车现在市场上有一款汽车A很热销，售价是很热销，售价是2万美元。万美元。汽车汽车A每加仑汽油可以行驶每加仑汽油可以行驶20英里。普通汽车每年大英里。普通汽车每年大约行驶约行驶12000英里。油价是每加仑英里。油价是每加仑1美元。不久我公司美元。不久我公司就要推出新款节油汽车就要推出新款节油汽车B，汽车，汽车B每加仑汽油可以行驶每加仑汽油可以行驶30英里。现在我们要为英里。现在我们要为B制定价格制定价格(它的价格略高于它的价格略高于A)：我们预计如果用户能够在两年内通过节省油钱把：我们预计如果用户能够在两年内通过节省油钱把B高高出
2、出A的价钱弥补回来，则他们就会购买的价钱弥补回来，则他们就会购买B，否则就不会，否则就不会购买购买B。那么。那么B的最高价格应为的最高价格应为万美元。万美元。12000*2=24000(英里英里)24000/20=120024000/30=8001200-800=400(加仑加仑)400*1=400(美元美元)2004p-1一个家具公司生产桌子和椅子。现在有一个家具公司生产桌子和椅子。现在有113个单位的木材。个单位的木材。每张桌子要使用每张桌子要使用20个单位的木材，售价是个单位的木材，售价是30元；每张椅子要使元；每张椅子要使用用16个单位的木材，售价是个单位的木材，售价是20元。使用已有
3、的木材生产桌椅元。使用已有的木材生产桌椅（不一定要把木材用光），最多可以卖（不一定要把木材用光），最多可以卖元钱。元钱。20 x+16y113030+720=140130+520=130230+420=140330+320=150430+220=160530+020=1502004p-275名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，人这三种东西都玩过，55人人至少玩过其中的两种。若每样乘坐一次的费用是至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐元，游乐场总共收入
4、场总共收入700，可知有，可知有名儿童没有玩过其中任何一种。名儿童没有玩过其中任何一种。20*15=30035*10=35010*5=5075-55-10=102009t-2某个国家的钱币面值有某个国家的钱币面值有1,7,72,73共计四种，共计四种，如果要用现金付清如果要用现金付清10015元的货物，假设买卖双方元的货物，假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中各种钱币的数量无限且允许找零，那么交易过程中至少需要流通至少需要流通张钱币。张钱币。29+1+3+2=3529*343=681*49=193*7=-22*1=02009p-2有如下的一段程序：有如下的一段程序：1.a:
5、=1;2.b:=a;3.d:=-a;4.e:=a+d;5.c:=2*d;6.f:=b+e-d;7.g:=a*f+c;现在要把这段程序分配到若干台（数量充足）用电缆连接现在要把这段程序分配到若干台（数量充足）用电缆连接的的PC上做并行执行。每台上做并行执行。每台PC执行其中的某几个语句，并可随执行其中的某几个语句，并可随时通过电缆与其他时通过电缆与其他PC通讯，交换一些中间结果。假设每台通讯，交换一些中间结果。假设每台PC每单位时间可以执行一个语句，且通讯花费的时间不计。则这每单位时间可以执行一个语句，且通讯花费的时间不计。则这段程序最快可以在段程序最快可以在单位时间内执行完毕。注意：任意中单位
6、时间内执行完毕。注意：任意中间结果只有在某台间结果只有在某台PC上已经得到，才可以被其他上已经得到，才可以被其他PC引用。例引用。例如若语句如若语句4和和6被分别分配到两台被分别分配到两台PC上执行，则因为语句上执行，则因为语句6需需要引用语句要引用语句4的计算结果，语句的计算结果，语句6必须在语句必须在语句4之后执行。之后执行。52001p-1在在a,b,c,d,e,f六件物品中，按下面的条件能选出六件物品中，按下面的条件能选出的物品是：的物品是：(1)a,b两样至少有一样两样至少有一样(2)a,d不能同时取不能同时取(3)a,e,f中必须有中必须有2样样(4)b,c要么都选，要么都不选要么
7、都选，要么都不选(5)c,d两样中选一样两样中选一样(6)若若d不选，则不选，则e也不选也不选a,b,c,f假定取，根据（）则假定取，根据（）则不取，根据（）也不取，根据（）也不取，根据（）取，不取，根据（）取，根据（）取，最后根据（）取，最后（）矛盾（）矛盾假定都取，根据（）假定都取，根据（）则不取，根据（）也则不取，根据（）也不取，根据（）取，根不取，根据（）取，根据（）取，最后（）据（）取，最后（）能做到能做到2004t-2已知已知a,b,c,d,e,f,g七个人中，七个人中，a会讲英语；会讲英语；b会会讲英语和汉语；讲英语和汉语；c会讲英语、意大利语和俄语；会讲英语、意大利语和俄语；d
8、会会讲汉语和日语；讲汉语和日语；e会讲意大利语和德语；会讲意大利语和德语；f会讲俄语、会讲俄语、日语和法语；日语和法语；g会讲德语和法语。能否将他们的座会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以谈？如果可以，请以“ab”开头写出你的安排方案：开头写出你的安排方案：。abdfgec 2005p-2有有3个课外小组：物理组，化学组和生物组。今个课外小组：物理组，化学组和生物组。今有张、王、李、赵、陈、有张、王、李、赵、陈、5名同学，已知张、王为物名同学，已知张、王为物理组成员，张、李、赵为化学组成员，李、
9、赵、陈为理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员。如果要在生物组成员。如果要在3个小组分别选出个小组分别选出3位组长，一位组长，一位同学最多只能担任一个小组的组长，共有位同学最多只能担任一个小组的组长，共有_种选种选择方案。择方案。张张王王李李赵赵陈陈陈陈张张王王陈陈李李王王陈陈赵赵王王陈陈李李张张陈陈赵赵张张李李赵赵王王赵赵李李王王李李赵赵张张赵赵李李张张李李张张王王赵赵张张王王1998p-2某班有某班有50名学生，每位学生发一张调查卡，上写名学生，每位学生发一张调查卡，上写a，b，c三本书的书名，将读过的书打三本书的书名，将读过的书打，结果统计数字，结果统计数字如下：如下：
10、只读只读a者者8人；只读人；只读b者者4人；只读人；只读c者者3人；全部人；全部读过的有读过的有2人；读过人；读过a，b两本书的有两本书的有4人；读过人；读过a，c两两本书的有本书的有2人；读过人；读过b，c两本书的有两本书的有3人人.（1）读过）读过a的人数是的人数是()（2）一本书也没有读过的人数是）一本书也没有读过的人数是()8+(4+2-2)=128+4+3+(4+2-2)+(3-2)=2050-20=301995p-5有红、黄、黑、白四色球各一个，放置在一个内有红、黄、黑、白四色球各一个，放置在一个内存编号为存编号为1、2、3、4四个格子的盒中，每个格子放置四个格子的盒中，每个格子放
11、置一只球，它们的顺序不知。甲、乙、丙三人猜测放置一只球，它们的顺序不知。甲、乙、丙三人猜测放置顺序如下：顺序如下：甲：黑编号甲：黑编号1，黄编号，黄编号2；乙：黑编号乙：黑编号2，白编号，白编号3；丙：红编号丙：红编号2，白编号，白编号4。结果证明甲乙丙三人各猜中了一半。写出四色球结果证明甲乙丙三人各猜中了一半。写出四色球在盒子中放置情况及推理过程。在盒子中放置情况及推理过程。1234黑黑红红白白黄黄假定：假定：黑为黑为1黄为黄为2黑为黑为2白为白为3红为红为2白为白为4黄为黄为41995t-2ABCD4312有标号为有标号为A、B、C、D和和1、2、3、4的的8个球，每两个球个球，每两个球装
12、一盒，分装装一盒，分装4盒。标号为字母的球与标号为数字的球有着某盒。标号为字母的球与标号为数字的球有着某种一一对应的关系（称为匹配），并已知如下条件：种一一对应的关系（称为匹配），并已知如下条件：1.匹配的两个球不能在一个盒子内。匹配的两个球不能在一个盒子内。2.2号匹配的球与号匹配的球与1号球在一个盒子里。号球在一个盒子里。3.A号和号和2号球在一个盒子里。号球在一个盒子里。4.B匹配的球和匹配的球和C号球在一个盒子里。号球在一个盒子里。5.3号匹配的球与号匹配的球与A号匹配的球在一个盒子里。号匹配的球在一个盒子里。6.4号是号是A或或B号球的匹配球。号球的匹配球。7.D号与号与1号或号或2
13、号球匹配。号球匹配。请写出这四对球匹配的情况。请写出这四对球匹配的情况。1，22BB,C2，AAA,334DD1998p-3任给自然数任给自然数n，k(1K9)，按如下计算步骤求序列，按如下计算步骤求序列XJXJ-1X0的步骤：的步骤：1.j=02.如果如果N=K则转第则转第3步，否则转第步，否则转第7步步3.Xj=NMODK4.N=NDIVK5.j=j+16.回第回第2步步7.Xj=N8.结束结束试求当：试求当：N=1998，K=3时，时，XJXJ-1X0之值。之值。2202000(三进制数三进制数)排排序序2005p-1将数组将数组32,74,25,53,28,43,86,47中的元素按中
14、的元素按从小到大的顺序排列，每次可以交换任意两个元素，从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换最少需要交换_次。次。5用直接选择排序实现：用直接选择排序实现：25,74,32,53,28,43,86,4725,28,32,53,74,43,86,4725,28,32,53,74,43,86,4725,28,32,43,74,53,86,4725,28,32,43,47,53,86,7425,28,32,43,47,53,86,7425,28,32,43,47,53,74,86基本思想：基本思想：首先在所有数据中选首先在所有数据中选最小的数据，把它与第一最小的数据，把它与第一个
15、数据交换；然后在其余个数据交换；然后在其余的数据中再选出最小的数的数据中再选出最小的数据与第二个数据交换，依据与第二个数据交换，依次类推，直到全部排完。次类推，直到全部排完。const n=10;var a:array1.n of integer;k,i,j,temp:integer;begin randomize;for i:=1 to n do ai:=random(100);for i:=（）do begin k:=i;for j:=（）do if ajak then（）;if ()then begin temp:=ak;ak:=ai;ai:=temp;end;end;for i:=1
16、to n do write(ai:3);writeln;end.1 to n-1i+1 to nk:=jki排列组合排列组合2008p-1 书架上有四本不同的书书架上有四本不同的书A、B、C、D。其中。其中A和和B是红皮的，是红皮的，C和和D是黑皮的。把这四本书摆在书架上，是黑皮的。把这四本书摆在书架上，满足所有黑皮的书都排在一起的摆法有（满足所有黑皮的书都排在一起的摆法有（）种。满）种。满足足A必须比必须比C靠左，所有红皮的书要摆放在一起，所靠左，所有红皮的书要摆放在一起，所有黑皮的书要摆放在一起，共有（有黑皮的书要摆放在一起，共有（）种摆法。）种摆法。2009p-1小陈现有小陈现有2个任务
17、个任务A，B要完成，每个任务分别要完成，每个任务分别有若干步骤如下：有若干步骤如下：A=a1-a2-a3，B=b1-b2-b3-b4-b5。在任何时候，小陈只能专心做某个任务。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如能打乱，例如a2-b2-a3-b3是合法的，是合法的，而而a2-b3-a3-b2是不合法的。小陈从是不合法的。小陈
18、从B任务的任务的b1步骤开始做，当恰做完某个任务的某个步步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务己已经完成了整个任务A，其他的都忘了。试计算小，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有陈饭前已做的可能的任务步骤序列共有种。种。70排列组合排列组合+加法原理加法原理:B任务中的任务中的b1一定做，而且肯定是第一个做的。除了一定做，而且肯定是第一个做的。除了b1外，外，第一类：完成第一类：完成A任务任务只有只有1种。种。第二类：完成第二类：完成A任务和任务和b2有有C(4,1)=
19、4种。种。第三类：完成第三类：完成A任务和任务和b2、b3有有C(5,2)=10种。种。第四类：完成第四类：完成A任务和任务和b2、b3、b4有有C(6,3)=20种。种。第五类：完成第五类：完成A任务和任务和b2、b3、b4、b5有有C(7,4)=35种。种。加起来加起来1+4+10+20+35=70。2002p-2将将N个红球和个红球和M个黄球排成一行。例如个黄球排成一行。例如:N=2,M=3可可得到得到10种排法。种排法。问题问题:当当N=4,M=3时有时有种不同排法种不同排法?7!/(4!*3!)=352001p-2 平面上有三条平行直线，每条直线上分别有平面上有三条平行直线，每条直线
20、上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？些点为顶点，能组成多少个不同三角形？C(7,2)*(5+6)+C(5,2)*(7+6)+C(6,2)*(7+5)+7*6*5=21*11+10*13+15*12+210=231+130+180+210=7512001t-平面上有三条平行直线，每条直线上分别有平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？问用这些点
21、为顶点，能组成多少个不同四边形？21*10+21*15+21*5*6+10*15+10*6*7+15*5*7=2250归纳归纳1999p-2根据根据Nocomachns定理，任何一个正整数定理，任何一个正整数n的立的立方一定可以表示成方一定可以表示成n个连续的奇数的和。个连续的奇数的和。例如：例如：131233533791143=13+15+17+19在这里，若将每一个式中的最小奇数称为在这里，若将每一个式中的最小奇数称为X，那，那么当给出么当给出n之后，请写出之后，请写出X与与n之间的关系表达式。之间的关系表达式。X=N2-N+11995p-4已知如下已知如下N*(N+1)/2个数据，按行的
22、顺序存入数组个数据，按行的顺序存入数组A1，A2中：中：a11a21a22a31a32a33an1an2an3ann其中：第一个下标表示行，第二个下标表示列。其中：第一个下标表示行，第二个下标表示列。若：若：aij(ij,j,i=1,2,n)存贮在存贮在Ak中，试问：中，试问：k和和i，j之间的关系如何表示？之间的关系如何表示？给定给定k值（值（kn*(n+1)/2)后，写出能决定相应的后，写出能决定相应的i，j值的算法。值的算法。k=(i-1)*i/2+jj:=k;i:=1;whilejidobeginj:=j-i;i:=i+1;end;2002t-2n0=(k-1)nk+1设有一棵设有一棵
23、k叉树，其中只有度为叉树，其中只有度为0和和k两种结点，两种结点，设设n0，nk，分别表示度为，分别表示度为0和度为和度为k的结点个数，的结点个数，试求出试求出n0和和nk之间的关系（之间的关系（n0=数学表达式，数学数学表达式，数学表达式仅含表达式仅含nk、k和数字）。和数字）。n0=n2+1n0=2*n3+1n0=3*n4+11999t将将Ln定义为求在一个平面中用定义为求在一个平面中用n条直线所能确定的最大区条直线所能确定的最大区域数目。例如：当域数目。例如：当n=1时，时，L1=2.进一步考虑，用进一步考虑，用n条折成角的直线（角度任意），放在平条折成角的直线（角度任意），放在平面上，
24、能确定的最大区域数目面上，能确定的最大区域数目Zn是多少？例如：当是多少？例如：当n=1时，时，Z1=2（如下图所示）（如下图所示）当给出当给出n后，请写出以下的表达式：后，请写出以下的表达式：Ln=_Zn=_12Ln=n(n+1)/2+1(n0)Zn=L2n-2n=2n2-n+112345678910112=1+14=1+1+27=1+1+2+311=1+1+2+3+4Zn=L2n-2n=2n2-n+12006t-2将将边边长长为为n的的正正三三角角形形每每边边n等等分分，过过每每个个分分点点分分别别做做另另外外两两边边的的平平行行线线，得得到到若若干干个个正正三三角角形形，我我们们称称为为
25、小小三三角角形形。正正三三角角形形的的一一条条通通路路是是一一条条连连续续的的折折线线，起起点点是是最最上上面面的的一一个个小小三三角角形形，终终点点是是最最下下面面一一行行位位于于中中间间的的小小三三角角形形。在在通通路路中中，只只允允许许由由一一个个小小三三角角形形走走到到另另一一个个与与其其有有公公共共边边的的且且位位于于同同一一行行或或下下一一行行的的小小三三角角形形，并并且且每每个个小小三三角角形形不不能能经经过过两两次次或或两两次次以以上上（图图中中是是n=5时时一一条条通通路路的的例例子子）。设设n=10，则则该该正正三三角角形的不同的通路的总数为形的不同的通路的总数为。n=5时
26、，方案有时，方案有12344!n=10时，方案有时，方案有1299!n=2时，方案有时，方案有1种。种。n=3时，方案有时，方案有2种。种。n=4时，方案有时，方案有6种。种。递推递推2000p-2有有2n的一个长方形方格，用一个的一个长方形方格，用一个12的骨牌铺满方格。的骨牌铺满方格。例如例如n=3时，为时，为23方格。方格。此时用一个此时用一个12的骨牌铺满方格，共有的骨牌铺满方格，共有3种铺法：种铺法：试对给出的任意一个试对给出的任意一个n（n0），求出铺法总数的递推公），求出铺法总数的递推公式。式。对给对给出的任意一个出的任意一个n（n0），用），用F（n）表示其）表示其铺铺法的法的
27、总总数的数的递递推公式推公式为为:F（1）=1F（2）=2F（n）=F（n-2）+F（n-1）（）（n3）2000t-2设有一个共有设有一个共有n级的楼梯，某人每步可走级的楼梯，某人每步可走1级，级，也可走也可走2级，也可走级，也可走3级，用递推公式给出某人从底级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当层开始走完全部楼梯的走法。例如：当n=3时，共时，共有有4种走法，即种走法，即1+1+1,1+2,2+1,3。F（1）1F（2）2F（3）4F（N）F（N3）F（N2）F（N1）（）（N4）2007p-2:最短路线最短路线 某城市的街道是一个很规整的矩形网络（见下某城市的街道是
28、一个很规整的矩形网络（见下图），有图），有7条南北向的纵街，条南北向的纵街，5条东西向的横街。现条东西向的横街。现要从西南角的要从西南角的A走到东北角的走到东北角的B，最短的走法共有多，最短的走法共有多少种？少种？_210111111111123456736101521284102035568451535701262102009p-1小陈现有小陈现有2个任务个任务A，B要完成，每个任务分别要完成，每个任务分别有若干步骤如下：有若干步骤如下：A=a1-a2-a3，B=b1-b2-b3-b4-b5。在任何时候，小陈只能专心做某个任务。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可
29、以在做完手中任的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如能打乱，例如a2-b2-a3-b3是合法的，是合法的，而而a2-b3-a3-b2是不合法的。小陈从是不合法的。小陈从B任务的任务的b1步骤开始做，当恰做完某个任务的某个步步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务己已经完成了整个任务A，其他的都忘了。试
30、计算小，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有陈饭前已做的可能的任务步骤序列共有种。种。70a3014102035a201361015a101234511111b1b2b3b4b5然后把然后把a3那一行加起来那一行加起来1+4+10+20+35=70。1998p-1已知一个数列已知一个数列U1，U2，U3，UN，往往可往往可以找到一个最小的以找到一个最小的K值和值和K个数个数a1，a2，ak使得数使得数列从某项开始都满足：列从某项开始都满足：UN+K=a1UN+K-1+a2UN+K-2+akUN(A)例如对斐波拉契数列例如对斐波拉契数列1，1，2，3，5，可以发可以发现：当现
31、：当K=2，a1=1，a2=1时，从第时，从第3项起（即项起（即N=1）都满足都满足Un+2=Un+1+Un。试对数列。试对数列12，22，32，n2,求求K和和a1,a2,aK使得（使得（A）式成立。）式成立。当当K=3,a1,a2,ak为为a1=3,a2=-3,a3=1时。时。Un+=Un+Un+1 1Un猜想是，则可得下列方程：猜想是，则可得下列方程：展开可得：展开可得：可得方程组：可得方程组：解得：解得：a1=3,a2=-3,a3=1递归递归2007p-1:子集划分子集划分 将将n个数（个数（1，2，n）划分成）划分成r个子集。每个个子集。每个数都恰好属于一个子集，任何两个不同的子集没
32、有共数都恰好属于一个子集，任何两个不同的子集没有共同的数，也没有空集。将不同划分方法的总数记为同的数，也没有空集。将不同划分方法的总数记为S(n,r)。例如，。例如，S(4,2)=7，这，这7种不同的划分方法依次种不同的划分方法依次为为(1),(234)，(2),(134)，(3),(124)，(4),(123)，(12),(34)，(13),(24)，(14),(23)。当。当n=6，r=3时，时，S(6,3)=_。90对任一元素对任一元素an，必然出现以下两种情况：，必然出现以下两种情况：an是是r个子集合中的一个，于是我们只要把个子集合中的一个，于是我们只要把a1,a2,an-1划分为划
33、分为r-1个子集，便解决了本题，这种个子集，便解决了本题，这种情况下的划分数共有情况下的划分数共有s(n-1,r-1)。an不是不是r个子集合中的一个，则个子集合中的一个，则an必与其它的元必与其它的元素构成一个子集。则问题相当于先把素构成一个子集。则问题相当于先把a1,a2,an-1划分划分为为r个子集，这种情况下的划分数共有个子集，这种情况下的划分数共有s(n-1,r)。然后再。然后再把元素把元素an加入到加入到r个子集合中的任一个中去，共有个子集合中的任一个中去，共有r种加种加入方式，这样对于入方式，这样对于an的每一种加入方式，都可以使集的每一种加入方式，都可以使集合划分为合划分为r个
34、子集。因此根据乘法原理，划分数共有个子集。因此根据乘法原理，划分数共有r*s(n-1,r)。确定边界：确定边界：首先不能把首先不能把n个元素不放进任何一个集合中去，个元素不放进任何一个集合中去，即即r=0时，时，s(n,r)=0；也不可能在不允许空集的情况下把也不可能在不允许空集的情况下把n个元素放进个元素放进多于多于n的的r个集合中去，即个集合中去，即rn时时,s(n,r)=0；再者，把再者，把n个元素放进一个集合或把个元素放进一个集合或把n个元素放进个元素放进n个集合，方案数显然都是，即个集合，方案数显然都是，即r=1或或r=n时时,s(n,r)=1。varn,r:integer;func
35、tions(n,r:integer):longint;beginif(n1dobeginn1:=n1div3;三分法三分法s1:=0;s2:=0;fori:=k+1tok+n1dos1:=s1+ai;fori:=k+n1+1tok+2*n1dos2:=s2+ai;分别求前两组数据和分别求前两组数据和ifs1=2*16x=43+4+4=11图中各顶点的度数总和是边数的图中各顶点的度数总和是边数的2倍。倍。1999p-1在磁盘的目录结构中，我们将与某个子目录有关联的目录数称为度。在磁盘的目录结构中，我们将与某个子目录有关联的目录数称为度。如下图所示：如下图所示：该该图图表表达达了了A盘盘的的目目录
36、录结结构构：D1，D11，均均表表示示子子目目录录的的名名字字。在在这这里里，根根目目录录的的度度为为2，D1子子目目录录的的度度为为3，D11子子目目录录的的度度为为4，D2，D12，D111，D112，D113的的度度均均为为1。若若不不考考虑虑子子目目录录的的名名字字，则则可可简简单单的的图图示示为为如如右右边边的的树树结结构构。现现知知道道一一个个磁磁盘盘的的目目录录结结构构中中，度度为为2的的子子目目录录有有2个个，度度为为3的的子子目目录录有有1个个，度度为为4的的子子目目录录有有3个个。试试问问度度为为1的的子子目目录有几个？录有几个？答：应把树结构看作图，并假设度为答：应把树结
37、构看作图，并假设度为1 1的子目录有的子目录有x x个，则该图共有个，则该图共有6+x6+x个结点，共有个结点，共有5+x5+x条边。就可以列出以下方程：条边。就可以列出以下方程：2*(5+x)=3*4+1*3+2*2+x*1 2*(5+x)=3*4+1*3+2*2+x*1 解得解得x=9 x=9 1997p-8下图中用点表示城市，点与点之间的联系表示城市间的下图中用点表示城市，点与点之间的联系表示城市间的 道路。道路。试问：试问：能否找出一条从能否找出一条从A A城市出发，经过图中所有道路一次城市出发，经过图中所有道路一次后又回到出发点的通路来？后又回到出发点的通路来？能否从能否从A A出发
38、，找出去每个城市且只去一次的通路来？出发，找出去每个城市且只去一次的通路来？若能，则写出通路，否则说明理由。若能，则写出通路，否则说明理由。EFABCD 能，全是偶点。能，全是偶点。只去一次的通路不存在。从只去一次的通路不存在。从A A出发只能到达其中的出发只能到达其中的3 3个点（每个点只个点（每个点只能去一次），因此要找到这样的通路是不可能的。能去一次），因此要找到这样的通路是不可能的。一笔画一笔画 只有当一个连通图的顶点全是偶点或仅有两个奇点时才只有当一个连通图的顶点全是偶点或仅有两个奇点时才能实现能实现一笔画一笔画。（把无向图不重复地一笔画出）。（把无向图不重复地一笔画出）如果没有奇点
39、，则可以从任意一点出发开始一笔画；此如果没有奇点，则可以从任意一点出发开始一笔画；此时图中存在经过每条边一次且仅一次的时图中存在经过每条边一次且仅一次的回路回路，称欧拉回路。，称欧拉回路。如果仅有两个奇点，则可以从其中一个奇点出发一笔画。如果仅有两个奇点，则可以从其中一个奇点出发一笔画。此时图中存在经过每条边一次且仅一次的此时图中存在经过每条边一次且仅一次的路径路径，称欧拉路径。，称欧拉路径。V1V3V2V4V1V3V2V4V1V3V2V41998t-3用邻接矩阵表示下面的无向图用邻接矩阵表示下面的无向图 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 1
40、0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 1 1 0A=1 1当当i i与与j j两个结点相邻时两个结点相邻时2 20 0 当当i i与与j j两个结点不相邻时，或两个结点不相邻时，或i=ji=jAiAi，j=j=2008p-2有有6个个城城市市，任任何何两两个个城城市市之之间间有有一一条条道道路路连连接接，6个个城城市市之之间间两两两两之之间间的
41、的距距离离如如下下表表表表示示，则则城城市市1到到城市城市6的最短距离为的最短距离为_。城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市615125920基本思想基本思想：设置两个顶点的集合：设置两个顶点的集合S S和和T=V-ST=V-S，集合，集合S S中中存放已找到最短路径的顶点，集合存放已找到最短路径的顶点，集合T T存放当前还未找存放当前还未找到最短路径的顶点。初始状态时，集合到最短路径的顶点。初始状态时，集合S S中只包含源中只包含源点点v0v0，然后不断从集合，然后不断从集合T T中选取到顶
42、点中选取到顶点v0v0路径长度最路径长度最短的顶点短的顶点u u加入到集合加入到集合S S中，集合中，集合S S每加入一个新的顶每加入一个新的顶点点u u，都要修改顶点，都要修改顶点v0v0到集合到集合T T中剩余顶点的最短路中剩余顶点的最短路径长度值，集合径长度值，集合T T中各顶点新的最短路径长度值为原中各顶点新的最短路径长度值为原来的最短路径长度值与顶点来的最短路径长度值与顶点u u的最短路径长度值加上的最短路径长度值加上u u到该顶点的路径长度值中的较小值。此过程不断重到该顶点的路径长度值中的较小值。此过程不断重复，直到集合复，直到集合T T的顶点全部加入到的顶点全部加入到S S中为止
43、。中为止。迪杰斯特拉算法是解决单源最短路径问题的贪心算法。迪杰斯特拉算法是解决单源最短路径问题的贪心算法。1383032V2:813-133032V1:13-13302220V3:13-192220V4:19终点从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj-2120V6:20516432032856230137179vara:array1.20,1.20ofinteger;v:array1.20ofboolean;i,j,max,n,p:integer;flag:boolean;beginreadln(n);fori:=1tondoforj:=1tondoread(ai,j);
44、fillchar(v,sizeof(v),false);v1:=true;源点源点forj:=2tondon-1次贪心次贪心beginmax:=maxint;fori:=1tondo寻找源点到其它顶点的最短权值寻找源点到其它顶点的最短权值ifnotviand(a1,i0)and(a1,imax)thenbeginmax:=a1,i;打擂台打擂台p:=i;end;vp:=true;已求出标志已求出标志fori:=1tondo更新权值更新权值if(a1,p0)and(ap,i0)thenif(a1,ia1,p+ap,i)or(a1,i=0)thena1,i:=a1,p+ap,i;end;fori:
45、=2tondowrite(a1,i,);end.原来是无路的原来是无路的123544294463650 4 29 4 02 0 0 0 30 6 0 0 40 0 0 0 60 0 4 0 04 11 4 7样例样例有有6个个城城市市，任任何何两两个个城城市市之之间间有有一一条条道道路路连连接接，6个个城城市市之之间间两两两两之之间间的的距距离离如如下下表表表表示示，则则城城市市1到城市到城市6的最短距离为的最短距离为_。城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市6151259200 2 3 0 8
46、 100 0 3 0 5 100 0 0 0 5 80 0 0 0 0 72000p-1已知，按中序遍历二叉树的结果为：已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。并画出这些二叉树。1998t-2给出一棵二叉树的中序遍历：给出一棵二叉树的中序遍历：DBGEACHFI与后与后序遍历：序遍历：DGEBHIFCA,画出此二叉树。画出此二叉树。2001t-1已知一棵二叉树的结点名为大写英文字母，已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：其中序与后序遍历的顺序分别为：
47、CBGEAFHDIJ与与CGEBHFJIDA则该二叉树的先序遍历的顺序为则该二叉树的先序遍历的顺序为()ABCEGDFHIJABDECGFHIJ1996t-7下面是一个利用完全二叉树特性，用顺序表来存下面是一个利用完全二叉树特性，用顺序表来存储的一棵二叉树，结点数据为字符型（结点层次号从储的一棵二叉树，结点数据为字符型（结点层次号从小到大，同一层从左到右顺序存储，小到大，同一层从左到右顺序存储，#表示空结点，表示空结点，表示存储数据结束）。表示存储数据结束）。现要求画出对应该存储结构的二叉树示意图。现要求画出对应该存储结构的二叉树示意图。1234567891011121314151997p-9
48、为了便于处理表达式，常常将普通表达式（称为中缀表为了便于处理表达式，常常将普通表达式（称为中缀表示）转换为前缀示）转换为前缀运算符在前，如运算符在前，如X/Y写为写为/XY和后缀和后缀运算运算符在后，如符在后，如X/Y写为写为XY/的表达形式。的表达形式。在这样的表示中可以不用括号即可确定求值的顺序，如：在这样的表示中可以不用括号即可确定求值的顺序，如：（P+Q）*（R-S）*+PQ-RS或或PQ+RS-*试将下面的表达式改写成前缀与后缀的表示形式：试将下面的表达式改写成前缀与后缀的表示形式：A+B*C/DA-C*D+B E试将下面的前缀表示还原成中缀的表示形式，同时试将下面的前缀表示还原成中
49、缀的表示形式，同时写出后缀表示：写出后缀表示：+A*BC前缀式中前缀式中表示一元运算符取负号，如表示一元运算符取负号，如A表示（表示（-A）+A/*BCDABC*D/+-A*CDBEACD*-BE+中缀形式为：中缀形式为：A+B*（C）；后缀形式为：）；后缀形式为：ABC*+标识符树标识符树1、标识符树的定义、标识符树的定义 将算术表达式用二叉树来表示，称为标识符树。将算术表达式用二叉树来表示，称为标识符树。2、标识符树的特点：、标识符树的特点：（1）运算对象都是叶结点；）运算对象都是叶结点；（2）运算符都是根结点。）运算符都是根结点。3、从表达式产生标识符树的方法：、从表达式产生标识符树的方
50、法：（1）读入表达式的一部分产生相应二叉树后，再读入运算符时，运算）读入表达式的一部分产生相应二叉树后，再读入运算符时，运算符与二叉树根结点的运算符比较优先级的高低：符与二叉树根结点的运算符比较优先级的高低：读入优先级高于根结点的优先级，则读入的运算符作为根的右子树，读入优先级高于根结点的优先级，则读入的运算符作为根的右子树，原来二叉树的右子树，成为读入运算符的左子树；原来二叉树的右子树，成为读入运算符的左子树；读入优先级等于或低于根结点的优先级，则读入运算符作为树根，读入优先级等于或低于根结点的优先级，则读入运算符作为树根，而原来二叉树作为它的左子树而原来二叉树作为它的左子树（2）遇到括号，