题目

一、单项选择题

1. 下列程序结束时，x 的取值为(   )

x=91: y=100;
while(y>0){
    if(x>100){
        x=x-10; y--;
    }
    else x++;
}

A 90        B 91        C 92         D  100

2. 在双向循坏链表的指针p所指的结点之前插入指针s所指的结点的操作是(  )

A s->prior =p->prior; p->prior =s; s->next =p; p->prior->next =s;

B s->next =p; p->prior->next =s; p->prior =s; s->prior =p->prior;

C s->prior =p; s->next =p->next; p->next->prior =s; p->next->prior =s;

D p->prior->next =s; s->prior =p->prior; s->next =p; p->prior =s;

3. 若已知一个栈的入栈序列是 1, 2, 3,…, n, 其输出序列为p1,p2,p3,…,p n

若 p1=m(1<=m<n),p2=n 则 pi(2<i<=n)为(   )。

A  若 i<=n-m, 则为 n-i+1; 若 i>n-m, 则为 n-i

B  若 i<=n-m, 则为 n-i+2; 若i>n-m, 则为 n-i+1

C  若 i<=n-m+1,则为 n-i+2; 若 i>n-m+1, 则为 n-i+1

D  若 i<=n-m+1,则为 n-i+1; 若 i>n-m+1, 则为 n-i

4. 设将三对角矩阵A[n][n]按行优先存储在数组B[3*n-2]之中， 按列优先存储在 C[3*n-2]中，元素 B[i]在原三对角矩阵里对应元素 C[j]，所有数组标号均从0

开始, i 和 j 的关系表达式为(   )。

Aj=2i-3(i+1)/3  Bj=2i-3(i+2)/3  Cj=3i-3(i+1)/3 Dj=2i-2(i+1)/3

5. 4个结点最多构造成(   )种不同的树

A 12    B 13     C 14    2 0D 15

6. 因特网的前身是(   )。

A X.25NET         B ARPANET          C MILNET:         D CERNET

7. 下列 IP地址属于 B类地址的是(  ).

A 64516         B 130.53.42.10            C 200.245.20.11             D 221.121.16.12

8.在局域网中，交换机根据( )转发帧

A 目的网络地址          B 源网络地址         C 原 MAC 地址          D目的 MAC 地址

9. 测试计算机网络时发送的ping包属于(   )协议

A IP          B ARP         C RARP        D ICMP

10，FTP 协议中控制连接端口和连接方式为(   )。

A TCP 21           B TCP 20          C UDP 21          D UDP 20

11. AES 加密算法的密钥长度不可能是(   )。

A.64   位

B.128  位

C.192  位

D.256  位

12. 设n=4, f(al,a2, a3, a4)=  al ④ a4 ⊕ a2a3, 初始状态为 (al,a2,a3,a4) =(1,1,0,1), 此反馈移位寄存器的周期为 (   )。

A.4

B.5

C.6

D.7

13. RFC 1321 中以下关于MD5 的说法正确的有 (   )。

A. MD5 是一个消息摘要算法标准、

B. MD5 的输入可以为任意长，但其输出是 128位

C. MD5 的输入不能为任意长，但其输出是128位ˣ

D.当 MD5 的输入长度为 448bit时, 消息无需填充

14.关于椭圆曲线加密算法(ECC)的说法不正确的是 (   )。
A.椭圆曲线加密算法是基于椭圆曲线上的离散对数困难问题
B.椭圆曲线加密算法属于非对称算法
c.椭圆曲线加密算法在实现方式上有不同的变化
D.对于椭圆曲线方程y³=x³+ax+b，需要满足4a³+27b²=0
15.关于数字签名下列说法不正确的是 (   )。

A.非对称密码体制的出现解决了数字签名问题

B.数字签名可由对称密码、公钥密码以及数字签名算法实现

C.使用对称密码体制进行数字签名时，如果存在第三方， 会产生抵赖问题

D.数字签名算法都基于数字田困难问题

二、填空题

1.算法的每条指令都应在有限的时间内完成这被称为算法的           。

2.己知循环队列中的头指针 front 和尾指针 rear，队列长度为M则当前队列中元素个数为           。

3.模式串 abaacabacabac的 next 数组为           。

4.在长度为11的顺序存储线性表中，采用折半查找法的平均查找长度为           。

5.幼态规划算法具有           性质和          性质。

6.计算机的通信模式有           、           、           。  

7，收发双端传输距离为 1000km，信号在媒体上的传播速率为 2×10⁸m/s。       试计算数据长度为10%数据发送速率为100kb/s的情况下的发送时延为           s, 传输时延为          s。

8.对于带宽为6kHz的信道，假设离散电平为4，信噪比为30dB，则信道极限传输速率为         。(log4Ω1001≈10)

9.用比特填充法对比特序列 111110111111110111 组帧后结果为           。 

10.HDLC 帧分为            、         和          三种。

11.在 j=8的 CFB模式中，如果密文在传输过程中有 1bit的错误，该错误会影响除该组的          组结果。

12.设在 RSA的公钥密码体制中,公钥为(e,n)=(7,55),则私钥 d=           。

13.消息认证函数与哈希函数的区别是 。

14.属于分组密码的古典密码是           。

15.己知 P=23 的椭圆曲线密码体制, 对其椭圆曲线上的两点 p=(5,19),Q=(9,7)求运算P+Q=           。

三、简答题

1.请述 KMP 算法的运算过程

2.分别简述0-1 背包问题和背包问题的概念和解决方法

3.请简述TCP协议如何实现可告传输。

4.请简述RIP、OSPF 的相同点与不同点。

