2001年度高級程序員級下午試題
試題一

閱讀下列說明和流程圖,回答問題1至問題3,把解答填入答題紙的對應欄內。

[說明]

某計算機廠生產多種型號的計算機,通過分布在世界各地的銷售點銷售,銷售點應在收到計算機商品后的規定時間內把貨款匯給該計算機廠。

流程圖 1 描述了該廠發貨、收款、催款的處理過程。其中商品文件、銷售點文件、發貨文件和收款文件的記錄格式如下:

    商品文件 = 商品代號 + 計算機規格名稱 + 單價

    銷售點文件 = 銷售點代號 + 銷售點名稱 + 地址

    發貨文件 = 發貨單號 + 發出日期 + 銷售點代號 + 商品代號 + 數量 + 金額

    收款文件 = 收款單號 + 收款日期 + 銷售點代號 + 商品代號 + 數量 + 金額 + 發貨單號

在流程圖中,處理 1～處理 3 把當天的發貨單合并到發貨文件。處理 4～處理 6 把當天的收款單合并到收款文件。每天在處理 3 和處理 5 完成之后,由處理 7 在發貨文件中當天已收款的記錄上加上已收款標記。處理 8 在月末執行一次,它有三個功能:

①匯總輸出本月發貨清單;

②刪除發貨文件中已收款的所有記錄,形成一個新的發貨文件,作為下月初處理時的初始文件

③產生催款通知單,以便對那些一個月以前已發貨但至今仍未收到貨款的銷售點催款。

[問題1]

指出流程圖 l 中應在哪幾個處理框中檢查發貨單和收款單的錯誤，并分別說明它們各能指出什么錯誤。

[問題2]

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

[問題3]

處理 9 每月末執行一次如流程圖所示，利用收款文件產生月收款報告并更新收款文件。要求指出它對收款文件做什么更新操作。

 
(見圖1）

試題二

閱讀下列說明和流程圖,回答問題 1 至問題 3 ,把解答填入答題紙的對應欄內。

[說明]

某考務處理系統具有以下功能:

1.輸入報名單;

2.自動編制準考證號;

3.輸出準考證;

4.輸入成績清單;

5.輸出成績通知單;

6.輸出成績分布表;

7.輸入合格標準、輸出錄取通知單;

8.試題難度分析,并輸出試題難度分析表。

這里給出了實現上述要求的部分不完整的數據流圖,其中部分數據流的組成如下所示:

報名單 = 報名號 + 姓名 + 通信地址

考生名冊 = 報名號 + 準考證號 + 姓名 + 通信地址

成績冊 = 準考證號 + { 課程號 + 成績 } (其中{W}表示W重復多次)

準考證 = 報名號 + 姓名 + 準考證號

[問題1]

指出 0 層圖中可以刪去的部分。

[問題2]

在加工 1 子圖中將遺漏的數據流添加在答題紙上。

[問題3]

加工 2 子圖分解成如圖所示的 4 個子加工及相關的文件(即數據存儲)。試在此基礎上將相關的DFD 成份添加在答題紙上,以完全該加工子圖。

[數據流圖]

    頂層
（見圖2）
（見圖3）

試題三

在COMET型計算機上可以使用試卷上所附的 CASL 匯編語言。閱讀程序說明和 CASL 程序,將應填入__(n)__處的字句,寫在答題紙的對應欄內。

[程序3說明]

子程序 DEHZ 用來對 HZ 編碼的字串做解碼處理。

HZ 編碼是海外華人創造的一種將含有高位為 1 的漢字雙字節字串轉換成易于在網絡中傳輸的ASCII 字符串的變換方式。編碼過程中,被轉換字符串中的原漢字子字符串各字節高位作清零處理,使之成為 ASCII 子字符串,并在其前后兩端分別添加 ~{ 和 ~} 作為標記；而對于原 ASCII 子字符串,則將其中的 ~ 改寫為 ~~,其余字符不變。

DEHZ 解碼子程序則是 HZ 編碼的復原過程。復原 ASCII 子字符串過程中遇有 ~~ 字符則改寫為一個 ~ ,遇有 ~{ 則將其后直至 ~} 標記前的各字節高位置1,復原為漢字子字符串,同時刪除其前后標記。~的后續字符不屬于以上情況均作為錯誤處理。

調用該子程序時, GR1 存放原始字符串首地址, GR2 存放還原后的目標字符串首地址。工作寄存器  GR3 用作處理漢字子字符串的識別標志,進入子程序時應初始化為處理 ASCII 子字符串。程序按照   CASL 語言的標準約定,字符串的每個字符只占用一個存儲字的低八位。原始字符串和目標字符串均以 0 作為結束標志。

[程序3]

        START

DEHZ    PUSH    0,GR3

        PUSH    0,GR2

        PUSH    0,GR1

        LEA     GR3,0

LOOP    __(1)__

        CPA     GR0,MARK0

        JNZ     GOON

        LEA     GR1,1,GR1

        LD      GR0,0,GR1

        CPA     GR0,MARK0

        __(2)__

        CPA     GR0,MARK1,GR3

        JNZ     ERROR

        __(3)__

        LEA     GR1,1,GR1

        JMP     LOOP

ERROR   OUT     ERS1R,ERLEN

        JMP     EXIT

GOON    __(4)__

        ST      GR0,0,GR2

        LEA     GR2,1,GR2

        LEA     GR1,1,GR1

        CPA     GR0,VO

        __(5)__

EXIT    P0P     GR1

        P0P     GR2

        P0P     GR3

        RET

V1      DC      1

V0      DC      O

        DC      #0080

MARK0   DC      '~ '

MARK1   DC      '{ }'

ERSTR   DC      'ERROR!'

ERLEN   DC      6

        END


試題四

閱讀下列程序說明和C代碼,將應填入__(n)__處的字句寫在答題紙的對應欄內。

[程序4說明]

設 M 叉樹采用列表法表示,即每棵子樹對應一個列表,列表的結構為:子樹根結點的值部分 (設為一個字符) 和用“( )”,括起來的各子樹的列表 (如有子樹的話) ,各子列表間用“,”,分隔。例如下面的三叉樹可用列表 a( b( c,d ),e,f( g,h,i ))表示。

　
（見圖4）
本程序輸入列表,生成一棵 M 叉樹,并由 M 叉樹輸出列表。假定輸入無錯誤。

[程序4]

#include〈stdio.h〉

#include〈stdlib.h〉

#define M 3

typedef struct node{ char val;

        struct node *subTree[M];

        } NODE;

char buf[255] ,*str = buf

NODE *d = NULL

NODE *mackTree( ) /*由列表生成M叉樹*/

{ int k; NODE *s ;

    s = __(1)__

    s -> val = *str++ ;

    for ( k = 0 ; k < M ; k++ ) s-> subTree[k] = NULL ;

    if(*str='( '){

        k = 0;

        do { str++;

            s -> subTree[k] = __(2)__ ;

            if ( *str == ')' ) { str++; break ; }

            k = k+l ;

        } while ( __(3)__ );

    }

    return s ;

}

void walkTree( NODE *t ) /*由 M 叉樹輸出列表*/

{ int i ;

    if t != NULL ) {

        __(4)__

        if ( t -> subTree[0] == NULL ) return ;

        putchar ( '( ' ) ;

        for ( i = 0 ; i < m ; i++) {

            __(5)__ 

           if ( i! = M - l && t -> subTree[i+l] != NULL )

                putchar ( ', ' ) ;

        }

        putchar ( ') ' ) ;

    }

}

　

