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

声明：

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

一、单项选择：

第1～40小题，每小题2分，共80分。

DataStructure

🤓✍️「1」、若栈S1中保存整数，栈S2中保存运算符，假定S1中的操作数依次是5,8,3,2，S2中的运算符依次是*,-,+，栈顶均在右侧。函数F()依次执行下述各步操作👇，调用3次F()后，S1的栈顶是（）？

①从S1中依次弹出两个操作数𝒶和𝒷；
②从S2中弹出一个运算符𝒐𝒑；
③执行相应的运算𝒷‹𝒐𝒑›𝒶；
④将运算结果压入S1中。

  • A‣-15
  • B‣15
  • C‣-20
  • D‣20
【A】模拟题。注意第2次调用`F()`时，𝒶=5,𝒷=8,𝒐𝒑='-'，将8-5=3压入S1中。

🤓✍️「2」、现有队列Q与栈S，初始时Q中的元素依次是1,2,3,4,5,6，队头在左侧，S为空。若仅允许下列3种操作：❶出队并输出出队元素；❷出队并将出队元素入栈；❸出栈并输出出栈元素；则不能得到的输出序列是（）？

  • A‣1,2,5,6,4,3,
  • B‣2,3,4,5,6,1,
  • C‣3,4,5,6,1,2,
  • D‣6,5,4,3,2,1,
【C】模拟题。得以2,1,的顺序出栈。

🤓✍️「3」、设有一个12×12的对称矩阵𝜧，将其上三角部分的元素M[i][j](1≤i≤j≤12)按行优先存入C语言的一维数组N中，元素M[6][6]在N中的下标是（）？

  • A‣50
  • B‣51
  • C‣55
  • D‣66
【A】该元素前面有几个非零，下标就是几，12+11+10+9+8=50。

🤓✍️「4」、设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。若T有𝓀个叶结点，则T的结点总数是（）？

  • A‣2𝓀-1
  • B‣2𝓀
  • C‣𝓀^2
  • D‣exp(𝓀)-1
【A】直接得度为2的结点有𝓀-1个，共2𝓀-1个。

🤓✍️「5」、已知字符集{a,b,c,d,e,f}，若各字符出现的次数分别为{6,3,8,2,10,4}，则对应字符集中各字符的哈夫曼编码可能是（）？

  • A‣00,1011,01,1010,11,100,
  • B‣00,100,110,000,0010,01,
  • C‣10,1011,11,0011,00,010,
  • D‣0011,10,11,0010,01,000,
【A】直接建造哈夫曼树得到的编码并不唯一，但是可以得出：b,d是兄弟，a,c是兄弟，兄弟结点的编码只有最后一位的差异。

🤓✍️「6」、已知二叉排序树如下图所示，元素之间应满足的大小关系是（）？



  • A‣𝓧1<𝓧2<𝓧5
  • B‣𝓧1<𝓧4<𝓧5
  • C‣𝓧3<𝓧5<𝓧4
  • D‣𝓧4<𝓧3<𝓧5
【C】中序遍历一下，𝓧1𓊆𓊈𝓧3𓊆𓊈𝓧5𓊉𝓧4𓊇𓊉𝓧2𓊇，𓊈𓊉括起来的是左子树，𓊆𓊇括起来的是右子树。

🤓✍️「7」、下列选项中，不是如下有向图的拓扑序列的是（）？



  • A‣1,5,2,3,6,4,
  • B‣5,1,2,6,3,4,
  • C‣5,1,2,3,6,4,
  • D‣5,2,1,6,3,4,
【D】按照拓扑排序规则，2不可能出现在1前面。

🤓✍️「8」、高度为5的3阶B-树含有的关键字个数至少是（）？

  • A‣15
  • B‣31
  • C‣62
  • D‣242
【B】3阶B-树中每个结点至少⌈3/2⌉-1=1个关键字，高度为5的B-树必须有exp(5)-1=31个结点。

🤓✍️「9」、现有长度为7，初始为空的散列表H，散列函数𝒉(𝓀)=𝓀%7，用线性探测再散列法解决冲突。将关键字22,43,15依次插人到H后，查找成功的平均查找长度是（）？

  • A‣1.5
  • B‣1.6
  • C‣2
  • D‣3
