中久数创——笔试题

一、计算机系统基础（不定项选择）

1.1 下列关于存储容量大小换算正确的是( )

A. 1KB-1024MB **B.**1GB-1024KB **C.**1TB-1024GB **D.**1TB-1024MB

答案：C

解析：这个没啥说头，初中生都了解

1.2 若某文件权限是-rwxr–rw-,下面描述正确的是（ ）

A. 文件的权限值是 746 **B.**其他用户对文件只有读权限 **C.**文件的权限值是755 **D.**文件的所有者对文件只有读权限

答案：A B

解析：

1. 文件类型：第 1 位为 -，表示是普通文件。
2. 所有者权限（第 2-4 位：rwx）：
   • r（读）：允许所有者读取文件内容。
   • w（写）：允许所有者修改文件内容。
   • x（执行）：允许所有者执行该文件（若为可执行文件）。
     即所有者拥有读、写、执行的全部权限。
3. 所属组权限（第 5-7 位：r–）：
   • r（读）：允许所属组用户读取文件内容。
   • 后两位为 -，表示没有写和执行权限。
     即所属组用户仅拥有读权限。
4. 其他用户权限（第 8-10 位：rw-）：
   • r（读）：允许其他用户读取文件内容。
   • w（写）：允许其他用户修改文件内容。
   • 最后一位为 -，表示没有执行权限。
     即其他用户拥有读和写权限

1.3 具有 32 个结点的完全二叉树的深度为( )

**A.**5 **B.**6 **C.**7 **D.**8

答案：B

解析：

要确定具有 32 个结点的完全二叉树的深度，需先明确完全二叉树深度的计算规则：

对于一棵深度为h的完全二叉树，其结点总数n满足以下范围：
$$(2^{h-1}\le n<2^h)$$
其中，h为正整数（深度从 1 开始计数）。

代入计算：

已知结点总数(n = 32)，代入不等式验证：

• 当(h = 6)时：(2^{6-1} = 32)，(2^6 = 64)，即(32 \leq 32 < 64)，满足条件。

因此，具有 32 个结点的完全二叉树的深度为6。

1.4 某分段内存管理系统中，逻辑地址长度为32位，其中段号占8位，则最大段长是( )

A.16GB B.16MB C.256MB D.64KB

答案：B

解析：

在某分段内存管理系统中，逻辑地址长度为 32 位，其中段号占 8 位，则段内地址占 32 - 8 = 24 位。

因为段内地址的位数决定了段的最大长度，所以最大段长是(2^{24})字节。

1KB=1024字节(2^10)

则（2^20）=1MB

则（2^4）=16MB

1.5 线程可以独立拥有的资源包括( )

A:程序计数器 B:寄存器 C:栈 D:虚拟空间

答案：A B C

• A: 程序计数器
  程序计数器用于记录线程当前执行指令的地址，每个线程需要独立记录自己的执行位置，因此是线程独立拥有的资源。
• B: 寄存器
  寄存器用于暂存线程执行过程中的数据和地址，不同线程的执行状态不同，需要独立的寄存器组来保存，因此是线程独立拥有的资源。
• C: 栈
  栈用于存储线程的局部变量、函数调用信息等，属于线程私有的执行环境，每个线程有自己的栈，因此是线程独立拥有的资源。
• D: 虚拟空间
  虚拟空间是进程级的资源，由进程内的所有线程共享，用于映射物理内存、代码段、数据段等，线程不独立拥有虚拟空间。

综上，线程可以独立拥有的资源是程序计数器、寄存器和栈。

1.6 在操作系统中，引入缓冲的主要原因包括()

A.改善CPU与I/O设备间速度不匹配的矛盾

B.可以减少对 CPU的中断频率，放宽对中断响应时间的限制

C.提高CPU和I/O设备之间的并行圆

D提高内存的利用率

答案：A B C

• A. 改善 CPU 与 I/O 设备间速度不匹配的矛盾
  CPU 处理速度远快于 I/O 设备（如磁盘、打印机等），缓冲可以作为数据临时存储区域，让 CPU 不必等待 I/O 设备完成操作就能继续处理其他任务，有效缓解速度差异带来的影响，这是引入缓冲的核心原因之一。
• B. 可以减少对 CPU 的中断频率，放宽对中断响应时间的限制
  没有缓冲时，I/O 设备每传输一小部分数据就需中断 CPU；引入缓冲后，可积累一定量数据再一次性中断 CPU，显著减少中断次数，同时降低对 CPU 及时响应中断的要求。
• C. 提高 CPU 和 I/O 设备之间的并行性
  缓冲允许 CPU 在 I/O 设备传输数据的同时处理其他任务（如 CPU 向缓冲写入数据后，可继续执行计算，而 I/O 设备从缓冲读取数据），从而提高两者的并行工作程度。
• D. 提高内存的利用率
  缓冲本身需要占用内存空间，其主要作用是协调 CPU 与 I/O 设备的速度，而非直接提高内存利用率，因此该选项不属于引入缓冲的主要原因。

综上，引入缓冲的主要原因是 A、B、C。

