問題解答專題

問題解答專題1基礎題22003p-1現(xiàn)在市場上有一款汽車A很熱銷，售價是2萬美元。汽車A每加侖汽油可以行駛20英里。普通汽車每年大約行駛12000英里。油價是每加侖1美元。不久我公司就要推出新款節(jié)油汽車B，汽車B每加侖汽油可以行駛30英里?，F(xiàn)在我們要為B制定價格(它的價格略高于A)：我們預計如果用戶能夠在兩年內通過節(jié)省油錢把B高出A的價錢彌補回來，則他們就會購買B，否則就不會購買B。那么B的最高價格應為

萬美元。12000*2=24000(英里)24000/20=120024000/30=8001200-800=400(加侖)400*1=400(美元)2.0432004p-1一個家具公司生產桌子和椅子?，F(xiàn)在有113個單位的木材。每張桌子要使用20個單位的木材，售價是30元；每張椅子要使用16個單位的木材，售價是20元。使用已有的木材生產桌椅（不一定要把木材用光），最多可以賣

元錢。20x+16y≦1130×30+7×20=1401×30+5×20=1302×30+4×20=1403×30+3×20=1504×30+2×20=1605×30+0×20=15042004p-275名兒童到游樂場去玩。他們可以騎旋轉木馬，坐滑行鐵道，乘宇宙飛船。已知其中20人這三種東西都玩過，55人至少玩過其中的兩種。若每樣乘坐一次的費用是5元，游樂場總共收入700，可知有

名兒童沒有玩過其中任何一種。20*15=30035*10=35010*5=5075-55-10=1052009t-2某個國家的錢幣面值有1,7,72,73共計四種，如果要用現(xiàn)金付清10015元的貨物，假設買賣雙方各種錢幣的數(shù)量無限且允許找零，那么交易過程中至少需要流通

張錢幣。29+1+3+2=3529*343=……681*49=……193*7=……-22*1=……062009p-2有如下的一段程序：1.a:=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;現(xiàn)在要把這段程序分配到若干臺（數(shù)量充足）用電纜連接的PC上做并行執(zhí)行。每臺PC執(zhí)行其中的某幾個語句，并可隨時通過電纜與其他PC通訊，交換一些中間結果。假設每臺PC每單位時間可以執(zhí)行一個語句，且通訊花費的時間不計。則這段程序最快可以在

單位時間內執(zhí)行完畢。注意：任意中間結果只有在某臺PC上已經得到，才可以被其他PC引用。例如若語句4和6被分別分配到兩臺PC上執(zhí)行，則因為語句6需要引用語句4的計算結果，語句6必須在語句4之后執(zhí)行。572001p-1在a,b,c,d,e,f六件物品中，按下面的條件能選出的物品是：

(1)a,b兩樣至少有一樣(2)a,d不能同時取(3)a,e,f中必須有2樣(4)b,c要么都選，要么都不選(5)c,d兩樣中選一樣(6)若d不選，則e也不選a,b,c,f假定?。粒鶕?jù)（２）則Ｄ不取，根據(jù)（６）Ｅ也不取，根據(jù)（３）?。?，根據(jù)（５）?。?，最后（４）矛盾．假定ＡＢ都取，根據(jù)（２）則Ｄ不取，根據(jù)（６）Ｅ也不取，根據(jù)（３）?。?，根據(jù)（５）?。?，最后（４）能做到．82004t-2已知a,b,c,d,e,f,g七個人中，a會講英語；b會講英語和漢語；c會講英語、意大利語和俄語；d會講漢語和日語；e會講意大利語和德語；f會講俄語、日語和法語；g會講德語和法語。能否將他們的座位安排在圓桌旁，使得每個人都能與他身邊的人交談？如果可以，請以“ab”開頭寫出你的安排方案：

。abdfgec

92005p-2有3個課外小組：物理組，化學組和生物組。今有張、王、李、趙、陳、5名同學，已知張、王為物理組成員，張、李、趙為化學組成員，李、趙、陳為生物組成員。如果要在3個小組分別選出3位組長，一位同學最多只能擔任一個小組的組長，共有___種選擇方案。張王李趙陳陳張王陳李王陳趙王陳李張陳趙張李趙王趙李王李趙張趙李張李張王趙張王101998p-2某班有50名學生，每位學生發(fā)一張調查卡，上寫a，b，c三本書的書名，將讀過的書打

，結果統(tǒng)計數(shù)字如下：只讀a者8人；只讀b者4人；只讀c者3人；全部讀過的有2人；讀過a，b兩本書的有4人；讀過a，c兩本書的有2人；讀過b，c兩本書的有3人.（1）讀過a的人數(shù)是()

