2023年考研408计算机统考真题在线评测（附答案）

第41题

(13分)对于有向图，如果一个顶点的出度大于入度，则这个顶点称为K页点，有向图用邻接矩阵存储，数据结构定义如下:

typedef struct{
int numVertex, numEdge;//顶点数，边数
char VertexList[MAXV];//顶点表
int Edge[MAXV][MAXV];//邻接矩阵
}MGraph;

要求实现函数int printVertices(MGraph G)，输出有向图中所有K页点，并返回K顶点的总数

(1)说明算法思想(占5-6分)

(2)用C/C++实现算法(占7-8分)

[参考答案]

(1)算法思想：遍历有向图中所有顶点，并统计各顶点的出度和入度，输出出度大于入度的KJ页点，并使用变量 count 累计顶点的总数。

计算顶点i的出度: 遍历邻接矩阵的i行元素，即 Edge[i][0]~Edge[i][numVertex-1]，统计非零元素个数，即为顶点i的出度

计算顶点i的入度：遍历邻接矩阵的i列元素，即Edge[0][i]~ Edge[numVertex-1][i]，统计非零元素个数，即为顶点i的入度

(2)算法实现：

int printVertices (MGraph G){
    int count =0;//K顶点的总数
    for (int i=0; i<G.numVertex; i++){
        int outDegree = 0;//顶点i的出度
        int inDegree = 0;//顶点i的入度
        for (int j=0;j<G.numVertex; j++)
            if (G.Edge[i][j]>0)  outDegreet+;
        }
        for (int j=0;j<G.numVertex; j++)
            if (G.Edge[j][i]>0)  outDegreet+;//循环两次方便理解
        }
        if (outDegree > inDegree) [//顶点i的出度大于入度
            printf ("c\n"，G.VertexList[i]);//输出顶点i
            count++;//累加K顶点总数
        }
     }
     return count;//返回x顶点总数
}

第42题

(10分)在进行外部排序时，可使用置换-选择排序生成初始归并段。内存工作区可存储n个记录，某文件含 n 个记录。

(1)若n=19，m=4。文件记录关键字为：51,94,37,92,14,63,15,99.48,56,23,60,31,17,43,8,90,166,100。使用置换-选择排序，可生成几个初始归并段?每个归并段各是什么?

(2)对于任意 m(n>>m>0)，使用置换-选择排序生成第一个初始归并段的最大可能长度、最小可能长度分别是?

[参考答案]

(1) 可生成3个初始归并段 (2分)

①37,51,63,92,94,99 (2分)

②14,15,23,31,48,56,60,90,166 (2分)

③8,17,43,100 (2分)

(2)最大可能长度为n，最小可能长度为m。(各1分)

第43题

(14分)某机器字长为32位的计算机M，采用请求调页存储管理。虚拟地址32位，页面大小4KB。Cache采用4路组相联映射，内存块大小为32B，Cache数据区大小为8KB。二维数组int a[24][64]按行优先存储，数组的起始虚拟地址为0042 2000H。数组a的数据初始时未调入内存，按如下方式访问数组a:

for (int i=0;i<24; i++)
for (int j=0;j<64; j++)
a[i][j]=10;

(1)数组a分为几个页面存储?访问数组a 缺页几次?页故障地址各是什么?

(2)不考虑对变量i，j的访问，访问数组 a 的过程是否具有时间局部性?为什么?

(3)在计算机M的32位地址中，块内地址是哪几位? Cache组号是哪几位?数组元素a[1][0]的虚拟地址是什么?对应的Cache组号是什么?

(4)数组a总共占多少块?访问a的Cache 命中率是多少?若采用如下方式访问数组a，则命中率又是多少?

for (int j=0;j<64;j++)
for (int i=0; i<24; i++)
a[i][j]=10;

[参考答案]

(1)数组a分为2个页面存储。(1分)

访问数组 a 缺页2次 (1分)

页故障地址分别是0042 2000H、0042 3000H。 (1+1分)

(2)没有时间局部性。(1分)

时间局部性是指，程序在一段时间内，访问同一个数据多次。对于数组a，每个元素仅被访问一次，因此不具有时间局部性。 (2分)

(3)32位地址结构如下: tag标记21bit + 组号6bt +块内地址5bit。若用A31-A0 表示32位地址，则

块内地址是A4~A0(1分)

Cache组号是A10~A5 (1分)

可[1][0]的虚拟地址是0042 2100H (1分)

对应的Cache组号是8(1分)

(4)数组 a 总共占192块 (1分)

访同a的Cache命中率是 7/8=87.5% (1分)若按列访问数组 a，Cache命中率同样是 87.5% (1分)

第44题

(9分)43题的C语言代码，对应的机器级代码如下,请回答问题。

for(int i=0;i<24;i++)
1   00401070     C7...     mov[ebp-8],0
2   00401079     EB 09   jmp 00401084h
3   0040107B     8B 55 F8   mov eax,[ebp-8]
...  ...                    ...              ...
7   00401088     7D32    jpe 004010bch
for(int j=0;j<64;j++)
8   0040108A     C7 45...      mov[ebp-4],0
...   ...                   ...               ...
a[i][j]=10;
...   ...                   ...               ...
19  004010AE     C7 84 82 00 20 42 00 0A 00 00 00 mov[ecx+edx*4+00422000h],0Ah
20  ...                   ...

