閱讀下列說明和流程圖，回答問題 1 至問題 3，將解答寫在答卷的對應欄內(nèi)。

[說明]

流程圖 l 描述了某電信局數(shù)據(jù)通信專線計費業(yè)務管理系統(tǒng)的部分處理流程。

1．凡申請專線者，均需填寫專線申請表。系統(tǒng)把申請表存儲在專線申請登記文件中，等待分 配專線號。

2．系統(tǒng)為申請者指定專線號，并根據(jù)通信距離( 按地區(qū)計算 )、通信速率計算初裝費和月租費 ，然后發(fā)初裝通知單紿用戶，并產(chǎn)生施工單交有關部門施工。同時產(chǎn)生專線處理文件。專線號是 專線的唯一標識。

3．施工結(jié)束后，系統(tǒng)更新用戶文件．并產(chǎn)生專線計費文件，作為以后收費的依據(jù)。

4．一個用戶可以租用多條專線，用戶可用現(xiàn)金或銀行托付兩種方式支付租金，但一個用戶只能使用一種付款方式。系統(tǒng)每月按用戶( 而不是專線 )為單位計費出帳。

5．流程圖中各數(shù)據(jù)文件及有關單據(jù)所含的數(shù)據(jù)項如下：

專線申請表及專線申請登記文件：

用戶名稱，付款卞式，開戶銀行代碼，帳號，主端名稱，主端地址，申請?zhí)枺瑢Χ说刂�，端所在地區(qū)，通潔速率，設備接門，申請日期

專線處理文件：

申清號，專線號，用戶名稱，付款方式，開戶銀行代碼，帳號，初裝費，月租費，完工日期 初裝費收據(jù)： 專線號，初裝費，交費日期

施工單：

施工單號，專線號，主端名稱，主端地址，對端地址，對端所在地區(qū)，通信速率，設備接口， 申請日期，施工期限 完工單： 施工單號，專線號，完工日期

用戶文件：

用戶編號，用戶名稱，付款方式，開戶銀行代碼，帳號

專線計費文件：

專線號，用戶編號，月租金，開通日期

[問題 1]

專線價目文件由哪些數(shù)據(jù)項組成。

[問題 2]

為了避免在用戶尚未支付初裝費時就去施工，有人提議將圖中從處理 2 產(chǎn)生施工單改成從處理 3 產(chǎn)生施工單。試問從處理 3 能否產(chǎn)生施工單? 為什么?

[問題 3]

當一個用戶租用多條專線時，若允許該用戶對其中的一些專線采用現(xiàn)金支付，對另一些專線 采用銀行托付方式，則在盡量減少數(shù)據(jù)冗余的前提下，應如何調(diào)整有關的數(shù)據(jù)文件。

[流程圖1]

試題 2

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

[說明]

流程圖 2-1 用來實現(xiàn)在數(shù)組 A(n) 中尋找第K大的元素。 算法思想是通過比較和交換，在區(qū)間 1～n 中找到一個 m，使 A(1)～A(m-1) 的值均大于 A(m)， A(m+1)～A(n) 的值均小于 A(m)。若 m＝K，則 A(m) 即為第 K 大的元素，否則調(diào)整查找區(qū)間，繼續(xù)上述 查找。

[問題 1]

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

[問題 2]

若將流程圖 2-1 中的虛框部分改成圖 2-2 所示的框圖，則當 A(1) 為數(shù)組 A 的最大元素時，修改后 的流程圖能否正常運行? 為什么?

[流程圖 2-1]

試題 3

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

[說明]

流程圖 3 用來將數(shù)組 A 中的 n( n≥2 ) 個數(shù)經(jīng)變換后存儲到數(shù)組B中。變換規(guī)則如下：

1．若 A 中有連續(xù) t 個相同的元素( t>1 )，則在 B 中存入 t 和該元素的值；

2．若 A 中有連續(xù) t 個元素( t≥1 )，其中每個元素都與相鄰的元素不相同，則在 B 中存入 -t 和這 t 個元素的值。

例如：

A = { 3，3，3，3，5，5，7，6，3，6，2，2，2，2，1，2 } 則變換后 B = { 4，3，2，5，-4，7，6，3，6，4，2，-2，l，2 } 流程圖中，邏輯變量 C 用來區(qū)分正在進行連續(xù)相同元的計數(shù)還是連續(xù)不等元的計數(shù)，K1 用來記 錄數(shù)組 B 中存放 t 或 -t 的元素的下標。

[問題 1]

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