（2）一本書也沒有讀過的人數(shù)是()8+(4+2-2)=128+4+3+(4+2-2)+(3-2)=2050-20=30111995p-5有紅、黃、黑、白四色球各一個，放置在一個內存編號為1、2、3、4四個格子的盒中，每個格子放置一只球，它們的順序不知。甲、乙、丙三人猜測放置順序如下：甲：黑編號1，黃編號2；乙：黑編號2，白編號3；丙：紅編號2，白編號4。結果證明甲乙丙三人各猜中了一半。寫出四色球在盒子中放置情況及推理過程。1234黑紅白黃假定：黑為1√

黃為2×

黑為2×

白為3√

紅為2√

白為4×

黃為4√121995t-2ABCD4312有標號為A、B、C、D和1、2、3、4的8個球，每兩個球裝一盒，分裝4盒。標號為字母的球與標號為數(shù)字的球有著某種一一對應的關系（稱為匹配），并已知如下條件：1.匹配的兩個球不能在一個盒子內。2.2號匹配的球與1號球在一個盒子里。3.A號和2號球在一個盒子里。4.B匹配的球和C號球在一個盒子里。5.3號匹配的球與A號匹配的球在一個盒子里。

6.4號是A或B號球的匹配球。7.D號與1號或2號球匹配。請寫出這四對球匹配的情況。1，22BB,C2，AAA,334DD131998p-3任給自然數(shù)n，k(1≤K≤9)，按如下計算步驟求序列XJXJ-1……X0的步驟：1.j=02.如果N>=K則轉第3步，否則轉第7步3.Xj=NMODK4.N=NDIVK5.j=j+16.回第2步7.Xj=N8.結束試求當：N=1998，K=3時，XJXJ-1……X0之值。2202000(三進制數(shù))14排序152005p-1將數(shù)組{32,74,25,53,28,43,86,47}中的元素按從小到大的順序排列，每次可以交換任意兩個元素，最少需要交換___次。5用直接選擇排序實現(xiàn)：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基本思想：

首先在所有數(shù)據(jù)中選最小的數(shù)據(jù)，把它與第一個數(shù)據(jù)交換；然后在其余的數(shù)據(jù)中再選出最小的數(shù)據(jù)與第二個數(shù)據(jù)交換，依次類推，直到全部排完。16constn=10;vara:array[1..n]ofinteger;k,i,j,temp:integer;beginrandomize;fori:=1tondoa[i]:=random(100);fori:=（）dobegink:=i;forj:=（

）doifa[j]<a[k]then（）;if()thenbegintemp:=a[k];a[k]:=a[i];a[i]:=temp;end;end;fori:=1tondowrite(a[i]:3);writeln;end.1ton-1i+1tonk:=jk<>i17排列組合182008p-1書架上有四本不同的書A、B、C、D。其中A和B是紅皮的，C和D是黑皮的。把這四本書擺在書架上，滿足所有黑皮的書都排在一起的擺法有（）種。滿足A必須比C靠左，所有紅皮的書要擺放在一起，所有黑皮的書要擺放在一起，共有（）種擺法。192009p-1小陳現(xiàn)有2個任務A，B要完成，每個任務分別有若干步驟如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何時候，小陳只能專心做某個任務的一個步驟。但是如果愿意，他可以在做完手中任務的當前步驟后，切換至另一個任務，從上次此任務第一個未做的步驟繼續(xù)。每個任務的步驟順序不能打亂，例如……a2->b2->a3->b3……是合法的，而……a2->b3->a3->b2……是不合法的。小陳從B任務的b1步驟開始做，當恰做完某個任務的某個步驟后，就停工回家吃飯了。當他回來時，只記得自己已經完成了整個任務A，其他的都忘了。試計算小陳飯前已做的可能的任務步驟序列共有

種。7020排列組合+加法原理:B任務中的b1一定做，而且肯定是第一個做的。除了b1外，第一類：完成A任務只有1種。第二類：完成A任務和b2有C(4,1)=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。212002p-2將N個紅球和M個黃球排成一行。例如:N=2,M=3可得到10種排法。問題:當N=4,M=3時有

