2015年12月考研的408试题，本篇为小题部分，大题见下一篇。

声明：

• 0x和0b分别表示十六进制数和二进制数，其余为十进制数。
• 0y和0c分别表示十六进制形式补码和二进制形式补码。
• exp()和log()分别是以2为底的指数和对数，exp10()以10为底。
• 乘除号用最朴素的×÷，分数用/，参与计算的英文字母变量用手写体。
• 〔〕里的斜体为补充文字，另外对原题一些容易误会的文字做了修改。
• 图片使用亿图图示等绘制。

一、单项选择：

第1～40小题，每小题2分，共80分。显示所有答案

DataStructure

🤓✍️「1」、已知表头元素为c的单链表在内存中的存储状态如下如示，现将f存放于0x1014处并插入到单链表中，若f在逻辑上位于a和e之间，则a,e,f的链接地址依次是（）？

• A、0x1010,0x1014,0x1004,
• B、0x1010,0x1004,0x1014,
• C、0x1014,0x1010,0x1004,
• D、0x1014,0x1004,0x1010,

🤓✍️「2」、已知一个带有表头结点的双向循环链表L，结点结构为［prev｜data｜next］，其中prev和next分别是指向其直接前驱和直接后继结点的指针。现要删除指针所指的结点，正确的语句序列是（）？

• A、p->next->prev = p->prev; p->prev->next = p->prev; free(p);
• B、p->next->prev = p->next; p->prev->next = p->next; free(p);
• C、p->next->prev = p->next; p->prev->next = p->prev; free(p);
• D、p->next->prev = p->prev; p->prev->next = p->next; free(p);

🤓✍️「3」、设下图所示的火车车轨，入口到出口之间有n条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为1～9的9列列车，驶入的次序依次是8,4,2,5,3,9,1,6,7，若期望驶出的次序为1～9，则n至少（）？

• A、2
• B、3
• C、4
• D、5

🤓✍️「4」、有一个100阶的三对角矩阵M，其元素M[i][j]〔i,j均为1～100的整数〕按行优先依次压缩存入下标从0开始的一维数组N中。元素M[30][30]在N中的下标是（）？

• A、86
• B、87
• C、88
• D、89

🤓✍️「5」、若森林F有15条边，25个结点，则F包含树的个数是（）？

• A、8
• B、9
• C、10
• D、11

🤓✍️「6」、下列选项中，不是下图深度优先搜索序列的是（）？

• A、V1,V5,V4,V3,V2,
• B、V1,V3,V2,V5,V4,
• C、V1,V2,V5,V4,V3,
• D、V1,V2,V3,V4,V5,

🤓✍️「7」、若将n个顶点e条弧的有向图采用邻接表存储，则拓扑排序的时间复杂度是（）？

• A、𝜪(n)
• B、𝜪(n+e)
• C、𝜪(n^2)
• D、𝜪(ne)

🤓✍️「8」、使用迪杰斯特拉算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是（）？

• A、5,2,3,4,6,
• B、5,2,3,6,4,
• C、5,2,4,3,6,
• D、5,2,6,3,4,

🤓✍️「9」、在有n〔n是大于1000的正整数〕个元素的升序数组A中查找关键字x，查找算法伪代码如下，本算法与折半查找算法相比，有可能具有更少比较次数的情形是（）？

k = 0;
while (k < n && A[k] < x) k = k + 3;
if (k < n && A[k] == x) return true;
else if (k - 1 < n && a[k-1] == x) return true;
else return false;

• A、当x不在数组中
• B、当x接近数组开头处
• C、当x接近数组结尾处
• D、当x位于数组中间

🤓✍️「10」、B+树不同于B-树的特点之一是（）？

• A、能支持顺序查找
• B、结点中含有关键字
• C、根结点至少有两个分支
• D、所有叶结点都在同一层

🤓✍️「11」、对10TB的数据文件进行排序，应使用的方法是（）？

• A、希尔排序
• B、堆排序
• C、快速排序
• D、归并排序

🤓✍️「12」、将高级语言源程序转换为机器级目标代码文件的程序是（）？

• A、汇编程序
• B、链接程序
• C、编译程序
• D、解释程序

ComputerOrganization

🤓✍️「13」、有如下C语言程序段，执行后，usi的值为（）？

short si = -32767;
unsigned short usi = si;

• A、-32767
• B、32767
• C、32768
• D、32769

🤓✍️「14」、某计算机字长为32位，按字节编址，采用小端方式存放数据。假定有一个double型变量，其机器数为0x1122 3344 5566 7788，存放在0x0000 8040开始的连续存储单元中，则存储单元0x0000 8046中存放的是（）？

• A、0x22
• B、0x33
• C、0x77
• D、0x66

