科目组合

数据结构 、计算机组成原理 、操作系统 、计算机网络

已知带头结点的非空单链表L的头指针为 h，指针 p 指向L中间的一个链表结点（不是第一个和最后一个结点）。q=p->next, p->next=q->next, q->next=h->next, h->next=q。这段代码的功能是（）。

A、把q指向的结点插入到p的后面

B、把p指向的结点插入到q的后面

C、把p指向的结点插入到h的后面

D、把q指向的结点插入到h的后面

表达式 x+y*(z-u)/v 的等价后缀是（  ）

A.xyzu-*v/+

B.xyzu-v/*+

C.+x/*y-zuv

D.+x*y/-zuv

p、q、v 都是二叉树 T 中的结点，二叉树 T 的中序遍历为…, p, v, q, …，其中v有两个孩子结点，则下列说法正确的是（ ）。

A.p 没右孩子，q 没左孩子

B.p 没右孩子，q 有左孩子

C.p 有右孩子，q 没左孩子

D.p 有右孩子，q 有左孩子

给定无向图的邻接多重表，求顶点b、d的度（）

A.2, 4    B.4, 2    C.3, 2    D.2, 3

下列数据结构中，不适合直接使用折半查找的是（）

I 有序链表

II 无序数组

III 有序静态链表

IV 无序静态链表

A.仅1、II

B.仅II、IV

C.仅、II、 IV

D.I、II、III、IV

KMP算法使用修正后的 next 数组进行模式匹配，模式串 S = "aabaab"，当主串中某字符与 S 中某字符失去配对时，S 将向右滑动的最长距离是（  ）

A.5    B.4    C.3    D.2

一棵二叉搜索树如下图所示，K1、K2、K3 分别是对应结点中保存的关键字、三角形表示子树。则子树T 中任一结点中保存的关键字 X 满足的是（ ）。

A. X<K1

B. X>K2

C. K1<X<K3

D. K3<X<K2

使用快速排序算法对含 N(N>=3) 个元素的数组 M 进行排序，若第一趟排序将除枢轴外的N-1个元素划分为 P 和 Q 两个部分，则下列叙述中，正确的是（ ）。

A. P 和 Q 块间有序

B. P 和 Q 均块内有序

C. P 和 Q 的元素个数大致相等

D. P 和 Q 中均不存在相等的元素

已知关键字序列 28, 22, 20, 19, 8, 12, 15, 5是大根堆（最大堆），对该堆进行两次删除操作后，得到的新堆是（ ）。

A. 20, 19, 15, 12, 8, 5

B. 20, 19, 15, 5, 8, 12

C. 20, 19, 12, 15, 8, 5

D. 20, 19, 8, 12, 15, 5

初始有三个升序序列(3, 5)、(7, 9)、(6)，若按从左至右的次序选择有序序列进行二路归并排序，则关键字之间的总比较次数是（）。

A. 3    B. 4    C. 5    D. 6

在外排序中，利用败者树对初始为升序的归并段进行多路归并，败者树中记录"冠军"的结点保存的是（ ）

A、最大关键字

B、最小关键字

C、最大关键字所在的归并段号

D、最小关键字所在的归并段号
 

C 语言代码如下：

int i = 32777;

short si =i;

int j=si;

执行上述代码段后， j 的值为（ ）。

A. -32777    B. -32759    C. 32759    D. 32777

将汇编语言程序中实现特定功能的指令序列定义成一条伪指令。下列选项中，CPU能理解并直接执行的是

 Ⅰ 伪指令 Ⅱ 微指令 Ⅲ 机器指令 Ⅳ汇编指令

A. 仅Ⅰ和Ⅳ    B. 仅Ⅱ和Ⅲ    C. 仅Ⅲ和Ⅳ    D. 仅Ⅰ、Ⅲ和Ⅳ

某科学实验中，需要使用大量的整型参数，为了在保证表数精度的基础上提高运算速度，需要选择合理的数据表示方法。若整型参数a和β的取值范围分别为-2^20~2^20、-2^40~2^40，则下列选项中，a和B最适宜采用的数据表示方法分别是(  ）

A. 32 位整数、32 位整数

B. 单精度浮点数、单精度浮点数

C. 32 位整数、双精度浮点数

D. 单精度浮点数、双精度浮点数

下列关于整数乘法运算的叙述中，错误的是（ ）。

A. 用阵列乘法器实现乘运算可以在一个时钟周期完成

B. 用 ALU 和移位器实现的乘运算无法在一个时钟周期内完成

C. 变量与常数的乘运算可编译优化为若干条移位及加/减运算指令

D. 两个变量的乘运算无法编译为移位及加法等指令的循环实现

对于页式虚拟存储管理系统，下列关于存储器层次结构的叙述中，错误的是（）

A. Cache-主存层次的交换单位为主存块，主存-外存层次的交换单位为页

B. Cache-主存层次替换算法由硬件实现，主存-外存层次由软件实现

C. Cache-主存层次可采用回写法写策略，主存-外存层次通常采用回写法

D. Cache-主存层次可采用直接映射，主存-外存层次通常采用直接映射

某计算机按字节编址，采用页式虚拟存储管理方式，虚拟地址为32位，主存地址为30位，页大小为1 KB。若TLB共有32个表项，采用4路组相联映射方式，则TLB表项中标记字段的位数至少是（）

A.17    B.18    C.19    D.20
 

下列事件中，不是在MMU地址转换过程检测的是（）

A.访问越权

B.Cache缺失

C.页面缺失

D.TLB缺失
 

5 段流水线 RISC 说法错误的是（ ）。

A. 待更新

B. 待更新

C. 所有数据冒险都可以通过加入转发（旁路）电路解决

D.所有数据和关都可以通过添加nop指令以及调整指令顺序来解决

存储器总线的时钟频率为 420MHz，总线宽度为 64 位，每个时钟周期传送2 次数据，支持突发传输，最多传 8 次，第一个时钟传地址和读写命令，从第 4~7 个始终连续传8 次。总线带宽最大传输速率为（ ）。

A. 3.84GB/s    B. 6.72GB/s    C. 30.72 GB/s    D. 53.76GB/s

关于中断 I/O 方式，错误的是（ ）。

A. 中断屏蔽字决定中断响应顺序

B. 待更新

C. 保存通用寄存器和设置新中断屏蔽字由软件实现

D. 单重中断方式下，中断处理时 CPU 处于关中断状态

DMA 方式中，DMA 控制器控制的数据传输通路位于（ ）。

A. 待更新

B. 待更新

C. 设备接口和主存之间

D. 设备接口和 DMA 控制器之间

下面关于中断和异常的说法中，错误的是（ ）。

A. 中断或异常发生时，CPU 处于内核态

B. 待更新

C. 待更新

D.中断处理服务程序发生时，CPU处于内核态

终止进程时，不一定执行的是（ ）。

A.终止子进程

B.回收分配的内存资源

C.撤销进程Pcb

D.回收进程占用的设备
 

在支持页式存储管理的系统中，进程切换时 OS 要执行（ ）。

Ⅰ. 更新 PC(程序计数器) 值

Ⅱ. 更新栈基址寄存器值（ebp）

Ⅲ. 更新页表基址寄存器值

A. 仅Ⅲ

B. 仅Ⅰ、Ⅱ

C. 仅Ⅰ、Ⅲ

D. Ⅰ、Ⅱ、Ⅲ

文件系统需要额外的外存空间记录空闲块的位置，占用外存空间大小与当前空闲块数量无关的是(）。

A.位示图    B.空闲表    C.成组链接    D.空闲链表
 

回收分区时，仅合并大小相等的空闲分区的算法是（ ）。

A. 伙伴算法    B. 最佳适应算法    C. 最坏适应算法    D. 首次适应算法

若进程 P 中有一个线程 T，打开文件后获得 fd，再创建线程 Ta、Tb，则线程Ta、Tb 可共享的资源是（ ）。

Ⅰ. 进程 P 的地址空间    Ⅱ.线程 T 的栈    Ⅲ. fd

A. 仅Ⅰ

B. 仅Ⅰ、Ⅲ

C. 仅Ⅱ、Ⅲ

D.Ⅰ、Ⅱ、Ⅲ

以下系统调用中，包含文件按名查找功能的系统调用是（ ）。

A. open()    B. read()    C. write()    D. close()

RR（时间片轮转调度算法）调度，时间片为 5ms，有 10 个进程，初始状态均处于就绪队列，执行结束前仅处于执行态或就绪态，队尾进程 P 所需 CPU 时间最短，为 25ms，不考虑系统开销，则 P 的周转时间为（ ）。

A. 200ms

B. 205ms

C. 250ms

D. 295ms

键盘中断服务例程执行结束时，所输入的数据存放位置是() 。

A.用户缓冲区

B.CPU的通用寄存器

C.内核缓中区

D.键盘控制器的数据缓冲区

磁道数400（号为0~399），用循环扫描算法(CSCAN）进行调度。完成对200号磁道的请求后，磁头向磁道号减小的方向移动，若还有7个请求，磁道号分别为300,120,110,0,160,210,399，则完成上述请求后磁头移动的距离是（）

A. 599    B. 619    C. 788    D. 799

若分组交换网络及每段链路的带宽如下图，则 H1 到 H2 的最大吞吐量约为（）。

A. 1Mbps    B. 10Mbps    C. 100Mbps    D. 1000Mbps

在下列二进制数字调制方法中，需要 2 个不同频率载波的是（）。

A. ASP    B. PSK    C. FSK    D. DPSK

如下图的支持VLAN划分的交换机，已按端口划分了3个VLAN。部分端口连接主机的IP和MAC地址如图示，ARP表结构为<IP地址，MAC地址，TTL>。下列选项中，不会出现在ARP表中的是( )

A、IP2 168.3.81, 00-18A2-3B-36-21, 14:32:00

B、IP2.168.3.91, 00-3E-C2-39-12-B5, 14:37:00

C、IP2.168.3.125, 00-E5-78-4A-09-B2，14:35:00

D、IP2.168.3.129, 00-08-6E-05-A7-82, 14:52:00
 

在采用CSMA/CA 的 802.11无线局域网中，DIFS=128us，SIFS=28us，RTS、CTS和ACK帧的传输时延分别是3us，2us 和 2us，忽略信号传播时延，若主机A欲向AP发送一个总长度为1998B的数据帧，无线链路带宽为54Mbps，则隐藏站B到AP发送的CTS帧时，没置的网络分配向量NAV的值是（）

A.326us    B.354us    C.385us    D.513us

主机甲通过选择重传（SR）滑动窗口协议向主机乙发送帧的部分过程如下图所示。F为数据帧，ACKx为确认帧，x是位数为比特的序号。乙只对正确接收的数据帧进行独立确认。发送窗口与接收窗口大小相同且均为最大值。甲在t1时刻和t2时刻发送的数据帧分别是(  )

A. F1、F3      B. F1、F4      C. F3、F1      D. F4、F1

假设主机H通过TCP向服务器发送长度为3000B的报文，往返时间RTT=10ms，最长报文段寿命MSL=30s，最大报文段长度MSS=1000B,忽略TCP段的传输时廷，报文传输结束后H首先请求断开连接，则从H请求建立TCP连接时刻起,到H进入CLOSED状态为止，所需时间至少是（  ）

A.30.03s

R.30.04s

C.60.03s

D.60.04s
 

若UDP协议在计算校验和过程中，计算机得到中间结果为1011 1001 1011 0110时，还需要加上最后一个16位数0110 0101 1100 0101，则最终计算得到的校验和是（）

A. 0001 1111 0111 1011

B. 0001 1111 0111 1100

C. 1110 0000 1000 0011

D. 1110 0000 1000 0100
 

若浏览器不支持并行TCP连接，使用非持久的HTTP/1.0协议请求浏览1个web页，该页中引用同一个网站上7个小图像文件，则从浏览器传输web页请求建立TCP连接开始，到接收完所有内容为止，所需要的往返时间RTT数至少是（）

A. 4

B. 9

C. 14

D. 16

2023年10月26日，神州十七号载人飞船发射取得圆满成功，再次彰显了中国航天事业的辉煌成就。载人航天工程是包含众多子工程的复杂系统工程，为了保证工程的有序开展，需要明确各子工程的前导工程。以协调各子工程的实施。该问题可以简化、抽象为有向图的拓扑序列问题。已如有向图G采用邻接矩阵存储，类型定义如下：

typedef struct //图的类型定义
{
    int numVertices, numEdges; //图的顶点数和有向边数
    char verticesList[MAXV]; //项点表，MAXV为以定义常量
    int Edge[MAXV][MAXV]; //知接矩阵
}MGraph;

请设计算法：int uniquely(MGraph G)。判定G是否存在唯一的拓扑序列，若是则返回1，否则返回0。
要求:
（1）给出算法的基本设计思想（4分）

（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释（9分）

将关键字序列20，3，11，18，9，14，7，依次存储到初始值为空，长度为11的散列表中，散列函数H(key) = ( key * 3) %11，H (key〉计算机出的初始散列地址为H0，发生冲突时探查地址序列是H1，H2，H3，....，其中，Hk = (H0+k^2)%11，K=1，2，3....，请回答下列问题。
（1）画出所构造的HT。并计算HT的域装因子(6分)

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

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

假定计算机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分）

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

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

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

（5）若一条指令的机器码是A040 A103H，则该指令一定是lw指令，为什么？(2分）

（6）若执行该指令时，R[01H]=FFFF A2D0H，则所读取数据的存储地址是多少?(2分）

对于题43中的计算机M，C语言程序Р包含的语句"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的通用寄存器编号(3分)

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

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

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

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

请回答下列，用十六进制表示：

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

（2）进程Р的页表所在页的页号是什么？该页对应的页表项的虚拟地址是什么？该页表项中的页框号是多少？(4分)

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

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

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

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

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

请回答下列问题：

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

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

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

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

（5）若R14和R15均收到分别由R11、R12、R13通告的到达网络136.5.16.0/20的可达性信息为：
目的网络：136.5.16.0/20，AS路径：AS2 AS8 AS19，下一跳：R11
目的网络：136.5.16.0/20，AS路轻：AS3 AS7 AS11 AS19，下一跳：R12
目的网络：136,5.16.0/20，AS路径：AS4 AS10 AS19，下一跳：R13
则在无策略约束情况下，R14和R15更新路由表后，各自路由表中到达网络136.5.16.0/20路由的下一跳分别是什么(用路由器名称表示)?(2分)