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

声明：

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

一、单项选择：

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

DataStructure

🤓✍️「1」、已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（）？

  • A、𝜪(n)
  • B、𝜪(m×n)
  • C、𝜪(min(m,n))
  • D、𝜪(max(m,n))
【D】最坏情况是两链表都从头比到尾。12年的41题考过这个。

🤓✍️「2」、一个栈的入栈序列为1,2,3,...,n，其出栈序列是p1,p2,p3,...,pn。若空p2=3，则p3可能取值的个数是（）？

  • A、n-3
  • B、n-2
  • C、n-1
  • D、无法确定
【C】显然4,5,...,n可以一直入栈直到想要作p3时出栈，再看p1只能是1或2，而相应地p3可以是2和1。

🤓✍️「3」、若将关键字1,2,3,4,5,6,7依次插入到初始为空的平衡二叉树T中，则T中平衡因子为0的分支结点的个数是（）？

  • A、0
  • B、1
  • C、2
  • D、3
【D】考平衡二叉树的插入如图。



🤓✍️「4」、已知三叉树T中6个叶结点的权分别是2,3,4,5,6,7，T的带权外部路径长度最小是（）？

  • A、27
  • B、46
  • C、54
  • D、56
【B】三叉哈夫曼树，首先叶结点个数N须满足：(N-1)%(3-1)==0，不够得先补权为0的叶结点。这里需要补1个，于是对应三叉哈夫曼树如图。最小带权路径长度=27+14+5=46。


🤓✍️「5」、若X是后序线索二叉树中的叶结点，且X存在左兄弟结点Y，则X的右线索指向的是（）？

  • A、X的父结点
  • B、以Y为根的子树的最左下结点
  • C、X的左兄弟结点Y
  • D、以Y为根的子树的最右下结点
【A】线索二叉树中，左线索指前驱右线索指后继。由题意，某结点Z的左孩子是Y右孩子是X，在后序线索中，X的后继是其父结点Z。

🤓✍️「6」、在任意一棵非空二叉排序树T1中，删除某结点v之后形成二叉排序树T2，再将v插入T2形成二叉排序树T3。下列关于T1与T3的叙述中，正确的是（）？

i'若v是T1的叶结点，则T1与T3不同。   ii'若v是T1的叶结点，则T1与T3相同。
iii'若v不是T1的叶结点，则T1与T3不同。   iv'若v不是T1的叶结点，则T1与T3相同。

  • A、i,iii
  • B、i,iv
  • C、ii,iii
  • D、ii,iv
【C】二叉排序树插入进来的新结点都是在叶结点。

🤓✍️「7」、设图的邻接矩阵A={{0,1,0,1},{0,0,1,1},{0,1,0,0},{1,0,0,0}}，各顶点的度依次是（）？

  • A、1,2,1,2
  • B、2,2,1,1
  • C、3,4,2,3
  • D、4,4,2,2
【C】按行统计各顶点的出度为(2,2,1,1)，按列统计各行的入度为(1,2,1,2)，相加得(3,4,2,3)。

🤓✍️「8」、对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是（）？



  • A、h,c,a,b,d,e,g,f
  • B、e,a,f,g,b,h,c,d
  • C、d,b,c,a,h,e,f,g
  • D、a,b,c,d,h,e,f,g
【D】a的第一层相邻结点有b,h,e，没有c。

🤓✍️「9」、下列AOE网表示一项包含8个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是（）？



  • A、c,e
  • B、d,e
  • C、d,f
  • D、f,h
【C】求得该图中有3条关键路径：(b,d,c,g)，(b,d,e,h)，(b,f,h)，只有选项C能将全部关键路径缩短。

🤓✍️「10」、在一棵高度为2的5阶B-树中，所含关键字的个数最少是（）？

  • A、5
  • B、7
  • C、8
  • D、14
【A】对于5阶B-树，根结点有5个关键字时才能分裂，成为高度为2的B-树。

🤓✍️「11」、对给定的关键字序列110,119,007,911,114,120,122进行基数排序，则第2趟分配收集后得到的关键字序列是（）？

  • A、007,110,119,114,911,120,122
  • B、007,110,119,114,911,122,120
  • C、007,110,911,114,119,120,122
  • D、110,120,911,122,114,007,119
【C】按照基数排序规则如图。



ComputerOrganization

🤓✍️「12」、某计算机主频为1.2GHz，其指令分为4类，它们在基准程序中所占比例及CPI如下表所示，该机的MIPS数是（）？

指令类型所占比例CPI
A50%2
B20%3
C10%4
D20%5
  • A、100
  • B、200
  • C、400
  • D、600