5.请简述Elgamal 签名体制?

四、计算题

1.假设用于通信的电文由一下几种不同的符号组成， 各个符号在电文中出现的频率如下所示 A:8, B:11, C:31, D:32, E:14, F:37, G:62, H:5, I:20, 请画出这个符号的哈夫曼树(要求左孩子比右孩子小)，并给出响应的编码(5分)

2.设散列表长度为15,散列函数为H(k)=k%13,给定的关键字序列为 19,14,23, 01, 68, 20, 84, 27, 55, 11, 10, 79。

试画出分别用拉链法和线性探查法解决冲突时所构造的散列表， 并分别求出在等概率情况下， 两种方法的查找成功和查找不成功的平均查找长度。(5分)

3.有向网络 G 如图所示,试从V1开始用 dijkstra算法补充下表(5分)

4.如图稀疏矩阵， 画出下图转换成按行优先存取的三元组表， 并完成下列三元组表转置代码填空(5分)

5.在一个 AOE 网络中包括7个事件和 10 个活动, 其中<V1,v2>=3, <v1,v3>=2,<v2,v4>=4, <v3,v4>=3, <v2, v5>=8, <v3, v6>=7,<v4, v5>=4, <v4, v6>=2,<v5, v7>=9,<v6,v7>=6。  

若Ve(i)代表事件i 开始的最早时间，Vi(i)代表事件 i 开始的最晚时间,    代表活动<vi，vj>开始的最早时间，  代表活动<vi, vj>开始的最晚时间，求出所有事件和活动的最早最晚发生时间和关键路径。(5分)

6.校验生成多项式   接受的报文 1010110001101 是否正确, 给出校验过程，若不正确，设报文数据部分正确，那正确的校验码应该是多少? (5分)

7.某网络如图所示，现将网络地址空间 140.24.7.0/24 按子网号从小到大的顺序分别分配给组织机构1，2，3，4. 其中每个组织机构的主机数相等， R1 路由器的 m0,m1,m2 接口 ip地址均为该局域网的第一个可用 ip 地址, m3 接口的 ip 地址为 222.118.2.3。 R2 路由器 m0, ml,m2 接口的 ip 地址分别为 222.118.2.2,222.118.2.1,130.11.120.1。R3路由器的ml,m2接口 ip 地址为222.118.3.1,222.118.3.3, m0 为该对应局域网的第一个可用 ip。 域名服务器为 222.118.3.2。

(1)分别写出组织机构1, 2, 3, 4的 ip 地址。 (2分)

(2)请完成下列路由表(8分)

R1 路由表

R2 路由表

R3 路由表

8.如下图所示某主机进行web请求的一个以太网数据帧前 80 个字节的十六进制及 ASCII 码内容

0000         00 21 27 21 51 ee 00 15             c5 c1 5 e 28 08 00 45 00

0010         01 ef 1 1 3b 40 40 80 06           ba 9d 0a 02 80 64 40 aa

0020          62 20 04 ff 00 50 e0 e2             00 fa 7b f9 f8 05 50 18

0030          fa f0 la c400 00 47 45              54 20 2f 72 66 63 2e 68

0040          74 6d 6c 20 48 54 54 50              2f 31 2e 31 0d 0a 41 63

帧结构如下图所示：

(1)求主机的源 MAC 地址和源 IP 地址(3分)

(2)求该报文段 IP 数据报总长度为多少?位偏移量是多少?  (3分)

(3)结合该数据报文分析该主机请求通信中可能使用了哪些协议， 并简述这些协议功能?  (4分)

　　　　　　　　　　　　　　　　　　　　　　　　　　　      6B                　　　　　　　　  6B                　　　　　　　　2B         　　　　　　46-1500B           　　　　　　4B

一、选择题

1 - 10：BDCAC BBDDA

11. A

12. B

13. B

14. D

15. C

二、填空题

1. 有穷性

2. (rear-front+M)%M

3. 01122123412234

4. 3

5. 最优子结构性质和子问题重叠性质

6. 单工、 半双工、 全双工

7. 100s、 5×10-3

8. 24000bit/s

9. 11111001111101110111

10.信息帧、 监督帧和无编号帧

11.8

12.23

13. 有无密钥

14. 维吉尼亚密码

15. (18, 20)

三、计算题

1.

A:01011        B:0100 C:011 D:110 E:1110 F:00  G:10  H:01010   I:1111

2.

线性探查法：查找成功：2.5　　查找不成功： 7

拉链法：查找成功: 1.67　　查找不成功: 0.923

3.参照书本 

4.参照书本

5.

活动和事件开始最早时间， 最晚时间， 要求全部写出。关键路径<V1,V2>, <V2,V4>, <V2,V5>, <V4,V5>, <V5,V7>

6.

校验过程略, 不正确, 正确的为 01100

7.

(3) 分别写出组织机构1, 2, 3, 4的ip地址。

组织机构 1 140.24.7.0/26

组织机构2 140.24.7.64/26

组织机构 3 140.24.7.128/26

组织机构 4 140.24.7.192/26

(4)请完成下列路由表(8)

R 1 路由表

R2 路由表

R3 路由表

8.

(4) 求主机的源MAC 地址和源 IP 地址

00-15-C5-C1-5E-28, 10.2.128.100

(5) 求该报文段IP数据报总长度为多少? 位偏移量是多少?

01ef=495B      64*8=512B

(6)结合该数据报文分析该主机请求通信中可能使用了哪些协议， 并简述这些协

议功能?

RIP, IP, TCP, HTTP, (PPP 或HDLC), ARP, NAT(注意该IP 地址为私有地址, 其它协议表述合理即可)

9.