24%11=2，存储 24 的地址为 2 33%11=0，存储 33 的地址为 0
21%11=10，存储 21 的地址为 10。 整个序列存入后的哈希表的结构为：
地址号
0 1 2 3 4 5 6 7 8 9 10
存储的元素 33 12 24
39 18
21
分析：当存储长度为 9 时，产生了多次地址的冲突，而当长度为 11 时，没有产生冲突， 说明模的选取很重要。，选取不当，可能会产生较多的冲突。
第 4 章作业 参考解答
5．什么是变量？为什么要划分数据类型？不同的数据类型不同在什么地方？ 答案要点（尽量举例说明）： 变量是程序运行时可变值的标识符。一个变量往往归属于某种数据类型且有一个名字 （代表存储器中一个存放其值的区域）。 数据形式各种各样（数字、文字、图、声等），计算机中各有不同的存储和处理方式， 故需划分数据类型。 不同数据类型的存储方式、占用字节数多少以及能够执行的运算各不相同 在 Visual Basic 中执行应用程序期间，用变量临时存储数值。变量具有名字（用来引用变量 所包含的值的词）和数据类型（确定变量能够存储的数据的种类）。 8．什么是过程？什么是函数？引入的好处？ 答案要点（尽量举例说明）： 过程：过程名标识、可完成某种任务的语句或指令序列。 过程：函数名标识、可完成某种任务并得到一个计算结果的语句或指令序列。 好处：实现代码重用；便于复杂问题划分为多个较简模块并分头处理；增强程序通用性。 14．用伪代码描述计算欧拉常数的近似值的算法。其中欧拉常数 e 的计算公式为：
5. 绘出比特流为 011000101111 的基本曼彻斯特编码波形图。 答：
6. 绘出比特流为 011000101111 的差分曼彻斯特编码波形图。 答：
7. 接收端接收到采用奇校验（最后一位为校验位）的两组信息分别为：①101101011； ②101001101，问两组信息的传输是否出错，为什么？
规模在内的所有要求，则该候选解就是问题的一个解；如果发现当前候选解不可能是解时， 就退回一步，重新试探下一个候选解（回溯）；如果当前候选解满足除问题规模要求之外的 所有其他要求，则继续扩大当前候选解的规模并继续试探。
比较：穷举法就是把所有可能的情况一一列举出来。适用于解决效率低，规模小的问题。 回溯法可看作一种改进了的穷举法，能够搜索问题的所有解或任一解，在保持了穷举法的系 统性的同时，放弃对于已判定为不可能解的候选解的延伸试探，从而提高解题的效率。
⑸ 进程是一个独立的运行单位，也是系统进行资源分配和调度的一个独立单位。因此， 进程具有独立性,但有时进程间又具有相互制约性。
8．画出进程的状态图。
参考答案:
9. 常用输入输出方式有哪几种？各适用于什么设备？ 参考答案: ⑴ 程序控制方式：完全由 CPU 控制输入输出，外围设备每发送或接收一个数据都要由 CPU 执行相应的指令来完成；与 CPU 异步工作；适合于少量、低速 I/O 设备（如键盘）的 数据输入输出。 ⑵ 中断方式：当出现来自系统外部、机器内部甚至处理机本身的例外事件，或虽为事 先安排但无法预知何时何地出现的事件时，CPU 暂停现行程序的执行，转去处理这些事件， 处理完毕后再继续执行原来的程序。适用于随机请求服务且必须及时响应的 I/O 设备（如打 印机）的数据输入输出。 ⑶ DMA（直接存储器存取）方式：I/O 设备与内存之间建立直接数据通路，数据传输 由专门的 DMA 控制器来完成而不需要 CPU 干预也不必执行专门的程序。主要用于高速 I/O 设备（如磁盘）的数据输入输出。
5. 已知 RSA 加密系统的公钥为 e=7, N=77，问私钥是什么？用计算机求解的算法思路是 什么？
简答: S1 穷举法选取两个互素的素数：
由 N=p*q=77 得 p=7、q=11 S2 计算 z=(p-1)*(q-1)=6*10=60 S3 穷举法选取 d：
条件：2～z-1 之间、与 z 互素且满足 e*d=1 (mod z)，即(7*d) mod 60=1
请依据汉明距离，解码下列信息： 1）100001 101010 110101 2）110010 110110 100100 3）010111 111011 101001 011110 参考答案:
符号 代码
A 111010
B 110101
1) C 101001
D 100110
E
011100
F
010011
转到 S6 S6 输出 e
17. 利用除留余数法将数列
{12, 39, 18, 24, 33, 21}
分别存放到长度为 9 和长度为 11 的数组中，比较两者的差异并分析原因。 解：用除留余数法构造哈希表，解决冲突的方法使用线性探测再散列。
当存储长度为 9 时，构造哈希表： 12%9=3，存储 12 的地址为 3
39%9=3，冲突，按线性探测再散列获得下一个地址码为(3+1)%9=4,不冲突，存入 18%9=0，存储 18 的地址为 0 24%9=6，存储 24 的地址为 6 33%9=6，冲突，按线性探测再散列获得下一个地址码为(7+1)%9=7,不冲突，存入 21%9=3，冲突，按线性探测再散列获得下一个地址码为(3+1)%9=4,冲突，再次获得的地
址码为(3+2)%9=5，不冲突，存入。 整个序列存入后的哈希表的结构为：
地址号
0
1
2
3
4
5
6
7
8
存储的元素 18
12 39 21 24 33
当存储长度为 1 时，构造哈希表： 12%11=1，存储 12 的地址为 1
39%11=6，存储 39 的地址为 6 18%11=7，存储 18 的地址为 7
答： ① 101101011 偶数个零，错 ② 101001101 奇数个零，对 8．传输字符串“school”，采用垂直水平奇偶校验编码，请写出编码的矩阵。字符使 用 ASCII 编码，school 的 ASCII 的十六进制分别为：73H 63H 68H 6FH 6FH 6CH，8 位 编码的最高位作为校验位，垂直和水平均采用偶校验。 答： 01110011 1 01100011 0 01101000 1
3
4
4
1
F
010011
1
2
4
3
所传输的字符
F
A
C
E
3. 用 Caesar 密码加密法加密 best wishes，密文是什么？ 答:
ehvw zlvkhv
4. 用 RSA 公钥加密技术对 11 进行加密，其中，公钥 e=5, n=91。
答:
密文 C= Pe Mod n = 115 mod 91 = 161051 mod 91 = 72
所传输的字符
代码 111010 110101 101001 100110 011100 010011
Hamming 距离
100001 101010 110101
4
1
4
2
5
0
1
2
3
3
2
3
5
4
3
3
4
3
C
A
B
符号
代码
Hamming 距离 110010 110110 100100
A 111010
1
2
4
B 110101
01101111 0 01101111 0 01101100 0 00010100 0 9. 已知信息位串 11000101，生成多项式为 x4+x+1，计算 CRC 编码的位串。 答： 信息位串 11000101， G(x)= x4+x+1 → 10011 → k=4 11000101 0000 模 2 除 10011 得 校验码 110 编码后的报文：11000101 0110 10. 接收端接收到以 x4+x+1 为生成多项式的 CRC 编码序列 11011110111110，请检查信 息接收是否有错。 答： 不能被生成多项式整除，故有错。
穷举： 故私钥：（7，43）
求得 d=43
6. 数字签名系统需要满足哪三项条件？ 参考答案: 签名者事后不能否认自己的签名； 接收者能够验证签名，而任何其他人都不能伪造签名； 当事双方发生签名真伪争执时，可在公正的仲裁者面前通过验证签名来确认其真伪。
7. 进程和程序有什么区别？ 参考答案: ⑴ 进程是程序的一次执行，属于动态概念，而程序是一组有序的指令，是一种静态概 念。但进程离开了程序也就失去了存在的意义。 ⑵ 一个进程可以执行一个或几个程序。反之，同一程序可能由几个进程同时执行。 ⑶ 程序可作为软件资源长期保留，而进程是程序的一次执行过程，是暂时的。进程具 有生命期。 ⑷ 进程具有并发性，能与其它进程并发运行。而程序不具备这种特征。
输出 Class
第5章
1. 下图是不归零制编码的波形图，正电压表示 1，负电压表示 0，请写出它代表的二 进制序列。
答：10110001 2. 下图是曼彻斯特编码的波形图，请写出它代表的二进制序列。
答：11010101 3. 下图是曼彻斯特编码的波形图，请写出它代表的二进制序列。
答：1011111 4. 绘出比特流为 1101 0100 的不归零制编码的波形图。 答：
21. 伪代码写出寻找数组中最大值的算法。
循环：输入十个数，挑最大数并输出：
第五次作业：
第4章
18．枚举法和回溯法有何异同？ 答案要点： 枚举法、回溯法：都是解题时逐步搜索问题的解的策略。 枚举法：逐个枚举和检验问题的所有候选解，从而找出问题的解。 回溯法：按某种顺序逐个枚举和检验问题的所有候选解。如果当前候选解满足包括问题
3
2
2
2) C 101001
4
5
3
D 100110
2