2017年考研计算机统考408真题

2017年考研计算机统 408真 考题一、单项选择题下列函数的时间复杂度是1。int func(int n)1.int i = 0; sum = 0;while( sum n) sum += +i; return i;A.B.O(logn)O(ni/2 )2.3.4.5.为C.D.O(n)O(nlogn)下列关于栈的叙述中，错误的是2。I采用非递归方式重写递归程序时必须使用栈II函数调用时，系统要用栈保存必要的信息III只要确定了入栈的次序，即可确定出栈次 IV栈是一种受限的线性表，允许在其两端进行操作A.仅IB.仅 I、II、 IIIC.仅 I、III、IVD.仅 II、III、IV适用于压缩存储稀疏矩阵的两种存储结构是3 。A.B.C.D.三元组表和十字链表 三元组表和邻接矩阵 十字链表和二叉链表 邻接矩阵和十字链表要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足的条件是4只有左子树只有右子树结点的度均为1结点的度均为2A.B.C.D.已知一棵二叉树的树形如下图所示，其后序丿的结点是 5。一e,丿-x 结点 O Oa,c,b,d,g,f,树中与 a同层A. cB. dDg6.已知字符集a,b,c,d,e,f,g,h,若各字符的哈夫曼编码依次是 0100,10,0000,0101,001,011,11,0001，贝 I编码序列0100011001001011110101 的译码结果是 6。A. a c g a b f hB. a d b a g b bC.7.8.D.a f e e f g d已知无向图G含有16条边，其中度为4的顶点个数 为 其他顶点的度均小于3。A.B.C.D.G所含的顶点个数至少是43,度为3的顶点个数为，7。1013 :15屛（不含外部结点）的是8。E为折半查找判定树F列二叉树中，可C.9. 下列应用中，适合使用B+树的是9。A. 编译器中的词法分析B关系数据库系统中的索引C. 网络中的路由表快速查找D一操作系统的磁盘空闲块管理10. 在内部排序中，若选择了归并排序而没有选择插入排序，贝何能的理由是1A. 仅 IIB. 仅 IIIC. 仅 I、 IID. 仅I/ III11. 下列排序方法中，若将顺序存储更换为链式存储，贝I算法的时间效果会降低的是11 。I插入排序 II选择排序III 起泡排序IV希尔排序A.仅 I、IIB仅II、IIIC.仅 III、IVD.仅 IV、V12假定计算M1和机M21.2GHz。在 M1 和M2V.堆排序ISA），主频分别为1.5GHz 具有相同的指令集体系结构（和P,平均CPI分别为2和1,则程序P 上运行某基准程序在M1和M2 上运行时间的比值是12A. 0.40.62B. 5C. 1.6D. 2.513. 某计算机主存按字节编址， 由 4 个 64M*8 位的 DRAM 芯片采用交叉编址方式构成double 并与宽度为 32 位的存储器总线相连，主存每次最多读写 32 位数据。若 型 变量x的主存地址 804 001AH,则读取x需要的存储周为期是13 。A. 1B. 2C. 3D. 414. 某 C 语言程序段如下 for(i = 0; i = 9; i+) lemp = 1;for(j 0; j = I; j+) temp *= aj;sum += temp;A.时间局部性和空间局部性皆有B.无时间局部性，有空间局部性C.有时间局部性，无空间局部性D.时间局部性和空间局部性皆无15.下列寻址方式中，最适合按下标顺序访问一维数组兀素的是15 。A.相对寻址B.寄存器寻址C.直接寻址D.变址寻址16.某计算机按字节编址，指令字长固定且只有两种指令格式，其中三地址指令14F列关于数组a的访问局部性的描述中，正确的是O24位26位28位32位17.下列关于超标量流水线特性的叙述中，正确的是16。29条，二地址指令107条，每个地址字段为6位，则指令字长至少应该是16。A.B.C.D.A. 仅 IIB. 仅 I、 IIIC. 仅 II、 IIID. I、 II 和 III18. 下列关于主存储器（MM ）和控制存储器（CS）的叙述中，错误的 18。A. MM 在CPU夕卜，CS在CPU内B. MM按地址访问，CS按内存访问C. MM存储指令和数据，CS存储微指令D. MM用RAM和ROM实现，CS用ROM实现 1919. 下列关于指令流水线数据通路的叙述中，错误的是。A. 包含生成控制信号的控制部件B. 包含算法逻辑运算部件（ALU）C. 包含通用寄存器组和取指部件D. 由组合逻辑电路和时序逻辑电路组合而成_20. 下列关于多总线结构的叙述中，错误的是20。A. 靠近 CPU 的总线速度较快B. 存储器总线可支持突发传送方式C. 总线之间须通过桥接器相连D. PC I_Express*16采用并行传输方式2121. I/O指令实现的数据传送通常发生在。A. I/O 设备和 I/O 端口之间B. 通用寄存器和 I/O 设备之间C. I/O 端口和 I/O 端口之间D. 通用寄存器和I/O端口之间22 。22. 下列关于多重中断系统的叙述中，错误的是A. 在一条指令执行结束时响应中断 B中断处理期间CPU处于关中断状态C.中断请求的产生与当前指令的执行无关DCPU通过采样中断23假设4个作业到达系统请求信号检测中断请求的时刻和运行时间如下表所示作业JT到达时间t运行时间返回用户态执行陷入(trap )指令 传递系统调用参数 执行相应的服务程序24。正确的执行顺序是 A. 2) 3)1)4)B. 2) 3) 3)1)25.某计算机按字节编址，其动态分区内存管理采用最佳适应算法，每次分配和 回收内存后都对空闲分区链重新排序。当前空闲分区信息如下所示。分区起始地址分区大小20K40KB60K、大小为500K80KB140KB的分区后，回收起始地址为链第一个分区的起始地址和大小分别1000K200K100KB200KB系统中空闲分区的数量、空闲 分区是A.3、B.3C.4D.4、20K、380KB500K、 80KB20K、 180KB500K、 80KB25 。J213J312J431系统在t=2时开始作业调度。若分别采用先来先服务和短作业优先调度算法，则选中的作业分别是 23A.J2、J3B.J1、J4C.J2、J4D.J1、J324.执行系统调用的过程包括如下主要操作:1)2)3)26. 某文件系统的簇和磁盘扇区大小分别 为 则系统分配给该文件的磁盘空间大小是A. 1026BB. 1536B1KB和512B。若一个文件的大小 1026B 为，4)C. 1538BD. 2048B2727. 下列有关基于时间片的进程调度的叙述中，错误的是。A. 时间片越短，进程切换的次数越多，系统开销也越大B. 当前进程的时间片用完后，该进程状态由执行态变为阻塞态C. 时钟中断发生后，系统会修改当前进程在时间片内的剩余时间D. 影响时间片大小的主要因素包括响应时间、系统开销和进程数量等。28. 与单道程序系统相比，多道程序系统的优先是28 。I. CPU利用率高II系统开销小III 系统吞吐量大IV.I/O设备利用率高A.仅I、IIIB.仅I、IVC.仅II、IIID.仅I、III、IV29. 下列选项中，磁盘逻辑格式化程序所做的工作是29。I对磁盘进行分区II建立文件系统的根目录III 确定磁盘扇区校验码所占位数IV对保存空闲磁盘块信息的数据结构进行初始化A. 仅 IIB. 仅 II、IVC. 仅 III、IVD. 仅 I、 II、 IV某文件系统中，针对每个文件，用户类别分3为4类：安全管理员、文件主、文件主5种：完全控制、执行、修改、读取、写入。 的伙伴、其他用户；访问权限分为若为表示不同类别用户对一个文件的访 文件控制块中用二进制位串表示文件权限，问权限，则描述文件权限的位数至少应为3。A. 5B. 9C. 12D. 2若文件fl的硬链接为f2,两个进程分别打fl和f2,获得对应的文件描述符为31. 开fd1和 fd2 ，则下列叙述中，正确的是 3l 。I. fl 和 f2 的读写指针位置保持相同II. fl 和 f2 共享同一个内存索引结点III. fdl 和 fd2 分别指向各自的用户打开文件表中的一项A. 仅 IIIB. 仅 II、 IIIC. 仅 I、 IID. I、 II 和 III32. 系统将数据从磁盘读到内存的过程包括以下操作：1) DMA 控制器发出中断请求2) 初始化 DMA 控制器并启动磁盘3) 从磁盘传输一块数据到内存缓冲区4) 执行“ DMA结束”中断服务程序32正确的执行顺序是。A. 3)1)2)4)B. 2)3)1)4)C_ 2)_1)3)4)C. 1)2)4)3)33假设OSI参考模型的应用层欲发送400B的数据(无拆分)，除物理层和应用层 之处，其他各层在封装PDU时均引入20B的额外开销，则应用层数据传输效率约 为33。A. 80%B 83%C. 87%D. 91%若信道在无噪声情况下的极限数据传输速率不小于信噪比30dB条件下的极限H发送一个封装访InternetIP分组的IEEE35在下图所示的网络中，若主机 问802.11数据帧F，则帧F的地址1、地址2和地址3分别是35 。A. 00-12-34-56-78-9a,00-12-34-56-78-9b,00-12-34-56-78-9cB 00-12-34-56-78-9b,00-12-34-56-78-9a,00-12-34-56-78-9cC. 00-12-34-56-78-9b,00-12-34-56-78-9c,00-12-34-56-78-9aD. 00-12-34-56-78-9a,00-12-34-56-78-9c,00-12-34-56-78-9b36. 下列IP地址中，只能作为IP分组源IP地址但不能作为目的IP地址是 36A.0.0.0.0B.127.0.0.1C.200.10.10.3D.255.255.255.25537. 直接封装RIP，OSPF，BGP报文的协议分别是37 。A. TCP、 UDP、 IPB. TCP、 IP、 UDPC. UDP、 TCP、 IPD. UDP、 IP、 TCP128 个规模IP38. 若将网络 21.3.0.0/16 划分为相同的子网，则每个子网可分配的最大地址个数是 38 。A. 254A. 数据连接在每次数据传输完毕后就关闭B.B. IC. 彳接二、综合应F41.请设计(通过算法的制连接在 务器与客 户端与服 题丿务器的话期间保持打开状态、鶴TCP 20端口建立数据连接 tCp.2i端口建立控制连亠一个算法t括号反映操作符的计算次序 J输入时：I勺表(二叉树)转 F输出。例如为等当下列两棵表中缀表达式川 为B.256C.510D.51239. 若甲向乙发起了一个TCP连接，最大段长MSS=KB, RTT=5ms，乙开辟的接收缓存为64KB，贝I甲从连接建立蒽至发送窗口达到32KB，需经过的时间至少是38 。A.25msB.30msC.160msD.165ms40. 下列关于FTP协议的叙述中，错误的是 40衣次给出按算法选出的边。键之处给出注释。生成树(MST)。请回答下语言描输出的等价中缀表达式分别为(a+b)*(c+(-d)和(a*b)+(-(-c-d)。 二叉树结点定义如下：Typedef struct nodechar data10;/存储操作数或操作符Struct node * le仕，* right;BTree;要求：(1) 给出算法的基本设计思想。(2) 根据设计思想，采用C或42 使用Prim (普里姆)算法求带权连通 列问题。(1) 对下列图G,从顶点A开始)(2) 图G的MST是唯一的吗？J 对任意的带权连通图，满足什么条件时，其MST是唯一的？，计算 f(n) 的 C 语言函 f1 如43 已知数下：1int f1(unsigned n)2int sum = 1, power = 1;3for(unsigned i =0; i = n-1; i+)4power *= 2;5sum += power;67return sum;8将 f1 中的int 都改为 float ，可得到计算f(n)的另一个函数f2。假设unsigned 和 int型数据都占 32 位， float 采用 IEEE 754 单精度标准。 请回答下列问题。(1) 当n=0时，fl会出现死循环，为什么？若将fl中的变量i和n都定义为int 型，则 f1 是否还会出现死循环？为什么？(2) f1(23)和f2(23)的返回值是否相等？机器数各是什么(用十六进制表示)？(3) F1(24)和f2(24)的返回值分别为 33 554 431和33 554 4320,为什么不相等？(4) f(31)=232-1，而f1(31)的返回值却为-1，为什么？若使fl(n)的返回值与f(n) 相等，则最大的 n 是多少？(5) F2(127)的机器数为7F80 0000H，对应的值是什么?若使f2(n) 的结果不溢出， 则最大的 n 是什么？若使 f2(n) 的结果精确(无舍入) ，则最大的 n 是多少？44 在按字节编址的计算机 M 上，题 43 中 f1 的部分源程序(部分)与对应的机器级代码(包括指令的虚拟地址)如下：int f1(unsigned n)10040102055push ebp for(unsigned i = 0; i =n-1; i+) cmp dword ptrebp-200040105E39 4D F4 0Ch, ecx power *= 2; 2300401066D1 E2shledx,l return sum; 350040107FC3ret其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令。请回答下列问题。(1)计算机M是RISC还是CISC？为什么？(2) f1 的机器指令代码共占多少字节？要求给出计算过程。 第20条指令cmp通过i减n-1实现对i和n-1的比较。执行fl(O)过程中， 当 i=0 时， cmp 指令执行后，进 / 借位标志 CF 的内容是什么？要求给出计算 过程。J (4)第23条指令shl通过左移操作实现了 powvr*2运算，在f2中能否也用shl指 令实现power*2 ?为什么？45假定题44给出的计算机 M采用二级分布虚拟存储管理方式，邪气地址格式如下： 页目录号(10位)页表索引(10位)页内偏移量(12位)请针对题43的函数fl和44中的机器指令代码，回答下列问题。题(1) 函数fl的机器指令代码占多少页？(2) 取第1条指令(push ebp)时，若在进行地址变换的过程中需要访问内存中的页目录和页表，而会分别访订可它们各自的第几个表项(编彳号从 o开始)？(3) M的I/O采用中断控制方式。若进程P在调用f1 ；匕前通过scanf()获取n的值则在执行scanf()的过程中，进程P的状态会如何变化? CPU是否会进入内核态.某进程中有3个并发执行的线程 thread1、和thead3，其伪代码如下所示。ead2thread3/复数的结构类型定义thread1typedef structcnum w;cnum w;w.a =1;float a;w= add(x,y);float b;w.b = 1; cnum;z = add(z,w);cnum x, y, z; / 全局变量Ly = add(y,w);thread 2/计算两个复数之和cnum add(cnum p,cnum w;46cnum q)w= add(y,z);cnum s;s.a = p.a +q.a;s.b= p.b +q.b;return s;请添加必要的信号量和P、V (或wait()、signal。)操作，要求确保线程互斥访 问临界资源，并且最大程序地并发执行。47.甲乙双方均采用后退N帧协议(GBN)进行持续的双向数据传输，且双方始终采 用捎带确认，帧长均为 1000B。 Sx,y 和 Rx,y 分别表示甲方和乙方发送的数据帧， 其中：x 是发送序号； y 是确认序号(表示希望接收对方的下一帧序号) ；数据帧的发送序 号和确认序号字段均为3比特。信道传输速率为100Mbps，RTT=O96ms。下图给出 了甲方发送数据帧和接收数据帧的两种场景，其中 t0 为初始时刻，此时甲方的发 送和确认序号均为 0， t1 时刻甲方有足够多的数据待发送。请回答下列问题。(1) 对于图 (a)，t 时刻期间，甲方可以断定乙方已正确接收的数据帧数是多 0少？正确接收的是哪几个帧(请用 S 形式给出)？x,y 对于图(a),从t时刻起，甲方在不出现超时且未收到乙方新的数据帧之前，最1 多还可以发送多少个数据帧？其中第一个帧和最后一个帧分别是哪个 (请 Sx,y 用形式给出)？ 对于图(b)，从t时刻起，甲方在不出现新的超时且未收到乙方新的数据帧之前，1 需要重发多少个数据帧？重发的第一个帧是哪个(请用 S 形式给出)？ x,y(4) 甲方可以达到的最大信道利用率是多少？