🤓✍️「15」、有如下C语言程序段，若数组a[]及变量k均为int型，int型占4B，数据Cache采用直接映射方式，数据区大小为1KB，块大小为16B，该程序段执行前Cache为空，则该程序段执行过程中访问数组a[]的Cache缺失率约为（）？

for (k = 0; k < 1000; k++)
    a[k] = a[k] + 32;

• A、1.25%
• B、2.5%
• C、12.5%
• D、25%

🤓✍️「16」、某存储器容量为64KB，按字节编址，地址0x4000～0x5FFF为ROM区，其余为RAM区。若采用8K×4b的SRAM芯片设计，则需要该芯片的数量是（）？

• A、7
• B、8
• C、14
• D、16

🤓✍️「17」、某指令格式为［OP｜M｜I｜D］，其中M为寻址方式，I为变址寄存器编号，D为形式地址。若采用先变址后间址的寻址方式，则操作数的有效地址是（）？

• A、I+D
• B、(I)+D
• C、[(I)+D]
• D、[(I)]+D

🤓✍️「18」、某计算机主存地址空间为4GB，字长为32位，按字节编址，采用32位定长指令字格式。若指令按字边界对齐存放，则程序计数器PC和指令寄存器IR的位数至少是（）？

• A、30,30,
• B、30,32,
• C、32,30,
• D、32,32,

🤓✍️「19」、在无转发机制的五段基本流水线，〔取指｜译码或读寄存器｜运算｜访存｜写回寄存器〕中，下列指令序列存在数据冒险的指令对是（）？

I1: add R1, R2, R3 ;(R2)+(R3)➔R1
I2: add R5, R2, R4 ;(R2)+(R4)➔R5
I3: add R4, R5, R3 ;(R5)+(R3)➔R4
I4: add R5, R2, R6 ;(R2)+(R6)➔R5

• A、I1和I2
• B、I2和I3
• C、I2和I4
• D、I3和I4

🤓✍️「20」、单周期处理器中所有指令的指令周期为一个时钟周期。下列关于单周期处理器的叙述中，错误的是（）？

• A、可以采用单总线结构数据通路。
• B、处理器时钟频率较低。
• C、在指令执行过程中控制信号不变。
• D、每条指令的CPI=1。

🤓✍️「21」、下列关于总线设计的叙述中，错误的是（）？

• A、并行总线传输比串行总线传输速度快。
• B、采用信号线复用技术可减少信号线数量。
• C、采用突发传输方式可提高总线数据传输率。
• D、采用分离事务通信方式可提高总线复用率。

🤓✍️「22」、异常是指令执行过程中在处理器内部发生的特殊事件，中断是来自处理器外部的请求事件。下列关于中断或异常情况的叙述中，错误的是（）？

• A、访存时缺页属于中断。
• B、整数除以0属于异常。
• C、DMA传送结束属于中断。
• D、存储保护错属于异常。

OperatingSystem

🤓✍️「23」、下列关于批处理系统的叙述中，正确的是（）？

Ⅰº批处理系统允许多个用户与计算机直接交互。
Ⅱº批处理系统分为单道批处理系统和多道批处理系统。
Ⅲº中断技术使得多道批处理系统和I/O设备可与CPU并行工作。

• A、Ⅱ,Ⅲ,
• B、Ⅱ,
• C、Ⅰ,Ⅱ,
• D、Ⅰ,Ⅲ,

🤓✍️「24」、某单CPU系统中有输入和输出设备各1台，现有3个并发执行的作业，每个作业的输入➧计算➧输出时间分别为2ms➧3ms➧4ms，且都按输入➧计算➧输出的顺序执行，则执行完3个作业需要的时间最少是（）？

• A、15ms
• B、17ms
• C、22ms
• D、27ms

🤓✍️「25」、系统中有3个不同的临界资源R1,R2,R3，被4个进程P1,P2,P3,P4共享，各进程对资源的需求为：P1申请R1,R2，P2申请R2,R3，P3申请R1,R3，P4申请R2。若系统出现死锁，则处于死锁状态的进程数至少是（）？

• A、1
• B、2
• C、3
• D、4

🤓✍️「26」、某系统采用改进型CLOCK置换算法，页表项中字段A为访问位，M为修改位，A=0表示最近没有访问过，M=0表示页没有被修改过。按(A,M)所有可能的取值，将页分为4类：(0,0),(1,0),(0,1),(1,1)，则该算法淘汰页的次序为（）？

• A、(0,0),(0,0),(1,0),(1,1)
• B、(0,0),(1,0),(0,1),(1,1)
• C、(0,0),(0,1),(1,1),(1,0)
• D、(0,0),(1,1),(0,1),(1,0)

🤓✍️「27」、使用TSL"Test and Set Lock"指令实现进程互斥的伪代码如下所示，下列与该实现机制相关的叙述中，正确的是（）？