種不同排法?7!/(4!*3!)=35222001p-2平面上有三條平行直線，每條直線上分別有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=751232001t-２平面上有三條平行直線，每條直線上分別有7，5，6個點，且不同直線上三個點都不在同一條直線上。問用這些點為頂點，能組成多少個不同四邊形？21*10+21*15+21*5*6+10*15+10*6*7+15*5*7=225024歸納251999p-2根據(jù)Nocomachns定理，任何一個正整數(shù)n的立方一定可以表示成n個連續(xù)的奇數(shù)的和。例如：13＝123＝3＋533＝7＋9＋1143=13+15+17+19在這里，若將每一個式中的最小奇數(shù)稱為X，那么當給出n之后，請寫出X與n之間的關系表達式。X=N2-N+1261995p-4已知如下N*(N+1)/2個數(shù)據(jù)，按行的順序存入數(shù)組A[1]，A[2]…中：a11a21a22a31a32a33……an1an2an3……ann其中：第一個下標表示行，第二個下標表示列。若：aij(i≥j,j,i=1,2,……n)存貯在A[k]中，試問：k和i，j之間的關系如何表示？給定k值（k≤n*(n+1)/2)后，寫出能決定相應的i，j值的算法。k=(i-1)*i/2+jj:=k;i:=1;whilej>idobeginj:=j-i;i:=i+1;end;272002t-2n0=(k-1)nk+1設有一棵k叉樹，其中只有度為0和k兩種結點，設n0，nk，分別表示度為0和度為k的結點個數(shù)，試求出n0和nk之間的關系（n0=數(shù)學表達式，數(shù)學表達式僅含nk、k和數(shù)字）。n0=n2+1n0=2*n3+1n0=3*n4+1281999t將Ln定義為求在一個平面中用n條直線所能確定的最大區(qū)域數(shù)目。例如：當n=1時，L1=2.進一步考慮，用n條折成角的直線（角度任意），放在平面上，能確定的最大區(qū)域數(shù)目Zn是多少？例如：當n=1時，Z1=2（如下圖所示）當給出n后，請寫出以下的表達式：Ln=______________Zn=______________12Ln=n(n+1)/2+1(n≥0)Zn=L2n-2n=2n2-n+12912345678910112=1+14=1+1+27=1+1+2+311=1+1+2+3+430Zn=L2n-2n=2n2-n+1312006t-2將邊長為n的正三角形每邊n等分，過每個分點分別做另外兩邊的平行線，得到若干個正三角形，我們稱為小三角形。正三角形的一條通路是一條連續(xù)的折線，起點是最上面的一個小三角形，終點是最下面一行位于中間的小三角形。在通路中，只允許由一個小三角形走到另一個與其有公共邊的且位于同一行或下一行的小三角形，并且每個小三角形不能經過兩次或兩次以上（圖中是n=5時一條通路的例子）。設n=10，則該正三角形的不同的通路的總數(shù)為

。32n=5時，方案有1×2×3×4＝4!n=10時，方案有1×2×…×9＝9!n=2時，方案有1種。n=3時，方案有2種。n=4時，方案有6種。33遞推342000p-2有2×n的一個長方形方格，用一個1×2的骨牌鋪滿方格。例如n=3時，為2×3方格。此時用一個1×2的骨牌鋪滿方格，共有3種鋪法：試對給出的任意一個n（n>0），求出鋪法總數(shù)的遞推公式。對給出的任意一個n（n>0），用F（n）表示其鋪法的總數(shù)的遞推公式為:F（1）=1F（2）=2F（n）=F（n-2）+F（n-1）（n≥3）352000t-2設有一個共有n級的樓梯，某人每步可走1級，也可走2級，也可走3級，用遞推公式給出某人從底層開始走完全部樓梯的走法。例如：當n=3時，共有4種走法，即1+1+1,1+2,2+1,3。F（1）＝1

F（2）＝2

F（3）＝4

F（N）＝F（N－3）＋F（N－2）＋F（N－1）（N≥4）362007p-2:最短路線

某城市的街道是一個很規(guī)整的矩形網絡（見下圖），有7條南北向的縱街，5條東西向的橫街?，F(xiàn)要從西南角的A走到東北角的B，最短的走法共有多少種？_____21011111111112345673610152128410203556845153570126210372009p-1小陳現(xiàn)有2個任務A，B要完成，每個任務分別有若干步驟如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何時候，小陳只能專心做某個任務的一個步驟。但是如果愿意，他可以在做完手中任務的當前步驟后，切換至另一個任務，從上次此任務第一個未做的步驟繼續(xù)。每個任務的步驟順序不能打亂，例如……a2->b2->a3->b3……是合法的，而……a2->b3->a3->b2……是不合法的。小陳從B任務的b1步驟開始做，當恰做完某個任務的某個步驟后，就停工回家吃飯了。當他回來時，只記得自己已經完成了整個任務A，其他的都忘了。試計算小陳飯前已做的可能的任務步驟序列共有

