《2017年计算机408统考真题.pdf》由会员分享，可在线阅读，更多相关《2017年计算机408统考真题.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2017年全国硕士研究生人学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题（第140小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求）1.下列函数的时间复杂度是。in七fun6(int n)int i=O,sum=O;while(s.um n)sum+=+i;return i;A.O(logn)B.O(n112)C.O(n)2.下列关千栈的叙述中，错误的是I.采用非递归方式重写递归程序时必须使用栈II.函数调用时，系统要用栈保存必要的信息III.只要确定了入栈次序，就可确定出栈次序IV.栈是一种受限的线性表，允许在其两端进行操作A.仅I
2、B.仅I、II、IIIC.仅I、III、IVD.仅II、III、IV3.适用于压缩存储稀疏矩阵的两种存储结构是。A.三元组表和十字链表B.三元组表和邻接矩阵C.十字链表和二叉链表D.邻接矩阵和十字链表4.要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足的条件D.O(nlogn)勹三的结树0结a。.t1码D3DD,0译是g是的为ld次1度的为b)，点依o均d1d3度生码10g为结编la的d曼11e数部点为夫10fb个。外0a点13含不结列dg哈o序C(01顶BD的0c勺符11是c序后字004、树，定判其各10为至找，若ob度数示列b中树斤序ag其畛查子h半右f，顶马b,i 图gd
3、边的11折有为只右i编a如，则条B形eB6含B成匕匕4月dL1所cf 0有G可树。hO，含图的树G 1 伈1。中3 叉树二集11,fh图树子棵。符ob向吁叉左一字01,a无lJ二有知知jeg知g10曰的la已。只己cf已是1.5点AC60A1点A8。A,结0顶是的00他2017年计算机408统考真题 第 1 页，共 8 页 A.c.*9.下列应用中，适合使用B+树的是。B.D.A.编译器中的词法分析B.关系数据库系统中的索引C.网络中的路由表快速查找D.操作系统的磁盘空闲块管理10.在内部排序时，若选择了归并排序而没有选择插入排序，则可能的理由 是。I.归并排序的程序代码更短II.归并排序的占
4、用空间更少III.归并排序的运行效率更高A.仅IIB.仅IIIC.仅I、IID.仅I、III11.下列排序方法中，若将顺序存储更换为链式存储，则算法的时间效率会降低的是。I.插入排序 I.选择排序 III.起泡排序IV.希尔排序 V.堆排序A.仅I、IIB.仅II、IIIC.仅III、IVD.仅IV、V12.假定计算机Ml和M2具有相同的指令集体系结构CISA),主频分别为 1.5GHz和1.2GHz。在 Ml和M2上运行某基准程序P,若平均C PI分别为2和1,则程序P在Ml和M2上运行时间的比值是A.0.4B.0.625C.1.6D.2.513.某计算机主存按字节编址，由4个64Mx8位的
5、DRAM芯片采用交叉编址方式构成，并与宽度为32位的存储器总线相连，主存每次最多读写32位数据。若double型变量x的主存地址为804 OOlAH,则读取x需要的存储周期数是。A.1B.214.某C语言程序段如下：for(i=O;i=9;i+)temp=l;for(j=O;jc 00-12-34-56-78-9a 00-12-34-56-78-9b 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
6、-78-%,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地址的是。A.0.0.0.0B.127.0.0.1C.200.10.10.337.直接封装 RIP、OSPF、BGP报文的协议分别是。D.255.255.255.255A.TCP、UDP、IPB.TCP、IP、UDPC.UDP、TCP、IPD.UDP、IP、TCP38.若将网络 21.3.0.0/16 划分为 128 个规模相同的
7、子网，则每个子网可分配的最大 IP地址个数是。A.24B.256C.510D.51239.若甲向乙发起一个 TCP连接，最大段长 MSS=lKB,RTT=5ms,乙开辟的接收缓存为 64KB,则甲从连接建立成功至发送窗口达到 32KB,需经过的时间至少是。A.25msB.30msC.160ms40.下列关于 FTP协议的叙述中，错误的是A.数据连接在每次数据传输完毕后就关闭B.控制连接在整个会话期间保持打开状态C.服务器与客户端的 TCP20端口建立数据连接D.客户端与服务器的 TCP21端口建立控制连接二、综合应用题（第 4147 小题，共 70 分）D.165ms41.(15分）请设计一个
8、算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，当下列两棵表达式树作为算法的输入时，输出的等价中缀表达式分别为(a+b)*(c*(-d)和(a*b)+(-(c-d)。二叉树结点定义如下：七ypedef struct node char datalO;S七rue七node*left,*right;II存储操作数或操作符2017年计算机408统考真题 第 5 页，共 8 页)BTree;要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用 C 或 C+语言描述算法，关键之处给出注释。42.(8分）使用 Prim(普里姆）算法求带权连通图的
9、最小（代价）生成树(MST)。请回答下列问题。(1)对下列图 G,从顶点 A 开始求 G的 MST,依次给出按算法选出的边。(2)图 G的 MST是唯一的吗？(3)对任意的带权连通图，满足什么条件时，其 MST是唯一的？n+l位 43.C 13分）已知f(n)=吝2i=2n+l-1=111B 计算 f(n)的 C 语言函数 fl如下：int fl(unsigned n)int sum=l,power=l;for(unsigned i,;,O;i=n1;i+)power*=2;sum.+=power;J/rturn.sum;将 fl 中的 int 都改为 float,可得到计算 f(n)的另一个
10、函数仅。假设 unsigned和int 型数据都占 32 位，float 采用IEEE 754 单精度标准。请回答下列问题。(1)当 n=O 时，fl 会出现死循环，为什么？若将 fl 中的变量 i 和 n 都定义为 int 型，则 fl是否还会出现死循环？为什么？(2)fl(23)和:f2(23)的返回值是否相等？机器数各是什么（用十六进制表示）？(3)fl(24)和:f2(24)的返回值分别为 33 554 431 和 33 554 432.0,为什么不相等？(4)f(31)=232-1,而 fl(31)的返回值却为-1,为什么？若使 fl(n)的返回值与 f(n)相等，则最大的n是多少？
11、(5):f2(127)的机器数为 7F80 OOOOH,对应的值是什么？若使:f2(n)的结果不溢出，则最大的 n是多少？若使:f2(n)的结果精确（无舍入），则最大的 n是多少？44.oo分）在按字节编址的计算机 M 上，题 43 中 fl的部分源程序（阴影部分）与对应的机器级代码（包括指令的虚拟地址）如下图所示。int fl(unsign廿d n)00401020 55 push ehp for(unsignecl i=O;i=n-I;i+)20 0040105E 39 4D F4 cmp rlword ptr l ehp-OCh,ecx 2017年计算机408统考真题 第 6 页，共 8
12、 页 23 35 pown*=2;00401066 DI E2 return sum;0040107F C3 sh!edx,I rel 其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令。请回答下列问题。(1)计算机M是RISC还是CISC?为什么？(2)fl的机器指令代码共占多少字节？要求给出计算过程。(3)第20条指令cmp通过i减n-1实现对i和n-1的比较。执行fl(O)过程中，当i=O时，cmp指令执行后，进借位标志CF的内容是什么？要求给出计算过程。(4)第23条指令shl通过左移操作实现了power*2运算，在f2中能否也用shl指令实现power*2?为什么？45.(7分
13、）假定题44给出的计算机M采用二级分页虚拟存储管理方式，虚拟地址格式如下：页目录号(IO位）页表索引(IO位）页内偏移董(12位）请针对题43的函数fl和题44中的机器指令代码，回答下列问题。(1)函数fl的机器指令代码占多少页？(2)取第1条指令(push ebp)时，若在进行地址变换的过程中需要访问内存中的页目录和页表，则会分别访问它们各自的第几个表项（编号从0开始）？(3)M的I/0采用中断控制方式。若进程P在调用fl之前通过scanf()获取n的值，则在执行scanf()的过程中，进程P的状态会如何变化?CPU是否会进入内核态？46.(8分）某进程中有3个并发执行的线程threadl、
14、thread2和thread3,其伪代码如下所示。II复数的结构类型定义thread!thread3 typedef slrucl I!i cnum w:cnum w;float a;W=adu(X,y);w.a=l;float b;.w,b=I;I cnum;z=add(z,w);(、num x,y,z;/全局变扯y=add(y,w);thrcad2 II计算两个复数之和！en um add(en um p,en um q)cnum w;I w=add(y,z);cnum s;.s.a=p.a+q.a;s.b=p.b+q.b;return s;2017年计算机408统考真题 第 7 页，共
15、8 页 请添加必要的信号量和P、V(或wait()、signal()操作，要求 确保线程互斥访问临界资源，并且最大限度地并发执行。47.(9分）甲乙双方均采用后退N帧协议(GBN)进行持续的双向数据传输，且双方始终采用捎带确认，帧长均为1000B。SXJI和RXJI分别表示甲方和乙方发送的数据帧，其中x是发送序号，y是确认序号（表示希望接收对方的下一帧序号）；数据帧的发送序号和确认序号字段均为3 比特。信道传输速率为lOOMb ps,RTT=0.96ms。下图给出了甲方发送数据帧和接收数据帧的两种场景，其中t。为初始时刻，此时甲方的发送和确认序号均为O,t1时刻甲方有足够多的数据待发送。甲方甲
16、方t。lo t l 11 时间时间(a)(b)请回答下列问题。(1)对于图(a),t。时刻到t,时刻期间，甲方可以断定乙方已正确接收的数据帧数是多少？正确接收的是哪几个帧？（请用SXJ形式给出。）(2)对于图(a),从t,时刻起，甲方在不出现超时且未收到乙方新的数据帧之前，最多还可以发送多少个数据帧？其中第一个帧和最后一个帧分别是哪个？（请用SXJ形式给出。）(3)对于图(b),从t,时刻起，甲方在不出现新的超时且未收到乙方新的数据帧之前，需要重发多少个数据帧？重发的第一个帧是哪个？（请用SXJ形式给出。）(4)甲方可以达到的最大信道利用率是多少？2017年计算机408统考真题 第 8 页，共 8 页