(1)第20条指令的虚拟地址是什么?

(2)第2条指令jmp的操作码是 EBH，它的转移目标地址是00401084h。第7条指令jge的操作码是7DH，它的转移目标地址是 004010bch。这两条指令分别采用什么寻址方式?请给出jmp 指今的转移目标地址计算过程

(3)第19条指令，实现了adll-10该指今的源操作数采用什么寻址方式?已知edx 存放的值，ecx存放的是什么?该系统采用大端还是小端存储?

(4)第一次取第19条指令时，是否发生缺页?为什么?

[参考答案]

(1)第20条指令的虚拟地址是 004010B9h (1分)

(2)jmp 指今采用相对寻址《(1分)

ige 指今采用相对寻址《1分)

执行jmp指令时，程序计数器PC指向jmp指令的后一条指令，即0040107Bh。jmp 指令的转移目标地址计算过程为 0040107Bh+09h = 00401084h (1分)

(3)源操作数采用立即寻址(1分)

ecx存放的值 =i64*4 =256 (1分)

系统采用小端存储 (1分)

(4)没有发生缺页(1分)

第19条指令的页号是00401h，第1条指令的页号也是00401h。刚开始访问第1条指令时，就会把页面00401h 调入内存。之后当第一次访问到第19条指令时，页面已经在内存中，因此不会发生缺页。 (2分)

注:第2小问，jmp、jge指令的寻址方式，如果答“偏移导址”，可能也会给分

第45题

(7分)采用swap 指今实现进程互斥。lock为TRUE时，不可进入临界区; lock 为FALSE 时，可以进入临界区。某学生写的代码如下:

bool lock = FAlSE;//共享变量
......
// 进入区
bool key = TRUE;
if (key == TRUE)
     swap (key，lock);
// 临界区
......
// 退出区
lock=TRUE;
......

newSwap (boola， bool *b){
       bool temp =*a;
       *a=*b;
       *b=temp;
}

(1)请修改代码，正确实现互斥(不增加语句条数)

(2)是否可以用函数newSwap(&a&b)代替swap 指令?为什么?

[参考答案]

(1)修改进入区代码: if (key == TRUE) 改为 while (key == TRUE)(2分)

修改退出区代码:lock=TRUE;   改为 lock=FALSE;(2分)

(2)不可以代替swap指令。(1分)

因为 newSwap函数的执行不具备原子性，执行newSwap 的过程中，可能会切换为其他线程，从而导致无法正确实现线程互斥。(2分)

第46题

(8分)进程P通过系统调用请求从键盘读入一个字符。题目乱序给出6个处理步骤:1.将进程P插入就绪队列，2.将进程插入阻塞队列，3.将字符从键盘控制器读入系统缓冲区，4.启动中断处理程序，5.系统调用返回，6.用户通过键盘输入字符。

（1）1.的前、后分别是哪个步骤? 6.的后面是什么步聚?

（2）哪个步骤一定会使CPU从P进程切换到其他进程?哪个步骤之后调度器可以调度进程p？（3）哪个步骤是由键键盘驱动程序完成的?

（4）中断处理时，进程P是什么状态? CPU处于内核态还是用户态?

[参考管案]

（1）1的前面是3(1分)

1的后面是5(1分)

6的后面是4(1分)

（2）2使得CPU从进程P切换为其他进程 (1分)

1之后调度器可以调廉进程P (1分)

（3）3由键盘驱动程序完成(1分)

（4）中断处理时，进程P处于阻塞态(1分)

CPU处于内核态(1分)

[解析]6个步骤的处理序是: 2 6 4 3 1 5

第47题

计算机网络:

(9分)主机H登录FTP服务器后自服务器上估一个大小为18000B的文件F，假设H传输F建立数据连接时，选择的初始序号为100，MTU=1000B，拥塞控制初始闻值为4MSS，RTT=10ms，忽略TCP的传输时延，在F的传榆过程中，H以MSS段向服务器发送散据，且未发生差错、丢包和乱序。

(1)FTP的控制连接是持久的还是非持久的?FTP的数据连接是持久的还是非持久的?H登录FTP服务器时，建立的TCP连接是控制连持还是数据连接?

(2)H通过数据连接发送F时，F的第一个字节序号是多少?在断开数据连接的过程中，FTP发达的第二次挥手的ACK序号是?

(3)F发送过程中,当H收到确认序号为2101的确认段时，H的拥塞窗口调整为多少?收到确认序号为7101的确认段时，H的拥塞窗口调整为多少?

(4)H从请求建立数据连接开始，到确认F已被服务器全部接收为止，至少需要多长时间期间应用层数据平均发送速率是多少?

[参考答案]

(1)控制连接是持久的；数据连接是非持久的；控制连接。

(2)101；18102

(3)3MSS；5MSS

(4)6个RTT=60ms；18000B/60ms = 2.4Mbps