【C】基准程序平均CPI=0.5×2+0.2×3+0.1×4+0.2×5=3，该机1秒执行1.2G÷3=0.4G条指令，MIPS=400。

🤓✍️「13」、某数采用IEEE754单精度浮点数格式表示为0x C640 0000，则该数的值是（）？

  • A、-1.5×exp(13)
  • B、-1.5×exp(12)
  • C、-0.5×exp(13)
  • D、-0.5×exp(12)
【C】0xC640=0b1100011001000000，后面的全0不用看了，根据IEEE754单精度浮点数格式标准，符号是负，尾数加上1得小数=1.5，阶数减去127得指数=13。

🤓✍️「14」、某字长为8位的计算机中，已知整型变量x,y的机器数分别为{x}‾补码=1 1110100，{y}‾补码=1 0110000。若整型变量z=2*x+y/2，则z的机器数为（）？

  • A、1 1000000
  • B、0 0100100
  • C、1 0101010
  • D、溢出
【A】2*x等效于x算术左移一位，y/2等效于y算术右移一位，11101000+11011000=11000000，用十进制来算是-12×2-80÷2=-64，没溢出也没有丢失精度。

🤓✍️「15」、用海明码对长度为8位的数据进行检／纠错时，若能纠正一位错，则校验位数至少为（）？

  • A、2
  • B、3
  • C、4
  • D、5
【C】能纠正一位错的是码距为3的海明码，校验位数𝓀应满足：8+𝓀+1≤exp(𝓀)，取4即可。

🤓✍️「16」、某计算机主存地址空间大小为256MB，按字节编址。虚拟地址空间大小为4GB，采用分页式存储管理，页面大小为4KB，TLB{快表}采用全相联映射，有4个页表项，内容如下表所示，则对虚拟地址0x03FFF180进行虚实地址变换的结果是（）？

有效位标记页框号···
00xFF1800x0002···
10x3FFF10x0035···
00x02FF30x0351···
10x03FFF0x0153···
  • A、0x0153180
  • B、0x0035180
  • C、TLB缺失
  • D、缺页中断
【A】页内偏移占log(4K)=12位，故虚拟地址0x03FFF180的页面号为0x03FFF，在TLB中有，有效位为1，对应页框号是0x0153。

🤓✍️「17」、假设变址寄存器R的内容为0x1000，指令中的形式地址为0x2000；地址0x1000中的内容为0x2000，地址0x2000中的内容为0x3000，地址0x3000中的内容为0x4000，则变址寻址方式下访问到的操作数是（）？

  • A、0x1000
  • B、0x2000
  • C、0x3000
  • D、0x4000
【D】有效地址=0x1000+0x2000=0x3000。

🤓✍️「18」、某CPU主频为1.03GHz，采用4级指令流水线，每个流水段的执行需要1个时钟周期。假定CPU执行了100条指令，在其执行过程中，没有发生任何流水线阻塞，此时流水线的吞吐率为（）？

  • A、0.25×exp10(9)条指令/秒
  • B、0.97×exp10(9)条指令/秒
  • C、1.0×exp10(9)条指令/秒
  • D、1.03×exp10(9)条指令/秒
【C】一条指令分四流水段，执行100条指令共花费100+4-1=103个时钟周期，流水线的吞吐率=100条÷(103÷(1.03×exp10(9))秒)=1.0×exp10(9)条/秒。

🤓✍️「19」、下列选项中，用于设备和设备控制器{I/O接口}之间互连的接口标准是（）？

  • A、PCI
  • B、USB
  • C、AGP
  • D、PCI-Express
【B】联系生活，键鼠都可以通过USB连接到电脑上。PCI连接主存等，AGP连接网卡等，PCI-Express连接显卡等。

🤓✍️「20」、下列选项中，用于提高RAID可靠性的措施有（）？

i'磁盘镜像   ii'条带化   iii'奇偶校验   iv'增加Cache机制

  • A、i,ii
  • B、i,iii
  • C、i,iii,iv
  • D、ii,iii,iv
【B】"Redundant Arrays of Independent/Inexpensive Disks"“独立／廉价磁盘冗余阵列”，可靠性即对存储数据的检错和纠错能力。i'磁盘镜像就是数据一模一样的备份，iii'奇偶校验是典型的检错法。ii'条带化类似存储芯片的低位交叉法，用于提高对磁盘的访问速度。iv'Cache位于CPU和主存之间，和磁盘没有关系。