種。7038a3014102035a201361015a101234511111

b1b2b3b4b5然后把a3那一行加起來1+4+10+20+35=70。391998p-1已知一個數(shù)列U1，U2，U3，…，UN，…往往可以找到一個最小的K值和K個數(shù)a1，a2，…，ak使得數(shù)列從某項開始都滿足：UN+K=a1UN+K-1+a2UN+K-2+……+akUN(A)例如對斐波拉契數(shù)列1，1，2，3，5，…可以發(fā)現(xiàn)：當K=2，a1=1，a2=1時，從第3項起（即N>=1）都滿足Un+2=Un+1+Un。試對數(shù)列12，22，32，…，n2,…求K和a1,a2,…,aK使得（A）式成立。當K=3,a1,a2,…,ak為a1=3,a2=-3,a3=1時。Un+３=３Un+２－３Un+1＋Un40猜想Ｋ是３，則可得下列方程：展開可得：可得方程組：解得：a1=3,a2=-3,a3=141遞歸422007p-1:子集劃分

將n個數(shù)（1，2，…，n）劃分成r個子集。每個數(shù)都恰好屬于一個子集，任何兩個不同的子集沒有共同的數(shù)，也沒有空集。將不同劃分方法的總數(shù)記為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)=______。9043對任一元素an

，必然出現(xiàn)以下兩種情況：⑴｛an｝是r個子集合中的一個，于是我們只要把a1,a2,…,an-1劃分為r-1個子集，便解決了本題，這種情況下的劃分數(shù)共有s(n-1,r-1)。⑵｛an｝不是r個子集合中的一個，則an必與其它的元素構成一個子集。則問題相當于先把a1,a2,…,an-1劃分為r個子集，這種情況下的劃分數(shù)共有s(n-1,r)。然后再把元素an加入到r個子集合中的任一個中去，共有r種加入方式，這樣對于an的每一種加入方式，都可以使集合劃分為r個子集。因此根據(jù)乘法原理，劃分數(shù)共有r*s(n-1,r)。44確定邊界：首先不能把n個元素不放進任何一個集合中去，即r=0時，s(n,r)=0；也不可能在不允許空集的情況下把n個元素放進多于n的r個集合中去，即r>n時,s(n,r)=0；再者，把n個元素放進一個集合或把n個元素放進n個集合，方案數(shù)顯然都是１，即r=1或r=n時,s(n,r)=1。45varn,r:integer;functions(n,r:integer):longint;beginif(n<r)or(r=0)thens:=0elseif(r=1)or(r=n)thens:=1elses:=s(n-1,r-1)+r*s(n-1,r)end;beginreadln(n,r);writeln(s(n,r))；end.462002t-1在書架上放有編號為1,2,…,n的n本書。現(xiàn)將n本書全部取下然后再放回去，當放回去時要求每本書都不能放在原來的位置上。例如：n=3時：原來位置為：123放回去時只能為：312或231這兩種問題：求當n=5時滿足以上條件的放法共有多少種?44種47解：

第一步：第一本書不放在原來的第一個位置，有n-1種放法。

第二步：假設第一本書放在第2個位置，則第二本書的放法又可以分為兩類：第一類，第二本書恰好放在第一個位置，則余下的n-2本書有An-2種放法；第二類，第二本書不放在第一個位置，則就是第二本書不放在第一個位置，第三本書不放在第三個位置，第四本書不放在第四個位置，……，第n本書不放在第n個位置，所以有An-1種放法。由分步計數(shù)原理和分類計數(shù)原理，我們便得到了遞歸公式：邊界：

48varn:integer;functiond(n:integer):longint;begincasenof1:d:=0;

2:d:=1;

elsed:=(n-1)*(d(n-1)+d(n-2));end;end;begin

readln(n);

writeln('d=',d(n));end.49分治501996p-9已知：A1，A2，……，A81共有81個數(shù)，其中只有一個數(shù)比其它數(shù)大，要用最少的比較運算次數(shù)，把這個值大的數(shù)找出來（假設兩個數(shù)比較一次能決定出大于、小于或等于這三種情況），請將以下算法補充完整：5152constn=81;vara:array[1..n]ofinteger;m,n1,i,k,k0,s1,s2:integer;begin

