你可能感兴趣的试题

设线性表 L=(a1，a2，a…，an-2，a-1，a。)采用带头结点的单链表保存，链表中结点定义如下：
typedef struct node {
int data；
struct node* next；
} NODE；
请设计一个空间复杂度为 O(1)且时间上尽可能高效的算法，重新排列 L 中的各结点，得到线性表 L'=(a₁，a_n，a₂，a_n-1，a₃，a_n-2…)。
要求：

给出算法的基本设计思想。

请设计一个队列，要求满足：①初始时队列为空；②入队时，允许增加队列占用空间；③出队后， 出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；④人队操作和出队操作的时间 复杂度始终保持为 O(1)。请回答下列问题：

该队列应该选择链式存储结构，还是顺序存储结构？

设线性表 L=(a1，a2，a…，an-2，a-1，a。)采用带头结点的单链表保存，链表中结点定义如下：
typedef struct node {
int data；
struct node* next；
} NODE；
请设计一个空间复杂度为 O(1)且时间上尽可能高效的算法，重新排列 L 中的各结点，得到线性表 L'=(a₁，a_n，a₂，a_n-1，a₃，a_n-2…)。
要求：

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

请设计一个队列，要求满足：①初始时队列为空；②入队时，允许增加队列占用空间；③出队后， 出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；④人队操作和出队操作的时间 复杂度始终保持为 O(1)。请回答下列问题：

画出队列的初始状态，并给出判断队空和队满的条件。

设线性表 L=(a1，a2，a…，an-2，a-1，a。)采用带头结点的单链表保存，链表中结点定义如下：
typedef struct node {
int data；
struct node* next；
} NODE；
请设计一个空间复杂度为 O(1)且时间上尽可能高效的算法，重新排列 L 中的各结点，得到线性表 L'=(a₁，a_n，a₂，a_n-1，a₃，a_n-2…)。
要求：

说明你所设计的算法的时间复杂度。

请设计一个队列，要求满足：①初始时队列为空；②入队时，允许增加队列占用空间；③出队后， 出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；④人队操作和出队操作的时间 复杂度始终保持为 O(1)。请回答下列问题：

画出第一个元素入队后的队列状态。

请设计一个队列，要求满足：①初始时队列为空；②入队时，允许增加队列占用空间；③出队后， 出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；④人队操作和出队操作的时间 复杂度始终保持为 O(1)。请回答下列问题：

给出入队操作和出队操作的基本过程。

有 n(n≥3)位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有 m(m≥1)个碗， 每两位哲学家之间有 1 根筷子。每位哲学家必须取到一个碗和两侧的筷子之后，才能就餐，进餐完毕， 将碗和筷子放回原位，并继续思考。为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信 号量的 P、V 操作(wait()、signal()操作)描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。 

某计算机系统中的磁盘有 300 个柱面，每个柱面有 10 个磁道，每个磁道有 200 个扇区，扇区大小 为 512B。文件系统的每个簇包含 2 个扇区。请回答下列问题：

磁盘的容量是多少？

某计算机系统中的磁盘有 300 个柱面，每个柱面有 10 个磁道，每个磁道有 200 个扇区，扇区大小 为 512B。文件系统的每个簇包含 2 个扇区。请回答下列问题：

假设磁头在 85 号柱面上，此时有 4 个磁盘访问请求，簇号分别为：100260、60005、101660 和 110560。 若采用最短寻道时间优先(SSTF)调度算法，则系统访问簇的先后次序是什么？

某计算机系统中的磁盘有 300 个柱面，每个柱面有 10 个磁道，每个磁道有 200 个扇区，扇区大小 为 512B。文件系统的每个簇包含 2 个扇区。请回答下列问题：

第 100530 簇在磁盘上的物理地址是什么？将簇号转换成磁盘物理地址的过程是由 I/O 系统的什么程 序完成的？

已知 f(n)=n！=n×(n-l)×(n-2)×…×2×1，计算 f(n)的 C 语言函数 fl 的源程序(阴影部分)及其在 32 位计算机 M 上的部分机器级代码如下：

其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令，计算机 M 按字节编址，int 型数据占 32 位。请回答下列问题：

计算 f(10)需要调用函数 f1 多少次？执行哪条指令会递归调用 f1？