[NextPage]

[問題 2]

如果刪除流程圖中的判斷框 t+1，那末，當數(shù)組 A＝{ 5，5，4，4 }時，經(jīng)改變后的流程圖的變換，數(shù)組 B 將會有什么樣的元素值?

[流程圖3]

試題4

閱讀下列說明和流程圖，回答問題 1 至問題 3，把解答寫在答卷的對應欄內(nèi)。

[說明]

流程圖 4-1 用于把文件 A 和文件 B 合并成按上升順序分類(排序)的文件 C。 已知文件 A 和 B 中的關鍵碼均小于 M。

[問題 1]

為使流程圖 4-1 能正確工作，文件 A 和文件 B 諸記錄的關鍵碼必須滿足什么條件?

[問題2]

按流程圖 4-1 的處理方式，分別指出文件 A 和文件 B 至少應含有的記錄個數(shù)。

[問題3]

若將流程圖 4-1 中的虛線部分改成框圖 4-2，則圖中的“判斷條件”應是什么?

[流程圖 4-1 ]

試題5

閱讀下列說明和 E—R 圖，回答問題，把解答寫在答卷的對應欄內(nèi)。

[說明]

設有下列關于學生成績管理系統(tǒng)的 E—R 圖。圖中矩形表示實體，圓表示屬性，雙圓表示關鍵字屬性，菱形表示實體間的聯(lián)系。假定已通過下列 SQL 語言建立了基本表： 

CREATE TABLE STUDENT 

( SNO CHAR(6)NOT NULL，

SNAME CHAR(20)，

DEPT CHAR(20)，

AGE SMALLINT)；

CREATE TABLE COURSE

( CNO CHAR(6)NOT NULL，

CNAME CHAR(20)，

HOUR SMALLINT)；

CREATE TABLE S—C

( SNO CHAR(6)，

CNOefIAR(6)，

GRADE SMALLINT )；

為了答題的方便，圖中的實體和屬性同時給出了中英兩種名字，回答問題時只須寫出英文名即可。

[E-R]圖

[問題]

填充下列 SQL 程序 5.1～5.4 中的 ①～⑥，使它們分別完成以下查詢功能：

程序 5.1：檢索選讀所有課程的學生姓名。

程序 5.2：給出全體學生人數(shù)。

程序 5.3：按學號給出每個學生的平均成績。

程序 5.4：按學號給出每個學生選讀課程的門數(shù)。

[程序 5.1]

SELECT STUDENT.SNAME

FROM STUDENT

WHERE[__①__]

( SELECT ^* 

FROM COURSE

WHERE[__②__]

( SELECT ^*

FROM S-C

WHERE[__③__]))

[程序 5.2]

SELECT [__④__]

FROM STUDENT

[程序 5.3]

SELECT [__⑤__]

FROM S-C

GROUP BY SNO

[程序 5.4]

SELECT [__⑥__]

FROM S-C

GROUPBY SNO

試題6

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

[程序說明]

子程序 DIVIDE 將真分數(shù) a/b ( 0<a<b )轉(zhuǎn)換成 N 位小數(shù)( 0<N≤20 )，并輸出結(jié)果。

子程序從棧中接受參數(shù)。參數(shù)的入棧順序為：分子 (a)、分母 (b) 和小數(shù)位數(shù) (N)。進入子程序已保證 0<a<b 且 0<N≤20，子程序不再對參數(shù)作合法性檢查。

由于需要將結(jié)果輸出，所以子程序中計算出每一位小數(shù)后直接用字符方式順次存放在標號 OUTPUT 之后的存儲區(qū)域中。數(shù)字字符 0～9 的 ASCII 編碼依次是 48～57。

[程序]

試題7

閱讀下列程序說明和 C 程序，把應填入其中[__n__]處的字句，寫在答卷的對應欄內(nèi)。

[程序說明]

由二叉樹的前序遍歷和中序遍歷兩個遍歷序列能唯一確定一棵二叉樹。 前序遍歷為：訪問根結(jié)點、訪問左子樹、訪問右子樹； 中序遍歷為：訪問左子樹、訪問根結(jié)點、訪問右子樹。 如右圖所示的二叉樹，其前序和中序遍歷序列分別為：        pred[  ]：A、B、D、E、C、F、G。        inod[  ]：D、B、E、A、C、G、F。

本程序?qū)崿F(xiàn)已知某二叉樹的前序遍歷和中序遍歷序列，生成一棵鏈接表示的二叉樹。