【C】22,43,15的𝒉(𝓀)值都是1，ASL_success=(1+2+3)÷3=2。

🤓✍️「10」、对初始数据序列(8,3,9,11,2,1,4,7,5,10,6)进行希尔排序。若第一趟排序结果为(1,3,7,5,2,6,4,9,11,10,8)，第二趟排序结果为(1,2,6,4,3,7,5,8,11,10,9)，则两趟排序采用的增量依次是（）？

  • A‣3,1,
  • B‣3,2,
  • C‣5,2,
  • D‣5,3,
【D】第一趟结果中1到了初始序列中8的位置，可确定增量是5；第二趟结果中2到了第一趟序列中3的位置，可确定增量是3。

🤓✍️「11」、在将数据序列(6,1,5,9,8,4,7)建成大根堆时，正确的序列变化过程是（）？

  • A‣6,1,7,9,8,4,5 ⮕ 6,9,7,1,8,4,5 ⮕ 9,6,7,1,8,4,5 ⮕ 9,8,7,1,6,4,5
  • B‣6,9,5,1,8,4,7 ⮕ 6,9,7,1,8,4,5 ⮕ 9,6,7,1,8,4,5 ⮕ 9,8,7,1,6,4,5
  • C‣6,9,5,1,8,4,7 ⮕ 9,6,5,1,8,4,7 ⮕ 9,6,7,1,8,4,5 ⮕ 9,8,7,1,6,4,5
  • D‣6,1,7,9,8,4,5 ⮕ 7,1,6,9,8,4,5 ⮕ 7,9,6,1,8,4,5 ⮕ 9,7,6,1,8,4,5 ⮕ 9,8,6,1,7,4,5
【A】考大根堆的调整，父结点下沉法，从最后一个非叶结点开始往前直到根结点。

ComputerOrganization

🤓✍️「12」、冯•诺依曼结构计算机中数据采用二进制编码表示，其主要原因是（）？

Ⅰ꙳二进制的运算规则简单。
Ⅱ꙳制造两个稳态的物理器件较容易。
Ⅲ꙳便于用逻辑门电路实现算术运算。

  • A‣Ⅰ,Ⅱ,
  • B‣Ⅰ,Ⅲ,
  • C‣Ⅱ,Ⅲ,
  • D‣Ⅰ,Ⅱ,Ⅲ,
【D】都是二进制的优点。

🤓✍️「13」、假定有符号整数采用补码表示，若int型变量x和y的机器数分别是0yFFFFFFDF和0y00000041，则x,y的值以及x-y的机器数分别是（）？

  • A‣x=-65，y=41，x-y的机器数溢出。
  • B‣x=-33，y=65，x-y的机器数为0yFFFFFF9D。
  • C‣x=-33，y=65，x-y的机器数为0yFFFFFF9E。
  • D‣x=-65，y=41，x-y的机器数为0yFFFFFF96。
【C】0yFFFFFFDF-0y00000041=0yFFFFFFDF+0yFFFFFFBF=0yFFFFFF9E。

🤓✍️「14」、IEEE754单精度浮点格式表示的数中，最小的规格化正数是（）？

  • A‣1.0×exp(-126)
  • B‣1.0×exp(-127)
  • C‣1.0×exp(-128)
  • D‣1.0×exp(-129)
【A】阶数的正常取值范围是1～254，相应的最小指数是-126。

🤓✍️「15」、某32位计算机按字节编址，采用小端模式。若C语句int i = 0;对应的机器代码为"C7 45 FC 00 00 00 00"，则语句int i = -64;对应的机器代码是（）？

  • A‣C7 45 FC C0 FF FF FF
  • B‣C7 45 FC 0C FF FF FF
  • C‣C7 45 FC FF FF FF C0
  • D‣C7 45 FC FF FF FF 0C
【A】容易看出题中机器代码的后8个十六进制数就是赋给i的值的补码，-64=0yFFFFFFC0。小端模式适合机器阅读，FF FF FF C0在小端模式下是C0 FF FF FF。

