全部知识点

将关键字序列 20, 3, 11, 18, 9, 14, 7 依次存储到初始为空、长度为 11 的散列表HT 中，散列函数H(key) = (key×3)%11。H(key)计算出的初始散列地址为H0，发生冲突时探查地址序列是H1 , H2 , H3 , …，其中，Hk =(H0 + k2)%11，k = 1, 2, 3, …。

请回答下列问题。

（1）画出所构造的HT，并计算HT 的装填因子。

（2）给出在HT 中查找关键字 14 的关键字比较序列。

（3）在HT 中查找关键字 8，确认查找失败时的散列地址是多少？

假定计算机M 字长为 32 位，按字节编址，采用 32 位定长指令字，指令add、slli 和 lw 的格式、编码和功能说明如题 43 图（a）所示。

其中，R[x]表示通用寄存器x 的内容，M[x]表示地址为x 的存储单元内容，shamt 为移位位数，imm 为补码表示的偏移量。题 43 图（b）给出了计算机M 的部分数据通路及其控制信号（用带箭头虚线表示），其中，A 和B 分别表示从通用寄存器rs1和rs2 中读出的内容；IR[31:20]表示指存器中的高 12 位；控制信号Ext 为 0、1 时扩展器分别实现零扩展、符号扩展，ALUctr 为 000、001、010 时ALU 分别实现加、减、逻辑左移运算。

请回答下列问题。

（1）计算机M 最多有多少个通用寄存器？为什么shamt 字段占 5 位？

（2）执行add 指令时，控制信号ALUBsrc 的取值应是什么？若rs1和rs2 寄存器内容分别是8765 4321H 和 9876 5432H，则add 指令执行后，ALU 输出端F、OF 和CF 的结果分别是什么？若该add 指令处理的是无符号整数，则应根据哪个标志判断是否溢出？

（3）执行slli 指令时，控制信号Ext 的取值可以是 0 也可以是 1，为什么？

（4）执行lw 指令时，控制信号Ext、ALUctr 的取值分别是什么？

（5）若一条指令的机器码是A040A103H，则该指令一定是lw 指令，为什么？若执行该指令时，R[01H]=FFFF A2D0H，则所读取数据的存储地址是什么？

对于题 43 中的计算机M，C 语言程序P 包含的语句“sum+=a[i];”在M 中对应的指令序列S 如下。

slli r4, r2, 2  //R[r4]←R[r2]<<2
add r4, r3, r4  //R[r4]←R[r3]+R[r4]
lw r5, 0(r4)    //R[r5]←M[R[r4]+0]
add r1, r1, r5  //R[r1]←R[r1]+R[r5]

已知变量i、sum 和数组a 都为int 型，通用寄存器r1~r5 的编号为 01H～05H。请回答下列问题。

（1）根据指令序列S 中每条指令的功能，写出存放数组a 的首地址、变量i 和sum 的通用寄存器编号。

（2）已知M 为小端方式计算机，采用页式存储管理方式，页大小为 4KB。若执行到指令序列S中第 1 条指令时，i = 5且r1和r3 的内容分别为 0000 1332H 和 0013DFF0H，从地址 0013DFF0H 开始的存储单元内容如题 44 图所示，则执行“sum+=a[i];”语句后，a[i]的地址、a[i]和sum 的机器数分别是什么（用十六进制表示）？a[i]所在页的页号是多少？此次执行中，数组a至少存放在几页中？

（3）指令“slli r4, r2, 2”的机器码是什么（用十六进制表示）？若数组a 改为short 类型，则指令序列S 中slli 指令的汇编形式应是什么？

某计算机按字节编址，采用页式虚拟存储管理方式，虚拟地址和物理地址的长度均为 32位，页表项的大小为 4 字节，页大小为 4MB，虚拟地址结构如下。

进程P 的页表起始虚拟地址为B8C0 0000H，被装载到从物理地址 6540 0000H 开始的连续主存空间中。

请回答下列问题，要求答案用十六进制表示。

