试题一

 阅读下列说明，回答问题1至问题4，将解答填入答题纸的对应栏内。
【说明】
某证券交易所为了方便提供证券交易服务，欲开发一证券交易平台，该平台的主要功能如下：
（1）开户。根据客户服务助理提交的开户信息，进行开户，并将客户信息存入客户记录中，账户信息（余额等）存入账户记录中；
（2）存款。客户可以向其账户中存款，根据存款金额修改账户余额；
（3）取款。客户可以从其账户中取款，根据取款金额修改账户余额；
（4）证券交易。客户和经纪人均可以进行证券交易（客户通过在线方式，经纪人通过电话），将交易信息存入交易记录中；
（5）检查交易。平台从交易记录中读取交易信息，将交易明细返回给客户。
现采用结构化方法对该证券交易平台进行分析与设计，获得如图1-1所示的上下文数据流图和图1-2所示的0层数据流图。

 问题：1.1 （3分）

使用说明中的词语，给出图1-1中的实体E1-E3的名称。

问题：1.2 （3分）
使用说明中的词语，给出图1-2中的数据存储D1-D3的名称。

问题：1.3 （4分）
根据说明和图中的术语，补充图1-2中缺失的数据流及其起点和终点。

问题：1.4 （5分）
实际的证券交易通常是在证券交易中心完成的，因此，该平台的“证券交易”功能需将交易信息传递给证券交易中心。针对这个功能需求，需要对图1-1和图1-2进行哪些修改，请用200字以内的文字加以说明。

 答案

问题：1.1

E1：客户服务助理，E2：客户，E3：经纪人。

本题要求识别E1-E3具体为哪个外部实体，通读试题说明，可以了解到适合充当外部实体的包括：客户、客户服务助理、经记人。具体的对应关系，可以通过将顶层图与题目说明进行匹配得知。如：从图中可看出E1会向交易平台发出数据流开户信息;；而从试题说明根据客户服务助理提交的开户信息，进行开户，并将客户信息存入客户记录中，账户信息存入账户记录中可以看出，E1对应是客户服务助理。E2、E3同理可得。

问题：1.2

D1：客户记录，D2：账户记录，D3：交易记录。

本题要求识别存储，解决这类问题，以图的分析为主，配合说明给存储命名，因为存储相关的数据流一般展现了这个存储中到底存了些什么信息，如从图中可以看到D1中有客户信息，而D2中有账户信息，题目说明中又有根据客户服务助理提交的开户信息，进行开户，并将客户信息存入客户记录中，账户信息存入账户记录中。自然D1应为客户记录，D2应为账户记录。同理，D3为交易记录。

问题：1.3

数据流名称：修改账户余额，起点：存款，终点：D2。
数据流名称：修改账户余额，起点：取款，终点：D2。
数据流名称：交易信息存入交易记录，起点：证券交易，终点：D3。

缺失数据流1
名称：修改账户余额，起点：存款，终点：D2。
理由：从试题说明客户可以向其账户中存款，根据存款金额修改账户余额可以看出，这个功能有操作根据存款金额修改账户余额。据此可以了解到从该功能应有数据流存款至D2，而0层图没有。
缺失数据流2:
名称：修改账户余额，起点：取款，终点：D2。
理由：从试题说明客户可以从其账户中取款，根据取款金额修改账户余额可以看出，这个功能有操作根据取款金额修改账户余额。据此可以了解到从该功能应有数据流取款至D2，而0层图没有。
缺失数据流3
名称：交易信息存入交易记录，起点：证券交易，终点：D3。
理由：从试题说明客户和经纪人均可以进行证券交易，将交易信息存入交易记录中可以看出，这个功能有操作将交易信息存入交易记录中。据此可以了解到从该功能应有数据流证券交易至D3，而0层图没有。

问题：1.4

增加外部实体证券交易中心，原来证券交易中的交易信息的数据流终点改为证券交易中心，数据流检测交易中的起点改为证券交易中心。

本题强调实际的证券交易通常是在证券交易中心完成，这个证券交易中心属于典型的外部实体，所以需要增加外部实体证券交易中心。由于该平台的证券交易功能需将交易信息传递给证券交易中心，因此将原来证券交易中的交易信息的数据流终点改为证券交易中心，数据流检测交易中的起点改为证券交易中心。