🤓✍️「16」、整数𝓍的机器数为11011000，分别对𝓍进行逻辑右移1位和算术右移1位操作，得到的机器数各是（）？

  • A‣11101100,11101100,
  • B‣01101100,11101100,
  • C‣11101100,01101100,
  • D‣01101100,01101100,
【B】逻辑右移补0，算术右移补符号位。

🤓✍️「17」、假定DRAM芯片中存储阵列的行数为𝓇，列数为𝒸，对于一个2K×1b的DRAM芯片，为保证其地址引脚数最少，并尽量减少刷新开销，则𝓇,𝒸的取值分别是（）？

  • A‣2048,1,
  • B‣64,32,
  • C‣32,64,
  • D‣1,2048,
【C】地址引脚数最少，𝓇,𝒸尽量相近；DRAM按行刷新，让减少刷新开销，𝓇小一点。

🤓✍️「18」、按字节编址的计算机中，某double型数组A[]的首地址为0x2000，使用变址寻址和循环结构访问数组A[]，保存数组下标的变址寄存器初值为0，每次循环取一个数组元素，其偏移地址为变址值乘以sizeof(double)，取完后变址寄存器内容自动加1。若某次循环所取元素的地址为0x2100，则进入该次循环时变址寄存器的内容是（）？

  • A‣25
  • B‣32
  • C‣64
  • D‣100
【B】sizeof(double)=8，设该次IX的内容是𝒿，0x2000+𝒿×8=0x2100 ⇒ 𝒿=32。

🤓✍️「19」、减法指令"sub R1, R2, R3"的功能为“(R1)-(R2)→R3”，执行后将生成进位／借位标志CF和溢出标志OF。若(R1)=0yFFFFFFFF，(R2)=0yFFFFFFF0，则该减法指令执行后，CF与OF分别为（）？

  • A‣CF=0,OF=0,
  • B‣CF=1,OF=0,
  • C‣CF=0,OF=1,
  • D‣CF=1,OF=1,
【A】题目没讲是有符号数还是无符号数，但是结果一样，(R1)=-1，(R2)=-16，(R1)-(R2)明显既没借位也没溢出。

🤓✍️「20」、若某计算机最复杂指令的执行需要完成5个子功能，分别由功能部件A～E实现，各功能部件所需时间分别为80ps,50ps,50ps,70ps,50ps，采用流水线方式执行指令，流水段寄存器延时为20ps，则CPU时钟周期至少为（）？

  • A‣60ps
  • B‣70ps
  • C‣80ps
  • D‣100ps
【D】80ps+20ps=100ps。

🤓✍️「21」、下列选项中，可提高同步总线数据传输率的是（）？

Ⅰ꙳增加总线宽度     Ⅱ꙳提高总线工作频率     Ⅲ꙳支持突发传输     Ⅳ꙳采用地址／数据线复用

  • A‣Ⅰ,Ⅱ,
  • B‣Ⅰ,Ⅱ,Ⅲ,
  • C‣Ⅲ,Ⅳ,
  • D‣Ⅰ,Ⅱ,Ⅲ,Ⅳ,
【B】采用地址／数据线复用是为了降低线路复杂度，节省成本。

🤓✍️「22」、下列关于外部I/O中断的叙述中，正确的是（）？

  • A‣中断控制器按所接收中断请求的先后次序进行中断优先级排队。
  • B‣CPU响应中断时，通过执行中断隐指令完成通用寄存器的保护。
  • C‣CPU只有在处于中断允许状态时，才能响应外部I/O设备的中断请求。
  • D‣有中断请求时，CPU立即暂停当前指令执行，转去执行中断服务程序。
【C】选项A，中断优先级由屏蔽字决定。选项B，中断隐指令保存的是程序计数器。选项D，CPU在指令周期的中断周期响应中断，不是立即。

OperatingSystem

🤓✍️「23」、下列关于多任务操作系统的叙述中，正确的是（）？

Ⅰ꙳具有并发和并行的特点。     Ⅱ꙳需要实现对共享资源的保护。     Ⅲ꙳需要运行在多CPU的硬件平台上。

  • A‣Ⅰ,
  • B‣Ⅱ,
  • C‣Ⅰ,Ⅱ,
  • D‣Ⅰ,Ⅱ,Ⅲ,
【C】Ⅲ꙳单个CPU也可以。