do {
    ...
    while (TSL(&lock)) ;
    critical_section;
    lock = false;
    ...
} while (true);

• A、退出临界区的进程负责唤醒阻塞态进程。
• B、等待进入临界区的进程不会主动放弃CPU。
• C、上述伪代码满足“让权等待”的同步原则。
• D、while (TSL(&lock)) ;语句应在关中断状态下进行。

🤓✍️「28」、某进程的段表内容如下所示，当访问段号为2，段内地址为400的逻辑地址时，进行地址转换的结果是（）？

• A、段缺失异常
• B、得到内存地址4400
• C、越权异常
• D、越界异常

🤓✍️「29」、某进程访问页面的序列如下所示，若工作集的窗口大小为6，则在t时刻的工作集为（）？

• A、{6,0,3,2}
• B、{2,3,0,4}
• C、{0,4,3,2,9}
• D、{4,5,6,0,3,2}

🤓✍️「30」、进程P1,P2均包含并发执行的线程，部分伪代码描述如下所示，下列选项中，需要互斥进行的操作是（）？

// Processor P1:          // Processor P2:
|int x = 0;               |int x = 0;
|Thread1():               |Thread3():
|    int a;               |    int a;
|    a = 1; x += 1;       |    a = x; x += 3;
|Thread2():               |Thread4():
|    int a;               |    int b;
|    a = 2; x += 2;       |    b = x; x += 4;

• A、a = 1与a = 2
• B、a = x与b = x
• C、x += 1与x += 2
• D、x += 1与x += 3

🤓✍️「31」、下列关于SPOOLing技术的叙述中，错误的是（）？

• A、需要外存的支持。
• B、需要多道程序设计技术的支持。
• C、可以让多个作业共享一台独占式设备。
• D、由用户作业控制设备与输入／输出井之间的数据传送。

🤓✍️「32」、下列关于管程的叙述中，错误的是（）？

• A、管程只能用于实现进程的互斥。
• B、管程是由编程语言支持的进程同步机制。
• C、任何时候只能有一个进程在管程中执行。
• D、管程中定义的变量只能被管程内的过程访问。

ComputerNetWork

计算机网络相关第33～41题均依据此图作答。

🤓✍️「33」、在OSI七层参考模型中，R1,Switch,Hub实现的最高层功能分别是（）？

• A、2,2,1,
• B、2,2,2,
• C、3,2,1,
• D、3,2,2,

🤓✍️「34」、若连接R2和R3链路的频率带宽为8KHz，信噪比为30dB，该链路实际传输速率约为理论最大数据传输速率的50%，则该链路的实际数据传输速率约为（）？

• A、8Kbps
• B、20Kbps
• C、40Kbps
• D、80Kbps

🤓✍️「35」、若H2向H4发送1个数据帧，H4向H2立即发送1个确认帧，则除H4外，从物理层上能收到该确认帧的主机还有（）？

• A、仅H2
• B、仅H3
• C、H1和H2
• D、H2和H3

🤓✍️「36」、若Hub再生比特流过程中，会产生1.535us延时，信号传播速度为200m/us，不考虑以太网帧的前导码，则H3和H4之间理论上可以相距的最远距离是（）？

• A、200m
• B、205m
• C、359m
• D、512m

🤓✍️「37」、假设R1,R2,R3采用RIP交换路由信息，且均已收敛。若R3检测到网络201.1.2.0/25不可达，并向R2通告一次新的距离向量，则R2最终更新完，其到达该网络的距离是（）？

• A、2
• B、3
• C、16
• D、17

🤓✍️「38」、假设连接R1,R2,R3之间的点对点链路使用201.1.3.x/30地址，当H3访问Web服务器S时，R2转发出去的封装HTTP请求报文的IP分组的源IP地址和目的IP地址分别是（）？

• A、192.168.3.251和130.18.10.1
• B、192.168.3.251和201.1.3.9
• C、201.1.3.8和130.18.10.1
• D、201.1.3.10和130.18.10.1

🤓✍️「39」、若H1和H2的默认网关和子网掩码都分别配置为192.168.3.1和255.255.255.128，H3和H4的默认网关和子网掩码都分别配置为192.168.3.254和255.255.255.128，则下列现象中可能发生的是（）？

• A、H1不能与H2正常IP通信。
• B、H2不能与H4都不能访问Internet。
• C、H1不能与H3正常IP通信。
• D、H3不能与H4正常IP通信。

🤓✍️「40」、假设所有域名服务器均采用迭代查询方式进行域名解析。当H4访问规范域名为www.abc.xyz.com的网站时，域名服务器201.1.1.1在完成该域名解析过程中，可能发出DNS查询的最少和最多次数分别是（）？

• A、0和3
• B、1和3
• C、0和4
• D、1和4