对于题 45，若计算机 M 的主存地址为 32 位，采用分页存储管理方式，页大小为 4KB，则第 1 行 push 指令和第 30 行 ret 指令是否在同一页中(说明理由)？若指令 Cache 有 64 行，采用 4 路组相联映射方 式，主存块大小为 64B，则 32 位主存地址中，哪几位表示块内地址？哪儿位表示 Cache 组号？哪几位表 示标记(tag)信息？读取第 16 行 call 指令时，只可能在指令 Cache 的哪一组中命中(说明理由)？

已知 f(n)=n！=n×(n-l)×(n-2)×…×2×1，计算 f(n)的 C 语言函数 fl 的源程序(阴影部分)及其在 32 位计算机 M 上的部分机器级代码如下：

其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令，计算机 M 按字节编址，int 型数据占 32 位。请回答下列问题：

上述代码中，哪条指令是条件转移指令？哪几条指令一定会使程序跳转执行？

某网络拓扑如题图所示，其中R为路由器，主机H1~H4的IP地址配置以及R的各接口IP地址 配置如图中所示。现有若干台以太网交换机(无 VLAN 功能)和路由器两类网络互连设备可供选择。

请回答下列问题：

已知 f(n)=n！=n×(n-l)×(n-2)×…×2×1，计算 f(n)的 C 语言函数 fl 的源程序(阴影部分)及其在 32 位计算机 M 上的部分机器级代码如下：

其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令，计算机 M 按字节编址，int 型数据占 32 位。请回答下列问题：

根据第 16 行 call 指令，第 17 行指令的虚拟地址应是多少？已知第 16 行 call 指令采用相对寻址方式， 该指令中的偏移量应是多少(给出计算过程)？已知第 16 行 call 指令的后 4 字节为偏移量，M 采用大 端还是小端方式？

某网络拓扑如题 47 图所示，其中 R 为路由器，主机 H1~H4 的 IP 地址配置以及 R 的各接口 IP 地址 配置如图中所示。现有若干台以太网交换机(无 VLAN 功能)和路由器两类网络互连设备可供选择。

请回答下列问题：

设备 1、设备 2 和设备 3 中，哪几个设备的接口需要配置 IP 地址？并为对应的接口配置正确的 IP 地 址。

某网络拓扑如题 47 图所示，其中 R 为路由器，主机 H1~H4 的 IP 地址配置以及 R 的各接口 IP 地址 配置如图中所示。现有若干台以太网交换机(无 VLAN 功能)和路由器两类网络互连设备可供选择。

请回答下列问题：

为确保主机 H1~H4 能够访问 Internet，R 需要提供什么服务？

已知 f(n)=n！=n×(n-l)×(n-2)×…×2×1，计算 f(n)的 C 语言函数 fl 的源程序(阴影部分)及其在 32 位计算机 M 上的部分机器级代码如下：

其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令，计算机 M 按字节编址，int 型数据占 32 位。请回答下列问题：

f(13)=6 227 020 800，但 f1(13)的返回值为 1 932 053 504，为什么两者不相等？要使 f1(13)能返回正 确的结果，应如何修改 f1 源程序？

某网络拓扑如题 47 图所示，其中 R 为路由器，主机 H1~H4 的 IP 地址配置以及 R 的各接口 IP 地址 配置如图中所示。现有若干台以太网交换机(无 VLAN 功能)和路由器两类网络互连设备可供选择。

请回答下列问题：

若主机 H3 发送一个目的地址为 192.168.1.127 的 IP 数据报，网络中哪几个主机会接收该数据报？

已知 f(n)=n！=n×(n-l)×(n-2)×…×2×1，计算 f(n)的 C 语言函数 fl 的源程序(阴影部分)及其在 32 位计算机 M 上的部分机器级代码如下：

其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令，计算机 M 按字节编址，int 型数据占 32 位。请回答下列问题：

第 19 行 imul eax,ecx 表示有符号数乘法，乘数为 R[eax]和 R[ecx]，当乘法器输出的高、低 32 位乘积 之间满足什么条件时，溢出标志 OF=1？要使 CPU 在发生溢出时转异常处理，编译器应在 imul 指令 后加一条什么指令？