🤓✍️「24」、某系统采用基于优先权的非抢占式进程调度策略，完成一次进程调度和进程切换的系统时间开销为1us。在𝑻时刻就绪队列中有3个进程P1,P2,P3，其在就绪队列中的‧等待时间‧需要的CPU时间‧优先权如下表👇，若优先权值大的进程先获得CPU，从𝑻时刻起系统开始进程调度，系统的平均周转时间为（）？

进程等待时间需要的CPU时间优先权
P130us12us10
P215us24us30
P318us36us20
  • A‣54us
  • B‣73us
  • C‣74us
  • D‣75us
【D】P2的周转时间：15+1+24=40(us)，P3的周转时间：18+1+24+1+36=80(us)，P1的周转时间：30+1+24+1+36+1+12=105(us)，平均(40+80+105)÷3=75(us)。

🤓✍️「25」、属于同一进程的两个线程thread1和thread2并发执行，共享初值为0的全局变量x。thread1和thread2实现对全局变量x加1的机器级代码描述如下，在所有可能的指令序列中，使x的值为2的序列个数是（）？

thread1():                        |thread2():
❶mov R1, x  ; (x)→R1              |❹mov R2, x  ; (x)→R2
❷inc R1     ; (R1)+1→R1           |❺inc R2     ; (R2)+1→R2
❸mov x, R1  ; (R1)→x              |❻mov x, R2  ; (R2)→x
  • A‣1
  • B‣2
  • C‣3
  • D‣4
【B】❶❷❸❹❺❻，❹❺❻❶❷❸，2种。

🤓✍️「26」、假设系统中有4个同类资源，进程P1,P2,P3需要的该资源数分别为4,3,1，P1,P2,P3已申请到的资源数分别为2,1,0，则执行安全性检测算法的结果是（）？

  • A‣不存在安全序列，系统处于不安全状态。
  • B‣存在多个安全序列，系统处于安全状态。
  • C‣存在唯一安全序列P3,P1,P2，系统处于安全状态。
  • D‣存在唯一安全序列P3,P2,P1，系统处于安全状态。
【A】该资源还剩1个，只够P3使用，给P3用完也不够P1,P2所需。

🤓✍️「27」、下列选项中，可能导致当前进程P阻塞的事件是（）？

Ⅰ꙳进程P申请临界资源   Ⅱ꙳进程P从磁盘读数据   Ⅲ꙳ 系统将CPU分配给高优先权的进程

  • A‣Ⅰ,
  • B‣Ⅱ,
  • C‣Ⅰ,Ⅱ,
  • D‣Ⅰ,Ⅱ,Ⅲ,
【C】进程等待资源或I/O会进入阻塞态，等待CPU会进入就绪态。

🤓✍️「28」、若x是管程内的条件变量，则当进程执行x.wait()时所做的工作是（）？

  • A‣实现对变量x的互斥访问。
  • B‣唤醒一个在x上阻塞的进程。
  • C‣根据x的值判断该进程是否进人阻塞状态。
  • D‣阻塞该进程，并将之插入x的阻塞队列中。
【D】管程内的条件变量x.wait()只能做到选项D，信号量y.wait()才能做到选项C。

🤓✍️「29」、当定时器产生时钟中断后，由时钟中断服务程序更新的部分内容是（）？

Ⅰ꙳内核中时钟变量的值   Ⅱ꙳当前进程占用CPU的时间   Ⅲ꙳当前进程在时间片内的剩余执行时间

  • A‣Ⅰ,Ⅱ,
  • B‣Ⅱ,Ⅲ,
  • C‣Ⅰ,Ⅲ,
  • D‣Ⅰ,Ⅱ,Ⅲ,
【D】时钟中断处理和时间有关的所有信息。

🤓✍️「30」、系统总是访问磁盘的某个磁道而不响应对其他磁道的访问请求，这种现象称为磁臂黏着。下列磁盘调度算法中，不会导致磁臂黏着的是（）？

  • A‣先来先服务FCFS
  • B‣最短寻道时间优先SSTF
  • C‣扫描算法SCAN
  • D‣循环扫描算法CSCAN
【A】题出得不好，但FCFS很公平。