（1）若CPU 在执行进程P 的过程中，访问虚拟地址 1234 5678H 时发生了缺页异常，经过缺页异常处理和MMU 地址转换后得到的物理地址是BAB4 5678H，在此次缺页异常处理过程中，需要为所缺页分配页框并更新相应的页表项，则该页表项的虚拟地址和物理地址分别是什么？该页表项中的页框号更新后的值是什么？

（2）进程P 的页表所在页的页号是什么？该页对应的页表项的虚拟地址是什么？该页表项中的页框号是什么？

计算机系统中的进程之间往往需要相互协作以完成一个任务。在某网络系统中，缓冲区B 用于存放一个数据分组，对B 的操作有C1、C2和C3。C1 将一个数据分组写入B 中，C2从B 中读出一个数据分组，C3对B 中的数据分组进行修改。要求B 为空时才能执行C1，B 非空时才能执行C2和C3。

（1）假设进程P1和P2 均需要执行C1，实现C1 的代码是否为临界区？为什么？

（2）假设B 初始为空，进程P1执行C1 一次，进程P2执行C2 一次。请定义尽可能少的信号量，并用wait()、signal()操作描述进程P1和P2 之间的同步或互斥关系，说明所用信号量的作用及其初值。

（3）假设B 初始不为空，进程P1和P2 各执行C3 一次。请定义尽可能少的信号量，并用wait()、signal()操作描述进程P1和P2 之间的同步或互斥关系，说明所用信号量的作用及其初值。

网络空间是继陆海空天之后的“第五疆域”，网络技术是网络疆域建设与治理的基础。路由算法与协议是网络核心技术之一，对其准确认知、合理选择与应用，对于网络建设十分重要。假设现有互联网中的 4 个自治系统如题 47 图所示。其中，AS1 运行内部网关协议RIP；AS3 规模较小，自治系统内任意两个主机间通信，经过路由器数量不超过 15 个；AS4 规模较大，自治系统内任意两个主机间通信，经过路由器数量可能超过 20 个。

请回答下列问题。

（1）若仅有RIP 和OSPF 内部网关协议供选择，则AS4 应该选择哪个协议？

（2）若 AS3 中的某主机向本自治系统内另一主机发送 1 个 IP 分组，为确保该 IP 分组能够被正常接收，则该IP 分组的初始TTL 值应该至少设置为多少？

（3）假设AS1 中的路由器同一时刻启动，启动后立即构建并交换初始距离向量，之后，每隔 30s交换一次最新的距离向量。则从交换初始距离向量时刻算起，R11~R16 路由器均获到达网络210.2.4.0/24 的正确路由，至少需多长时间？

（4）R44向R13 通告到达网络 136.5.16.0/20 路由时，由BGP 协议哪类会话完成？通过哪个BGP报文通告？R13 通过BGP 协议的哪类会话将该网络可达性信息通告给R14和R15？

（5）若 R14 和 R15 均收到分别由 R11、R12、R13 通告的到达网络 136.5.16.0/20 的可达性信息为：

则在无策略约束情况下，R14和R15 更新路由表后，各自路由表中到达网络 136.5.16.0/20 路由的下一跳分别是什么（用路由器名称表示）？

编写代码，在屏幕上输出“你好，世界！”。

编写代码，获得用户输入的一个合法算式并输出结果。

编写代码，获得用户输入的一段文字并垂直输出。

编写代码，获得用户输入的一个整数，计算其平方和立方并输出结果（用空格分隔）。

编写代码，获得用户输入的一个两位自然数，输出其十位和个位上的数字。

编写代码，获得用户输入的一个字符串，将其以逗号分隔输出。

编写代码，获得用户输入的一个数字（1~12），输出对应月份的英文名称字符串。

编写代码，获得用户输入的一个复数，计算、输出其共轭复数，并提取其实部和虚部。

编写代码，获得用户输入的一个十进制数，分别输出其二进制、八进制、十六进制形式的字符串。

 编写代码，输出 1～100 的所有素数。

编写代码获得用户输入的一个三角形的 3 条边长，计算三角形周长。