1) 阅读下列说明和图，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。
【说明】
设有二维整数数组（矩阵）A[1:m,1:n],其每行元素从左至右是递增的，每列元素从上到下是递增的。以下流程图旨在该矩阵中需找与给定整数 X 相等的数。如果找不到则输出“false”;只要找到一个（可能有多个）就输出“True”以及钙元素的下标 i 和 j（注意数组元素的下标从 1 开始）。
例如，在如下矩阵中查找整数 8，则输出伟：True,4,1
2 4 6 9
4 5 9 10
6 7 10 12
8 9 11 13
流程图中采用的算法如下：从矩阵的右上角元素开始，按照一定的路线逐个取元素与给定整数 X 进行比较（必要时向左走一步或向下走一步取下一个元素），直到找到相等的数或超出矩阵范围（找不到）。
【流程图】

【问题】该算法的时间复杂数是（）
供选择答案：A.O（1） B.O（m+n） C.（m*n） D,O（m²+n²）

2) 阅读下列说明和 C 函数，填补函数中的空缺，将解答填入答案纸的对应栏目内。
【说明】
函数 isLegal（char*ipaddr）的功能是判断以点分十进制数表示的 iPV4 地址是否合法。参数 ipadddr 给出表示 iPV4 地址的字符串的首地址，串中仅含数字字符和“.”。若 iPV4 地址合法则返回1，否则反馈 0.判定伟合法的条件是：每个十进制数的值位于整数区间[0,25]，两个相邻的树之间用“.”分隔，共 4 个数、3 个“.”。；例如，192.168.0.15、1.0.0.1 是合法的，192.168.1.256、1.1..1是不合法的。
【函数】

int isLegal(char* ipaddr)
{
    int flag;
    int curVal;  //curVal 表示分析出的一个十进制数
    int decNum=0,dotNum=0;  // decNum 用于记录十进制数的个数
    //dotNum 用户记录点的个数
    char* p=(   )
    for (;*p;p++) {
        curVal=0;flag=0;
        while  (isdigit(*p)) { //判断是否伟数字字符
            curVal=(   )+*p-′0′;
            (   )
            flag=1;
        }
        if (curVal>255) {
            return 0;
        }
        if (flag) {
            (   )
        } 
        if (*p=′.′) {
            dotNum++;
        }
    }
    if (   ) {
        return 1；
    }
    return 0;
}

3) 阅读下列说明和 C 函数，填补 C 函数中的空缺，将解答填入答案纸的对应栏目内。
【说明】
字符串是程序中常见的一种处理对象，在字符串中进行子串的定位、插入和删除是常见的运算。
设存储字符串时不设置结束标志，而是另行说明串的长度，因此串类型定义如下：
typedef struct ｛
    char* str;  //字符串存储空间的起始地址
    int lehgth;  //字符串长
    int capacity;  //存储空间的容量
} SString;
【函数 1 说明】
函数 indexStr（S,T,pos）的功能是：在 S 所表示的字符串中，从下标 pos 开始查找 T 所表示字符串首次出现的位置。方法是：第一趟从 S 中下标为 pos、T 中下标伟 0 的字符开始，从左往右逐个对于来比较 S 和 T 的字符，直到遇到不同的字符或者到达 T 的末尾。若到达 T 的末尾，则本趟匹配的起始下标 pos 为 T 出现的位置，结束查找；若遇到了不同的字符，则本趟匹配失效。下一趟从 S 中下标 pos+1 处的字符开始，重复以上过程。若在 S 中找到 T，则返回其首次出现的位置，否则返回-1。
例如，若 S 中的字符串伟″students ents″,T 中的字符串伟″ent″，pos=0，则 T 在 S 中首次出现的位置为 4。
【C 函数 1】

int indexStr(SString S, SString T, int pos)
{
    int i,j:
    if (S.length<1||S.length<pos+T.length-1)
        return-1;
    for (i=pos,j=0;i<S.length &&j<T.length;) {
        if (S.str[i]==T.str[j]) {
            i++;j++;
        } else {
            i=(   );j=0;
        }
    }
    if (   ) return i -T.length;
    return-1;
}

【函数 2 说明】
函数 eraseStr(S，T)的功能是删除字符串 S 中所有与 T 相同的子串，其处理过程为: 首先从字符串 S 的第一个字符（下标为 0）开始查找子串 T，若找到〈得到子串 在 S 中的起始位置），则将串 S中子串 T 之后的所有字符向前移动，将子串 T 覆盖，从而将 其删除，然后重新开始查找下一个子串 T，若找到就用后面的宇符序列进行覆盖，重复上述过程，直到将 S 中所有的子串 T 删除。
例如，若字符串 S 为 “12ab345abab678”、T 为“ab”。第一次找到 "ab" 时（位置为（2），将 "345abab678 "前移，S 中的串改为"12345abab678" ，第二次找到"ab"时（位置为 5）;将 ab678 前移，S 中的串改为 "12345ab678"，第三次找到"ab"时（位置 为 5）;将“678‘前移 ，S 中的串改为 "12345678 "。
【C 函数 2】

void eraseStr(SString*S,SStringT)
{
    int i;
    int pos;
    if (S->length<||T.length<1||S->length<T.length)
        return;
    pos=0;
    for (;;) {
        // 调用 indexStr 在 S 所表示串的 pos 开始查找 T 的位置
        pos=indexStr(   );
        if (pos＝-1) // S 所表示串中不存在子串 T
            return;
        for (i=pos+T.length;i<S->length;i++) // 通过覆盖来删除自串 T
             S->str[(   )]=S->str[i];
        S->length=(   );  //更新 S所表示串的长度
    }
}