fori:=1tondoa[i]:=10;randomize;k0:=random(81)+1;a[k0]:=a[k0]+1;writeln('number=',a[k0]);{測試數(shù)據(jù)}n1:=n;k:=0;whilen1>1dobeginn1:=n1div3;{三分法}s1:=0;s2:=0;fori:=k+1tok+n1dos1:=s1+a[i];fori:=k+n1+1tok+2*n1dos2:=s2+a[i];{分別求前兩組數(shù)據(jù)和}ifs1<s2thenk:=k+n1elseifs1=s2thenk:=k+2*n1;{確定大數(shù)在哪一組}end;writeln(a[k+1]);end.532006p-1現(xiàn)有80枚硬幣，其中有一枚是假幣，其重量稍輕，所有真幣的重量都相同，如果使用不帶砝碼的天平稱重，最少需要稱幾次，就可以找出假幣？你還要指出第1次的稱重方法。請寫出你的結果：______________________________________。4次，第一步：分成3組：27，27，26，將前2組放到天平上.54數(shù)據(jù)結構552003p-2無向圖G有16條邊，有3個4度頂點、4個3度頂點，其余頂點的度均小于3，則G至少有

個頂點。3*4+4*3+2*x>=2*16x>=43+4+4=11圖中各頂點的度數(shù)總和是邊數(shù)的2倍。561999p-1在磁盤的目錄結構中，我們將與某個子目錄有關聯(lián)的目錄數(shù)稱為度。如下圖所示：該圖表達了A盤的目錄結構：D1，D11，……均表示子目錄的名字。在這里，根目錄的度為2，D1子目錄的度為3，D11子目錄的度為4，D2，D12，D111，D112，D113的度均為1。若不考慮子目錄的名字，則可簡單的圖示為如右邊的樹結構。現(xiàn)知道一個磁盤的目錄結構中，度為2的子目錄有2個，度為3的子目錄有1個，度為4的子目錄有3個。試問度為1的子目錄有幾個？

答：應把樹結構看作圖，并假設度為1的子目錄有x個，則該圖共有6+x個結點，共有5+x條邊。就可以列出以下方程：2*(5+x)=3*4+1*3+2*2+x*1解得x=9571997p-8

下圖中用點表示城市，點與點之間的聯(lián)系表示城市間的道路。試問：①能否找出一條從A城市出發(fā)，經過圖中所有道路一次后又回到出發(fā)點的通路來？②能否從A出發(fā)，找出去每個城市且只去一次的通路來？若能，則寫出通路，否則說明理由。

EFABCD①能，全是偶點。②只去一次的通路不存在。從A出發(fā)只能到達其中的3個點（每個點只能去一次），因此要找到這樣的通路是不可能的。

58一筆畫只有當一個連通圖的頂點全是偶點或僅有兩個奇點時才能實現(xiàn)一筆畫。（把無向圖不重復地一筆畫出）如果沒有奇點，則可以從任意一點出發(fā)開始一筆畫；此時圖中存在經過每條邊一次且僅一次的回路，稱歐拉回路。如果僅有兩個奇點，則可以從其中一個奇點出發(fā)一筆畫。此時圖中存在經過每條邊一次且僅一次的路徑，稱歐拉路徑。V1V3V2V4V1V3V2V4V1V3V2V4591998t-3用鄰接矩陣表示下面的無向圖．0100000101100001010000110111 000100100010010001110A=當i與j兩個結點相鄰時0當i與j兩個結點不相鄰時，或i=j

A[i，j]=

602008p-2有6個城市，任何兩個城市之間有一條道路連接，6個城市之間兩兩之間的距離如下表表示，則城市1到城市6的最短距離為______。城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市61512592061基本思想：設置兩個頂點的集合S和T=V-S，集合S中存放已找到最短路徑的頂點，集合T存放當前還未找到最短路徑的頂點。初始狀態(tài)時，集合S中只包含源點v0，然后不斷從集合T中選取到頂點v0路徑長度最短的頂點u加入到集合S中，集合S每加入一個新的頂點u，都要修改頂點v0到集合T中剩余頂點的最短路徑長度值，集合T中各頂點新的最短路徑長度值為原來的最短路徑長度值與頂點u的最短路徑長度值加上u到該頂點的路徑長度值中的較小值。此過程不斷重復，直到集合T的頂點全部加入到S中為止。迪杰斯特拉算法是解決單源最短路徑問題的貪心算法。6213<V0,V1>8<V0,V2>

30<V0,V4>

32<V0,V6>V2:8<V0,V2>13<V0,V1>-------13<V0,V2,V3>30<V0,V4>

