计算机专业(基础综合)-试卷1

计算机专业（基础综合）-卷1(分：104.00，题时间90分钟)一、单项择(总题数：，数82.00)1.单项选择1-40小题。下列每题给出的四个选项中，有一个选项是最符题目要求。__________________________________________________________________________________________2.堆的逻辑结构是)。A.性结构B.形结构C.状结构D.组

√堆是一种经过排序的树形数据结构，每个结点都有一个值。通常我们所说的堆是指二叉堆。堆的特点是根结点的值最小(最大)且根结点的两个子树也是一个堆。3.循环队列用数组A[0，1…m一1]放其元素值，已知其头尾指针分别为front，rear，则其队列元素个数为()。A.(rearfront+m)％mB.rear一front+1C.rear一frontD.frontrear

√数组下标从0开共m个元素，故队列元素个数(rear—front+m)％m4.设森林M中有三棵树，它们结点个数分别N1，N2N3，森林相对应的二叉树上，根结点的右子树上的结点个数为()。A.N1B.NI+N2C.N3D.N2+N3

√由森林和二叉树的转换关系可知，森林中第一棵树的根结点转换为二叉树的根结点、其他结点变为二叉树的根结点的左子树上的结点，森林中第二和第三棵树全部构成二叉树根结点的右子树，故知根结点的右子树上的结点个数为N2+N3故选D5.采用邻接表存储图的广度优先遍历算法类似于树的)。A.根遍历B.根遍历C.根遍历D.层次遍历

√图的深度优先遍历类似于树的先序遍历；图的广度优先遍历类似于树的层次遍历。6.已知一棵完全二树的第6层(根为第1层有8叶结点，则完全二叉树的结点个数最多是)。A.39B.52C.111D.119

√第6层时第6层共有32个点，当第六层的最后8个结点为叶结点，其余24结点为非叶结点时完全二叉树结点总数达最多，此时共有个结点；故C7.判断有向图是否在回路，除了可以利用拓扑排序外，还可以利用的是)。A.关键路径的方法B.最短路径的DUKSTRA方法C.度优先遍历算法D.度优先遍历算法

√本题考查判断有向图是否存在回路的基本方法：拓扑排序和深度优先遍历。

8.对于序(49，3865，97，76，13，27，50)非递减方式排序，采用步长4希尔排序，第一次排序结果为()。A.(49，7665，13，27，509738)B.(13，2738，49，50，657697)C.(97，7665，50，49，382713)D.(49，1327，50，76，386597)

√由希尔排序的规则易知，步长为第一次排序是第1个元素和第5元素比较、小的放第元素所在位置，大的放第5个元素所在位置；以类推比较第2和第元素，第和第元素，第4和8个元素；故选D9.已知一个线性表38，25，74，6352，48)表长为，假定采用散列函数h(key)=key％7计算散列地址，并存储在散列表中，若采用线性探测方法解决冲突，在该散列表上，进行等概率成功查找的平均查找长度为()。A.1．5B.1．7C.2．0D.2．3

√由散列函数画出散列表后易知：38，，74，63，52，48找成功分别须要11，1，43次查找，故查找成功的平均查找长度=(1+1+2+1+4+3)／010.下关于无向连通图特性的叙述中，正确的描述是)。．所有顶点的度之和为偶数Ⅱ．边数大于顶点个数减1．至少有一个顶点的度为1A.有IB.有ⅡC.IⅡD.IⅢ

√参见无向连通图的定义。I确，对于任意一条边必然连接着两个顶点即产生2个度，所以顶点度之和必为偶数；Ⅱ错误，边数可能等于顶点个数减Ⅲ错误，无此特性。故A11.若求尽快地对序列进行稳定的排序，应选择)。A.速排序B.并排序C.泡排序D.排序

