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

声明：

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

一、单项选择：

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

DataStructure

🤓✍️「1」、下列程序段的时间复杂度是（）？

count = 0;
for (k = 1; k <= n; k *= 2)
    for (j = 1; j <= n; j++)
        count++;
  • A、𝜪(log(n))
  • B、𝜪(n)
  • C、𝜪(nlog(n))
  • D、𝜪(n^2)
【C】第一层的k迭代log(n)次，第二层的j迭代n次。

🤓✍️「2」、假设栈初始为空，将中缀表达式a/b+(c*d-e*f)/g转换为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是（）？

  • A、+(*-
  • B、+(-*
  • C、/+(*-*
  • D、/+-*
【B】过程如下。



🤓✍️「3」、循环队列放在一维数组A[0...(M-1)]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空。下列判断队空和队满的条件中，正确的是（）？

  • A、队空：end1 == end2；             队满：end1 == (end2+1) mod M
  • B、队空：end1 == end2；             队满：end2 == (end1+1) mod (M-1)
  • C、队空：end2 == (end1+1) mod M；   队满：end1 == (end2+1) mod M
  • D、队空：end1 == (end2+1) mod M；   队满：end2 == (end1+1) mod (M-1)
【A】考虑最简单的队满情况，end1=0,end2=M，队中M-1个元素，然后元素不停地从队尾出队，使得end1=0,end2=0时队空，可确定选项A。队中元素个数为(end2-end1)modM。

🤓✍️「4」、若对如下的二叉树进行中序线索化，则结点x的左右线索指向的结点分别是（）？



  • A、e,c
  • B、e,a
  • C、d,c
  • D、b,a
【D】该二叉树的中序序列为d,e,b,x,a,c，x的左右分别是b,a。

🤓✍️「5」、将森林F转换为对应的二叉树T，F中叶结点的个数等于（）？

  • A、T中叶结点的个数
  • B、T中度为1的结点个数
  • C、T中左孩子指针为空的结点个数
  • D、T中右孩子指针为空的结点个数
【C】普通树转二叉树的规则是：“每个分支结点只保留第一个孩子，其余的孩子依次变为左边兄弟的右孩子。”“在转化来的二叉树中左孩子原本是长子，右孩子原本是次弟。”。森林转二叉树的规则是：“每棵普通树先转二叉树，只保留第一棵树的根，其余的根都变为左边根的右孩子。”。F中的叶结点在T中可能有右孩子，但一定没有左孩子。

🤓✍️「6」、5个字符有如下4种编码方案，不是前缀编码的是（）？

  • A、01,0000,0001,001,1
  • B、011,000,001,010,1
  • C、000,001,010,011,100
  • D、0,100,110,1110,1100
【D】110是1100的前缀。

🤓✍️「7」、对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是（）？



  • A、3,1,2,4,5,6
  • B、3,1,2,4,6,5
  • C、3,1,4,2,5,6
  • D、3,1,4,2,6,5
【D】按照拓扑排序的算法。



🤓✍️「8」、用哈希方法处理冲突时可能出现聚集现象，下列选项中会受聚集现象直接影响的是（）？

  • A、存储效率
  • B、散列函数
  • C、装填因子
  • D、平均查找长度
【D】聚集现象会增大平均查找长度，要尽量避免聚集现象。

🤓✍️「9」、一棵4阶B-树，具有15个关键字，含有的结点个数最多是（）？

  • A、5
  • B、6
  • C、10
  • D、15
【D】关键字个数不变，要求结点数量最多。4阶B-树中非根结点至少要有1个关键字，取每个结点含1个关键字分2叉，15个结点刚好4层，失败结点只出现在第5层，符合B-树定义。

🤓✍️「10」、用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9,1,4,13,7,8,20,23,15，则该趟排序采用的增量可能是（）？

  • A、2
  • B、3
  • C、4
  • D、5
【D】猜测：增量可能是3，验证：(9,13,20),(1,7,23),(4,8,15)均为升序，猜测成功。

🤓✍️「11」、下列选项中，不可能是快速排序第2趟排序结果的是（）？

  • A、2,3,5,4,6,7,9
  • B、2,7,5,6,4,3,9
  • C、3,2,5,4,7,6,9
  • D、4,2,3,5,7,6,9
【C】选项C中只找得到1个枢轴‘9’，找不到第2个。

ComputerOrganization

🤓✍️「12」、程序P在机器M上的执行时间是20秒，编译优化后，P执行的指令数减少到原来的70%，而CPI增加到原来的1.2倍，则P在M上的执行时间是（）？

  • A、8.4秒
  • B、11.7秒
  • C、14秒
  • D、16.8秒
【D】20s×70%×1.2=16.8s。

🤓✍️「13」、若x=103,y=-25，则下列表达式采用8位定点补码运算实现时，会发生溢出的是（）？

  • A、x+y
  • B、-x+y
  • C、x-y
  • D、-x-y
【C】8位整数补码可表示范围为：-128~127，x-y=128，溢出。

🤓✍️「14」、float型数据据常用IEEE754单精度浮点格式表示。假设两个float型变量x和y分别存放在32位寄存器f1和f2中，若(f1)=0xCC900000，(f2)=0xB0C00000，则x和y之间的关系为（）？

  • A、x<y且符号相同
  • B、x<y且符号不同
  • C、x>y且符号相同
  • D、x>y且符号不同
【A】由IEE754单精度浮点格式标准，x和y都是负数，x的阶数为10011001，y的阶数为01100001，明显x的绝对值大。

🤓✍️「15」、某容量为256MB的存储器由若干4M×8b的DRAM芯片构成，该DRAM芯片的地址引脚和数据引脚总数是（）？

  • A、19
  • B、22
  • C、30
  • D、36
【A】256MB是干扰信息。8b：数据引脚8根，4M：地址引脚本需22根，但DRAM芯片里的电容是矩阵式排列，地址可分行号列号两次传送，故地址引脚只要11根。

🤓✍️「16」、采用指令Cache与数据Cache分离的主要目的是（）？

  • A、降低Cache的缺失损失
  • B、提高Cache的命中率
  • C、降低CPU平均访存时间
  • D、减少指令流水线资源冲突
【D】在指令流水线中，一条指令的取指阶段与前面某条指令的取数阶段有重合部分，若指令Cache与数据Cache不分离，两条指令就有Cache冲突。



🤓✍️「17」、某计算机有16个通用寄存器，采用32位定长指令字，含寻址方式位的操作码字段为8位，Store指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式。若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则Store指令中偏移量的取值范围是（）？

  • A、-32768 ~ +32767
  • B、-32767 ~ +32768
  • C、-65536 ~ +65535
  • D、-65535 ~ +65536
【A】指明源操作数在哪个寄存器需要log(16)=4位，指明目的操作数的内存基址寄存器需要4位，留给偏移量的还剩32-8-4-4=16位，16位补码表示范围为-exp(15) ~ +exp(15)-1。

🤓✍️「18」、某计算机采用微程序控制器，共有32条指令，公共的取指令微程序包含2条微指令，各指令对应的微程序平均由4条微指令组成，采用断定法〔下地址字段法〕确定下条微指令地址，则微指令中下地址字段的位数至少是（）？

  • A、5
  • B、6
  • C、8
  • D、9
【C】易错题。微指令共有2+32×4=130条，下地址至少需⌈log(130)⌉=8位。

🤓✍️「19」、某同步总线采用数据线和地址线复用方式，其中地址／数据线有32根，总线时钟频率为66MHz，每个时钟周期传送两次数据〔上升沿和下降沿各传送一次数据〕，该总线带宽是（）？

  • A、132MB/s
  • B、264MB/s
  • C、528MB/s
  • D、1056MB/s
【C】2×4B×66MHz=528MB/s。

🤓✍️「20」、一次总线事务中，主设备只需给出一个首地址，从设备就能从首地址开始的若干连续单元读出或写入多个数据。这种总线事务方式称为（）？

  • A、并行传输
  • B、串行传输
  • C、突发传输
  • D、同步传输
【C】概念题。

🤓✍️「21」、下列有关I/O接口的叙述中，错误的是（）？

  • A、状态端口和控制端口可以合用同一个寄存器。
  • B、I/O接口中CPU可访问的寄存器称为I/O端口。
  • C、采用独立编址方式时，I/O 端口地址和主存地址可能相同。
  • D、采用统一编址方式时，CPU不能用访存指令访问I/O端口。
【D】I/O接口与内存统一编址就是为了用访存指令访问I/O端口。

🤓✍️「22」、若某设备中断请求的响应和处理时间为100ns，每400ns发出一次中断请求，中断响应所允许的最长延迟时间为50ns，则在该设备持续工作过程中，CPU用于该设备的I/O时间占整个CPU时间的百分比至少是（）？

  • A、12.5%
  • B、25%
  • C、37.5%
  • D、50%
【B】允许延迟50ns是干扰信息。100ns÷400ns=12.5%。



OperatingSystem

🤓✍️「23」、下列调度算法中，不可能导致饥饿现象的是（）？

  • A、时间片轮转
  • B、静态优先数调度
  • C、非抢占式短作业优先
  • D、抢占式短作业优先
【A】时间片轮转是很公平的。

🤓✍️「24」、某系统有n台互斥使用的同类设备，3个并发进程分别需要3,4,5台设备，可确保系统不发生死锁的设备数n最小为（）？

  • A、9
  • B、10
  • C、11
  • D、12
【B】似09年第25题。根据组合数学中的鸽笼原理，考虑最极端的情况。3个进程各占据2,3,4台设备时，系统没有多余设备就会死锁，但凡多1台就不会死锁。

🤓✍️「25」、下列指令中，不能在用户态执行的是（）？

  • A、trap指令
  • B、jump指令
  • C、压栈指令
  • D、关中断指令
【D】关中断指令为特权指令，必须在内核态执行。

🤓✍️「26」、一个进程的读磁盘操作完成后，操作系统针对该进程必做的是（）？

  • A、修改进程状态为就绪态
  • B、降低进程优先级
  • C、给进程分配用户内存空间
  • D、增加进程时间片大小
【A】进程在运行态时想要读磁盘时会把自身阻塞，读完后操作系统理应将其改为就绪态。

🤓✍️「27」、现有一个容量为10GB的磁盘分区，磁盘空间以簇为单位进行分配，簇的大小为4KB，若采用位图法管理该分区的空闲空间，即用一个位标识一个簇是否被分配，则存放该位图所需簇的个数为（）？

  • A、80
  • B、320
  • C、80K
  • D、320K
【A】总共10GB÷4KB=2.5M个簇，位图大小为2.5Mb，位图放在磁盘里需2.5Mb÷4KB=80个簇。

🤓✍️「28」、下列措施中，能加快虚实地址转换的是（）？

i´增大TLB容量。   ii´让页表常驻内存。   iii´增大交换区。

  • A、i
  • B、ii
  • C、i,ii
  • D、ii,iii
【C】i´增大TLB容量可以减少页表项转换次数。ii´让页表常驻内存可以省去从外存调页表的开销。iii´增大交换区就是增大虚拟内存大小，跟虚实地址转换没关系。

🤓✍️「29」、在一个文件被用户进程首次打开的过程中，操作系统需做的是（）？

  • A、将文件内容读到内存中
  • B、将文件控制块读到内存中
  • C、修改文件控制块中的读写权限
  • D、将文件的数据缓冲区首指针返回给用户进程
【B】open(file)系统调用将文件控制块读到内存中，read(file)系统调用才是将文件内容读到内存中。

🤓✍️「30」、在页式虚拟存储管理系统中，采用某些页面置换算法，会出现Belady异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady异常现象的是（）？

i´LRU算法。   ii´FIFO算法。   iii´OPT算法。

  • A、ii
  • B、i,ii
  • C、i,iii
  • D、ii,iii
【A】概念题。只有FIFO页面置换算法会出现Belady异常。

🤓✍️「31」、下列关于管道通信的叙述中，正确的是（）？

  • A、一个管道可实现双向数据传输。
  • B、管道的容量仅受磁盘容量大小限制。
  • C、进程对管道进行读操作和写操作都可能被阻塞。
  • D、一个管道只能有一个读进程或一个写进程对其操作。
【C】管道对于进程而言就像共享文件。半双工通信机制，数据在某时刻只能往一个方向传输。管道位于内存中，不受磁盘限制。一个管道可以被多个进程使用，但在某一时刻只能被一个读进程或写进程操作。当管道空时读操作被阻塞，当管道满时写操作被阻塞。

🤓✍️「32」、下列选项中，属于多级页表优点的是（）？

  • A、加快地址变换速度
  • B、减少缺页中断次数
  • C、减少页表项所占字节数
  • D、减少页表所占的连续内存空间
【D】当页表太大时，内存中可能很难找到这么大的连续空闲空间，将页表再分级，可以把每张小页表控制在一页之内，减少页表所占的连续内存空间。

ComputerNetWork

🤓✍️「33」、在OSI参考模型中，直接为会话层提供服务的是（）？

  • A、应用层
  • B、表示层
  • C、传输层
  • D、网络层
【C】OSI七层参考模型中，会话层下面是传输层。

🤓✍️「34」、某以太网拓扑及交换机当前转发表如下图所示，主机00-e1-d5-00-23-a1向主机00-e1-d5-00-23-c1发送1个数据帧，主机00-e1-d5-00-23-c1收到该帧后，向主机00-e1-d5-00-23-a1发送1个确认帧，交换机对这两个帧的转发端口分别是（）？



  • A、{3}和{1}
  • B、{2,3}和{1}
  • C、{2,3}和{1,2}
  • D、{1,2,3}和{1}
【B】主机a1的数据帧会被交换机盲目转发，转发前留下了a1的记录，当主机c1发回确认帧时，目的MAC地址在转发表里能找到。

🤓✍️「35」、下列因素中，不会影响信道数据传输速率的是（）？

  • A、信噪比
  • B、频率宽带
  • C、调制速率
  • D、信号传播速度
【D】由香农公式，信道极限数据传输速率受频率宽带和信噪比影响。奈氏准则中的码元传输速率也称为调制速率。信号在介质上的传播速度与信道的发送速率无关。

🤓✍️「36」、主机甲与主机乙之间使用后退N帧协议GBN传输数据，甲的发送窗口尺寸为1000，数据帧长为1000字节，信道带宽为100Mbps，乙每收到一个数据帧立即利用一个短帧〔忽略其发送时延〕进行确认，若甲乙之间的单向传播时延是50ms，则甲可以达到的最大平均数据传输速率约为（）？

  • A、10Mbps
  • B、20Mbps
  • C、80Mbps
  • D、100Mbps
【C】GBN中，甲发送第1个数据帧开始至收到乙第1个确认帧的往返传播途中，约100ms内可将发送窗口中的1000×1000B全发出去，最大平均数据传输速率约80Mbps。



🤓✍️「37」、站点A,B,C通过CDMA共享链路，A,B,C的码片序列分别是(1,1,1,1),(1,-1,1,-1),(1,1,-1,-1)。若C从链路上收到的序列是(2,0,2,0,0,-2,0,-2,0,2,0,2)，则C收到A发送的数据是（）？

  • A、000
  • B、101
  • C、110
  • D、111
【B】将C收到的序列与A的码片序列做规格化点积运算，(2,0,2,0,0,-2,0,-2,0,2,0,2)•(1,1,1,1)/4=(1,-1,1)，-1视作比特0。

🤓✍️「38」、主机甲和主机乙已建立了TCP连接，甲始终以MSS=1KB大小的段发送数据，并一直有数据发送；乙每收到一个数据段都会发出一个接收窗口为10KB的确认段。若甲在t时刻发生超时时拥塞窗口为8KB，则从t时刻起，不再发生超时的情况下，经过10个RTT后，甲的发送窗口是（）？

  • A、10KB
  • B、12KB
  • C、14KB
  • D、15KB
【A】t时刻发生超时，慢开始门限降为4KB，发送窗口缩为1KB，10个RTT发送窗口变化应为：2,4,5,6,7,8,9,10,11,12，同时发送窗口受接收窗口限制，只能涨到10KB。选项BCD是怎样都不能选的。

🤓✍️「39」、下列关于用户数据报协议UDP的叙述中，正确的是（）？

i´提供无连接服务。   ii´提供复用／分用服务。   iii´通过差错校验，保障可靠数据传输。

  • A、i
  • B、i,ii
  • C、ii,iii
  • D、i,ii,iii
【B】概念题。UDP无连接不可靠，有差错检测也只是丢弃出错帧。使用端口来区分不同进程，为应用进程提供复用／分用服务。

🤓✍️「40」、使用浏览器访问某大学Web网站主页时，不可能使用到的协议是（）？

  • A、PPP
  • B、ARP
  • C、UDP
  • D、SMTP
【D】SMTP与发送电子邮件有关，与单纯地访问Web网站无关。
最后修改于：2024年10月07日
© 允许规范转载
如果觉得我的文章对你有用请狠狠地打赏我