试题四

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
模式匹配是指给定主串t和子串s，在主串t中寻找子串s的过程，其中s称为模式。如果匹配成功，返回s在t中的位置，否则返回-1 。
KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下：
1．在串t和串s中，分别设比较的起始下标i=j=0。
2．如果串t和串s都还有字符，则循环执行下列操作：
（1）如果j=-l或者t[i]=s[j]，则将i和j分别加1，继续比较t和s的下一个字符；
（2）否则，将j向右滑动到next[j]的位置，即j =next[j]。
3．如果s中所有字符均已比较完毕，则返回匹配的起始位置（从1开始）；否则返回-1．
其中，next数组根据子串s求解。求解next数组的代码已由get_next函数给出。

【C代码】
（1）常量和变量说明
t，s：长度为lt,ls的字符串
next:next数组，长度为ls
（2）C程序

#include <stdio.h>

#include <stdlib.h>
#include <string.h>
/*求next[]的值*/
void get_next( int *next, char *s, int ls)
{
    int i=0，j=-1;
    next[0]=-1;/*初始化next[0]*/
    while(i < ls) /*还有字符*/
    {
        if(j==-1 ll s[i]==s[j]) /*匹配*/
        {
            j++;
            i++;
            if( s[i]==s[j])
                next[i] = next[j];
            else
                next[i] = j;
        }
        else
            j = next[j];
    }
}
int kmp( int *next, char *t,char *s, int lt, int ls )
{
    Int i= 0,j =0 ;
    while (i < lt && （1） )
    {
        if( j==-1 || （2） )
        {
            i ++ ;
            j ++ ;
        }
        else
            （3） ;
    }
    if (j >= ls)
        return （4） ;
    else
        return -1;
}

问题：4.1   （8分）
根据题干说明，填充C代码中的空（1）～（4）.
 
问题：4.2   （2分）
根据题干说明和C代码，分析出kmp算法的时间复杂度为（5）（主串和子串的长度分别为lt和ls，用O符号表示）。
 
问题：4.3   （5分）
根据C代码，字符串“BBABBCAC”的next数组元素值为（6）（直接写素值，之间用逗号隔开）。若主串为“AABBCBBABBCACCD”，
子串为“BBABBCAC”，则函数Kmp的返回值是（7）。

答案

（1）：j<ls
（2）：t[i]==s[j];
（3）：get_next(next, s, ls)，
            j=next[j]
（4）：i+1-ls 
（5）：O(ls+lt) 
（6）：[-1,-1,1,-1,-1,2,0,0]
（7）：6 

试题五

阅读下列说明和java代码，将应填入 （n） 处的字句写在答题纸的对应栏内。
【说明】
某发票（lnvoice）由抬头（Head）部分、正文部分和脚注（Foot）部分构成。现采用装饰（Decorator）模式实现打印发票的功能，得到如图6-1所示的类图。

问题：6.1   【java代码】

class invoice
{
    public void printInvoice()
    {
        System.out.println ( "This is the content of the invoice!");
    }
}
class Decorator extends Invoice
{
    protected Invoice ticket;
    public Decorator(lnvoice t)
    {
        ticket = t;
    }
    public void printInvoice()
    {
        if(ticket != null)
            （1） ;
    }
}
class HeadDecorator extends Decorator
{
    public HeadDecorator(lnvoice t)
    {
        super(t);
    }
    public void printInvoice ()
    {
        System.out.println( "This is the header of the invoice! ");
        （2） ;
    }
}
class FootDecorator extends Decorator
{
    public FootDecorator(Invoice t)
    {
        super(t);
    }
    public void printlnvoice()
    {
        （ 3） ;
        System.out.println( "This is the footnote of the invoice! ");
    }
}
Class test
{
    public static void main(String[] args)
    {
        Invoice t =new Invioce();
        Invoice ticket;
        ticket= （4） ;
        ticket.printInvoice();
        System.out.println(“------------------“);
        ticket= （5） ;
        ticket.printInvoice();
    }
}

程序的输出结果为：
This is the header of the invoice!
This is the content of the invoice!
This is the footnote of the invoice!
----------------------------
This is the header of the invoice!
This is the footnote of the invoice!

答案

（1）ticket.printInvoice()
（2）super.printInvoice()
（3）super.printInvoice()
（4）new HeadDecorator(new FootDecorator(t)) 
（5）new HeadDecorator(new FootDecorator(null))