√A、，快速排序和堆排序是非稳定排序。归并排序和冒泡排序是稳定的排序。归并排序的时间复杂度为O(nlogn)冒泡排序的时间复杂度为O(n

2

)故选B12.浮运算尾数不是规格化数，执行左规操作，即尾数)。A.移一位，阶码加一B.移一位，阶码减一C.移一位，阶码加一D.移一位，阶码减一

√尾数左移一位，阶码减一即执行左规；尾数右移一位，阶码加一即执行右规。13.虚存储器由两级存储器组成，它们是)。A.存一辅存

√B.Cache主存C.Cache辅存D.用寄存器一辅存虚拟存储器的两级存储结构即主存一辅存结构，Cache一主存系统是解决存系统速度问题的。14.下关于计算机中指令和数据存放位置的叙述，正确的是)。A.令存放在内存中，数据存放在外存中B.令和数据任何时候都存放在内存中C.令和数据任何时候都存放在外存中

D.序启动前，指令和数据存放在外存中，启动后指令和数据存放在内存中√指令和数据在程序启动之前都放在外存中，只有当程序启动后才调入内存。15.下说法正确的是)A.ROM用刷新，但集成度比动态RAM，断电后存储内容消失B.导体RAM信息可读可写，且断电后仍能保持记忆C.DRAM和SRAM储信息都是易失性存储器，断电后存储信息均消失√D.DRAM属非易失性存储器，而属易失性存储器A错，ROM电后信息不丢失。B错，RAM断电后信息丢失。错，DRAM和SRAM属于易失性存储器。16.在列信息中，与Cache命率无关的是)。A.存的存储时间B.的大小C.Cache组织方式D.Cache容量

√块大小，Cache织方式和容量都和Cache命中率有关，而主存存储时间与命中率无关。17.某算机指令系统采用定长操作码指令格式，操作码位数为8位则其指令数最多为()。A.64B.128C.256√D.32操作码采用固定长度方案，操作码位数为，指令数最多为2

8

=256条。18.堆寻址方式中，设A为通用寄存器，为栈指示器，为SP指示的堆栈顶单元，如果进栈操作的动作是(A)→(SP)－SP，么出栈操作为)A.(SP)+1SP，Map→(A)√B.Map→(SP)+1→C.(SP)1→SP，→(A)D.Map→(A)(SP)－1→SP进栈是先存数再sP减一，故出栈是SP加一再取数。故A19.操控制器的功能是)A.生时序信号B.主存中取出一条指令C.成指令操作码的编译D.主存中取出一条指令，完成指令操作码的编译，产生有关操作控制信号√控制器是计算机的指挥中心责定执行程序的顺序出行指令时机器各部件需要的操作控制命令，由程序计数器、指令寄存器、指令译码器、时序产生器和操作控制器组成，完成协调和指挥整个计算机系统的操作。控制器的功能主要有：①从内存中取出一条指令，并指出下一条指令在内存中位置。②对指令进行译码或测试，并产生相应的操作控制信号，以便启动规定的动作。③指挥并控制CPU、内存和输入／输出设备之间数据流动的方向。20.若盘的转速提高一倍，则)。A.均存取时间减半B.均寻道时间减半C.储密度可以提高一倍D.均旋转延迟时间减半√平均存取时间一寻道时间+转延迟时间+数据传输替换间，寻道时间为磁头移动到指定磁道所需时间；旋转延迟时间指要读写的扇区旋转到磁头下方所需要的时间；数据传输时间指传输一个扇区的时间。磁盘寻道时间一般为510ms，旋转延迟时间大约为46ms数据传输时间相对于前两者来说非常短。当磁盘转速提高一倍时，旋转延迟时间和数据传输时间减半，寻道时间不变，A、。又存储密度与磁盘转速无关，故C错21.下陈述中正确的是)A.在DMA周内，CPU能执行程序。

