網(wǎng)上找的一些試題備用題目訓(xùn)練test

1、最小值(A)源程序名 A.? (pas,c,cpp)可執(zhí)行文件名 A.exe輸入文件名 A.in 輸出文件名 A.out已知整數(shù)X和由0.9組成的字符串S，其中，字符串S可以分割成若干個非空子集S0、S1、S2、使S0+S1+S2+=S。我們再定義字符串S分割成M個部分形成的P(x)=a0+a1*x+a2*x2+aM*xM。這里ai對應(yīng)著的就是si。例如字符串S=1204時，S可以分割成S=1+204（P(x)=1+204*x），或S=1+2+04（P(x)=1+2*x+4*x2）等。你的任務(wù)是寫一個程序，在所有的分割方法中找出最小的一種。已知結(jié)果不會超過12*1014。輸入第一行一個數(shù)字，表

2、示該輸入文件中測試數(shù)據(jù)的個數(shù)。如果有幾個最小值，你必須輸出分割最少的。輸出時，指數(shù)小的寫在前。輸出每一個測試數(shù)據(jù)，你都要輸出一行P(K)的最小值。輸出時，指數(shù)小的寫在前。例如X=3，S=123時，有以下幾種分割方法：S = 123P(X) = 123P(3) = 123S = 1 + 23P(X) = 1 + 23 * XP(3) = 70S = 12 + 3P(X) = 12 + 3 * XP(3) = 21S = 1 + 2 + 3P(X) = 1 + 2 * X + 3 * X2P(3) = 34最小值是21，所以答案便是12 + 3 * X。樣例a.in31 12343 1231 10

3、01a.out1 + 2 * X1 + 3 * X2 + 4 * X312 + 3 * X11 + 1 * X1注意：輸出時指數(shù)符號和數(shù)字（字母）間沒有空格，其他符號和數(shù)字（字母）間有空格。關(guān)鍵頂點問題源程序名 e.? (pas,c,cpp)可執(zhí)行文件名 e.exe輸入文件名 pe.dat輸出文件名 pe.out在十年里，人們意識到了數(shù)據(jù)通信的意義，大多數(shù)網(wǎng)絡(luò)通信的設(shè)計和分析，經(jīng)常用圖示法模仿他們的布局，因為許多有關(guān)網(wǎng)絡(luò)問題可以使用圖論解決。像往常一樣，一個信息網(wǎng)被圖中的結(jié)點和邊，相應(yīng)模擬通信站和連接。一個網(wǎng)絡(luò)G = (N,E)由頂點集合N以及邊的集合E（一對結(jié)點表示）組成。如果考慮這些對無序

4、，那么我們就有了一個無向圖，邊連接兩個頂點u和v表示成(u,v)。比如說，圖3描述了一個網(wǎng)絡(luò)G，它包含10個頂點和16條邊。圖3：一個網(wǎng)絡(luò)G在一個網(wǎng)絡(luò)G里，兩個頂點的距離表示為，是從u到v的最短路經(jīng)上的邊數(shù)和。一個定點順序，是一條從到的長k-1的路徑，僅當這里所有從到都有邊，。如果在點u到v中間不存在路徑，那么。一條路徑是頂點u到v的最短路徑，僅當這條路徑是所有從u到v的路徑中的最短一條。一個網(wǎng)絡(luò)，是如果這里對任意兩個頂點都存在路徑時的連接。結(jié)點w的退出，指的是w和所有它所連接的邊從G圖中刪除。而且剩余的子圖表示為G-w。一個結(jié)點w被叫做關(guān)鍵頂點，僅當G中存在兩個頂點u和v，滿足。這表示u到v

5、的距離，在將w從G中移除后增加了。因此，一個關(guān)鍵頂點就像通訊網(wǎng)絡(luò)上的必須頂點，這樣的結(jié)點的退出，會使剩下子網(wǎng)的通訊費用上升。例如，我們考慮圖3的網(wǎng)絡(luò)G。頂點v2是一個關(guān)鍵頂點，因為。當然，G包含的關(guān)鍵頂點集合是。假如我們有幾個網(wǎng)絡(luò)，每個網(wǎng)絡(luò)連接包含最多n個頂點，這里。假如現(xiàn)在你被雇傭當一名網(wǎng)絡(luò)管理員，你要分析通信費用。因此之故，你將感興趣與找到網(wǎng)絡(luò)中所有的關(guān)鍵頂點。特別的，你應(yīng)該設(shè)計一個程序，對給出的每個網(wǎng)絡(luò)，可以有效的計算出關(guān)鍵結(jié)點的總數(shù)。輸入輸入文件包含至少一個，最多六個網(wǎng)絡(luò)（測試點）。每個測試點以一個正整數(shù)n開始，這里。接下來n行表示網(wǎng)絡(luò)G的鄰接矩陣。最后一個數(shù)據(jù)緊接著一個“0”，表示“輸入的結(jié)束”。一個n個結(jié)點的鄰接矩陣，表示形式為，是一個的01矩陣，當，則，否則。注意這里在01矩陣a的每行任意兩個元素之間沒有分隔符。例如，圖3那幅圖的鄰接矩陣，在樣例輸入的測試點3中給出。輸出對每個測試點，在一行里輸出關(guān)鍵結(jié)點的總數(shù)。樣例pe.dat301010101030111011101001100010001001000111100