选择

1.算法的五个重要特性是（）

• A.有穷性、正确性、可用性、输入、输出
• B.有穷性、确定性、可用性、输入、输出
• C.有穷性、正确性、可行性、输入、输出
• D.有穷性、确定性、可行性、输入、输出

2.下面关于求关键路径的说法不正确的是（）

• A.求关键路径是以拓扑排序为基础的
• B.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
• C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
• D.关键活动一定位于关键路径

3.对下图进行拓扑排序，可以得到的拓扑序列可能是（）

• A.3，1，2，4，5，6
• B.3，1，2，4，6，5
• C.3，1，4，2，5，6
• D.3，1，4，2、6，5

4.设主串T="abaabaabcabaabc”，模式串S=abaabc”，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单全字符间的比较次数是（）

• A.9
• B.10
• C.12
• D.15

5.对 n 个不相同的符号进行哈夫编码。若生成的哈夫共有 115 个结点则 n 的值是（）

• A.56
• B.57
• C.58
• D.60

6.在 OSI 参考模型中，服务原语可划分为 4 种，包括请求、指示、响应和（）

• A.确认
• B.回答
• C.延迟
• D.反馈

7.某路由表中有转发接口相同的 4 条路表项，其目的网络地址分别为 35.230.32.0/21，35.230.40.0/21，35.230.48.0/21 和 35.230.56.0/21，将该4 条路由聚合后的目的网络地址为（）

• A.35.230.0.0/19
• B.35.230.0.0/20
• C.35.230.32.0/19
• D.35.230.32.0/20

8.主机甲采用停一等协议向主机乙发送数据，数据传输速率是 3kbps， 单向传播延时是 200ms 忽略确认帧的传输延时，当信道利用率等于40%时，数据的长度为（）

• A.240bit
• B.400bit
• C.480bit
• D.800bit

9.下列哪项协议不属于应用层协议（）

• A.SMTP
• B.ICMP
• D.DHCP
• C.HTTP

10.同步传输与异步传输相比（）

• A.同步传输更省线路
• B.同步传输具有更高的数据传输速率
• C.同步传输比异步传输的同步性能更好
• D.以上三点都不对。

11.IPSec 协议中的 AH 与 ESP 协议，不能够实现以下哪个功能（）

• A.完整性
• B.机密性
• C.认证性
• D.不可否认性

12.五级线性反馈移位寄存器需要多个 bit 的连续的明密对得到密钥

• A.5
• B.10
• C.15
• D.20

13.下列那种加密方式使用的 Feistal 密码结构

• A.DES
• B.AES
• C.ECC
• D.Rabin

14.Alice 生成了一条消息并希望确保接收者知道这条消息确实来自她，并且在传输过程中没有被修改。她应该采取以下哪种策略来发送消息和签名（）

• A.使用她的私钥加密消息，然后使用 Bob 的公钥加密签名
• B.使用她的私钥加密消息的哈希值作为签名然，然后使用 Bob 的公加密整个消息和签名
• C.使用她的公钥加密消息的哈希值作为签名，然后使用她的私钥加密整个消息和签名。
• D.使用 Bob 的公加密消息的哈希值作为签名，然后使用 Alice 的私加密整个消息和签名

15.HMAC 算法用于什么目的（）

• A.数据压缩
• B.公钥加密
• C.消息认证和完整性验证
• D.数据备份

填空

1.一棵二叉树后序遍历为 DGEBFCA，中序遍历为DBGEACF，其先序遍历为（）

2.数组在未分配存储空间时叫做（）

3.有 n 个结点的无向图最多能有（）条边

4.若元素以 abcdefg 顺序进栈，且出栈顺序是 bdcfeag，栈的的最小存储空间是（）

5.先序序列为 abcd 不同二叉树的个数是（）

6.用 5bit 来纠错，则可纠错（）位

7.225.124.12.7 是（）类地址

8.140.9.17.39/28 的第一个子网地址是（）

9.甲向乙发起一个 TCP 连接，最大段长 MSS=1KB，RTT=5ms，开的接收缓存为 64KB 则甲从连接建立成功至发送窗口达到 32KB，需经过的时间至少是（）