B.断发生时，CPU首先执行人栈指令将程序计数器的内容保护起来。C.DMA送方式中，DMAC每送一个数据就窃取一个指令周期。D.入输出操作的最终目的是要实现CPU与外设之间的据传输。√A错DMA周期内CPU然可以执行程序。B，对于单重中断发生时首先执行中断周期，其顺序为中断响应、关中断、程序断点(PC)进栈、向量址送PC22.在立编址方式下，存储设备和I／O备是)区分的。A.同地址代码B.同指令或不同的控制信号√C.同的地址总线D.上都不对独立编址方式下对IO备的操作使用单独的I／O令来完成。故可用不同的指令来区分是存储设备还是IO设备。23.显器的灰度是指)A.度B.示字符的清晰程度C.示器中光点亮暗的层次级别√D.示器的色彩度A错，灰度非亮度。B，清晰度由分辨率决定。错，灰度不是色彩度。确，灰度指每个像素点的亮暗级别如用8位示则灰度值可取0～25524.在作系统层次结构中，)操作系统的核心部分，它位于最内层。A.储管理B.理器管理C.备管理D.业管理

√处理器管理主要有两项工作：中断处理和处理器调度。处理器管理是操作系统的核心部分。25.在时操作系统中，进程通常采用)算。A.来先服务B.高优先级C.间片轮转D.机

√分时操作系统将系统处理机时间与内存空间进行时间上的分割，每个时间段称为一个时间片，每个用户依次轮流使用时间片。由于时间间隔很短，每个用户的感觉就像他独占计算机一样。26.在个单处理器系统中，存在3个进程，最多有几个进程处于就绪队列)。A.0B.1C.2D.3

√由于是单处理器，故每个时刻只能有一个进程处于运行状态，其他进程只能处于就绪状态或阻塞状态，故最多有2个程处于就绪队列。27.某统采用非抢战短作业优先的调度算法，现有作业序列，作业(交时间8：，行时1．5小时)作业二(交时间830运行时间8时作业三交时间9：00，运行时间1小时作业四(交时间9：30，运行时间0．3)，其平均带权周转时间为)A.2．6B.3

√C.5．5D.6．228.()是从磁盘移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱面的访问者，若沿臂的移动方向无访问请求时，就改变臂的移动方向再选择。A.来先服务调度算法

B.短寻找时间优先调度算法C.梯调度算法

√D.环扫描调度算法扫描算法(SCAN)可类似为按照楼层顺序依次服务请求，它让电梯在最底层和最顶层之间连续往返运行，在运行过程中响应处于电梯运行方向相同的各楼层上的请求。在这个算法中，每个电梯响应乘客请求使乘客获得服务的次序是由其发出请求的乘客的位置与当前电梯位置之间的距离来决定的，所有的与电梯运行方向相同的乘客的请求在一次电梯向上运行或向下运行的过程中完成。29.虚存储器技术是基于程序的)特。A.算机的高速性B.容量的内存C.环性原理D.部性原理

√虚拟存储器技术的原理是程序的局部性原理，它的实现需要软硬件的共同支持。30.某程代码页在页框中固定不换出，数据页在缺页时换页，每页大小为。当前正在执行一条指令，其语义为：从数据页读四个字节并以此为地址从数据页读另4个字节到寄存器中，则缺页次数最多是()次。A.1B.2C.3D.4

√每次读取的4个节可能不在同一页中。31.可定位内存分区的目的为了)。A.决碎片问题

√B.于多作业共享内存C.便回收空闲区D.脱用户干预32.I／O备控制的发展过程中，最主要的推动因素是)A.高资源利用率B.高系统吞吐量C.高IO设备与的行操作程度D.少主机对IO制的干预√33.下协议中，可以将IP地址转化为MAC地址的是()A.RARPB.ARPC.DNSD.ICMP

