閱讀下列說(shuō)明和流程圖，回答問(wèn)題 1～3，將解答寫在答卷的對(duì)應(yīng)欄內(nèi)。

　　[說(shuō)明]

　　有一種游戲，是用滾球擊十個(gè)柱-比賽分為十局，每局可滾球一次或多次，其規(guī)則和記分方法如下;

　　(1)若一局的第一個(gè)球擊倒全部十個(gè)柱( 稱為 strike )，則這局不再滾球( 例外，對(duì)第十局來(lái)說(shuō)，還可補(bǔ)滾兩次球 )，其得分為 10 加下兩次滾球所擊倒的柱數(shù)

　　(2)若一局的第一個(gè)球未擊倒十個(gè)柱，則可對(duì)剩下的柱再滾一次球。如果這局的兩次滾球擊倒全部十個(gè)柱( 稱為 spare )，則這局不再滾球( 例外，對(duì)第十局來(lái)說(shuō)，還可補(bǔ)滾一次球 )，其得分為 10 加上下一次滾球所擊倒的柱數(shù)，否則，這局也不再滾球，其得分為本局兩次滾球所擊倒的

　　(3)總得分為十局得分之和。 流程圖讀入每球擊倒的柱數(shù)，計(jì)算并輸出每局得分 scor 及總分 total。圖中 ball1 和 ball2 分別存放每局第一個(gè)球和第二個(gè)球( 如有的話 )所擊倒的柱數(shù)，frame 用于對(duì)局計(jì)數(shù)。

　　[問(wèn)題1]

　　填充流程圖中的 ①～⑤，使之成為完整的流程圖。

　　[問(wèn)題2]

　　若要把每球擊倒的柱數(shù)記錄在一個(gè)一維效組中，這個(gè)數(shù)組最少要有幾個(gè)元素，最多要有幾個(gè)元素。

　　[問(wèn)題3]

　　若計(jì)算每局得分的規(guī)則增加一條：當(dāng)前面各局累積得分超過(guò) 100 分時(shí)，每取得一次 strike 獎(jiǎng)勵(lì) 5 分，那么右邊的小流程圖應(yīng)插在總流程圖中 A～H 的哪一個(gè)位置上。

　　試題 2

　　閱讀下列說(shuō)明和流程圖，回答問(wèn)題 1 和問(wèn)題 2，把解答寫在答卷的對(duì)應(yīng)欄內(nèi)。

　　某毛紡廠生產(chǎn) 500 種毛料商品，這些商品送到 300 個(gè)銷售點(diǎn)銷售。銷售點(diǎn)應(yīng)在收到商品后的規(guī)定時(shí)間內(nèi)把貸款匯給毛紡廠。

　　流程圖描述了該廠發(fā)貨、收款、催款的處理過(guò)程。其中商品文件和銷售點(diǎn)文件的記錄格式如下：

　　商品文件：

　　銷售點(diǎn)文件：

　　發(fā)貨單的格式如下：

　　收款單的格式如下：

　　處理1～3把當(dāng)天的發(fā)貨單合并到發(fā)貨文件。處理4～6把當(dāng)天的收款單合并到收款文件。每天在處理3和處理5做過(guò)之后，由處理7在發(fā)貨文件中當(dāng)天已收款的記錄上加上已收款標(biāo)記。處理8在月末執(zhí)行一次，它有三個(gè)功能：

　　(1)匯總輸出本月發(fā)貨清單;

　　(2)刪除發(fā)貨文件中已收款的所有記錄，形成一個(gè)新的發(fā)貨文件，作為下月初處理時(shí)的初始文件;

　　(3)產(chǎn)生催款通知單，以便對(duì)那些一個(gè)月以前已發(fā)貨但至今仍未收到貨款的銷售點(diǎn)催款。

　　處理 9 也每月末執(zhí)行一次，除耩班本月收款報(bào)告外，還刪除收款文件中的所有記錄�，F(xiàn)假定不會(huì)有完全相同的發(fā)貨單。

　　[問(wèn)題1]

　　指出流程圖中應(yīng)在哪幾個(gè)處理框中檢查發(fā)貨單和收款單的錯(cuò)誤，并分別指出它們各能指出什么錯(cuò)誤。

　　[問(wèn)題2]

　　如果把流程圖中從日收款分類文件到處理 7 的連線改成從日收款文件到處理 7 的連線，則有什么缺點(diǎn)，理由是什么?

　　[問(wèn)題3]

　　如果把流程圖中從日收款分類文件到處理 7 的連線改成從收款文件到處理 7 的連線，則有什么缺點(diǎn)，理由是什么?

　　試題 3