🤓✍️「31」、下列优化方法中，可以提高文件访问速度的是（）？

Ⅰ꙳提前读   Ⅱ꙳为文件分配连续的簇   Ⅲ꙳延迟写   Ⅳ꙳采用磁盘高速缓存

  • A‣Ⅰ,Ⅱ,
  • B‣Ⅱ,Ⅲ,
  • C‣Ⅰ,Ⅲ,Ⅳ,
  • D‣Ⅰ,Ⅱ,Ⅲ,Ⅳ,
【D】都能减少磁盘I/O的机械操作次数。

🤓✍️「32」、在下列同步机制中，可以实现让权等待的是（）？

  • A‣Peterson方法
  • B‣Swap指令
  • C‣Semaphore方法
  • D‣TestAndSet指令
【C】最高级的Semaphore方法，引入了阻塞机制。

ComputerNetWork

🤓✍️「33」、下列TCP/IP应用层协议中，可以使用传输层无连接服务的是（）？

  • A‣FTP
  • B‣DNS
  • C‣SMTP
  • D‣HTTP
【B】概念题。DNS基于UDP。

🤓✍️「34」、下列选项中，不属于物理层接口规范定义范畴的是（）？

  • A‣接口形状
  • B‣引脚功能
  • C‣物理地址
  • D‣信号电平
【C】概念题。物理地址即MAC地址，链路层的东西。

🤓✍️「35」、IEEE802.11无线局域网的MAC协议CSMA/CA进行信道预约的方法是（）？

  • A‣发送确认帧
  • B‣采用二进制指数退避
  • C‣使用多个MAC地址
  • D‣交换RTS与CTS帧
【D】概念题。RTS"RequestToSend"，CTS"ClearToSend"。

🤓✍️「36」、主机甲采用停等协议向主机乙发送数据，数据传输速率是3Kbps，单向传播时延是200ms，忽略确认帧的发送时延。当信道利用率等于40%时，数据帧的长度为（）？

  • A‣200b
  • B‣400b
  • C‣480b
  • D‣800b
【D】设数据帧长度𝓁b，𝓁b/3Kbps÷(𝓁b/3Kbps+2×200ms)=40% ⇒ 𝓁=800。

🤓✍️「37」、路由器R通过以太网交换机S1和S2连接两个网络，R的接口，主机H1和H2的IP地址与MAC地址如下图所示。若H1向H2发送1个IP分组P，则H1发出的封装P的以太网帧的目的MAC地址，H2收到的封装P的以太网帧的源MAC地址分别是（）？

  • A‣00-a1-b2-c3-d4-62,00-1a-2b-3c-4d-52,
  • B‣00-a1-b2-c3-d4-62,00-a1-b2-c3-d4-61,
  • C‣00-1a-2b-3c-4d-51,00-1a-2b-3c-4d-52,
  • D‣00-1a-2b-3c-4d-51,00-a1-b2-c3-d4-61,
【D】IP分组传输旅途中，MAC地址逐段链路改变，IP地址不变，不考虑NAT过程。

🤓✍️「38」、某路由表中有转发接口相同的4条路由表项，其目的网络地址分别为⁰35.230.32.0/21,¹35.230.40.0/21,²35.230.48.0/21,³35.230.56.0/21，将该4条路由聚合后的目的网络地址为（）？

  • A‣35.230.0.0/19
  • B‣35.230.0.0/20
  • C‣35.230.32.0/19
  • D‣35.230.32.0/20
【C】找最长前缀，看第三个十进制数。

🤓✍️「39」、用户数据报协议UDP实现分用"demultiplexing"时所依据的头部字段是（）？

  • A‣源端口号
  • B‣目的端口号
  • C‣长度
  • D‣校验和
【B】概念题。源端口号实现复用，目的端口号实现分用。

🤓✍️「40」、无需转换即可由简单邮件传输协议SMTP直接传输的内容是（）？

  • A‣JPEG图像
  • B‣MPEG视频
  • C‣EXE文件
  • D‣ASCII文本
【D】概念题。SMTP直接传输ASCII文本，非ASCII文本通过MIME转换。

最后修改于：2024年09月24日
© 允许规范转载
如果觉得我的文章对你有用请狠狠地打赏我