🤓✍️「21」、某磁盘的转速为10000rpm，平均寻道时间是6ms，磁盘传输速率是20MB/s{此处不是MBps}，磁盘控制器延迟为0.2ms，读取一个4KB的扇区所需的平均时间约为（）？

  • A、9ms
  • B、9.4ms
  • C、12ms
  • D、12.4ms
【B】寻找一个扇区平均耗时为磁盘转半圈0.5r÷10000rpm=3ms，4KB数据传输时间为4KB÷20MB/s=0.2ms，共6ms+0.2ms+3ms+0.2ms=9.4ms。

🤓✍️「22」、下列关于中断I/O方式和DMA方式比较的叙述中，错误的是（）？

  • A、中断I/O方式请求的是CPU处理时间，DMA方式请求的是总线使用权。
  • B、中断响应发生在一条指令执行结束后，DMA响应发生在一个总线事务完成后。
  • C、中断I/O方式下数据传送通过软件完成，DMA方式下数据传送由硬件完成。
  • D、中断I/O方式适用于所有外部设备，DMA方式仅适用于快速外部设备。
【D】DMA方式适用于快速外设，相应地，中断I/O方式适用于慢速外设。

OperatingSystem

🤓✍️「23」、用户在删除某文件的过程中，操作系统不可能执行的操作是（）？

  • A、删除此文件所在的目录。
  • B、删除与此文件关联的目录项。
  • C、删除与此文件对应的文件控制块。
  • D、释放与此文件关联的内存缓冲区。
【A】文件所在目录下也许还有其它文件呢。

🤓✍️「24」、为支持CD-ROM中视频文件的快速随机播放，播放性能最好的文件数据块组织方式是（）？

  • A、连续结构
  • B、链式结构
  • C、直接索引结构
  • D、多级索引结构
【A】连续结构的查询时间最短。

🤓✍️「25」、用户程序发出磁盘I/O请求后，系统的处理流程是：用户程序→系统调用处理程序→设备驱动程序→中断处理程序。其中，计算数据所在磁盘的柱面号—磁头号—扇区号的程序是（）？

  • A、用户程序
  • B、系统调用处理程序
  • C、设备驱动程序
  • D、中断处理程序
【C】明显这是与磁盘硬件相关的操作，得由设备驱动程序来做。

🤓✍️「26」、若某文件系统索引结点{inode}中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是（）？

  • A、索引结点的总数
  • B、间接地址索引的级数
  • C、地址项的个数
  • D、文件块大小
【A】每个文件对应一个索引结点，所以文件系统中索引结点的总数反映的是文件的总数。

🤓✍️「27」、设系统缓冲区和用户工作区均采用单缓冲，从外设读入1个数据块到系统缓冲区的时间为100，从系统缓冲区读入1个数据块到用户工作区的时间为5，对用户工作区中的1个数据块进行分析的时间为90。进程从外设读入并分析2个数据块的最短时间是（）？

  • A、200
  • B、295
  • C、300
  • D、390
【C】以流水线方式工作如图。

🤓✍️「28」、下列选项中，会导致用户进程从用户态切换到内核态的操作是（）？

i'整数除以零   ii'正弦sin()函数调用   iii'read系统调用

  • A、i,ii
  • B、i,iii
  • C、ii,iii
  • D、i,ii,iii
【B】中断处理和系统调用会操作系统内核态执行。

🤓✍️「29」、计算机开机后，操作系统最终被加载到（）？

  • A、BIOS
  • B、ROM
  • C、EPROM
  • D、RAM
【D】操作系统的引导程序BIOS位于主板上的ROM，开机后由BIOS指引将位于外存的完整系统加载进RAM构成的内存里。

🤓✍️「30」、若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作是（）？

i'处理越界错误   ii'置换页   iii'分配内存

  • A、i,ii
  • B、ii,iii
  • C、i,iii
  • D、i,ii,iii
【B】i'越界中断，跟缺页中断没有关系。

🤓✍️「31」、某系统正在执行三个进程P1,P2,P3，各进程的CPU时间和I/O时间比例如下表所示，为提高系统资源利用率，合理的进程优先级设置应为（）？

进程CPU时间I/O时间
P190%10%
P250%50%
P315%85%
  • A、P1>P2>P3
  • B、P3>P2>P1
  • C、P2>P1=P3
  • D、P1>P2=P3
【B】应当让I/O时间占比高的优先级更高，以便I/O外设尽早投入工作。

🤓✍️「32」、下列关于银行家算法的叙述中，正确的是（）？

  • A、银行家算法可以预防死锁。
  • B、当系统处于安全状态时，系统中一定无死锁进程。
  • C、当系统处于不安全状态时，系统中一定会出现死锁进程。
  • D、银行家算法破坏了死锁必要条件中的“请求和保持”条件。
