2013年考研计算机统考408真题
一、单项选择题
1.已知两个长度分别为m和n的升序链表，若将它们合并为长度为m+n的降序链表，则最坏下的时间复杂度是    1    。
A.O(n)
B.O(m*n)
C.O(min(m, n))
D.O(max(m, n))
2.一个栈的入栈序列为1,2,3,…,n，其出栈序列是p1,p2,p3,…,pn，若p2=3，则p3可能取值的个数是        2    。
A.n-3
B.n-2
C.n-1
D.无法确定
3.若将关键字1,2,3,4,5,6,7依次插入到初始为空的平衡二叉树T中，则T中平衡因子为0的分支结点的个数是    3    。
A.0
B.1
C.2
D.3
4.已知二叉树T中6个叶结点的权分别是2,3,4,5,6,7，T的带权（外部）路径长度最小是    4    。
A.27
B.46
C.54
D.56
5.若X是后序线索二叉树中的叶结点，且X存在左兄弟结点Y。则X的右线索指的是        5    。
A.X的父结点
B.以Y为根的子树的最左下结点
C.X的左兄弟结点Y
D.以Y为根的子树的最右下结点
6.在任意一棵非空二叉排序树T1中，删除某结点v之后形成二叉排序树T2，再将v插入T东风标致408论坛2形
成二叉排序树T3.下列关于T1与T3的叙述中，正确的是    6    。
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
7.设图的邻接矩阵A如下所示。各顶点的度依次是    7    。
A.1,2,1,2
B.2,2,1,1,
C.3,4,2,3
D.4,4,2,2
8.若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是    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
9.下列AOE网表示一项包含8个活动的工程，通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是        9    。
A.c和e
B.d和c
C.f和d
D.f和h
10.在一颗高度为2的5阶B树中，所含关键字的个数最少是    10    。
A.5
B.7
C.8
D.14
11.对给定的关键字序列110,119,007,911,114,120,122进行基数排序，则第2趟分配收集后得到的关键字序列是    11    。
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
12.某计算机主频为1.2GHz，其指令分为4类，它们在基准程序中所占比例与CPI如下表所示。
该机的MIPS数是        12    。
A.100
B.200
C.400
D.600
13.某数采用IEEE754单精度浮点数格式表示为C640 0000H，则该数的值是    13    。
A.-1.5*213
B.-1.5*212
C.-0.5*213
D.-0.5*212
14.某字长为8位的计算机中，已知整型变量x,y的机器数分别为[x]补=1 1110100，[y]补=1 011000。若整型变量z=2*x+y/2，则z的机器数为    14    。
A.1 1000000
B.0 0100100
C.1 0101010
D.溢出
15.用海明码对长度为8位的数据进行检/纠错时，若能纠正一位错，则校验位数至少为    15    。
A.2
B.3
C.4
D.5
16.某计算机主存地址空间大小为256MB，按字节编址。虚拟地址空间大小为4GB，采用页
式存储管理，页面大小为4KB，TLB（快表）采用全相联映射，有4个页表项，容如下表所示。
则对虚拟地址03FF F180H进行虚实地址变换的结果是    16    。
A.015 3180H
B.033 5180H
C.TLB缺失
D.缺页
17.假设变址寄存器R的容为1000H，指令中的形式地址为2000H；地址1000H中的容为200
0H，地址2000H中的容为3000H，地址3000H中的容为4000H，则变址寻址方式下访问到的操作数是    17    。
A.1000H
B.2000H
C.3000H
D.4000H
18.某CPU主频为1.03GHz，采用4级指令流水线，每个流水段的执行需要1个时钟周期。假定CPU执行了100条指令，在其执行过程中，没有发生任何流水线阻塞，此时流水线的吞吐率为    18    。
A.0.25*109条指令/秒
B.0.97*109条指令/秒
C.1.0*109条指令/秒
D.1.03*109条指令/秒
19.下列选项中，用于设备和设备控制器（I/O接口）之间互连的接口标准是    19    。
A.PCI
B.USB
C.AGP
D.CPI-Express
20.下列选项中，用于提高RAID可靠性的措施有    20    。
I.磁盘镜像
II.条带化
III.奇偶校验
IV.增加Cache机制
A.仅I、II
B.仅I、III
C.仅I、III和IV
D.仅II、III和IV
21.某磁盘的转速为10 000转/分，平均寻道时间是6ms，磁盘传输速率是20MB/s，磁盘控制器延迟为0.2ms，读取一个4KB的扇区所需的平均时间约为    21    。
A.9ms
B.9.4ms
C.12ns
D.12.4ns
22.下列关于中断I/O方式和DMA方式比较的叙述中，错误的是    22    。
A.中断I/O方式请求的是CPU处理时间 ，DMA方式请求的是总线使用权
B.中断响应发生在一条指令执行结束后，DMA响应发生在一个总线事务完成后
C.中断I/O方式下数据传送通过软件完成，DMA方式下数据传送由硬件完成
D.中断I/O方式适用于所有外部设备，DMA方式仅适用于快速外部设备
23.用户在删除某文件的过程中，操作系统不可能执行的操作是        23    。
A.删除此文件所在的目录
B.删除与此文件关联的目录项
C.删除与此文件对应的文件控制块
D.删除与此文件关联的存缓冲区
24.为支持CD-ROM中视频文件的快速随机播放，播放性能最好的文件数据块组织方式是    24    。
A.连续结构
B.链式结构
C.直接索引结构
D.多级索引结构
25.用户程序发出磁盘I/O请求后，系统的处理流程是：用户程序→系统调用处理程序→设备驱动程序→中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序是        25    。
A.用户程序
B.系统调用处理程序
C.设备驱动程序
D.中断处理程序
26.若某文件系统索引结点（inode）中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是        26    。
A.索引结点的总数
B.间接地址索引的级数
C.地址项的个数
D.文件块大小
27.设系统缓冲区和用户工作区均采用单缓冲，从外设读入1个数据块到系统缓冲区的时间为100，从系统缓冲区读入1个数据块到用户工作区的时间为5，对用户工作区的1个数据块进行分析的时间为90（如下图所示）。进程从外设读入并分析2个数据块的最短时间为    27    。