二、算法与数据结构（单选）

2.1 对一个满二叉树，“m个树叶，k个分枝结点，n个结点”，则

A. n=m+1 B、m+1=2n C.n=2k+1 D.m=k-1

答案：C

满二叉树的核心性质：

1. 定义：满二叉树是指每一层的结点都达到最大数量的二叉树（即除最后一层外，所有结点都有左、右两个子结点，最后一层全为叶子结点）。
2. 叶子结点（m）与分枝结点（k）的关系：在满二叉树中，叶子结点数比分枝结点数多 1，即 (m = k + 1)（可通过归纳法证明：如深度为 1 的满二叉树，m=1，k=0，满足 1=0+1；深度为 2 的满二叉树，m=2，k=1，满足 2=1+1，以此类推）。
3. 总结点数（n）与分枝结点（k）的关系：总结点数 = 叶子结点数 + 分枝结点数，即 (n = m + k)。结合 (m = k + 1)，可得 (n = (k + 1) + k = 2k + 1)。
4. 总结点数（n）与叶子结点（m）的关系：由 (m = k + 1) 得 (k = m - 1)，代入 (n = m + k) 得 (n = m + (m - 1) = 2m - 1)，而非 (n = m + 1)。

选项分析：

• A. n = m + 1：错误。根据推导，(n = 2m - 1)，而非 (m + 1)。
• B. m + 1 = 2n：错误。该式与满二叉树的结点关系无关。
• C. n = 2k + 1：正确。由总结点数公式推导可得。
• D. m = k - 1：错误。实际应为 (m = k + 1)。

技巧：谁记这个啊？直接画一颗满二叉树，然后把n m k 实际带入选项中就可以了

        ①  <-- 第1层（根结点，分枝结点）
       / \
      /   \
     ②     ③  <-- 第2层（两个分枝结点）
    / \   / \
   /   \ /   \
  ④    ⑤⑥    ⑦  <-- 第3层（四个叶子结点）

• 总结点数 n：7（①②③④⑤⑥⑦）
• 叶子结点数 m：4（④⑤⑥⑦，即最后一层所有结点）
• 分枝结点数 k：3（①②③，即非叶子结点）

代入选项验证：

• C 选项 (n = 2k + 1) → 7 = 2×3 + 1 → 7 = 7（成立） 其他选项均不满足，进一步验证了结论。

2.2 关于"深拷贝"，下列说法正确的是( )

A.会拷贝成员数据的值和会拷贝静态分配的成员对象

B. 只会拷贝成员数据的值

C. 只会拷贝静态分配的成员对象

D.只会拷贝动态分配的成员对象

答案：A

• A. 会拷贝成员数据的值和会拷贝静态分配的成员对象
  深拷贝的核心是完整复制所有成员，包括基本数据类型的值（如 int、float）和静态分配的成员对象（如类中直接定义的对象成员，而非指针指向的动态对象）。此外，深拷贝还会处理动态分配的资源（如堆内存），但选项中未否定这一点，仅描述了其包含的部分正确内容，整体表述成立。
• B. 只会拷贝成员数据的值
  错误。深拷贝不仅拷贝基本数据类型的值，还会拷贝静态分配的成员对象，以及动态分配的资源（如指针指向的堆数据），并非 “只拷贝值”。
• C. 只会拷贝静态分配的成员对象
  错误。“只会” 一词排除了对基本数据类型值和动态资源的拷贝，与深拷贝的定义矛盾。
• D. 只会拷贝动态分配的成员对象
  错误。深拷贝并非只处理动态分配对象，静态分配的成员和基本数据类型均在拷贝范围内，且 “只会” 的表述不符合其完整拷贝的特性。

2.3 循环队列用数组 A[0…m-1]存放其元素值，已知其头尾指针分别是 front和rear，则当前队列的元素个数是( )

A.(rear-front+m)%m B.(rear-front+m)/ m C.(rear-front-m)% m D.(rear-front-m)/m

在循环队列中，数组A[0...m-1]的容量为m，front指向队头元素，rear指向队尾元素的下一个位置（即下一个待插入元素的位置）。由于队列是 “循环” 的，rear可能小于front（当队列元素跨越数组末尾时），因此需要通过公式处理这种边界情况。

公式推导：

• 当rear ≥ front时，元素个数为rear - front（直接计算两者差值）。
• 当rear < front时，元素个数为(rear + m) - front（需加上数组总容量m，以补偿循环带来的差值）。

综合两种情况，统一公式为：
(rear - front + m) % m

其中，+m是为了避免rear < front时出现负数，%m是为了确保结果在0到m-1之间（符合队列元素个数的范围）。

选项分析：

• A. (rear - front + m) % m：符合上述推导，正确。
• B. (rear - front + m) / m：除法会导致结果为0或1，无法表示实际元素个数（如队列有 3 个元素时，结果显然错误），错误。
• C. (rear - front - m) % m：减m会导致结果为负或超出合理范围，错误。
• D. (rear - front - m) / m：既减m又用除法，完全不符合元素个数的计算逻辑，错误。