　　閱讀下列說(shuō)明和流程圖，回答問(wèn)題 1 和 2 ，把解答寫在答卷的對(duì)應(yīng)欄內(nèi)。

　　[說(shuō)明]

　　(1)流程圖描述某大型百貨商店商品銷售的數(shù)據(jù)處理流程。

　　(2)商店設(shè)有若干柜臺(tái)，同一種商品可能在幾個(gè)柜臺(tái)上銷售，各柜臺(tái)每天提供一組日銷售數(shù)據(jù)，其格式如下：

　　日期，柜臺(tái)號(hào)，商品代碼，銷售數(shù)量，商品代碼，銷售數(shù)量，…

　　(3)數(shù)據(jù)處理系統(tǒng)每日產(chǎn)生一份反映各柜臺(tái)當(dāng)日銷售金額和商店日銷售金額的“日銷售金額報(bào)告”，必要時(shí)還產(chǎn)生一份“商品請(qǐng)購(gòu)報(bào)告”，給出那些低于最低庫(kù)存量的商品代碼、商品名稱、最低庫(kù)存量和實(shí)際庫(kù)存量。處理過(guò)程中產(chǎn)生存檔的“日銷售文件”和臨時(shí)工作文件“日銷售量文件”和“日銷售金額文件”。

　　(4)系統(tǒng)中所用到的數(shù)據(jù)均來(lái)自數(shù)據(jù)文件。

　　(5)流程圖中的商品庫(kù)存文件的記錄已按關(guān)鍵宇“商品代碼”排序。

　　[問(wèn)題1]

　　①指出商品庫(kù)存文件的記錄中必須包括哪些數(shù)據(jù)項(xiàng)?

　�、诜謩e指出在日銷售文件，日銷售量文件和日銷售金額文件的記錄中至少應(yīng)包括哪些數(shù)據(jù)項(xiàng)，同時(shí)不產(chǎn)生數(shù)據(jù)冗余?

　�、坼e(cuò)誤清單可能指出哪些錯(cuò)誤?

　　[問(wèn)題2]

　　簡(jiǎn)要敘述處理 6 的主要內(nèi)容。

　　[問(wèn)題3]

　　如果刪除流程圖中的虛框 A 部分，日銷售文件的記錄中應(yīng)增加什么數(shù)據(jù)項(xiàng)。

　　試題4

　　閱讀下列說(shuō)明和流程圖，回答問(wèn)題，把解答填入答卷的對(duì)應(yīng)欄內(nèi)。

　　[問(wèn)題]

　　將一個(gè) m×n 的矩陣 X 轉(zhuǎn)置后存放到矩陣 Y 中，其計(jì)算復(fù)雜度為 O(m*n)。對(duì)稀疏矩陣來(lái)說(shuō)，可以用緊湊的存貯方式來(lái)減少所需的存貯量，并降低計(jì)算復(fù)雜度。

　　已知有 t(t>0) 個(gè)非零元素的 m×n 稀疏矩陣 W(每行每列至少有一個(gè)非零元素)以緊湊方式存放在數(shù)組 X[l：t，1：3]中。X 中某行的三個(gè)值為(i，j，v)時(shí)表示在 W 的第 i 行第 j 列有一個(gè)非零元素 v。假定 X 中的元素已按行號(hào)列號(hào)遞增排序。現(xiàn)要求將 X 轉(zhuǎn)置后以緊湊表示形式存放在數(shù)組 Y[l：t，1：3] 中，并且 Y 也按行號(hào)列號(hào)遞增排序。

　　下面描述了兩種緊湊的稀疏矩陣的轉(zhuǎn)置算法：

　　算法一見(jiàn)流程圖a

　　算法二見(jiàn)流程圖b。爭(zhēng)扣外圖中：數(shù)組元素 S[i] 用來(lái)存放X中列號(hào)為 i 的元素個(gè)數(shù)，數(shù)組元素 U[j] 用來(lái)計(jì)算X中第 j 列元素在Y中的行號(hào)。

　　[問(wèn)題1]

　　填充流程圖 a 和流程圖 b 中的 ①～⑤，使之實(shí)現(xiàn)相應(yīng)的算法。

　　[問(wèn)題2]

　　分別寫出算法一和算法二的計(jì)算復(fù)雜度。

　　試題5

　　閱讀下列說(shuō)明和流程圖。回答問(wèn)題 1 和 2，把解答填入答卷的對(duì)應(yīng)欄內(nèi)。

　　有一個(gè)集合，集合中有 n 個(gè)元素，每個(gè)集合元素都是正整數(shù)，它們存放在一維數(shù)組A中，每個(gè)數(shù)組元素存放一個(gè)集合元素。對(duì)給定的整數(shù) total(假定集合中每個(gè)元素的值均小于 total)，流程圖求出所有滿足下列條件的子集：子集中各元素之和等于 total。