4) 阅读以下说明和 C 函数，填补函数中的空缺，将解答填入答题纸的对应栏内。
【说明】
简单队列是符合先进先出规则的数据结构，下面用不含有头结点的单向循环链表表示简单队列。
函数 enqueue(queue *q，KeyType new_elem) 的功能是将元素new_elem 加入队尾。
函数 dequeue(queue *q，KeyType *elem) 的功能使将非空队列的队头元素出队（从队列中删除），并通过参数带回刚出队的元素。
用单向循环链表表示的队列如图所示。

图 4-1 单向循环链表表示的队列示意图
队列及链表结点等相关类型定义如下:
enum {errOr， OK};
typedef int KeyType;
typedef struct qNode {
    KeyType data;
    Struct qNode* next;
} qNode，*Linkqueue;

typedef struct {
    int size;
    Linkqueue rear;
} queue;

【C 函数】

int enqueue(queue* q, KeyType new_elem)
{ //元素 new_elem 入队列
    qNode* p;
    p=(qNode*)malloc(sizeof(qNode));
    if (!p)
        return errOr;
    p->data=new_elem;
    if (q->rear) {
        p->next=q->rear->next;
        (   );
    }
    else
        p->next=p;
    (   );
    q->size++;
    return OK;
}

int dequeue(queue* q, KeyType* elem)
{ //出队列
    qNode* p;
    if (0＝＝q->size) //是空队列
        return errOr；
    p=(   ); //令 p 指向队头元素结点
    *elem =p->data;
    q->rear->next=(   ); //将队列元素结点从链表中去除
    if ((   )) //被删除的队头结点是队列中唯一结点
    q->rear=NULL //变成空队列
    free(p);
    q->size--;
    return OK;
}

5) 阅读以下说明和 Java 程序，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
以下 Jave 代码实现一个简单客户关系管理系统（CRM） 中通过工厂 （Customerrfactory ）对象来创建客户（Customer） 对象的功能。客户分为创建成功的客户 （realCustomer） 和空客户（NullCustomer） 。空客户对象是当不满足特定条件时创建或获取的对象。
【Java 代码】

abstract class Customer {
    protected String name;
    (   ) boolean isNil();
    (   ) String getName();
}

class realCustomer  (   ) Customer {
    public realCustomer(String name) { this.name=name; }
    public String getName() { return name; }
    public boolean isNil() { return false; }
}

class NullCustomer (   ) Customer {
    public String getName() { return "Not Available in Customer Database"; }
    public boolean isNil() { return true; }
}

class Customerfactory {
    public String[] names = {"rob"，"Joe"，"Julie"};
    public Customer getCustomer(String name) {
        for (int i = 0; i < names.length;i++) {
            if （names[i].(   )）{
                return new realCustomer(name);
            }
        }
        return (   );
    }
}

public class CRM {
    public viod getCustomer() {
        Customerfactory（   ）
        Customer customer1 = cf.getCustomer("rob");
        Customer customer2 = cf.getCustomer("rob");
        Customer customer3 = cf.getCustomer("Julie");
        Customer customer4 = cf.getCustomer("Laura");
        System.out.println(customer1.getName());
        System.out.println(customer2.getName());
        System.out.println(customer3.getName());
        System.out.println(customer4.getName());
    }

    public static viod main(String[] args) {
        CRM crm =new CRM();
        crm.getCustomer();
    }
}

／*程序输出为：
rob
Not Available in Customer Database
Julie
Not Available in Customer Database
*／

6) 阅读下列说明和 C++代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
以下 C++代码实现一个简单客户关系管理系统（CrM）中通过工厂（Customerfactory）对象来创建客户（Customer）对象的功能。客户分为创建成功的客户（realCustomer）和空客户（NullCustomer）。空客户对象是当不满足特定条件时创建或获取的对象。类间关系如图6-1 所示。

【C++代码】

#include<iostream>
#include<string>
using namespace std;

class Customer｛
protected:
    string name;
public:
    ( 1 ) boll isNil()=0;
    ( 2 ) string getName()=0;
}；

class realCustomer ( 3 ) {
public:
    realCustomer(string name)｛this->name=name; }
    bool isNil()｛ return false; }
    string getName()｛ return name; }
};

class NullCustomer ( 4 ) {
public:
    bool isNil() { return true; }
    string getName() { return "Not Available in Customer Database"; }
};

class Customerfactory {
public:
    string names[3]= {"rob", "Joe", "Julie"};
public:
    Customer* getCustomer(string name) {
        for (int i=0；i<3；i++) {
            if (names[i].( 5 ) ) {
                return new realCustomer(name);
            }
        }
        return ( 6 );
    }
};

class CRM {
public:
    void getCustomer() {
        Customerfactory* ( 7 );
        Customer*customer1=cf->getCustomer("rob");
        Customer*customer2=cf->getCustomer("Bob");
        Customer*customer3=cf->getCustomer("Julie");
        Customer*customer4=cf->getCustomer("Laura");

        cout<<"Customers"<<endl;
        cout<<Customer1->getName() <<endl； delete customer1;
        cout<<Customer2->getName() <<endl； delete customer2;
        cout<<Customer3->getName() <<endl； delete customer3;
        cout<<Customer4->getName() <<endl； delete customer4;
        delete cf；
    }
};

int main() {
    CRM* crm=new CRM();
    crm->getCustomer();
    delete crm;
    return 0;
}

/*程序输出为：
Customers
rob
Not Available in Customer Database
Julie
Not Available in Customer Database
*/