10.假设一个采用 CSMA/CD 协议的 100Mbps 局域网，最小长度是 128B，则在一个冲突域内两个站点之间的单向传播延时最多是（）

11.二密钥三重 DES 算法中加密函数为 Ek()，解密函数为 Dk()，密为 k1、k2，请写出对明文的加密形式（）

12.在 DES 加解密算法中，属于非线性变换的是（）

13.A 与 B 进行 Difie-Hellman 密钢交换，选择 p=23，g=5，A 选择私钥为 6，B 选择私钥为 15，求解会话密钥 s = （）

14.某哈希函 H(x)输出长度为 m，以生日碰撞为参考。若要大于 50% 获得一次碰撞，输入次数至少为（）

15.Kerckhoff 说过系统的保密性不依赖于对加密体制或算法的保密,而依赖于（）

16.在 RSA 的公钥密码体制中，公钥为 (e，n) = (13,35)，计算得出私钥 d = （）

简答

1.已知有(12，31，26，52，7，4，11，21，44，39，50)，请画出对应的哈夫曼树并给出带权路径长度

2.删除给定顺序表中某一元素，并使得顺序表相对位置不发生改变，要求删除元素的时间复杂度为 O(1)，且使用首尾指针，不额外开辟地址空间，请给出算法（例：[2 4 4 2] 删除4 => [2 2]）

3.简述了1-坚持CSMA 和非坚持CSMA的原理和优缺点

4.简述停止-等待ARQ，回退N ARQ，选择重复ARQ三者特点及其区别

5.RSA 和 Elgamal 谁能抗选择明文攻击，简述原因

计算

1.设一组有序的关键字序列为(13,18.,24,35,47,50,62,83,90)，设散列表为HT[0...12]，散列函数为 H(key)=kev%13。写出拉链法表示方法，并给出查找成功和失败的平均查找长度

2.无向图

• (1) 用邻接矩阵表示
• (2) 用邻接表表示
• (3) 借助队列 Q 进行广度优先遍历，从 1 开始，求在遍历过程中 Q 中元素情况

3.算法填空

float D[n];
int p[n], s[n];
Diikstra (int v, float dist[][]){
    int i, j, k, vl, min, max=10000, pre;
    v1 = v;
    for(i = 0; i < n; i++){ // 各数组进行初始化
        D[i]=dist[v1][i];
        if(________)	p[i]= v1+1;
        else	p[i]=0;
        s[i]=0;
    }
    ________;
    for(i = 0; i < n; i++){
        min=10001;
        for(j = 0; j < n; j++){
            if((!s[i])&&(D[j] < min)){
                min = D[j];
                k = j;
            }
            ________;
        }
        for(j = 0; j < n; j++){
            if((!s[j])&&(________)){
                D[j]=D[k]+dist[k][j]
            }
        }
    }
}

4.已知有校验字x5+x3+x+1，如图

• (1) 请用NRZ-I编码方式填写上图
• (2) 已知 A，B 两种编码方案，请说出 A，B 分别代表什么编码，并给出比特流

5.给定网络拓扑图

• (a) 用 RIP，求 net2 到其他网络路径，并给出 R2 路由表
• (b) 用 OSPF，求 net2 到其他网络路径，并给出 R2 路由表

6.在TCP 拥塞控制中，若客户向服务器发出 TCP 链接，其中客户端初始序号为 100，要发送的数据大小为 500B，每次允许发送的最大报文段为 100B，则

• (1) 画出客户端初始发送窗口状态
• (2) 当客户端发送了 3200B 后，画出当前窗口状态
• (3) 若此时拥塞窗口为 1600B 时发生了拥塞，则此时起再过 5 个 RTT，则客户端的发送序号是多少

7.已知椭圆曲线 E11(1,6)，对于圆曲线上的点 P(2,7)，Q(5,2)

• (a) 求解 P 的逆元
• (b) 求解 P+Q，2P 的结果

8，对于 RSA 算法

• (a) 选择公钥 e = 3，有什么优缺点
• (b) n = 33，e = 7 时，解密密文 C = 8 的明文 M