√ARP议将IP址转换为MAC址，RARP协将MAC地址转换为IP地址。34.FCPIP模型由以下层次构成)A.理层、数据链路层、网络层、传输层、会话层、表示层、应用层B.络接口层、互联网层、传输层、应用层√C.理层、数据链路层、网络层、传输层、应用层D.域网层、广域网层、互联网层A属于OSI的7模型。35.下关于奈氏准则和香农公式说法错误的是)。A.氏准则指出了码元传输的速率是受限的，不能任意提高，否则在接收端就无法正确判定码元是1还0B.农公式给出了信息传输速率的极限，即对于一定的传输带宽和传输信噪比，信息传输速率的上限就确定了√C.氏准则虽然是在理想条件下推导出的，但是给出了在实际条件下对信息传输率的限制

D.农公式告诉我们，若要得到无限大的信息传送速率，有两个办法：要么使用无限大的传输带宽，要么使信号的信噪比为无限大，即采用没有噪声的传输信道或使用无限大的发送功率A选项即为奈氏准则B错，对于一定的传输带宽和传输信噪比，则给出了码元传输率的限制，没有对信息传输速率(bits)给出限制，可以通过让每个码元携带更多比特的方法提高信息传输速率C、项由香农定理可以得出。36.假一台连接到网络上的计算机的网络配置为地=136子网掩码一255网关地址=13662．89．这台计算机在网络中不能与其他主机进行通信。其中)项设置导致了问题的产生。A.网掩码B.关地址C.IP地D.他配置

√易知本网络是B类网络192=11000000IP址中前18位是网络地址，89=01011011，2=00000010现IP地与网关地址的前18位不同，前位同，要使IP址与网关地址属于同一子网，子网掩码必须为2552551280显lP址与网关地址二者之一有错。B类网络下子网掩码2551280所允许的有效子网是2

一子网掩码255．255．192．0允许的有效子网是

一子网号01和10(00保留地址)个子网的主机地址分别为136—136和136一13662．191．故IP地址不在上述范围内。故选C。37.内网关协议包括)A.OSPF和IGPB.OSPF和C.RIPBGPD.OSPF和

√动态路由协议包括内部网关协议(IGP)和外部网关协(EGP)。具体的内部网关协议有OSPF、、IGRP以及．EIGP等具体的外部网关协议有和BGPA的原因在于IGP是部网关协议的英文简写，它并不是一个具体的协议。38.对算机网络按照信号频带占用方式来划分，可以划分的网络是)。A.绞线网和光纤网B.域网和广域网C.带网和宽带网D.形网和总线形网