32<V0,V6>V1:13<V0,V1>--------------13<V0,V2,V3>30<V0,V4>22<V0,V1,V5>20<V0,V1,V6>V3:13<V0,V2,V3>---------------------19<V0,V2,V3,V4>22<V0,V1,V5>20<V0,V1,V6>V4:19<V0,V2,V3,V4>終點從V0到各終點的最短路徑及其長度V1V2V3V4V5V6Vj--------------------------------21<V0,V2,V3,V4,V5>20<V0,V1,V6>V6:20<V0,V1,V6>51643203285623013717963vara:array[1..20,1..20]ofinteger;v:array[1..20]ofboolean;i,j,max,n,p:integer;flag:boolean;beginreadln(n);fori:=1tondoforj:=1tondoread(a[i,j]);fillchar(v,sizeof(v),false);v[1]:=true;{源點}forj:=2tondo{n-1次貪心}

beginmax:=maxint;

fori:=1tondo{尋找源點到其它頂點的最短權值}ifnotv[i]and(a[1,i]<>0)and(a[1,i]<max)thenbeginmax:=a[1,i];{打擂臺}p:=i;end;v[p]:=true;{已求出標志}fori:=1tondo{更新權值}if(a[1,p]<>0)and(a[p,i]<>0)thenif(a[1,i]>a[1,p]+a[p,i])or(a[1,i]=0)thena[1,i]:=a[1,p]+a[p,i];

end;fori:=2tondowrite(a[1,i],'');end.原來是無路的64123544294463650429402000306004000060040041147樣例65有6個城市，任何兩個城市之間有一條道路連接，6個城市之間兩兩之間的距離如下表表示，則城市1到城市6的最短距離為____________。城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市61512592002308100030510000058000007662000p-1已知，按中序遍歷二叉樹的結果為：abc問：有多少種不同形態(tài)的二叉樹可以得到這一遍歷結果，并畫出這些二叉樹。671998t-2給出一棵二叉樹的中序遍歷：DBGEACHFI與后序遍歷：DGEBHIFCA,畫出此二叉樹。682001t-1已知一棵二叉樹的結點名為大寫英文字母，其中序與后序遍歷的順序分別為：CBGEAFHDIJ與CGEBHFJIDA則該二叉樹的先序遍歷的順序為()

ABCEGDFHIJABDECGFHIJ691996t-7下面是一個利用完全二叉樹特性，用順序表來存儲的一棵二叉樹，結點數(shù)據(jù)為字符型（結點層次號從小到大，同一層從左到右順序存儲，#表示空結點，@表示存儲數(shù)據(jù)結束）。現(xiàn)要求畫出對應該存儲結構的二叉樹示意圖。123456789101112131415701997p-9為了便于處理表達式，常常將普通表達式（稱為中綴表示）轉換為前綴{運算符在前，如X/Y寫為/XY}和后綴{運算符在后，如X/Y寫為XY/}的表達形式。在這樣的表示中可以不用括號即可確定求值的順序，如：（P+Q）*（R-S）→*+PQ-RS或→PQ+RS-*①試將下面的表達式改寫成前綴與后綴的表示形式：

<A>A+B*C/D<B>A-C*D+B∧E②試將下面的前綴表示還原成中綴的表示形式，同時寫出后綴表示：+△A*B△C{前綴式中△表示一元運算符取負號，如△A表示（-A）}+A/*BCDABC*D/++-A*CD∧BEACD*-BE∧+中綴形式為：△

A+B*（△

C）；后綴形式為：A△BC△*+71標識符樹1、標識符樹的定義將算術表達式用二叉樹來表示，稱為標識符樹。2、標識符樹的特點：（1）運算對象都是葉結點；（2）運算符都是根結點。3、從表達式產生標識符樹的方法：（1）讀入表達式的一部分產生相應二叉樹后，再讀入運算符時，運算符與二叉樹根結點的運算符比較優(yōu)先級的高低：讀入優(yōu)先級高于根結點的優(yōu)先級，則讀入的運算符作為根的右子樹，原來二叉樹的右子樹，成為讀入運算符的左子樹；讀入優(yōu)先級等于或低于根結點的優(yōu)先級，則讀入運算符作為樹根，而原來二叉樹作為它的左子樹（2）遇到括號，先使括號內的表達式產生一棵二叉樹，再把它的根結點連到前面已產生的二叉樹根結點的右子樹上去；（3）單目運算符+、-，加運算對象θ（表示0）。例如：-A，表示為：θ-A724、應用舉例（1）畫出表達式：A*B*C的標識符樹，并求它的前序序列和后序序列。 **CBA前序序列：**ABC

后序序列：AB*C*73（2）畫出表達式：A*（B*C）的標識符樹，并求它的前序序列和后序序列。B*C*A前序序列：*A*BC

后序序列：ABC**74（3）畫出表達式：-A+B-C+D的標識符樹，并求它的前序序列和后序序列。+-+Dθ-CBA前序序列：+–+–θABCD

后序序列：θA–B+C–D+75（4）畫出（A+（B-C））/（（D+E）*（F+G-H））的標識符樹，并求它的前序序列和后序序列。/A-CB+DE+*F-HG+前序序列：/+A–BC*+DE–+FGH后序序列：ABC–+DE+FG+H–*/