　　本題在使用試探法找出全部解答的過(guò)程中，依次選取當(dāng)前的候選元素，嘗試組成一個(gè)小于 total 的部分和，如果合適，則選取下一元素試探;若不合適，則回溯取另一個(gè)候選元素嘗試，題中利用 s 棧存放候單元素的下標(biāo)，用它實(shí)現(xiàn)回溯。如果候選元素加上部分和等于 total ，則表示找到一個(gè)解答，然后通過(guò)回溯，再試探尋找其它的解答。

　　[問(wèn)題1]

　　問(wèn)流程圖中的 ④ 應(yīng)與 A～D 中的那一點(diǎn)相連，并填充圖中的①～③，使之成為完整的流程圖。

　　[問(wèn)題2]

　　設(shè) total=10，n=6，數(shù)組 A 中各元素的值為(8，4，1，2，5，3)。

　　若圖中的(1)框改為 sp：0，則執(zhí)行該流程圖后輸出什么結(jié)果。

　　[流程圖]

　　試題6

　　在 COMET 型計(jì)算機(jī)上可以使用試卷上所附的 CASL 匯編語(yǔ)言。閱讀下列程序說(shuō)明和 CASL 程序，把應(yīng)填入其中__n__處的字句，寫在答卷的對(duì)應(yīng)欄內(nèi)。

　　[程序說(shuō)明]

　　本程序完成兩個(gè) 4 位十進(jìn)制數(shù)相加，并輸出兩數(shù)之和。

　　例： 輸入 '5794+6438'

　　輸出 '12232'

　　(1)必須按上述要求輸入，否則輸出 'INPUTERROR' 信息，并重新輸入。

　　(2)從低位開始，逐位進(jìn)行十進(jìn)制相加。

　　(3)若輸入長(zhǎng)度為 0 時(shí)，本程序結(jié)束。

　　[問(wèn)題]

　　在程序中的 ①～⑦ 處各填入一條正確指令，以完成此程序。除非必要，標(biāo)號(hào)欄不要填寫。

　　[程序]

　　標(biāo)號(hào)　　　　　　指令碼 　　　　　　 操作數(shù)

　　START

　　BEGIN 　　　　　ST 　　　　　　　　 GR4，SPW

　　RETRY 　　　　　IN 　　　　　　　　 INBUF，LENG1

　　LEA　　　　　　　　 GR1，0

　　CPA　　　　　　　　 GR1，LENG1

　　JZE 　　　　　　　　HALT

　　LEA 　　　　　　　　GR2，9

　　CPA 　　　　　　　　GR2，LENG1

　　JNZ 　　　　　　　　ERROR

　　LEA 　　　　　　　　GR3，4

　　__①__

　　CPL 　　　　　　　　GR0，SING

　　JZE 　　　　　　　　PASS1

　　ERROR 　　　　　OUT 　　　　　　　　INERR，LENG2

　　JMP 　　　　　　　　RETRY

　　PASS1 　　　　　LD 　　　　　　　　 GR1，SM

　　ST 　　　　　　　　 GR1，INBUF，GR3

　　LEA 　　　　　　　　GR1，0

　　LOOPl 　　　　　LD 　　　　　　　　 GR3，INBUF，GR1

　　LEA 　　　　　　　　GR1，1，GR1

　　CPL 　　　　　　　　GR3，SM

　　JMI 　　　　　　　　ERROR

　　CPA 　　　　　　　　GR3，LM

　　JPZ 　　　　　　　　ERROR

　　AND 　　　　　　　　GR3，BCD

　　PUSH 　　　　　　　 0，GR3

　　__②__

　　JNZ 　　　　　　　　LOOP1

　　ST 　　　　　　　　 GR2，CY

　　LEA 　　　　　　　　GRl，4

　　__③__

　　ADD 　　　　　　　　GR3， __④__

　　ADD 　　　　　　　　GR3，CY

　　CPA 　　　　　　　　GR3，TEN

　　JMI 　　　　　　　　LABl

　　ADD 　　　　　　　　GR3，SIX

　　AND 　　　　　　　　GR3，BCD

　　__⑤__

　　JMP　 　　　　　　　LAB2

　　LAB1 　　　　　 LEA 　　　　　　　　GR0，0

　　LAB2 　　　　　 ST 　　　　　　　　 GR0，CY

　　OR 　　　　　　　　 GR3，SM

　　ST 　　　　　　　　 GR3，OUTBUF，GRl

　　__⑥__

　　JNZ 　　　　　　　　LOOP2