2.4 以下代码的时间复杂度是（）

int sum =2;

while(sum<n/2)

{

	sum=sum*2;

}

A.O（n） B.O(log2(n)) C.O(nlog2(n)) D.O(nn)

答案：B

解析：(2^n)<(n/2) 高中数学题

2.5 下面给出的四种排序法（ ）排序是不稳定的排序

A.插入排序 B.冒泡 C.二路归并 D.堆积

答案：D

解析：

• A. 插入排序：
  插入排序的核心是将元素逐个插入到已排序序列的合适位置，当遇到相等元素时，会将新元素插入到原有相等元素的后面，从而保持相对位置不变。因此，插入排序是稳定排序。
• B. 冒泡排序：
  冒泡排序通过相邻元素的比较和交换实现排序，当两个元素相等时，不会发生交换，因此相等元素的相对位置不会改变。因此，冒泡排序是稳定排序。
• C. 二路归并排序：
  归并排序在合并两个已排序子序列时，当遇到相等元素，会先取出前一个子序列中的元素，再取后一个子序列中的元素，从而保持原有相对位置。因此，二路归并排序是稳定排序。
• D. 堆积排序（堆排序）：
  堆排序基于堆结构（大根堆或小根堆）实现，排序过程中需要频繁调整堆（如交换堆顶元素与最后一个元素、向下调整堆）。在调整过程中，相等元素的相对位置可能被打破。例如，堆中两个相等元素，可能因交换操作导致它们在最终序列中的顺序与初始顺序相反。因此，堆排序是不稳定排序。

2.6 设abcdef以所给的次序进栈，若在进栈操作时，允许退操作，则下面不可能得到的序列为( )

A.fedcba B.BCAFED c.dcefba D.cabdef

答案：D

解析：没啥可说的，自己脑袋里头推算一遍就行了

三、编程题

3.1 题目描述

你正在对一个高性能。集群设计一个资源调度器。集群有一批待处理的作业记录在一个字符串jobs中。每个字符串代表一种特定的作业，（例如’A’可能代表图像渲染，'B’代表数据分析）。集群的处理器在每一个时间周期内只能执行一个作业，作业可以按照任何顺序执行。但存在一个重要的约束，当处理器完成一个特定的作业后，必须经过，Come_load_time个时间周期的冷却才能再次执行同种作业。在冷却期间，处理器可以执行其他类型的作业或处于空闲状态。你的任务是计算出所有。待处理作业所需的最短总时间周期。

3.1.1 示例1

输入:jobs=「“A”,“A”,“A”,“B”,“B”,“B”].cooldownTime = 2
输出:8
解释:

• 这是一个可能的调度序列:A->B->空闲->A->B->空用->A->B
  在执行了一个’A’ 类型的作业后，处理器必须等待2个同期才能再次执行’A’。这导致在第3和落6个周期，处理器必须选择’空闲’，因为两种中可用的作业类型都在冷却中。

3.1.2 示例2

输入:jobs=「“A”,“C”,“A”,“B”,“D”,“B”].cooldownTime = 1
输出:8
解释:

• 这是一个可能的调度序列:A->B->C->D->A->B
  由于冷却时间仅为1，处理器总能找到一个不在冷却期的不同类型作业来执行，因此不需要任何空闲周期。

3.1.3 示例3

输入:jobs=「“A”,“A”,“A”,“B”,“B”,“B”].cooldownTime = 2
输出:8
解释:

• 一个可能的调度序列是：A->空闲->空闲->A->空闲->A…

由于只有一种作业，每次执行后都必须强制等待2个空闲周期。

3.1.4 代码

3.2 题目描述

你正在为一个自动化运维平台开发一个核心的指令解析器，该平台接收一个由底层系统产生的、连续的、没有任何分隔符的原始指令流（commandStream）。同时，你有一个预定义好的“有效指令集”。它是一个列表，包含了所有已知的，合法的单元指令，你的任务是编写一个函数，判断给定的commandStream是否可以被完全地，无遗漏地分解为一串或多串来自validinstructions列表中地单位指令。

• 指令焦中的同一个单元指令可以在一次成功的分解中重复出现。

• 指令出中的指令不一定都会被用到

3.2.1 示例1

输入:commandStream=“runtestexecute”, valldinstructions = [“run”, “test”, “execute”]
输出:true
解程;原始指令流可以被成功解折为“run"，“test”，"execute”这三个有效的单元指令,

3.2.2 示例2

输入:commandStream=“startprocossstart”, validinstructions = [“start”, "process “]
输出:true
解程;原始指令流可以被成功解折为“start”，"process "，"start”这三个有效的单元指令,

3.2.3 示例3

输入:commandStream=“systemcheckfair”, valldinstructions = [“system”, “check”, “sys”,“fail”]
输出:false
解程:无法找到一种方式，使用指令集中的指今来完整拼接成“systemcheckfail”,你可以匹配"system" 和"check”,但是剩下的“fail”虽然是一个有效指令，但中间的“systemcheck”无法匹配、只能匹配“sys”,但剩下的“temcheckfair”无法解析。

3.2.4 代码