【B】银行家算法可以避免死锁。破坏死锁的必要条件都属于预防死锁。

ComputerNetWork

🤓✍️「33」、在OSI参考模型中，下列功能需由应用层的相邻层实现的是（）？

  • A、对话管理
  • B、数据格式转换
  • C、路由选择
  • D、可靠数据传输
【B】OSI七层参考模型中，应用层的相邻层只有表示层，将网络数据转换为用户看得懂的东西。

🤓✍️「34」、若下图为10BaseT网卡接收到的信号波形，则该网卡收到的比特串是（）？



  • A、0011 0110
  • B、1010 1101
  • C、0101 0010
  • D、1100 0101
【A】10BaseT即10Mbps-基带传输-双绞线介质的以太网，采用曼彻斯特编码，以一个码元中间时刻往高电平跳变还是往低电平跳变来表示0和1，故图中的信号应为11001001或00110110。

🤓✍️「35」、主机甲通过1个路由器{存储转发方式}与主机乙互联，两段链路的数据传输速率均为10Mbps，主机甲分别采用报文交换和分组大小为10Kb{此处1K=1000}的分组交换向主机乙发送1个大小为8Mb{此处1M=exp10(6)}的报文。若忽略链路传播时延+分组头开销和分组拆装时间，则两种交换方式完成该报文传输所需的总时间分别是（）？

  • A、800ms，1600ms
  • B、801ms,1600ms
  • C、1600ms,800ms
  • D、1600ms,801ms
【D】按照题目给的换算单位和某些忽略的东西，两段链路，采用报文交换方式的传输时间为8Mb÷10Mbps×2=1600ms，采用分组交换方式有8Mb÷10Kb=800个分组，传输时间为(800+2-1)×10Kb÷10Mbps=801ms。

🤓✍️「36」、下列介质访问控制方法中，可能发生冲突的是（）？

  • A、CDMA
  • B、CSMA
  • C、TDMA
  • D、FDMA
【B】CDMA“码分复用”，TDMA“时分复用”，FDMA“频分复用”，都是静态划分信道方法，一定不会有冲突。CSMA“载波监听多址接入”，会发生冲突，相应地有冲突检测CSMA/CD和冲突避免CSMA/CA。

🤓✍️「37」、HDLC对01111100 01111110组帧后对应的比特串是（）？

  • A、01111100 00111110 10
  • B、01111100 01111101 01111110
  • C、01111100 01111101 0
  • D、01111100 01111110 01111101
【A】HDLC“高级数据链路控制”，一个在同步网络上面向比特的数据链路层协议，0111 1110是该协议帧的开始和结束标识，发送方需要在每5个连续的比特1后附加1个比特0。

🤓✍️「38」、对于100Mbps的以太网交换机，当输出端口无排队，以直通交换{cut-through switching}方式转发一个以太网帧{不包括前导码}时，引入的转发延迟至少是（）？

  • A、0us
  • B、0.48us
  • C、5.12us
  • D、121.44us
【B】以太网交换机有两种交换模式：存储转发模式{完整接受和存储整个帧检测到错误帧就丢弃}和直通交换模式{只接收帧的一小部分立即转发}，结合以太网帧格式[目的MAC地址6B|源MAC地址6B|类型2B|数据载荷46~1500B|校验码4B]，本题最少接受目的MAC地址供转发用，引入转发延迟6×8b÷10Mbps=0.48us。

🤓✍️「39」、主机甲与主机乙之间已建立一个TCP连接，双方持续有数据传输，且数据无差错与丢失。若甲收到1个来自乙的TCP段，该段的序号为1913，确认序号为2046，有效载荷为100字节，则甲立即发送给乙的TCP段的序号和确认序号分别是（）？

  • A、2046,2012
  • B、2046,2013
  • C、2047,2012
  • D、2047,2013
【B】易错题，甲发给乙的TCP段的序号就是2046，确认序号是1913+100=2013。

🤓✍️「40」、下列关于简单邮件传输协议SMTP的叙述中，正确的是（）？

i'只支持传输7比特ASCII码内容。   ii'支持在邮件服务器之间发送邮件。
iii'支持从用户代理向邮件服务器发送邮件。   iv'支持从邮件服务器向用户代理发送邮件。

  • A、i,ii,iii
  • B、i,ii,iv
  • C、i,iii,iv
  • D、ii,iii,iv
【A】iv'是第三代邮局协议POP3的。
最后修改于：2024年08月25日
© 允许规范转载
如果觉得我的文章对你有用请狠狠地打赏我