762002p-234521342153214532451

34251

32415321543542132541如下圖,有一個無窮大的的棧S,在棧的右邊排列著1,2,3,4,5共五個車廂。其中每個車廂可以向左行走,也可以進入棧S讓后面的車廂通過?，F(xiàn)已知第一個到達出口的是3號車廂，請寫出所有可能的到達出口的車廂排列方案。32145345354771997p-4設數(shù)組A[10..100,20..100]以行優(yōu)先的方式順序存儲，每個元素占4個字節(jié)，且已知A[10，20]的地址為1000，則A[50，90]的地址是

。142401000+[（50-10）*（100-20+1）+（90-20）]*478其他792006t-1將2006個人分成若干不相交的子集，每個子集至少有3個人，并且：（1）在每個子集中，沒有人認識該子集的所有人。（2）同一子集的任何

3個人中，至少有

2個人互不認識。（3）對同一子集中任何2個不相識的人，在該子集中恰好只有1個人認識這兩個人。則滿足上述條件的子集最多能有

個？80將2006個人分成若干不相交的子集，每個子集至少有3個人，并且：（1）在每個子集中，沒有人認識該子集的所有人。（2）同一子集的任何

3個人中，至少有

2個人互不認識。（3）對同一子集中任何2個不相識的人，在該子集中恰好只有1個人認識這兩個人。則滿足上述條件的子集最多能有

個？2006÷5＝401812006p-2:取石子游戲現(xiàn)有5堆石子,石子數(shù)依次為3，5，7，19，50，甲乙兩人輪流從任一堆中任?。看沃荒苋∽砸欢眩荒懿蝗。?取最后一顆石子的一方獲勝。甲先取，問甲有沒有獲勝策略（即無論乙怎樣取，甲只要不失誤，都能獲勝）？如果有，甲第一步應該在哪一堆里取多少？請寫出你的結果.82為了解決這類一般情況，我們需要用到整數(shù)的二進位制，把m元數(shù)組{a1，a2，…，am}中的每一個分量用二進位制數(shù)表示，ai(1≤i≤m)寫在第i行，同時對齊二進位制數(shù)的位數(shù)，在列上作十進位制加法，其和寫在第(m+1)行，記為{n1，n2，…，nj，…，nl}，如果所有這些和數(shù)nj(1≤j≤l)均為偶數(shù)，我們稱這個m元數(shù)組為偶數(shù)組；若nj(1≤j≤l)，中有一個數(shù)為奇數(shù)，則稱之為非偶數(shù)組。例如：對于3元數(shù)組{2，3，5}；a1

2

0

1

0a2

3

0

1

1a3

5

1

0

1

１2

2n1

n2n3因為其中n1=1，所以{2，3，5}是非偶數(shù)組。同樣，對于3元數(shù)組{2，3，1}：a1

2

1

0a2

3

1

1a3

1

0

1

2

2

n1

n2由于nj(j=1，2)為偶數(shù)，則{2，3，1}為偶數(shù)組。

83偶數(shù)組與非偶數(shù)組在T變換下具有如下性質：(1)偶數(shù)組經過一次T變換之后一定變?yōu)榉桥紨?shù)組；

(2)對于非偶數(shù)組，一定可以找到某一個T變換，使其變?yōu)榕紨?shù)組。

這樣我們容易判定：如果給定的m元數(shù)組是偶數(shù)組，則后取者必有獲勝策略；相反，若給定m元數(shù)組為非偶數(shù)組，則先取者有方法獲勝，因為給定的m元數(shù)組為偶數(shù)組，先取者無論怎樣取，只能將偶數(shù)組變?yōu)榉桥紨?shù)組，后取者則有策略將此時的非偶數(shù)組變?yōu)榕紨?shù)組，由于每次取走石子，剩下石子數(shù)目一定越來越小，而{0，0，…，0}是偶數(shù)組，所以后取者獲勝，同理可證相反情況。84例：有三堆石子，各堆數(shù)目分別是2、3、6，兩人輪流取，取完的人為勝者，若甲先乙后，誰取勝？解：a1

2

0

1

0a2

3

0

1

1a3

6

1

1

0

1

3

1

n1n2

n3

