2017全硕士研生招生考试计算机科学技术学科联考计算机学科业基础综合试题一单选择题1～40小题，每小题2，共80列每题给出的四个选中，只有一 个选符合题目要求1．列函数的时间复度是int func ( int n){int i=0, sum=0;while(sum n) sum += ++ i;return i ;{A. O(log n) B. O(n1/2) C. O(n)D. O(nlog n)2 ．列关于的述中，错误的是．．．采用非递方式写递程序时必使用．函数调用时，系统要用保必要的信息．只要确定了入次序，可确定出次序．是一种限的线性表，允许在两端进行操作A ．仅B ．仅C ．仅 D ．仅3．用于压缩储稀疏矩的两种储结构是A ．元组表和十链表 B ．元组表和邻接矩C ．十链表和二链表 D ．邻接矩和十链表4 ．要使一棵非空二树的先序序列中序序列相同，所有非结点满足的条是A ．只有子树 B ．只有右子树C ．结点的度均1D．结点的度均25．已知一棵二树的树形如所示，后序序列e，a，c，b ，d，g，f，树中结点a 同层的结点是A ．c B ．d C ．f D ．g6．已知符集{a，b ，c，d，e，f，g，h} ，若各符的哈夫曼编码依次是0100，10，0000，0101，001，011，11，0001，则编码序列 的译码结果是A ．a c g a b f h B ．a d b a g b bC ．a f b e a g d D ．a f e e f g d7 ．已知无G含有16条边，中度4 的点个数3，度3的点个数4 ，他点 的度均小于3 G所含的点个数至少是A ．10 B．11 C．13D．158．列二树中，可能成折半查找判定树(含外部结点) 的是9．列用中，合使用B+树的是A ．编译器中的词法析 B ．关系数据系统中的索引C ．网络中的路表快速查找 D ．操作系统的磁盘空闲块管理10．在内部排序时，若选择了并排序而没有选择插入排序，则可能的理是．并排序的程序码更短．并排序的占用空间更少．并排序的行效率更高A ．仅 B ．仅 C ．仅D ．仅11．列排序方法中，若将序储更换链式储，则算法的时间效率降的是. 插入排序．选择排序 ．起泡排序．希尔排序．堆排序A ．仅 B ．仅 C ．仅 D ．仅12．假定计算机M1和M2有相同的指集体系结构( SA)，频别1.5 GHz和1.2 GHz 在M1和M2行某基准程序P ，均CP 别2和1，则程序P在M1和M2行时的值 是A ．0.4 B ．0.625 C ．1.6 D．2.513．某计算机按节编址，4个64M×8的DRAM芯采用交编址方式构成，并 宽度32的储器总线相连，每次最多读写32数据若double型量x 的地址804 001AH，则读x需要的储周期数是A ．1 B．2 C ．3 D ．414．某C语言程序段如for(i=0i=9 i++){ temp=1for(j=0j=i j++)temp * =asum + =temp}列关于数组a的局部性的述中，确的是A ．时间局部性和空间局部性皆有B ．无时间局部性，有空间局部性C ．有时间局部性，无空间局部性D ．时间局部性和空间局部性皆无15．列寻址方式中，最合按序一维数组元素的是A ．相对寻址 B ．寄器寻址 C ．直接寻址 D ．址寻址16．某计算机按节编址，指长固定只有两种指格式，中地址指29条，二 地址指107条，每个地址段6，则指长至少该是A ．24 B ．26 C ．28 D ．3217．列关于超量流水线特性的述中，确的是. 能缩短流水线能段的处理时间．能在一个时钟周期内同时发射多条指．能结合态调度技术高指执行并行性A ．仅 B ．仅 C ．仅D ．和18．列关于储器(MM)和控制储器(CS)的述中，错误的是．．A ．MM在CPU外，CS在CPU 内B ．MM按地址，CS按内容C ．MM储指和数据，CS储微指D ．MM用RAM和ROM实，CS用ROM实19．列关于指流水线数据通路的述中，错误的是．．A ．包含生成控制信的控制部B ．包含算术逻辑算部(ALU)C ．包含通用寄器组和指部D ．组合逻辑电路和时序逻辑电路组合而成20 ．列关于多总线结构的述中，错误的是．．A ．靠CPU的总线速度较快B ．储器总线可支持突发传方式C ．总线之间通过桥接器相连D ．PC - Express×16采用并行传输方式21 ．I/O指实的数据传通常发生在A ．I/O备和I/O端口之间 B ．通用寄器和I/O备之间C ．I/O端口和I/O端口之间 D ．通用寄器和I/O端口之间22 ．列关于多中断系统的述中，错误的是．．A ．在一条指执行结束时响中断B ．中断处理期间CPU处于关中断状态C ．中断请求的产生前指的执行无关D ．CPU通过采中断请求信检测中断请求23 ．假4个作业到达系统的时刻和行时间如表所示作业到达时刻t行时间J103J213J312J431系统在t=2时开始作业调度若别采用先来先服和短作业先调度算法，则选中的作业 别是A ．J2 J3 B ．J1J4C ．J2J4D ．J1 J324 ．执行系统调用的过程包括如要操作返回用户态执行陷入(trap)指传递系统调用参数 执行相的服程序确的执行序是A ．→→→ B ．→→→C ．→→→ D ．→→→25 ．某计算机按节编址，态内管理采用最佳算法，每次和回收内 后都对空闲链新排序前空闲信息如表所示起始地址20 K500 K1000 K200 K大小40 KB80 KB100 KB200 KB回收起始地址60 K大小140 KB的后，系统中空闲的数量空闲链第一 个的起始地址和大小别是A ．320 K380 KBB ．3500 K80 KBC ．420 K180 KBD．4 500 K80 KB26 ．某文系统的簇和磁盘扇大小别1 KB和512 B 若一个文的大小1 026 B， 则系统给该文的磁盘空间大小是A ．1026 B B．1536 B C．1538 B D．2048 B27 ．列有关基于时间的进程调度的述中，错误的是．．A ．时间越短，进程换的次数越多，系统开销也越大B ．前进程的时间用完后，该进程状态执行态阻塞态C ．时钟中断发生后，系统修改前进程在时间内的剩余时间D ．影响时间大小的要因素包括响时间系统开销和进程数量等28 ．单道程序系统相，多道程序系统的点是．CPU利用率高．系统开销小．系统吞量大．I/O备利用率高A ．仅 B ．仅C ．仅 D ．仅29 ．列选中，磁盘逻辑格式化程序所做的作是．对磁盘进行．建立文系统的目录．确定磁盘扇校验码所占数．对保空闲磁盘块信息的数据结构进行初始化A ．仅B ．仅C ．仅 D ．仅30．某文系统中，针对每个文，用户类别4类安全管理员文文的 伴他用户限5种完全控制执行修改读写入若文控制块中用二 进制串表示文限，表示同类别用户对一个文的限，则述文限的数 至少A ．5 B．9 C ．12 D．2031．若文f1的硬链接f2，两个进程别打开f1和f2，获得对的文述符fd1和fd2， 则列述中，确的是．f1和f2的读写指针置保持相同．f1和f2共享同一个内索引结点．fd1和fd2别指各自的用户打开文表中的一A ．仅 B ．仅 C ．仅D ．和32．系统将数据从磁盘读到内的过程包括操作DMA控制器发出中断请求初始化DMA控制器并启磁盘从磁盘传输一块数据到内缓执行“DMA结束” 中断服程序确的执行序是A ．→→→ B ．→→→C ．→→→ D ．→→→33．假OS 参考模型的用层欲发400 B 的数据(无拆) ，除物理层和用层之外， 他各层在封装PDU时均引入20 B 的额外开销，则用层数据传输效率A ．80 ％ B ．83 ％ C ．87 ％D ．91 ％34．若信道在无噪声情况的极限数据传输速率小于信噪30 dB条的极限数据传 输速率，则信状态数至少是A ．4 B ．8 C．16 D ．3235．在所示的网络中，若机H发一个封装Internet 的IP组的IEEE 802.11数据 F，则F的地址1地址2和地址3别是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地址的是A ．B ．C ． D ．5537．直接封装RIP OSPFBGP报文的协议别是A ．TCPUDP IPB ．TCPIP UDPC ．UDP TCPIPD ．UDP IP TCP38．若将网络/16划128个规模相同的子网，则每个子网可的最大IP地址个 数是A ．254 B ．256C ．510 D ．51239．若发起一个TCP连接，最大段长MSS=1 KB ，RTT=5 ms ，开辟的接收缓 64 KB，则从连接建立成至发窗口达到32 KB，需经过的时间至少是A ．25 ms B ．30 msC ．160 ms D．165 ms40 ．列关于FTP协议的述中，错误的是．．A ．数据连接在每次数据传输完后就关B ．控制连接在整个话期间保持打开状态C ．服器客户端的TCP 20端口建立数据连接D ．客户端服器的TCP 21端口建立控制连接二综合用题41～47小题，共7041 ．(15)请计一个算法，将给定的表达式树(二树)转换等的中缀表达式(通过括 映操作符的计算次序)并输出例如，列两棵表达式树作算法的输入时输出的等中缀表达式别(a+b) * (c * (-d))和(a * b)+(-(c-d))二树结点定如typedef struct node{ char data //储操作数或操作符struct node * left，*right} BTree要求(1)给出算法的基本计思想(2)据计思想，采用C或C++语言述算法，关键之处给出注释42 ．(8)使用Prim(姆)算法求连通的最小()生成树(MST) 请回答列题(1)对列G，从点A开始求G 的MST，依次给出按算法选出的边(2) G的MST是唯一的吗?(3)对任意的连通，满足什条时，MST是唯一的?n 1+n6 7 8i n 143 ．(13) 已知f(n)=+L ，计算f(n)的C语言函数f1如∑22 −1 11 1Bi 01 int f1( unsigned n)2 { int sum=1, power=1;3for(unsigned i=0; i= n -1; i ++)4{ power * = 2;5sum += power;6}7return sum ;8 }将f1 中的int都改float，可得到计算f(n)的另一个函数f2 假unsigned和int型数据都占32 ，float采用IEEE 754单精度准请回答列题(1)n=0时，f1出死循，什?若将f1中的量i和n都定int型，则f1是否还出 死循?什?(2)f1(23)和f2(23)的返回值是否相等?机器数各是什(用十六进制表示)?(3)f1(24)和f2(24)的返回值别33 554 431和33 554 432.0，什相等?(4)f(31)=232-1，而f1(31)的返回值-1，什?若使f1(n)的返回值f(n)相等物业经理人，则最大的n 是多少?(5)f2(127)的机器数7F80 0000H，对的值是什?若使f2(n)的结果溢出，则最大的n是 多少?若使f2(n)的结果精确(无舍入)，则最大的n是多少?44 ．(10)在按节编址的计算机M，题43 中f1的部源程序(影部)对的机器 码(包括指的虚拟地址)如int f1 ( unsigned n)155push ebp………………for(unsigned i=0; i= n-1; i++)………………20 0040105E39 4D F4 cmp dword ptr ,ecx………………{power * = 2;………………23D1 E2shl edx,1………………return sum ;………………35 0040107F C3ret中，机器码行包括行虚拟地址机器指和汇编指请回答列题(1)计算机M是RISC还是CISC?什?(2)f1的机器指码共占多少节?要求给出计算过程(3)第20条指cmp通过i减n-1实对i和n-1 的较执行f1(0)过程中，i=0时，cmp指执 行后，进/借志CF的内容是什?要求给出计算过程(4)第23条指sh1通过移操作实了power * 2算，在f2中能否也用sh1指实power * 2?什?45 ．(7)假定题44给出的计算机M采用二虚拟储管理方式，虚拟地址格式如 目录(10 )表索引(10 )内偏移量(12 )请针对题43 的函数f1和题44 中的机器指码，回答列题(1)函数f1的机器指码占多少?(2)第1条指(push ebp)时，若在进行地址换的过程中需要内中的目录和表， 则别它们各自的第几个表(编从0开始)?(3)M的I/O采用中断控制方式若进程P在调用f1之前通过scanf( )获n 的值，则在执行 scanf( )的过程中，进程P 的状态如何化?CPU是否进入内态?46 ．(8)某进程中有3个并发执行的线程thread1 thread2和thread3 ，伪码如所示 //复数的结构类型定thread1thread3 typedef struct{{ }cnum wcnum wfloat aw=add(x ，y)w.a=1float b……w.b=1 } cnum}z=add(z，w) cnum x，y，z //全局量y=add(y，w)thread2…… //计算两个复数之和}} cnum add(cnum p，cnum q)cnum w {w=add(y，z)cnum s……s.a=p.a+q.a}s.b=p.b+q.breturn s }请添必要的信量和P V(或wait() signal( ))操作，要求确保线程互斥临界资源， 并最大程度地并发执行47 ．(9) 方均采用后N 协议(GBN)进行持续的数据传输，方始终采用 捎确认，长均1000 BSx，y和Rx ，y别表示方和方发的数据，中x是发 序y是确认序(表示希望接收对方的一序) 数据的发序和确认序段均 3 特信道传输速率100 Mbps，RTT=0.96 ms给出了方发数据和接收数据的 两种场，中t 初始时刻，时方的发和确认序均0，t 时刻方有足够多的数据01 待发请回答列题(1)对于(a)，t 时刻到t 时刻期间，方可断定方已确接收的数据数是多少?确01 接收的是哪几个(请用Sx，y形式给出)?(2)对于(a)，从t1时刻起，方在出超时未收到方新的数据之前，最多还可 发多少个数据?中第一个和最后一个别是哪个(请用Sx，y形式给出)?(3)对于(b)，从t1时刻起，方在出新的超时未收到方新的数据之前，需要 发多少个数据?发的第一个是哪个(请用Sx，y形式给出)?(4) 方可达到的最大信道利用率是多少?计算机学科业基础综合试题参考答案(2017)一单选择题1. B 2. C 3. A 4. B 5. B6. D 7. B 8. A 9. B 10. B11. D 12. C 13. C 14. A 15. D16. A 17. C 18. B 19. A 20. D21. D 22. B 23. D 24. C 25. B26. D 27. B 28. D 29. B 30. D31. B 32. B 33. A 34. D 35. B36. A 37. D 38. C 39. A 40. C二综合用题41． 答案要点(1)算法的基本计思想表达式树的中序序列必要的括等的中缀表达式可基于二树的中序遍历 策略得到所需的表达式(3)表达式树中支结点所对的子表达式的计算次序，该支结点所处的置定得 到确的中缀表达式，需要在生成遍历序列的同时，在置增必要的括显然，表达 式的最外层(对结点)操作数(对结点)需要添括(2)(2)算法实(10)void BtreeToE(BTree * root){BtreeToExp(root，1) //的高度1void BtreeToExp(BTree * root, int deep){if( root =