《2020考研计算机学科专业基础综合真题汇编及答案(2009-2019).pdf》由会员分享，可在线阅读，更多相关《2020考研计算机学科专业基础综合真题汇编及答案(2009-2019).pdf（143页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机基础综合试题 1目 录2009年全国硕士研究生入学统一考试.22010年全国硕士研究生入学统一考试.132011年全国硕士研究生入学统一考试.242012年全国硕士研究生入学统一考试计算机科学与技术学.372013年全国硕士研究生入学统一考试.502014年全国硕士研究生招生考试计算机科学与技术学科联考.632015年全国硕士研究生招生考试计算机科学与技术学科联考.742016年全国硕士研究生招生考试计算机科学与技术学科联考.872017年全国硕士研究生招生考试计算机科学与技术学科联考.1002018年全国硕士研究生入学统一考试.1132019 二 召 用，口 开 先？书 斗 工I，.”
2、,.252 2009年全国硕士研究生入学统一考试计算娴学与技术学科联新十算机学科专业SM综合试题一,单 顼 圜 整:鞘 F）小 威,厨 映 分，莪80分”小列每频给幽蒯弹通献由，1.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是A.栈 B.队 列 C.树 D.图2.设栈S和队列Q 的初始状态均为空，元素a，b，c d,e.f,g 依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是b，d.c,f，e,a，g,则栈S的容量至少是A.1 B.2C.3 D.43,
3、给定二叉树如右图所示。设 N 代表二叉树的根，L 代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3,1,7,5,6.2,4,则其遍历方式是A.LRN B.NRLC.RLN D.RNL4.下列二叉排序树中，满足平衡一叉树定义的是5.已知一棵完全二叉树的第6 层（设根为第1层）有 8 个叶结点，则该完全二叉树的结点个数最多是A.39 B.52 C,111 D.1196.将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和 v 可能具有的关系是I.父子关系 n.兄 弟 关 系 in.u 的父结点与v 的父结点是兄弟关系A.只有II B.
4、I 和 HC.1 和HID.I、II和皿7.下列关于无向连通图特性的叙述中，正确的是2 I.所有顶点的度之和为偶数 I I.边数大于顶点个数减1III.至少有一个顶点的度为1A.只有I B,只有II C.I和II D-I和III8.下 列叙述中，工符合m阶B树定义要求的是A.根结点最多有m棵子树B,所有叶结点都在同一层上C.各结点内关键字均升序或降序排列D.叶结点之间通过指针链接9.已 知关键字序列5，8，12,19,28.20，15,22是小根堆（最小堆），插入关键字3，调整后得到的小根堆是A.3.5，12.8,28，20，15,22,19 B.3，5，12,19,20，15.22，8.28
5、C.3.8,12,5.20，15,22,28-19 D,3,12,5，8,28,20-15,22，1910.若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是A.起泡排序B.插入排序C,选择排序D.二路归并排序11.冯诺依曼计算机中指令和数据均以二进制形式存放在存储器中，C P U区分它们的依据是A.指令操作码的译码结果B.指令和数据的寻址方式C.指令周期的不同阶段D.指令和数据所在的存储单元12.一个C语言程序在一台32位机器上运行。程序中定义了三个变量x、y和z，其中x和z为in t型，y为short型。当x=127,
6、y=-9时，执行赋值语句z=z+y后，x、y和z的值分别是A.x=0000007FH,尸FFF9H，z=00000076HB.x=0000007FH,y=FFF9H,z=FFFF0076HC.x=0000007FH-y=FFF7H.z=FFFF0076HD.x=0000007FH,y=FFF7H-z=00000076H13.浮点数加、减运算过程一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为5位和7位（均含2位符号位）。若有两个数X=27x29/32,丫=25x5/8，则用浮点加法计算X+丫的最终结果是A.00111 1100010 B.00
7、111 0100010C.01000 0010001D.发生溢出14.某计算机的Cache共有16块，采用2路组相联映射方式（即每组2块）。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache组号是A.OB.2C.4D .615.某计算机主存容量为64 KB，其中R O M区为4 KB，其余为R A M区，按字节编址。现要用2Kx8位的ROM芯片和4Kx4位的RAM芯片来设计该存储器，则需要上述规格的ROM芯片数和RAM芯片数分别是A.1、15B.2、15C.1、30D.2、3016.某机器字长16位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第一字
8、节为操作码字段，第二字节为相对位移量字段。假定取指令时，每取一个字节PC自动加1。若某转移指令所在主存地址为2000H,相对位移量字段的内容为06H，则该转移指令成功转移后的目标地址是A.2006HB.2007H C.2008H D.2009H1 7.下列关于RISC的叙述中，错谬的是A.RISC普遍采用微程序控制器B.RISC大多数指令在一个时钟周期内完成C.RISC的内部通用寄存器数量相对CISC多D.RISC的指令数、寻址方式和指令格式种类相对CISC少4 318.某计算机的指令流水线由四个功能段组成，指令流经各功能段的时间（忽略各功能段之间的缓存时间）分别为90 ns、80 ns、70
9、 ns和60 ns，则该计算机的CPU时钟周期至少是A.90ns B.80ns C.70ns D.60ns19.相对于微程序控制器，硬布线控制器的特点是A.指令执行速度慢，指令功能的修改和扩展容易B.指令执行速度慢，指令功能的修改和扩展难C.指令执行速度快，指令功能的修改和扩展容易D.指令执行速度快，指令功能的修改和扩展难20.假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，总线时钟频率为10 M H z,则总线带宽是A.10 MB/s B.20 MB/s C.40MB/S D.80MB/S21.假设某计算机的存储系统由Cache和主存组成。某程序执行过程中访存
10、1 000次，其中访问Cache缺失（未命中）50次，则Cache的命中率是A.5%B.9.5%C.50%D.95%22.下列选项中，能引起外部中断的事件是A.键盘输入B.除数为0C.浮点运算下溢D.访存缺页23.单处理机系统中，可并行的是I.进程与进程 I I.处理机与设备 I I I.处理机与通道 I V.设备与设备A.I、n和RIB.I、1 1 和iv c .1 iii n ivD.11、in和iv24.下列进程调度算法中，综合考虑进程等待时间和执行时间的是A.时间片轮转调度算法B.短进程优先调度算法C.先来先服务调度算法D.高响应比优先调度算法25.某计算机系统中有8台打印机 由K个进
11、程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是A.2B.3C.4D.526.分区分配内存管理方式的主要保护措施是A.界地址保护B,程序代码保护C.数据保护D.栈保护27.一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是A.28字节B.2伯字节C.224字节D.乎 字节28.下列文件物理结构中，适合随机访问且易于文件扩展的是A.连续结构 B.索引结构C.链式结构且磁盘块定长D 链式结构且磁盘块变长29.假设磁头当前位于第105道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为35,45，12,68,110，180，170，195，采用S
12、CAN调度（电梯调度）算法得到的磁道访问序列是A.110,170,180，195，68,45,35，12 B.110-68,45,35，12,170,180-195C.110,170.180，195，12,35,45-68 D 12-35,45,68,110,170,180,19530.文件系统中，文件访问控制信息存储的合理位置是A.文件控制块B.文件分配表C.用户口令表D.系统注册表31.设文件F1的当前引用计数值为1,先建立F1的符号链接（软链接）文件F 2,再建立F1的硬链接文件F 3,然后删除F1。此时，F2和F3的引用计数值分别是A.0、1 B.1、1 C.1、2D.2、14 32.
13、程序员利用系统调用打开I/O设备时，通常使用的设备标识是A.逻辑设备名B.物理设备名C.主设备号D.从设备号33.在OSI参考模型中，自下而上第一个提供端到端服务的层次是A,数据链路层B.传 输 层C.会话层D.应用层34.在无噪声情况下，若某通信链路的带宽为3 k H z,采用4个相位、每个相位具有4种振幅的Q AM调制技术，则该通信链路的最大数据传输速率是A.12 kbps B.24 kbps C.48 kbps D.96 kbps35.数据链路层采用后退N帧（GBN）协议，发送方已经发送了编号为07的帧。当计时器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是A.2B
14、,3C.4D .536.以太网交换机进行转发决策时使用的PDU地址是A.目的物理地址B.目的IP地址C.源物理地址D 源IP地址37.在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1G bps,电缆中的信号传播速度是200 000 km/s。若最小数据帧长度减少800比特，则最远的两个站点之间的距离至少需要A.增加160 m B.增加80 m C.减少160 m D.减少80 m38.主机甲与主机乙间已建立一个TCP连接，主机甲向主机乙发送了两个连续的TCP段，分别包含300字节和500字节的有效载荷，第一个段的序列号为2 0 0,主机乙正确接收到两个段后，发送给主
15、机甲的确认序列号是A.500B.700C.800D.100039.一个TCP连接总是以1 K B的最大段长发送TCP段，发送方有足够多的数据要发送。当拥塞窗口为16 K B时发生了超时，如果接下来的4个RTT（往返时间）时间内的TCP段的传输都是成功的，那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时，拥塞窗口大小是A.7 KB B.8 KB C.9 KB D.16 KB40.FTP客户和服务器间传递FTP命令时，使用的连接是A.建立在TCP之上的控制连接B.建立在TCP之上的数据连接C.建立在UDP之上的控制连接D.建立在UDP之上的数据连接二 综合翊麒 獭 1 -47 4、曝.珈
16、 0分.41.（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；选择离U最近且尚未在最短路径中的一个顶点V,加入到最短路径中，修改当前顶点u=v；重复步骤，直到U是目标顶点时为止。请问上述方法能否求得最短路径?若该方法可行，请证明之；否则，请举例说明。42.（15分）已知一个带有表头结点的单链表，结点结构为data link，假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查
17、找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：描述算法的基本设计思想；（2）描述算法的详细实现步骤；（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C、C+或Java语言实 5现），关键之处请给出简要注释。43.（8分）某计算机的CPU主频为500 MHz,CPI为5（即执行每条指令平均需5个时钟周期）。假定某外设的数据传输率为0.5 MB/s，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。
18、（1）在中断方式下，CPU用于该外设I/O的时间占整个CPU时间的百分比是多少？当该外设的数据传输率达到5 MB/S时，改用D M A方式传送数据。假定每次D M A传送块大小为5000 B，且D M A预处理和后处理的总开销为500个时钟周期，则CPU用于该外设I/O的时间占整个CPU时间的百分比是多少?（假设D M A与CPU之间没有访存冲突）44.（13分）某计算机字长16位，采用16位定长指令字结构，部分数据通路结构如下图所示，图中所有控制信号为1时表示有效、为0时表示无效，例如控制信号MDRinE为1CB存储器（M）MetnRMemW DataAddrMARMARin1_ J I_
19、DBfl_ 1ABMDRoulb-A .MDRin MDR|控制信号图例ACou(X o u t二态门及其控制信号-X in 寄存器输入控制信号,fk-PCout|PC|-PCinPCMAC l-J i R 0）个单元的缓冲区。P1每次用6 produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用8untodd()统计奇数个数；P3每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。46.(8分)请求分
20、页管理系统中，假设某进程的页表内容如下表所示:页号页框(Page Frame)号有效位(存在位)0101H1102254H1页面大小为4 K B，一次内存的访问时间是100 ns，一次快表(TLB)的访问时间是10ns，处理一次缺页的平均时间为108ns(已含更新T L B和页表的时间)，进程的驻留集大小固定为2,采用最近最少使用置换算法(LRU)和局部淘汰策略。假设T L B初始为空：地址转换时先访问TLB，若T L B未命中，再访问页表(忽略访问页表之后的T L B更新时间)；有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2
21、362H、1565H、2 5 A 5 H.请问：(1)依次访问上述三个虚地址，各需多少时间?给出计算过程。(2)基于上述访问序列，虚地址1565H的物理地址是多少?请说明理由。47.(9分)某网络拓扑如下页图所示，路由器R1通过接口 E1、E2分别连接局域网1、局域网2,通过接口 L 0连接路由器R 2.并通过路由器R 2连接域名服务器与互联网。R 1的L 0接口的IP地址是202.11821；R 2的L 0接口的IP地址是202.118.22,L 1接口的IP地址是130.11.120.1,E0接口的 IP地址是 202.118.3.1：域名服务器的 IP 地址是 202.118.3.2。2
22、02.118.3.1202.118.3.2域名服务器R1和R 2的路由表结构为:目的网络IP地址子网掩码下一跳IP地址 I 接口(1)将IP地址空间202.118.1.0/24划分为2个子网，分别分配给局域网1、局域网2,每个局域网需分配的IP地址数不少于120个。请给出子网划分结果，说明理由或给出必要的计算过程。(2)请给出R 1的路由表，使其明确包括到局域网1的路由、局域网2的路由、域名服务器的主机路由和互联网的路由。请采用路由聚合技术，给出R2到局域网1和局域网2的路由。7（2009 径）BCDBCBADA1.23.4.5&7.069.BCDDCDCAADBDADDCACBAAB10.1
23、1.12.13.14.15.16.亿18.19.2 0.2 1.2 2.2 3.2 4.2 5.2 6.2 7.2 8.2 9.3 0.3 1.BBC3 3.3 4.3 5.DDc3 7.3 8.3 9.8 40.A二、41.【物 鎏 落 疝该方法不一定能(或不能)求得最短路径。举例说明如下：图a图a 中，设初始顶点为1,目标顶点为4,欲求从顶点1到顶点4 之间的最短路径。显然，这两点之间的最短路径长度为2。但利用给定方法求得的路径长度为3,因此这条路径并不是这两点之间的最短路径。图 b 中，设初始顶点为1,目标顶点为3,欲求从顶点1到顶点3 之间的最短路径。利用给定的方法，无法求出顶点1到顶
24、点3 的路径。42.【甯 噗 篓 点 一(1)算法的基本设计思想：定义两个指针变量p 和 q，初始时均指向头结点的下一个结点。p 指针沿链表移动；当 p指针移动到第k 傕油时,q 指针开始与p 指针1 司步移动；当p指针移动到链表最后一个结点时，q 指针所指元素为倒数第k 个结点。以上过程对链表仅进行一遍扫描。(2)算法的详细实现步骤：count=01 p和 q 指向链表表头结点的下一个结点；若 p 为空，转；若8unt等于k，则 q 指向下一个结点；否则，count=count+1；p 指向下一个结点，转步骤；若su n t等于k，则查找成功，输出该结点的data域的值，返回1；否则，查找失
25、败，返回0：算法结束。(3)算法实现：typedef struct LNodeint data：struct LNode*link；*LinkList：int SearchN(LinkList list,int k)LinkList p，q：int count=0：/*计数器赋初值*/p=q=list-link；/*p 和 q 指向链表表头结点的下一个结点*/while(p!=NULL)if(countlink；/*q 移到下一个结点*/p=p-link；/*p 移到下一个结点*/9if(countdata)；/*查找成功*/retum(1)；43.粽赚*(1)中断方式下，CPU每次用于数据传
26、送的时钟周期数：5x18+5x2=100。为达到外设0.5 MB/S的数据传输率，外设每秒申请的中断次数：0.5 MB/4 B=125 000。1秒钟内用于中断的开销：100 x125 000=12500000=12.5M个时钟周期。CPU用于外设I/O的时间占整个CPU时间的百分比：12.5 M/500 M=2.5%。(2)外设数据传输率提高到5 MB/S时，1秒钟内需产生的DMA 雄 5 MB/5 000 B=1 000。CPU用于D M A处理的总开销：1 000 x500=500 000=0.5 M个时钟周期。CPU用于外设I/O的时间占整个CPU时间的百分比：0.5 M/500 M=
27、0.1%。44.【蜜 踱 羲 五参考答案一：时钟功能有效控制信号C5 MAR-(R1)R1out，MARinC6MDR-M(MAR)A-(R 0)MemR,MDRinEROout,AinC7AC一(MDR)+(A)MDRout,Add,ACinC8MDR一(AC)ACout,MDRinC9M(MAR)一(MDR)MDRout E ，MemW“A-(R O)”也可在C7：“AC-(M DR)+(A)”之前单列的一个时钟周期内执行。参考答案二:时钟功能有效控制信号C5 MAR-(R1)R1out,MARinC6MDR-M(M AR)MemR，MDRinEC7A一(MDR)MDRout,AinC8A
28、C一(A)+(RO)ROout，Add,ACinC9MDR一(AC)ACout,MDRinC10M(MAR)一(MDR)MDRout E，MemW45.【省 笫 蛹 产(1)缓冲区是一互斥资源，因此设互斥信号量mutex。(2)同步问题：P1、P2因为奇数的放置与取用而同步，设同步信号量odd；P1、P3因为偶数的放置与取用而同步，设同步信号量even；P1、P2、P3因为共享缓冲区，设同步信号量empty。semaphore mutex=1;semaphore odd=0,even=0;semaphore empty=N;main()cobegin 1 0 Process P1while(T
29、rue)number=produce();P(empty);P(mutex);p u t()；V(mutex);if number%2=0V(even);elseV(odd);Process P2while(True)P(odd);P(mutex);getodd();V(mutex);V(empty);countodd();Process P3while(true)P(even);P(mutex);geteven();V(mutex);V(empty);counteven();coend46.【咨案 睡 点根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面大小为4 K
30、B=212B，则得到页内位移占虚地址的低12位，页号占剩余高位。血v/i汀m(4传)I”内 偏 例 吉(12位)(1)可得三个虚地址的页号P及访问时间如下(十六进制的一位数字转换成4位二进制，因此，十六进制的低12位正好为页内位移，最高位为页号)：1)2362H：页号P=2,有效位为1,存在内存中。先访问快表10 ns，因初始为空，不在快表中，因此 馥访问J裱ioo ns得到页框号，合成物理地址后访问主存100 ns，ftit 10 ns+100ns+100 ns=210 ns.2)1565H：页号P=1,有效位为0,不存在内存中。先访问快表10 ns，落空，访问页表100n s.落空，进行缺
31、页中断处理108ns,合成物理地址后访问主存100 ns，共计10 ns+10011n8+1O8ns+1OO ns=100 000 220 ns.3)25A5H：页号P=2,有效位为1,存在内存中。访问快表，因第一次访问已将该页号放入快表，因此花费10 ns便可合成物理地址，访问主存100 ns，共计10ns+100ns=110ns。(2)当访问虚地址1565H时，产生缺页中断，由于驻留集大小固定为2,必须从页表中淘汰一个页面。根据题目规定的最近最少使用置换算法，应淘汰0号页面，因此1565H的对应页框号为101H。由此可得1565H的物理地址为101565H.47.【鳍 髓 独 把IP地址空
32、间202.11810/24划分为2个等长的子网。戈吩结果为：子网1：子网地址为 202.11810,子网掩码为 255.255.255.128(或子网 1：202.11810/25)子网2：子网地址为202.1181128，子网掩码为255.255.255.128(或子网2：202.118.1.128/25)地址分配方案：子网1分配给局域网1,子网2分配给局域网2；或子网1分配给局域网2,子网2分配给局域网1。(2)R1的路由表如下：参考答案一：(若子网1分配给局域网1,子网2分配给局域网2)目的网络IP地址子网掩码下一跳IP地址接口202.118.1.0255.255.255.128E120
33、2.118.1.128255.255.255.128E2202.118.3.2255.255.255.255202.118.2.2L00.0.0.00.0.0.0202.118.2.2L0参考答案二：番 子 网1分配给局域网2,子网2分配给局域网1)目的网络IP地址子网掩码下一跳IP地址接口202.118.1.128255.255.255.128E1202.118.1.0255.255.255.128E2202.118.3.2255.255.255.255202.118.2.2L00.0.0.0(3)R2的路由表中，0.0.0.0到局域网1和局域网2的路由表项彳202.118.2.2【口下:L
34、0目的网络IP地址子网掩码下一跳IP地址接口202.118.1.0255255.255.0202.118.2.1L0122010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一*单 项 除 健 载 F）小 魅,短6蟋 分，共80%.下 冢 每 题 第 鼬 蒯 指 懑 娜；.只 有 一 个 速 丽 锥 帽 藕 室.1.若元素a,b.c d,e.f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是A.d,c,e，b，3 a B.c，b，d，a，e，fC.b,c.a,e,f,dD a,f,e，d,c,b2.某队列允许在其两端
35、进行入队操作，但仅允许在一端进行出队操作。若元素a,b,c，d,e依次入此队列后再进行出队操作，则不可能得到的出队序列是A.b,a,c,d，eB d，b，a,c,eC.d,b,c,a,e D e,e,b,a,d3.下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是4.在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是A.13、48B.24、48c.24、53D.24、905.在一棵度为4 的树T 中，若有20个度为4 的结点，10个度为3 的结点，1 个度为2 的结点,10个度为1 的结点，则树T 的叶
36、结点个数是A.41 B.82C.113 D.1226.对 n（n22）个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是 1 3A.该树一定是一棵完全二叉树B.树中一定没有度为1的结点C.树中两个权值最小的结点一定是兄弟结点D.树中任一非叶结点的权值一定不小于下一层任一结点的权值7.若无向图G=(V，E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是A.6B.15C.16D.218.对下图进行拓扑排序，可以得到不同拓扑序列的个数是A.4B.3C.2D.19.已知一个长度为16的顺序表L，其元素按关键字有序排列。若采用折半查找法查找一个L中不存在的元素，
37、则关键字的比较次数最多是A.4B.5C.6D.71 0,采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是A.递归次数与初始数据的排列次序无关B.每次划分后，先处理较长的分区可以减少递归次数C.每次划分后，先处理较短的分区可以减少递归次数D.递归次数与每次划分后得到的分区的处理顺序无关11.对一组数据(2,12,16,88,5,10)进行排序，若前三趟排序结果如下：第一趟排序结果:2，12，16,5-10.88第二趟排序结果：2 12.5 10，16.88第三趟排序结果：21 5，10，12,16,88则采用的排序方法可能是A.起泡排序B,希尔排序C.归并排序D.基数排序12
38、.下列选项中，能缩短程序执行时间的措施是I.提 高CPU时钟频率 I I.优化数据通路结构I I I.对程序进行编译优化A.仅1和iiB .仅1和n ic .仅n和山D.1、II和in13.假定有4个整数用8位补码分别表示为r1=FEH，r2=F2H，r3=90H,r4=F8H.若将运算结果存放在一个8位寄存器中，则下列运算中会发生溢出的是A.r1xr2 B.r2xr3C.r1 xr4 D.r2x41 4.假定变量i、f和d的数据类型分别为int、float和double(int用补码表示，float和double分别用IEEE 754单精度和双精度浮点数格式表示)，已知i=785,f=1.5
39、67 8e3,d=1.5el 00o若在32位机器中执行下列关系表达式，则结果为“真 的是I.i=(int)(float)i I I.f=(float)(int)fIII.f=(float)(double)f IV.(d+f)-d=fA.仅I和U B .仅I和H1C.仅II和O D .仅HI和IV15.假定用若干个2Kx4位的芯片组成一个8Kx8位的存储器，则地址OB1FH所在芯片的最小地址是A.0000HB.0600HC.0700HD.0800H1 4 1 6.下列有关RAM和ROM的叙述中，正确的是1 .RAM是易失性存储器，ROM是非易失性存储器II.RAM和ROM都采用随机存取方式进行
40、信息访问III.RAM和ROM都可用作CacheIV.RAM和ROM都需要进行刷新A.仅1和1IB.仅11和山C.仅1、II和W D.仅II、III和IV17.下列命中组合情况中，一次访存过程中不日能发生的是A.T LB未命中、Cache未命中、Page未命中B.T LB未命中、Cache命中、Page命中C.T LB命中、Cache未命中、Page命中D.T LB命中、Cache命中、Page未命中18.下列寄存器中，汇编语言程序员可见的是A.存储器地址寄存器(MAR)B.程序计数器(PC)C.存储器数据寄存器(MDR)D.指令寄存器(IR)19.下列选项中，下会引起指令流水线阻塞的是A.数
41、据旁路(转发)B.数据相关C,条件转移D.资源冲突20.卜列选项中的英文缩写均为总线标准的是A.PCI、CRT、USB、EISA B.ISA、CPI、VESA、EISAC.ISA、SCSI、RAM、MIPSD.ISA、EISA，PCK PCI-Express2 1.单级中断系统中，中断服务程序内的执行顺序是I.保护现场 n.开中断 i n.关中断 W.保存断点v.中断事件处理 V I.恢复现场 v n.中断返回A.I-V-V I f H-V I lB .I I I-I-V-V Dc.m-iV f V f V i-v iiD .iv-1 -v-v if V ii2 2.假定一台计算机的显示存储器
42、用DRAM芯片实现，若要求显示分辨率为1 600 x12 0 0,颜色深度为24位，帧频为85 H z,显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约为A.245 Mbps B.979 Mbps C.1958 Mbps2 3,下列选项中，操作系统提供给应用程序的接口是D.7 834 MbpsA.系统调用B.中 断C.库函数D.原语24.下 列选项中，导致创建新进程的操作是I.用户登录成功 n.设备分配 n i.启动程序执行A.仅I和IIB.仅 1 1 和n ic .仅I和IIID.I、H和m2 5.设与某资源关联的信号量初值为3,示等待该资源的进程数，则M、N分别是当前值为1。若M表
43、示该资源的可用个数，N表A.0、1B.1、0C1、2D.2、026.下列选项中，降低进程优先级的合理时机是A.进程的时间片用完B.进程刚完成I/O,进入就绪队列C.进程长期处于就绪队列中D.进程从就绪态转为运行态27.进程P0和P1的共享变量定义及其初值为：boolean flag2；inttum=0：flagO=FALSE；flag1=FALSE；若进程P0和P1访问临界资源的类C伪代码实现如下:1 5void P0()进程 P0 while(TRUE)flagO=TRUE：tum=1；while(flag1&(tum=1)；临界区；flagO=FALSE；)void P1()/进程 P1
44、while(TRUE)nag1=TRUE：turn=O：while(flagO&(tum=O)；临界区；flag1=FALSE；)则并发执行进程P0和P1时产生的情形是A.不能保证进程互斥进入临界区，会出现 饥饿 现象B.不能保证进程互斥进入临界区，不会出现，饥饿.现象C.能保证进程互斥进入临界区，会出现“饥饿,现象D.能保证进程互斥进入临界区，不会出现，饥饿 现象28.某基于动态分区存储管理的计算机，其主存容量为55 MB(初始为空闲)，采用最佳适配(BestFit)算法，分配和释放的顺序为：分配15MB、分配30MB、释放15MB、分配8 MB、分配6 M B,此时主存中最大空闲分区的大小
45、是A.7 MB B.9 MB C.10 MB D.15 MB29.某计算机采用二级页表的分页存储管理方式，按字节编址，页 大 小 为 字 节，页表项大小为2字 亿 逻 辑 地 址 结 构|页 目 录 号 区 号 恢内偏 移 矍|为：,逻辑地址空间大小为2伯 页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少.是A.64B.128C.256 D.51230.设文件索引节点中有7个地址项，其中4个地址项是直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节。若磁盘索引块和磁盘数据块大小均为256字节，则可表示的单个文件最大长度是A.33 KB B.
46、519 KB3 1.设置当前工作目录的主要目的是C.1 057 KB D.16 513KBA.节省外存空间C.加快文件的检索速度DB.节省内存空间.加快文件的读/写速度32.本地用户通过键盘登录系统时，首先获得键盘输入信息的程序是A.命令解释程序B.中断处理程序C.系统调用服务程序D.用户登录程序33.下列选项中，不属于网络体系结构所描述的内容是A.网络的层次 B.每一层使用的协议C.协议的内部实现细节D.每一层必须完成的功能34.在下图所示的采用,存储一转发 方式的分组交换网络中，所有链路的数据传输速率为100 Mbps，分组大小为1 000 B-其中分组头大小为20 B。若主机H 1向主机
47、H 2发送一个大小为980 000 B的文件，则在不考虑分组拆装时间和传播延迟的情况下，从H1发送开始到H2接收完为止，需要的时间至少是A.80 msB.80.08 ms C.80.16 ms D.80.24 ms1 6 3 5.某自治系统内采用RIP协议，若该自治系统内的路由器R1收到其邻居路由器R2的距离矢量，距离矢量中包含信息，则能得出的结论是A.R2可以经过R1到达net1,跳数为17 B.R2可以到达net1，跳数为16C.R 1可以经过R2到达net1,跳数为17D.R1不能经过R 2到达net136.若路由器R因为拥塞丢弃IP分组，则此时R可向发出该IP分组的源主机发送的ICMP
48、报文类型是A.路由重定向B,目的不可达C,源抑制D.超时37.某网络的IP地址空间为192.168.5.0/24,采用定长子网划分，子网掩码为255.255.255,248,则该网络中的最大子网个数、每个子网内的最大可分配地址个数分别是A.32、8 B.32、6 c .8、32D.8、3038.下列网络设备中，能够抑制广播风暴的是I.中继器 II.集线器 I I I.网桥 I V.路由器A.仅I和HB.仅n ic .仅in和w o .仅tv39.主机甲和主机乙之间已建立了一个TCP连接，TCP最大段长度为1000字节。若主机甲的当前拥塞窗口为4000字节，在主机甲向主机乙连续发送两个最大段后，
49、成功收到主机乙发送的对第一个段的确认段，确认段中通告的接收窗口大小为2000字节，则此时主机甲还可以向主机乙发送的最大字节数是A.1 000 B,2 000 C.3000 D 4 00040.如果本地域名服务器无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为A.一条、一条B.一条、多条C.多条、一条D.多条、多条二 缘 畲 蒯 峨 粼 1 7 7 邪 ,曲 0 分.41.(10分)将关键字序列(7,8,30,11,18,9,14)散列存储到散列表中，散列表的存储空间是一个下标从。开始的一维数组，散列函数为：H(key)=(keyx3)MOD 7
50、,处理冲突采用线性探测再散列法，要求装填(载)因子为0.7。请画出所构造的散列表。(2)分别计算等概率情况下查找成功和查找不成功的平均查找长度。42.(13分)设将n(n1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移p(0pn)竹 置 艮 畸R中的数据由优，%，X Q变换为g,X p*，Xn.r%,Xi，Xg)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C+或Java语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度。43.(11分)某计算机字长为16位，主存地址空间大小为128 K B,