　　OR 　　　　　　　　 GR0，SM

　　__⑦_(dá)_

　　OUT 　　　　　　　　OUTBUF，LENG3

　　JMP　 　　　　　　　RETRY

　　HALT 　　　　　 LD 　　　　　　　　 GR4，SPW

　　EXIT

　　SPW 　　　　　　DS 　　　　　　　　 1

　　INBUF 　　　　　DS 　　　　　　　　 80

　　LENG1 　　　　　DS 　　　　　　　　 1

　　INERR 　　　　　DC 　　　　　　　　　'INPUT ERROR'

　　LENG2 　　　　　DC 　　　　　　　　 11

　　SING 　　　　　 DC 　　　　　　　　 '+'

　　SM 　　　　　　 DC 　　　　　　　　 '0'

　　LM 　　　　　　 DC 　　　　　　　　 '：'

　　BCD 　　　　　　DC 　　　　　　　　 #000F

　　CY 　　　　　　 DS 　　　　　　　　 1

　　TEN 　　　　　　DC 　　　　　　　　 10

　　SIX 　　　　　　DC 　　　　　　　　 6

　　OUTBUF 　　　　 DS 　　　　　　　　 5

　　LENG3 　　　　　DC 　　　　　　　　 5

　　END

　　從下列的4道試題(試題7至試題10)中任選l道解答。 如果解答的試題數(shù)超過(guò)1道，則解答的前1道有效。

　　試題7

　　閱讀下列程序說(shuō)明和 C 程序，把應(yīng)填入其中__n__ 處的字句，寫在答卷的對(duì)應(yīng)欄內(nèi)。

　　[程序說(shuō)明]

　　設(shè)對(duì)于一個(gè) n×n 的上三角矩陣 a，為節(jié)約存貯，只將它的上三角元素按行主序連續(xù)存放在數(shù)組 b 中。下面的函數(shù) trans 在不引入工作數(shù)組的情況下，實(shí)現(xiàn)將 a 改為按列主序連續(xù)存放在數(shù)組 b 中。

　　設(shè) n=5，

　　b=(1，2，3，4，5，6，7，8，9，10，11，12，13，14，15)

　　經(jīng)調(diào)用 trans 函數(shù)后，b 變?yōu)?/p>

　　b=(1，2，6，3，7，10，4，8，11，13，5，9，12，14，15)

　　函數(shù) tans 對(duì)數(shù)組元素的存貯位置作調(diào)整。調(diào)整過(guò)程中存在若干個(gè)循環(huán)傳送鏈：

　　b(i1)→b(i2)→…→b(ij)→b(i1) 1≤j

　　例如，考察調(diào)整后的數(shù)組元素 b(2)( 值為 6 )，與該元素相關(guān)的位置調(diào)整將形成下面的循環(huán)傳送鏈：

　　b(2)→b(3)→b(6)→…→b(12)→b(9)→b(5)→b(2)

　　關(guān)鍵是確定循環(huán)傳送鏈的下標(biāo) i1，i2，…，ij ,以及在考察調(diào)整后的元素 b(k)( k;3，4，… ) 時(shí)能判定 b(k) 是已被傳送過(guò)的某傳送鏈上的元素。

　　函數(shù) ctr(k，n) 計(jì)算調(diào)整后的數(shù)組 b 的第 k 個(gè)元素 b(k) 在原數(shù)組 b 中的位置，該位置作為函數(shù) ctr(k，n) 的返回值。函數(shù) ctr 根據(jù) k 確定它在矩陣中的行號(hào) i 和列號(hào) j ( 注意行號(hào)和列號(hào)均從 0 算起 )，然后按矩陣存放原則計(jì)算出它在 b 中的位置。

　　[程序]

　　trans( b，n )

　　int n，b[]

　　{ int m，k，r，cc，rr;int w;

　　m=(n+1)*n/2-4;

　　k=2

　　while (m>0)

　　{ r=ctr(k，n);

　　if ( r == k )

　　m--;

　　else

　　{ cc=k;rr=r;

　　while(__①__)

　　{ CC=rr，rr=ctr(cc，n);

　　}

　　if (__②__

　　{ cc=k;rr=r;w=b[k];

　　while(__③__)

　　{ b[cc]=b[rr];m--;

　　cc=rr，rr=ctr(cc，n);

　　}

　　b[cc]-w;__④__;

　　}

　　}

　　k++;

　　}

　　}

　　ctr( k，n )

　　int k，n;

　　{ int i，j;

　　i=k;j=0 ;

　　while (__⑤__)

　　i -= ++j ;

　　return( i*n+j-i*(i+1)/2 );

　　}

　　試題8～10 略(COBOL、FORTRAN、PASCAL)