√计算机网络按覆盖范围分为：局域网作用范围一般为米到几十公里城域网MAN(介wAN与之间)广域网WAN(作用范围一般为几十到几千公里按拓扑结构分类：总线型、环型、星型、网状；按信息的交换方式来分电路交换报文交换、报文分组交换；按传输介质分类线网光纤网、无线网、局域网通常采用单一的传输介质，而城域网和广域网采用多种传输介质；按通信方式分类：点对点传输网络、广播式传输网络。39.下关于TCP和UDP的描述正确的是()。A.TCPUDP都是无连接的B.TCP无连接的，UDP面向连接C.TCP用于可靠性较差的广域网，UDP适用于可靠性较的局域网√D.TCP用于可靠性较高的局域网，UDP适用于可靠性较的广域网TCP面向连接的，UDP无连接的，所以A、B错。由TCP向连接，所以可用于可靠性较差的广域网，而UDP是连接的，适用于可靠性较高的局域网。故D错，选40.在特网中以下说法正确的是I机通常需要实现TCP议Ⅱ由器必须实现议Ⅲ机必须实现IP协议Ⅳ．路由器必须实IP协议A.I、和ⅢB.I、和ⅣC.I、和ⅣD.、Ⅲ和Ⅳ

√

主机是终端设备，需实现整个五层协议，而路由器是网络层设备，仅需实现网络层及其以下层的协议即物理层，数据链路层和网络层三个层次的协议。而传输层协议，路由器无需实现此协议故排除Ⅱ，即AB、错。41.下面)是数据报服务的特点。A.最大努力将分组交付给目的主机B.保证按源主机发送分组的先后顺序交付给目的主机C.一种没有质量保证的服务D.一种面向连接的服务√数据报服务提供的是一种尽最大努力的、不保证按源主机发送分组的先后顺序交付的、不可靠的服务，非面向连接的服务。故D选项错误。二、合应用题二、综合用(总题数：8，数22.00)42.合应用题41-47小题。__________________________________________________________________________________________已知一组关键字为(26，，41384415，，12，，5l，25)用链地址法解决冲突。假设装填因子a=0．75散列函数的形式为，回答下列问题（分数：）(1).造散列函数。__________________________________________________________________________________________正确答案(确答案：由a=075，得m=11／075，因此，取表长m(1)哈函数H(K)=K／13(P应该取不大于表长的最大素数))(2).画散列表。__________________________________________________________________________________________正确答案：(确答案：哈希表见下页。)(3).计出等概率情况下查找成功的平均查找长度。__________________________________________________________________________________________正确答案：(确答案：等概率情况下查找成功的平均查找长度：11。)(4).汁出等概率情况下查找失败的平均查找长度。__________________________________________________________________________________________正确答案：(确答案：等概率情况下查找失败的平均查找长度：13。

)43.设一个算法，求无向图采用邻接表存储)连通分量个数。__________________________________________________________________________________________正确答案确答案解一深度优先遍历方法如下VoidDFS(AGraph*G,intv)；visited[v]=1／／置已访问标记printf(”％，；／／输出被访问点的编号p=G->adjlist[V]．firstarc／／向顶点第一条边的终结点while(p!=NULL){if(visited[p一>adjvex]==0)／若顶点未访问，递归访问它DFS(G，)44.假某计算机的运算器框图如下图所示，其中ALU16位加法器电平工作)SA、SB16锁存器，4通用寄存器由D触发器组成，端出，

读控制

写控制

微指令字长，格式如下(考虑顺序控制字段)：

各字段意义如下：一读R0一选择控(2位。F2写R0～R3的择控制2位F3打入的控制信号F4打入控制信号。F5一打开非反向三态门的控制信号LDALUF6一打开反向三态门的控制信号

并使加法器最低位加F7一锁存器SB零RESET信号。F8一微程序结束，转入取机器指令的控制信号。一寄存器读命令W寄存器写命令要求：用二进制代码设计出指令的微程序(求画出微程序流程图)。(1)“，R2”指令，(R1)+(R2)vR2(2)“MOV，R0R3指令，即(R0)→(R3)__________________________________________________________________________________________

正确答案：(确答案：

对应的微指令如下：ADD01XX1010000010XX10010000XX1001001001MOV00XX10100010XX1101001001)45.已x和y用变形补码计算结果，同时指出结果是否溢出。求写出计算步骤)x=一0．1011，一01001求，—y=?__________________________________________________________________________________________正确答案：确答案：补=10101[y]补=10111[一y]补=0．1001=11．+[y]补110111得到[x+y]补101100生溢出[x]=110101+[一y]补=00．1001得到x+y]补=11．发生溢出xy=一00010)若干个等待访问磁盘者依次要访问的柱面为，44，40，4，12，76，假设每移动一个柱面需要3毫秒时间动臂当前位于40柱面按下列算法分别计算为完成上述各次访问总共花费的寻找时间数：4.00(1).来先服务算法；__________________________________________________________________________________________正确答案：(确答案：(1)来先服务算法：移动臂的移动次序和移动的柱面数如下：移动次序40一>一>44>40一>4一>80->12一76移动柱面数分别为(20)、(24)(4)(36)、(76)、(68)、(64)然，共移动柱面数是292因此，总的寻道间是：毫×292=876毫)(2).最寻找时间优先算法。___________________________________________________________