计算机考研-数据结构-习题-王道前3套(标记版)

-1-王道计算机统考模拟试题1一、单项选择题：第1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。1.6个元素以6、5、4、3、2、1的顺序进栈，下列不合法的出栈序列是（）。A.5、4、3、6、1、2B.4、5、3、1、2、6C.3、4、6、5、2、1D.2、3、4、1、5、62.利用栈求表达式的值时，设立运算数栈OPEN。假设OPEN只有两个存储单元，则在下列表达式中，不会发生溢出的是（）。A.A-B*(C-D)B.(A-B)*C-DC.(A-B*C)-DD.(A-B)*(C-D)3.在一棵三叉树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。A.4B.5C.6D.74.已知某二叉树的中序、层序序列为DBAFCE、FDEBCA，则该二叉树的后序序列为（）。A.BCDEAFB.ABDCEFC.DBACEFD.DABECF5.以下关于二叉排序树的说法中，错误的有（）个。I.对一棵二叉排序树按前序遍历得出的结点序列是从小到大的序列II.每个结点的值都比它左孩子的值大、比它右孩子结点的值小，则这样的一棵二叉树就是二叉排序树III.在二叉排序树中，新插入的关键字总是处于最底层IV.删除二叉排序树中的一个结点再重新插入，得到的二叉排序树和原来的相同A.1B.2C.3D.46.如右图所示为一棵平衡二叉树（字母不是关键字），在结点D的右子树上插入结点F后，会导致该平衡二叉树失去平衡，则调整后的平衡二叉树应为（）。7.若G是一个具有36条边的非连通无向图（不含自回路和多重边），则图G的结点数至少是（）。A.11B.10C.9D.88.已知有向图G=(V，A)，其中V={a,b,c,d,e}，A={a,b，a,c，d,c，d,e，b,e，c,e}，对该图进行拓扑排序，下面序列中不是拓扑排序的是（）。A.a,d,c,b,eB.d,a,b,c,eC.a,b,d,c,eD.a,b,c,d,e9.折半查找有序表（2,10,25,35,40,65,70,75,81,82,88,100），若查找元素75，需依次与表中元素（）进行比较。A.65,82,75B.70,82,75C.65,81,75D.65,81,70,7510.对一组数据（84,47,25,15,21）排序，数据在排序的过程中的变化如下：（1）8447251521（2）2147251584（3）152152514784（4）15212115254784则所采用的排序方法是（）。A.堆排序B.冒泡排序C.快速排序D.插入排序11.若对29个记录只进行三趟多路平衡归并，则选取的归并路数至少是（）。A.2B.3C.4D.51模拟题中的问题请在王道答疑专区提问，标题请注明：模拟试题/第X套/第x题第1套CABDE-2-12.下列关于配备32位微处理器的计算机说法正确的是（）。A.该机器的通用寄存器一般为32位B.该机器的地址总线宽度为32位C.该机器能支持64位操作系统D.以上说法均不正确13.设[x]补=1.x1x2x3x4，当满足（）时，x-1/2成立。A.x1必须为1，x2x3x4至少有一个为1B.x1必须为1，x2x3x4任意C.x1必须为0，x2x3x4至少有一个为1D.x1必须为0，x2x3x4任意14.设机器数字长16位，有一个C语言程序段如下：intn=0xA1B6;unsignedintm=n;m=m1;//m右移一位则在执行完该段程序后，m的值为（）A.50DBHB.FFB6HC.A1B6HD.D0DBH15.某存储系统中，主存容量是Cache容量的4096倍，Cache被分为64个块，当主存地址和Cache地址采用直接映像方式时，地址映射表的大小应为（）。（假设不考虑一致维护位）A.6×4097bitB.64×12bitC.6×4096bitD.64×13bit16.下列关于Cache和虚拟存储器的说法中，错误的有（）。I.当Cache失效（即不命中）时，处理器将会切换进程，以更新Cache中的内容II.当虚拟存储器失效（如缺页）时，处理器将会切换进程，以更新主存中的内容III.Cache和虚拟存储器由硬件和OS共同实现，对应用程序员均是透明的IV.虚拟存储器的容量等于主存和辅存的容量之和A.I和IVB.III和IVC.I、II和IIID.I、III和IV17.在通用计算机指令系统的二地址指令中，操作数的物理位置可安排在（）。I.一个主存单元和缓冲存储器II.两个数据寄存器III.一个主存单元和一个数据寄存器IV.一个数据寄存器和一个控制存储器V.一个主存单元和一个外存单元A.II、III和IVB.II、IIIC.I、II和IIID.I、II、III和V18.指令（）从主存中读出。A.总是根据程序计数器PCB.有时根据PC，有时根据转移指令C.根据地址寄存器D.有时根据PC，有时根据地址寄存器19.流水线计算机中，下列语句发生的数据相关类型是（）。ADDR1,R2,R3;(R2)+(R3)-R1ADDR4,R1,R5;(R1)+(R5)-R4A.写后些B.读后写C.写后读D.读后读20.间址寻址第一次访问内存所得到信息经系统总线的（）传送到CPU。A.数据总线B.地址总线C.控制总线D.总线控制器21.传输一幅分辨率为640X480，6.5万色的照片（图像），假设采用数据传输速度为56kb/s，大约需要的时间是（）。A.34.82sB.42.86sC.85.71sD.87.77s22.当有中断源发出请求时，CPU可执行相应的中断服务程序，以下可以提出中断的是（）。I.外部事件II.CacheIII.虚拟存储器失效IV.浮点运算下溢V.浮点运算上溢A.I、III和IVB.I和VC.I、II和IIID.I、III和V23.相对采用单一内核结构，采用微内核结构设计和实现操作系统有诸多好处，但是（）不是微内核的优势。A.使系统更高效B.想添加新任务时，不必修改内核C.使系统更安全D.使系统更可靠-3-24.支持多道程序设计的操作系统在运行过程中，会不断选择新进程来运行，共享CPU资源，但是下面哪个不是操作系统选择新进程的直接原因，（）。A.运行进程的时间片用完B.运行进程出错C.运行进程等待某个事件的发生D.有新的进程被创建进入就绪队列25.设有3个作业，它们的到达时间和运行时间如下表所示，并在一台处理机上按单道方式运行。如按高响应比优先算法，则作业执行的次序和平均周转时间依次为（）。作业提交时间和运行时间表作业号提交时间运行时间（小时）18:00228:30139:300.25A.J1,J2,J3、1.73B.J1,J3,J2、1.83C.J1,J3,J2、2.08D.J1,J2,J3、1.8326.设有两个进程P1和P2，counter为共享变量，描述如下：intcounter=6;P1:computing;counter=counter+1;P2:printing;counter=counter-2;两个进程并发执行，运行完成后，counter的值不可能为（）。A.4B.5C.6D.727.设m为同类资源数，n为系统中并发进程数。当n个进程共享m个互斥资源时，每个进程的最大需求是w，则下列情况会出现系统死锁的是（）。A.m=2,n=1,w=2B.m=2,n=2,w=1C.m=4,n=3,w=2D.m=4,n=2,w=328.有一请求分页式存储管理系统，页面大小为每页100字节，有一个50×50的整型数组按行为主序连续存放，每个整数占两个字节，将数组初始化为0的程序描述如下：intA[50][50];for(inti=0;i50;i++)for(intj=0;j50;j++)A[i][j]=0;若在程序执行时内存只有一个存储块用来存放数组信息，则该程序执行时产生（）次缺页中断。A.1B.50C.100D.250029.若存储单元长度为n，存放在该存储单元的程序长度为m，则剩下长度为n-m的空间称为该单元的内部碎片。下面存储分配方法中，哪种存在内部碎片（）。I.固定式分区II.动态分区III.页式管理IV.段式管理V.段页式管理VI.请求段式管理A.I和IIB.I、III和VC.IV、V和VID.III和V30.下列关于文件系统的说法中，正确的是（）。A.文件系统负责文件存储空间的管理但不能实现文件名到物理地址的转换B.在多级目录结构中对文件的访问是通过路径名和用户目录名进行的C.文件可以被划分成大小相等的若干物理块且物理块大小也可任意指定D.逻辑记录是对文件进行存取操作的基本单位31.某文件系统物理结构采用三级索引分配方法，如果每个磁盘块的大小为1024B，每个盘块索引号占用-4-4字节，请问在该文件系统中，最大的文件大小为（）。A.16GTBB.32GTBC.8GTBD.以上均不对32.CPU输出数据的速度远高于打印机的打印速度，为解决这一矛盾，可采用的技术是（）。A.并行技术B.通道技术C.缓冲技术D.虚存技术33.传输层的作用是向源主机和目的主机之间提供―端对端‖的逻辑通信，其中―端对端‖的含义是（）。A.源主机网卡到目的主机网卡之间B.操作源主机的用户和操作目的主机的用户之间C.源主机和目的主机的进程之间D.源主机所在网络和目的主机所在网络之间34.在一种网络中，超过一定长度，传输介质中的数据就会衰减。如果需要比较长的传输距离，就需要安装（）设备。A.放大器B.中继器C.路由器D.网桥35.数据链路层采用后退N帧协议，如果发送窗口的大小是16，那么为了保证协议不会出错，序列号至少需要的位数是（）。A.4B.5C.6D.736.CSMA协议可以利用多种监听算法来减小发送冲突的概率，下面关于各种监听算法的描述中，错误的是（）。I.非坚持型监听算法有利于减少网络空闲时间II.1-坚持型监听算法有利于减少冲突的概率III.P坚持型监听算法无法减少网络的空闲时间IV.1-坚持型监听算法能够及时抢占信道A.I、II和IIIB.II和IIIC.I、II和IVD.II和IV37.若子网掩码是255.255.192.0，那么下列主机必须通过路由器才能与主机129.23.144.16通信的是（）。A.129.23.191.21B.129.23.127.222C.129.23.130.33D.129.23.148.12738.路由器中发现TTL值为0的分组，将进行（）处理，并向源主机返回（）的ICMP报文。A.返回发送方，源点抑制B.继续转发，改变路由C.丢弃，时间超过D.本地提交，终点不可达39.设TCP的拥塞窗口的慢启动门限初始值为8（单位为报文段），当拥塞窗口上升到12时，网络发生超时，TCP开始慢启动和拥塞避免，那么第12次传输时拥塞窗口大小为（）。A.5B.6C.7D.840.下列关于客户/服务器模型的描述中，错误的是（）。I.客户端和服务器必须都事先知道对方的地址，以提供请求和服务II.HTTP基于客户/服务器模型，客户端和服务器端的默认端口号都是80III.浏览器显示的内容来自服务器IV.客户端是请求方，即使连接建立后，服务器也不能主动发送数据A.I和IVB.II和IVC.I、II和IVD.只有IV二、综合应用题：第41～47小题，共70分。41.（10分）设有五个数据do，for，if，repeat，while，它们排在一个有序表中，其查找概率分别为p1=0.2，p2=0.15，p3=0.1，p4=0.03，p5=0.01。而查找它们之间不存在数据的概率分别为q0=0.2，q1=0.15，q2=0.1，q3=0.03，q4=0.02，q5=0.01。doforifrepeatwhileq0p1q1p2q2p3q3p4q4p5q5（1）试画出对该有序表分别采用顺序查找和折半查找时的判定树。（2）分别计算顺序查找时的查找成功和不成功的平均查找长度，以及折半查找时的查找成功和不成功的平均查找长度。（3）判定是顺序查找好？还是折半查找好？-5-42.