void main( )

{ printf( "Enter exp:" ) ;

    scanf( "%S" , str ) ;

    d = makeTree() ;

    walkTree( d ) ; putchar( '\n') ;

}

　

試題五

閱讀下列程序說明和C代碼,將應填入__(n)__處的字句寫在答題紙的對應欄內。

[程序5說明]

著名的四色定理指出任何平面區域圖均可用四種顏色著色,使相鄰區域著不同的顏色。本程序對給定的區域圖找出所有可能的不超過四種顏色的著色方案。程序中用 1～4 表示四種顏色。要著色的 N 個區域用 0～N一1編號,區域相鄰關系用 adj[][] 矩陣表示,矩陣的 i 行 j 列的元素為 1 ,表示區域 i 與區域 j 相鄰；矩陣的 i 行 j 列的元素為 0 ,表示區域 i 與區域 j 不相鄰。數組 color[] 用來存儲著色結果, color[i] 的值為區域 i 所著顏色。

【程序5】

#include〈stdio.h〉

#define  N 10

void output(int color[])/*輸出一種著色方案*/

{ int i ;

    for ( i = 0 ; i < N ; i++ ) 

        printf( "%4d" , color[i] ) ;

    printf( "\n" ) ;

}

int back( int *ip ,int color[] ) /*回溯*/

{ int c = 4 ;

    while ( c == 4 ){

        if ( *ip <= 0 ) return 0 ;

        --(*ip) ;

        c = __(1)__ ;

        color[*ip] = -1 ;

    } 

    return c ;

}

/*檢查區域i,對c種顏色的可用性*/

int color0k( int i , int c , int[][N] , int color[ ] }

{ int j ;

    for ( j = 0 ; j < i ; j++ }

        if ( __(2)__ )

            return 0 ;

    return 1 ;

}

　

/*為區域i選一種可著的顏色*/

int select( int i ,int c ,int adj[][N] , int color[ ] )

{ int k ;

    for ( k = c ; k <= 4 ; k++ )

        if ( colorOK( __(2)__ ) )

            return k ;

        return 0 ;

}

int coloring( int adj[][N] ) /*尋找各種著色方案*/

{ int color[N] , i , c , cnt ;

    for ( i = 0 ; i < N ; i++ ) color[i] = -1 ;

    i = c = 0 ; cnt = 0 ;

    while ( 1 ) {

        if ( ( c = __(4)__ ) == 0 ){

            c = back( &i , color) ;

            if ( c == 0) return cnt ;

        } else { __(5)__ ; i++ ;

            if ( i == N ) {

                    output(color) ;

                    ++cnt ;

                    c = back( &i , color ) ;

                  } e1se c = 0 ;

                }

        }

}

void main()

{ int adj[N][N] = 

            { {0,1,0,1,1,1,1,1,1,1},

              {1,0,1,1,0,1,1,1,1,0},

              {0,1,0,1,0,1,1,0,1,1},

              {1,1,1,0,1,1,0,0,1,1},

              {1,0,0,1,0,1,0,0,0,0},

              {1,1,1,1,1,0,1,0,0,1},

              {1,1,1,0,0,1,0,0,1,0},

              {1,1,0,0,0,0,0,0,1,1},

              {1,1,1,1,0,0,1,1,0,1},

              {1,0,1,1,0,1,0,1,1,0}

            } ;

    printf( "共有%d組解.\n",coloring( adj ) ) ;

}