所以{2，3，6}為非偶數(shù)組，我們可以判定：先取者甲獲勝，只需將a3=6變?yōu)?，可以驗證{2，3，1}是偶數(shù)組．85應用：19010011700011150001013000011010010(18)10也就是，還要18才能變成“必負局”，所以50－18＝32

所以第1次只能在第5堆石子中取32粒，使得取出32粒后為“必負局”。86例：桌上放著一堆小石子一共100顆，兩人(甲、乙)輪流取，每次可以取1至10顆，取完的人為勝者，怎樣才能取勝？容易看出11是取勝的關鍵數(shù)字，因為到此時，不論對方(甲)取多少顆(大于0且小于11)，總留下大于0且小于11顆石子，這樣乙方一次取完即獲得勝利。同樣地分析，要取到11必須取到22，33，44，55，66，77，88，99，這樣我們就知道了獲勝之道：①先取1顆石子，留下99顆，然后對方取a(1≤a≤10)顆，己方取(11—a)顆，就總能掌握這種致勝的關鍵數(shù)，從而確保獲勝。②如果對方先取，己方只需利用對方不知道其中奧秘，爭取到一個致勝數(shù)，就總能依①中方法取到下一個致勝數(shù)，最后取得勝利。下面是另一類游戲．872005t-2：取火柴游戲取火柴游戲的規(guī)則如下：一堆火柴有N根，A、B兩人輪流取出。每人每次可以取1根或2根，最先沒有火柴可取的人為敗方，另一方為勝方。如果先取者有必勝策略則記為1，先取者沒有必勝策略記為0。當N分別為100，200，300，400，500時，先取者有無必勝策略的標記順序為__________（回答應為一個由0或1組成的字符串）３是取勝的關鍵數(shù)字１１０１１88傳球問題4個人進行籃球訓練，互相傳球接球，要求每個人接球后馬上傳給別人，開始由甲發(fā)球，并作為第一次傳球，第五次傳球后，球又回到甲手中，問有多少種傳球方式？608990設有棱長為1米的正四面體ABCD，一只螞蟻從頂點A出發(fā)，遵循下列規(guī)則爬行：在每個頂點相交的3條棱中選一條，然后沿這條棱到另一個頂點。求螞蟻爬行了7米路之后，又回到頂點A的方法總數(shù)。設從點A出發(fā)走過n米回到點A的走法為an種。由于從A出發(fā)走n-1米的走法共有3n-1種,其中有an-1種是走到A的，下一步一定離開A，除去這an-1種，其它的每一種都可以再走1米到達A點。因此，an=3n-1-an-1。91一個學生暑假在A、B、C三個城市游覽。他今天在這個城市，明天就到另一個城市。假設他第一天在A市，第五天又回到A市，問他有幾種不同的游覽方案？a1=0,a2=21-0=2,a3=22-2=2,A4=23-2=6.92出棧序列統(tǒng)計【問題描述】棧是常用的一種數(shù)據(jù)結構，有n個元素在棧頂端一側等待進棧，棧頂端另一側是出棧序列。你已經知道棧的操作有兩種：push和pop，前者是將一個元素進棧，后者是將棧頂元素彈出?，F(xiàn)在要使用這兩種操作，由一個操作數(shù)序列可以得到一系列的輸出序列。請你編程求出對于給定的n，計算并輸出由操作數(shù)序列1，2，…，n，經過一系列操作可能得到的輸出序列總數(shù)?！据斎搿烤鸵粋€數(shù)n(1≤n≤100). 【輸出】一個數(shù)，即可能輸出序列的總數(shù)目?！緲永縮tack.in stack.out3 5123,132,213,231,32193分析

(根據(jù)第一個數(shù)的出棧順序來分類)如果操作數(shù)只有1個，那么輸出序列的總數(shù)也只有1種。如果操作數(shù)有2個，那么輸出序列的總數(shù)就有2種。即：如果操作數(shù)有3個，那么輸出序列的總數(shù)就有5種。即：如果操作數(shù)有4個，那么輸出序列的總數(shù)就有14種。即：94如果操作數(shù)有5個，那么輸出序列的總數(shù)就有42種。即：95由此我們不難發(fā)現(xiàn)遞推的規(guī)律，即有N個操作數(shù)時計算方法為：f（n）=2*f（n-1）+f（1）*f（n-2）+…+f（j）*f（n-j-1）+…+f（n-2

）*f（1）初始條件f（1）=1。96vara:array[0..50]oflongint;n,j,i,m:longint;beginreadln(n);a[1]:=1;{初值}fori:=2tondobeginm:=a[i-1]*2;forj:=1toi-2dom:=m+a[j]*a[i-j-1];