计算机专业基础综合

计算机专业（基础综合）-试卷4（总分98,考试时间90分钟）单项选择题单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。在顺序表中删除一个元素的时间复杂度为（）。O（1）B.O（logn）C.O（n）D.O（n2）设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是（）。A.1B.2C.3D.4设A是一个已有10个元素的栈，栈中依次是A1，A2，…，A10，栈顶是A10；B是一个已有10个元素的循环队列，队列中元素依次为B1，B2，…，B10，队头元素为B1。A、B均采用顺序结构，现要将栈中元素全部移入队列中，需（）次基本操作才能使得队列中元素与栈中元素交替排列，即B中排列后的元素为B1，A1，B2，.A2，…，B10，A10。（不必考虑存储空间）A,100B.1000C,50D.20设高度为H的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。A.2*HB.2*H-1C.2*H+1D.H+1设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有（）个结点。TOC\o"1-5"\h\zA.13B.12C.26D.25已知10个数据元素为（54，28，16，34，73，62，95，60，23，43），按照依次插入结点的方法生成一棵二叉排序树后，查找值为62的结点所需比较的次数为（）。A.2B.3C.4D.5当向一棵m阶的B一树做插入操作时，若一个结点中的关键字个数等于（），则必须分裂成两个结点，当向一棵m阶的B-树做删除操作时，若一个结点中的关键字个数等于（），则可能需要同它的左兄弟或右兄弟结点合并成一个结点。A.m，m/2-2B.m-1，m/2-1C.m+1，m/2D.m/2，m/2+1下面关于Prim算法和Kruskal算法的时间复杂度正确的是（）。Prim算法的时间复杂度与网中的边数有关，适合于稀疏图

