一. 单选

1.一进程刚获得三个主存块的使用权，若该进程访问页面的次序是｛1321215123｝，采用LRU算法时，缺页数

是（）次。
A 3
B 4
C 5
D 6

正确答案：C

缺页中断：要访问的页不在主存，需要操作系统将其调入主存后再进行访问
LRU算法：当要调入一页而必须淘汰旧页时，将最近最少使用的置换出去
缺页数：缺页中断次数，等于进程的物理块数+页面置换次数

1321215123
1——1
3——3 1（刚使用的放在前面，未使用的放在后面）
2——2 3 1
1——1 2 3
2——2 1 3
1——1 2 3
5——5 1 2（页面置换，淘汰最后一个3）
1——1 5 2
2——2 1 5
3——3 2 1（页面置换，淘汰最后一个5）
总共进行了两次页面置换，缺页数=3+2=5
缺页率：5/10=0.5

2. 以下关于多线程的叙述中错误的是（）

A 线程同步的方法包括使用临界区，互斥量，信号量等
B 两个线程同时对简单类型全局变量进行写操作也需要互斥
C 实现可重入函数时，对自动变量也要用互斥量加以保护
D 可重入函数不可以调用不可重入函数

正确答案：C

临界区：
一个访问共用资源（同一个全局变量，同一个类对象等）的程序片断。

互斥量：
互斥锁的底层就是互斥量，使用互斥锁可以限制多个执行流对临界资源的访问时，只有一个执行流可以访问资源，其他执行流需要等待。从而保证了程序结果没有二义性。

信号量：
可以描述并管理一个资源的数量，提供wait/post的接口来保证程序不会产生二义性结果，同时信号量也可以保证线程同步，信号量的底层有一个资源计数器+PCB等待队列

可重入函数：
在多线程的程序当中，如果一个函数可能同时被多个线程访问，没有导致程序的结果产生二义性。
不可重入函数：
在多线程的程序当中，如果一个函数可能同时被多个线程访问，从而导致程序的结果产生二义性。

C：
可重入函数可认为是可以被中断的函数，自动变量定义的时候才被创建，函数返回是，系统收回空间，它是局部作用域变量，不需要互斥量，可重入函数对全局变量才需要互斥量保护

3. 系统死锁的可能的原因是（）

A 进程死循环
B 资源循环等待
C 程序内存访问越界
D 进程释放资源

正确答案：B

死锁的四个必要条件：
互斥条件：一个资源每次只能被一个进程使用
请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放；（程序员可以破坏）
不剥夺条件：进程已获得的资源，在未使用完之前，不能强行剥夺。
循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系；（程序员可以破坏）

内存越界访问，程序有可能奔溃

4. 整数0x12345678，在采用bigendian中内存的排序序列是（ ）

A 12 34 56 78
B 78 56 34 12
C 87 65 43 21
D 21 43 65 87
正确答案：A

大端big endian
小端little endian

5.使用C语言将一个1G字节的字符数组从头到尾全部设置为字’A’，在一台典型的当代PC上，需要花费的CPU时间的数量级最接近（）

A 0.001秒
B 1秒
C 100秒
D 2小时

正确答案：B

CPU执行一条语句约1ns——10^-9s

6.对于普通的计算机，对以下事件的平均耗时从小到大排序为____：

A.读取1KB内存数据 B.从硬盘连续读取1KB数据 C.读取一次L2缓存 D.一次磁盘寻道
A C,A,D,B
B C,D,A,B
C D,C,A,B
D D,A,C,B

正确答案：A

7. 现代计算机普遍采用总线结构，包括数据总线、地址总线、控制总线，通常与数据总线位数对应相同的部

件是（ ）
A CPU
B 存储器
C 地址总线
D 控制总线

正确答案：A

地址总线当中每一根地址线都可以模拟0/1信号，所以32（64）位操作系统有32（64）根地址线。
32位操作系统的地址为0x00000000-0xFFFFFFFF
 

8.关于子进程和父进程的说法，下面哪一个是正确的（）