構(gòu)造二叉樹的算法要點是：由前序遍歷序列，該序列的第一個元素是根結(jié)點元素( 例中為 A )。該元素將中序遍歷序列分成左、右兩部分，那些位于該元素之前的元素是它的左子樹上的元素 ( 例中為D 、B、E )，位于該元素之后的元素是它的右子樹上的元素( 例中為 C、G、F )。對于左、右 子樹，由它們的前序遍歷序列的第一個元素可確定左、右子樹的根結(jié)點，參照中序遍歷序列又可進一步確定子樹的左、右子樹元素。如此遞歸地參照兩個遍歷序列，最終構(gòu)造出二叉樹。

兩個遍歷序列作為主函數(shù) main( )的參數(shù)。為簡單起見，程序假定兩個遍歷序列是相容的。 主函數(shù)調(diào)用函數(shù) restore( ) 建立二叉樹。函數(shù) restore( ) 以樹( 子樹 )的前序遍歷和中序遍歷兩序列及序列長為參數(shù)，采用遞歸方法建立樹( 子樹 )。 函數(shù) postorder( )實現(xiàn)二叉樹的后序遍歷序列輸出，用來驗證函數(shù)restore( )建立的二叉樹。

[程序]

#include (stdio．h>

#include <stdlib．h>

#define MAX 100

typedef struct node{

char info；

struct node * llink，*rlink；

} TNODE；

charpred[MAX]，inod[MAX]；

TNODE * restore( Char * ，char *,int )；

main( int argc，Char * * argv )

{

TNODE * root；

if ( argc<3 ) exit(0)；

strcpy( pred，argv[l] )；

strcpy( inod，argv[2] )；

root = restore( pred，inod，strlen( pred )) postorder( root )；

printf(”\n\n”)；

}

TNODE * restore( Char * ppos,char * ipos,int n )

{

TNODE * ptr；

Char * rpos；

int k；

if ( n <＝ 0 ) return NULL；

ptr = ( TNODE * ) malloc( sizeof( TNODE ))；

ptr->info ＝ [__1__] ；

for ( [__2__]；rpos < ipos+n；rpos++ )

if ( *rpos == * ppos ) break；

k = [__3__]；

ptr->llink = restore( ppos+1,[__4__],k )；

ptr->rlink = restore( [__5__] + k,

[__6__] + 1,

n-1-k )；

return ptr；

}

postorder( TNODE * ptr )

{ if ( ptr == NULL ) return；

postorder( ptr->llink )；

postorder( ptr->r1ink )；

prinft( ”％c”，ptr->info )；

}

試題8～10 略（COBOL、FORTRAN、PASCAL）

答案

試題一

[問題1]

對端所在地區(qū)，通信速率，初裝費，月租費

[問題2]

不能，因為處理3的輸入文件及單據(jù)中缺少施工單位所需的主端名稱，主端地址，對端地址，對端所在地區(qū)，通信速率，設備接口等數(shù)據(jù)項。

[問題3]

在專線計費文件中加上付款方式數(shù)據(jù)項，取消用戶文件中的付款方式數(shù)據(jù)項。

試題二

[問題1]

① i+1→i 或 m+1→i

② i:j

③ j-1→j 或 m-1→j

④ m+1→low

⑤ m-1→high

[問題2]

不能，因為A(1)為數(shù)組A的最大元時，修改后的流程圖將始終執(zhí)行j-1→j；以致數(shù)組下標越界。

試題三

[問題1]

① 1→t

② 1-t

③ 'tree'→C

④ 'false'→C

⑤ -t→B(K1)

[問題2]

B={2,5,0,2,4}

試題四

[問題1]

文件A和文件B必須均按升序排列，并且文件A的最后一個記錄的關鍵碼應小于或等于文件B的最后一個記錄的關鍵碼。

[問題2]

文件A至少有零個記錄；當文件A非空時，文件B至少有1個記錄；當文件A為空時，文件A至少有零個記錄.

[問題3]

A的關鍵碼等于M并且B的關鍵碼等于M。

試題五

① NOT EXISTS

② NOT EXISTS

③ STUDENT.SNO=S-C.SNO AND COURSE.CNO=S-C.CNO

④ COUNT（*）

⑤ SNO，AVG(GRADE)

⑥ SNO，COUNT(CNO)

試題六

試題七

（1） *ppos 或 ppos[0]

（2） rpos=ipos

（3） rpos-ipos

（4） ipos 或 rpos-k

（5） ppos+1

（6） rpos 或 ipos-k