Prim算法的时间复杂度与网中的边数无关，适合于稠密图Kruskal算法的时间复杂度与网中的边数有关，适合于稠密图Kruskal算法的时间复杂度与网中的边数无关，适合于稀疏图数据序列F={2，1，4，9，8，10，6，20）只能是下列排序算法中的（）的两趟排序后的结果。快速排序B,冒泡排序C.选择排序D.插入排序在含有n个关键字的大顶堆中，关键字最小的记录有可能存储在（）位置上。A.n/2B.n/2-1C.1D.n/2+2冯•诺依曼机中指令和数据均以二进制形式存放在存储器中，CPU区分它们的依据是（）。指令操作码的译码结果B.指令和数据的寻址方式C.指令周期的不同阶段D.指令和数据所在的存储单元IEEE754标准浮点数的尾数采用（）机器数形式。A.原码B.补码C.移码D.反码字长16位的补码定点小数的表示范围是（）。0〜1-2-15-（1-2-15）〜1-2-15-1〜1-2-15-1〜1补码定点小数除法中，被除数和除数应满足（）。A.0<I被除数IMI除数IB.0<|被除数IMI除数IC.0<|除数I<I被除数ID.0<I被除数I<I除数I某机器采用四体低位交叉存储器，现分别执行下述操作：（1）读取6个连续地址单元中存放的存储字，重复80次；（2）读取8个连续地址单元中存放的存储字，重复60次。则（1）、（2）所花时间之比为（）。A.1：1B.2：1C.4：3D.3：4下列说法中错误的是（）。虚拟存储器的引入主要是为了解决主存容量的问题虚拟存储器通过页表来实现虚实地址的映射虚拟存储器是一个容量很大的逻辑模型，不是任何实际的存储器虚拟存储器完全由硬件实现在指令格式中，采用扩展操作码设计方案的目的是（）。缩短指令字长B.增加指令字长C.保持指令字长不变的基础上增加指令数量D.保持指令字长不变的基础上扩大指令寻址空间磁盘的平均存取时间是指平均寻道时间和平均等待时间之和。若磁盘的转速提高一倍，则（）。A.平均存取时间减半B.平均寻道时间减半C.平均等待时间减半D.以上都正确下列说法正确的是（）。

取指周期一定等于机器周期指令字长等于机器字长的前提下，取指周期等于机器周期指令字长等于存储字长的前提下，取指周期等于机器周期取指周期与机器周期没有必然联系下列说法中正确的是（）。微处理器的程序称为微程序微指令控制器的执行速度比硬布线控制器快存放微程序的控制存储器可用ROM或EPROM来实现在微程序控制器中，微指令使用机器指令来解释执行同步通信比异步通信数据传输率高的原因是（）。A.同步通信不需要应答信号B.同步通信使用公共时钟进行同步同步通信中，通信双方的速度相近D.以上都包括CPU在中断周期要完成的任务不包括（）。A.保护断点B.关中断C.保护现场D.向量地址送PC实时系统中的进程调度，通常采用（）算法。A.先来先服务B,时间片轮转C.抢占式的优先数高者优先D.响应比高者优先进程由就绪态转换为运行态是由（）引起的。A.中断事件B.进程状态转换C.进程调度D.为程序创建进程以下（）不是产生死锁的原因。A.资源共享B.并发执行的进程数太多C.系统资源不足D.进程推荐顺序非法把程序地址空间中使用的逻辑地址变成内存中物理地址称为）。A.加载B.物理化C,重定位D.逻辑化下面关于虚拟存储器的论述中，正确的是（）。在段式系统中以段为单位管理用户的逻辑空间，以页为单位管理内存的物理空间；有了虚拟存储器才允许用户使用比内存更大的地址空间为了提高请求分页系统中内存的利用率，允许用户使用不同大小的页面为了能让更多的作业同时运行，通常只装入10%〜30%的作业即启动运行最佳适应算法是实现虚拟存储器的常用算法在下列文件的物理结构中，（）不利于文件长度的动态增长。A,连续结构B,链接结构C,索引结构D.哈希结构设文件F1的当前引用计数值为1，先建立F1的符号链接（软链接）文件F2,再建F1的硬链接文件F3，然后删除F1。此时，F2和F3的引用计数值分别是（）。A.0、1B.1、1C,1、2D.2、1如果I/O设备与存储设备间的数据交换不经过CPU来完成，则这种数据交换方式是（）。A.程序查询方式B.中断方式C.DMA方式D.无条件存取方式

驱动调度算法中，（）算法可能会随时改变移动臂的运动方向。A.电梯调度B.最短寻找时间优先C.扫描D,单向扫描某虚存系统有3页初始为空的页框，若采用先进先出的页面淘汰算法，则在下列的页面需求提出时，会产生（）次缺页中断?设页面走向为：432143543215〜。A.7B.8C.9D.10传输线上的位流信号同步，应该属于下列OSI的（）层处理。A.物理层B.数据链路层C.网络层D.传输层测得一个以太网数据的波特率是40Mbps，那么其数据率是（）。A.10MbpsB.20MbpsC.40MbpsD.80Mbps数据链路层采用了后退N帧（GBN）协议，发送方已经发送了编号为0〜7的帧。当计时器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是（）。TOC\o"1-5"\h\zA.2B.3C.4D.5一个C类地址，采用了40作为子网掩码，那么这个C类地址可以划分为（）个子网。A,16B.32C,64D.128下列地址中，不属于多播地址的是（）。A,3B.9C,2D.55下列的网络协议中，（）的运输层协议是使用TCP的。A.TFTPB.DNSC.RIPD.TELNEI、一个FTP的用户，发送了LIS27、命令来获取服务器的文件列表，这时候服务器应该通过（）端口来传输该列表。A,21B.20C,22D.19UDP的报文头部不包括（）。A.目的地址B.报文长度C.目的UDP端HD.源UDP端口综合应用题综合应用题41-47小题。1.

给定二叉椅坏点的结构定义(ypcdcfsirucrnode*link；structnod-etiniitem*linkIfr,"给定数维intoCLE,编写递归程序.由数组我}建立锦标机如给定数组m<!T*ASM,A‘I?,・E*对应的锦标树为给定集合S={0,1,2,3,4),以及优先关系R={0〈1,1<4,1<2,20,2<4,4<0)o(1)R是偏序关系吗？(2)证明你的结论。下图所示为双总线结构机器的数据通路，IR为指令寄存器，PC为程序计数器(具有自增功能)，M为主存(受R/W信号控制)，AR为地址寄存器，DR为数据缓冲寄存器，ALU由加、减控制信号决定完成何种操作，控制信号G控制的是一个门电路。另外，线上标注有小圈表示有控制信号，例中yi表示y寄存器的输入控制信号，R1o为寄存器R1的输出控制信号，未标字符的线为直通线，不受控制。(1)“ADDR2,R0”指令完成(R0)+(R2)一R0的功能操作，画出其指令周期流程图，假设该指令的地址已放APC中。并列出相应的微操作控制信号序列。(2)若将“取指周期”缩短为一个CPU周期，请先画出修改数据通路，后画出指令周期流程图。(3)在(2)的基础上，将“执行周期”也缩短为一个CPU周期，先修改运算器数据通路，后画出指令周期流程图。此时加法指令速度比(1)提高几倍？□tin有两部计算机M1和M2,指令系统相同。它们的操作频率频率分别是400MHz和200MHz。指令分成A、B和C三类，在M1上执行分别需4、6和8个周期；在M2上执行分别需2、4和3个周期。现有一程序在两机器上执行，其中A、B和C三类指令依次占30%、50%和20%。请问哪一部机器较快完成，快几倍？某会议有n个参与者，等大家到齐后会议才能开始，利用P、V原语操作实现会议参与者进程。

完成以下各小题。（1）什么是Belady现象?为什么会产生这种现象？（2）页面置换算法FIFO为什么会出现Belady现象?简述理由。（3）页面置换算法LRU为什么不会出现Belady现象?简述理由。假定A和B是试图在一个以太网上发送的两个站。每个站都有一个稳定的帧的队列准备发送，A的帧编号是A1，A2和A3等，B的帧编号是B1，B2和B3等。再假定指数后退的基本单元时间是T=51.2微秒。现在A和B同时尝试发送1号帧，碰撞，并且刚好分别选择了0xT和1xT的退避时间，也就是