A 一个父进程可以创建若干个子进程，一个子进程可以从属于若干个父进程
B 父进程被撤销时，其所有子进程也被相应撤消
C 子进程被撤销时，其从属的父进程也被撤销
D 一个进程可以没有父进程或子进程

正确答案：D

9.关于线程和进程，下面说法正确的是（）

A 终止一个进程比终止一个线程花费的时间少
B 进程切换比同一进程内部的线程切换花费的时间少
C 线程提高了不同执行程序间的通信效率
D 进程和线程都是资源分配和调度的基本单位

正确答案：C

A 终止一个进程比终止一个线程花费的时间少——花费时间多，因为线程只是一个执行流，不会将进程资源释放掉
B 进程切换比同一进程内部的线程切换花费的时间少——线程切换花费的时间少
C 线程提高了不同执行程序间的通信效率——可以让进程的某一线程执行通信任务，其他的线程做其他时期，提高程序的运行效率
D 进程和线程都是资源分配和调度的基本单位——进程是操作系统分配资源的基本单位，线程是操作系统调度的基本单位
 

10.进程调度时，下列进程状态的变化过程哪一项是不可能发生的（）

A 阻塞挂起->阻塞
B 就绪挂起->就绪
C 就绪挂起->阻塞挂起
D 阻塞挂起->就绪挂起

正确答案：C

二. 编程

1. 星际密码

链接

星际战争开展了100年之后，NowCoder终于破译了外星人的密码！他们的密码是一串整数，通过一张表里的信息映射成最终4位密码。表的规则是：n对应的值是矩阵X的n次方的左上角，如果这个数不足4位则用0填充，如果大于4位的则只输出最后4位。
|1 1|^n => |Xn …|
|1 0| |… …|
例如n=2时，
|1 1|^2 => |1 1| * |1 1| => |2 1|
|1 0| |1 0| |1 0| |1 1|
即2对应的数是“0002”。

输入描述：
输入有多组数据。
每组数据两行：第一行包含一个整数n (1≤n≤100)；第二行包含n个正整数Xi (1≤Xi≤10000)
输出描述：
对应每一组输入，输出一行相应的密码。

示例1:
输入
6 1
8 15 21 13 25 27
5 1
10 100 1000 10000

输出
418109877711037713937811
00010089410135017501

正确答案：

// write your code here cpp
#include<stdio.h>
#include<iostream>
using namespace std;

int main()
{
    int arr[10000] = {0,1,2};
    for(int i = 3;i<=10000;i++)
    {
        arr[i] = arr[i-1] + arr[i-2];
        arr[i] %= 10000;
    }
    
    int n;
    while(cin>>n)
    {
        for(int i = 0;i<n;i++)
        {
            int num;
            cin >> num;
            printf("%04d",arr[num]);
        }
        printf("\n");
}
    
    return 0;
}

2.数根

链接

数根可以通过把一个数的各个位上的数字加起来得到。如果得到的数是一位数，那么这个数就是数根；如果结果是两位数或者包括更多位的数字，那么再把这些数字加起来。如此进行下去，直到得到是一位数为止。
比如，对于24 来说，把2 和4 相加得到6，由于6 是一位数，因此6 是24 的数根。
再比如39，把3 和9 加起来得到12，由于12 不是一位数，因此还得把1 和2 加起来，最后得到3，这是一个一位数，因此3 是39 的数根。
现在给你一个正整数，输出它的数根。

输入描述：
输入包含多组数据。
每组数据数据包含一个正整数n（1≤n≤10E1000）。
输出描述：
对应每一组数据，输出该正整数的数根。

示例1:
输入
24
39
输出
6 3

正确答案：

// write your code here cpp
#include<iostream>
#include<string>
using namespace std;

int main()
{
    //数据庞大需要用string接受然后再转换为整型
    string s;
    while(cin>>s)
    {
        int n = 0;
        for(int i = 0;i<s.size();i++)
        {
            n += s[i]-'0';
        }
        
        int sum = 0;
        while(n)
        {
            sum += n%10;
            n = n/10;
            
            if(n == 0 && sum/10 != 0)
            {
                n = sum;
                sum = 0;
}
            
        }
        cout<<sum<<endl;
}
    return 0;
}