2009年考研计算机真题.doc

一单项选择题：140小题，每小题2分，共80分。在每小题给出的四个选项中，请选出一项最符合题目要求的。1 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用_存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表2 一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是_。A不确定 Bn-i+1 Ci Dn-i3 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。A13 B33 C18 D404 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。AM1 BM1+M2 CM3 DM2+M35 若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（ ）。An-1 Bn/m-1 C(n-1)/(m-1) D n/(m-1)-1 E(n+1)/(m+1)-16 用有向无环图描述表达式(A+B)*（A+B）/A），至少需要顶点的数目为()。A5 B6 C8 D9 7 在用邻接表表示图时，拓扑排序算法时间复杂度为( )。AO(n) BO(ne) CO(n*n) DO(n*n*n) 8 当采用分快查找时，数据的组织方式为( )A数据分成若干块，每块内数据有序B数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D数据分成若干块，每块（除最后一块外）中数据个数需相同9 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。A快速排序 B堆排序 C归并排序 D直接插入排序10 在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ ）位置上。 An/2 Bn/2 -1 C1 Dn/2 +211 硬件和软件实现在逻辑功能上是一样的，但硬件的优势在于_。A速度快 B.成本低C容量大 D.灵活性好12 数据发生溢出的根本原因是_。A数据的位数有限B数据运算中将符号位的进位丢弃C数据运算中将符号位的借位丢弃D数据运算中的错误13 在页式虚拟存储器中，为了提高主存的命中率，可以采取的措施是_。A增大主存容量 B.增大辅存容量C增大Cache容量 D.将LRU替换算法改为FIFO14 下列关于存储器的描述，正确的是_。ACPU访问时间由存储器容量决定BROM和RAM在存储器中是统一编址的CROM中任一单元可随机访问DDRAM是破坏性读出，因此需要读后重写15 在相对寻址方式中，若指令中地址码为X，则操作数的地址为_。AX B（PC）+XCX+段基址 D.变址寄存器+X16 指令系统中采用不同寻址方式的目的主要是_。A可直接访问内存B提供扩展操作码并降低指令译码难度C实现存储程序和程序控制D缩短指令长度，扩大寻址空间，提高编程灵活性。17 在总线结构的CPU中，各个部件连接到总线上，其中（在某一时间）_。A只有一个部件可以向总线发送信息，并且只有一个部件能从总线上接收消息B只有一个部件可以向总线发送消息，但可有多个部件能同时从总线上接收消息C可以有一个以上部件向总线上发送消息，但只有一个可以从总线上接收消息D可以有一个以上部件向总线上发送消息，并且可由多个部件同时从总线上接收消息18 微程序执行的顺序控制问题，实际上是如何确定下一条微指令的地址问题。通常采用的一种方法是断定方式，其基本思想是_。A用程序计数器PC来产生后继微指令地址B用微程序计数器PC来产生后继微指令地址C通过微程序顺序控制字段或由设计者指定的判断字段控制产生后继微指令地址D通过指令中指定的一个专门字段来控制产生一个后继微程序地址19 在各种异步通信握手方式中，速度最快的是_。A全互锁 B半互锁C非互锁 D与互锁性无关20 为了对n个设备使用总线的请求进行裁决，在链式查询方式中需要使用_条控制线。An条 B3条C2+ D2n+221 以下叙述错误的是_。A产生中断请求信号后，一般由硬件和中断屏蔽字完成中断的裁决和中断源识别B在多级中断中，CPU本身也有优先级C软中断是由程序员安排的指令（称为软中断指令和陷阱指令）引起的DDMA比通道具有更强的独立处理数据输入输出的功能。22 磁盘设备适宜于连接到_通道。A字节多路通道或数据组多路通道B字节多路通道或选择通道C数组多路通道或选择通道D任一种23 分时操作系统的主要目标是 _。A提高计算机系统的实时性 B提高计算机系统的利用率C提高软件的运行速度 D提高计算机系统的交互性24 并行技术可使系统的各种硬件资源尽量并行工作,这样的程序执行环境具有独立性,随机性和 _。A封闭性 B多发性 C顺序性 D资源共享性25 假设就绪进程中有10个进程,系统将时间片设为200ms,CPU进行进程切换要花费10ms，则系统开销所占的比率为_。A1% B5% C10% D20%26 在操作系统中,对信号量S的v原语操作定义中,进程从相应等待队列中出列并进入就绪队列中的条件是_。As=0 Bs=0 Cs0 Ds027 系统抖动是指_。A使用机器时，屏幕闪烁的现象B系统盘有问题，至使系统不稳定的现象C由于内存分配不当，偶然造成内存不够的现象D被调出的页面又立刻被调入形成的频繁调入调出现象28 下列哪一种属于操作系统中以空间换取时间的技术_。ASPOLLing技术 B虚拟存储技术 C覆盖和交换技术 D通道技术29 在文件系统中,下列关于当前目录(工作目录)的叙述中,不正确的是_。A提高文件目录的检索速度 B减少启动硬盘次数C利用全路径查找文件 D当前目录可以改变30 下列那种磁盘调度算法只考虑了公平性？_A先来先服务 B最短寻道时间优先 C先来先服务和扫描 D前3个都是 31 系统为了管理文件,设置了专门的数据结构文件控制块(FCB),FCB是在执行下列哪一个系统调用时建立的? _Acreate Bopen Cread Dwrite32 在下列叙述中正确的是 _。A在设备I/O中引入缓冲技术的目的是为了节省内存B指令中的地址结构和外存容量是决定虚存作业地址空间的两个因素C处于阻塞状态的进程被唤醒后,可直接进入运行状态D在虚拟页式管理中,FIFO置换算法的内存利用率是较高的33 波特率等于A每秒传输的比特B每秒钟可能发生的信号变化的次数C每秒传输的周期数D每秒传输的字节数34 一种编码的检错能力和纠错能力取决于它的海明距离。为了检测出d个比特错，需要使用海明距离为_的编码。Ad Bd+1 Cd+2 D2d+135 下列不属于数据链路层功能的是_。A帧同步功能 B电路管理功能C差错控制功能 D流量控制功能36 IEEE802.11MAC层具有多种功能，其中分布式协调功能采用的是_协议A CSMA/CA B CSMA/CB C CSMA/CC D CSMA/CD37 HDLC是一种_协议。A面向比特的同步链路控制 B面向字节数的异步链路控制C面向字符的同步链路控制 D面向比特的异步链路控制38 下面关于网桥的说法中不正确的是_。A网桥工作在数据链路层，对网络进行分段，并将整个物理网络连接成一个逻辑网络。B网桥可以通过对数据进行过滤，有效地组织广播数据C网桥可以连接数据链路层协议不同的局域网D网桥要处理器接收到的数据，增加了传播时延39 在距离矢量路由选择协议中，下列哪项最可能导致路由回路(rooting loop)问题？_A由于网络带宽的限制，某些路由更新数据包被丢弃B由于路由器不知道整个网络的拓扑结构信息，当收到一个路由更新时，又将该更新信息发回向自己发送该路由信息的路由器C当一个路由器发现自己的一条直接相邻链路断开时，没能将这个变化报告给其他路由器D慢收敛导致路由器接受了无效的路由信息40 PING使用了哪个协议？_AICMP BTCP CUDP DHTTP 二综合应用题：4147小题，共70分1 设哈希函数H（k）=3 K mod 11，散列地址空间为010，对关键字序列（32,13,49,24,38,21,4,12）按下述两种解决冲突的方法构造哈希表（1）线性探测再散列（2）链地址法，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。（15分）2 图的D_搜索类似与BFS,不同之处在于使用栈代替BFS中的队列 ,入出队列的操作改为入出栈的操作，即当一个顶点的所有邻接点被搜索之后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。用邻接表做存储结构,写一个D_搜索算法（10分）3 求信息码01101110的海明校验码，画出能指出2位出错和纠正一位出错位的海明校验逻辑。（15分）4 什么叫页式虚拟存储器？什么叫页表？说明工作原理。（6分）5 有一个虚拟存储系统,分配给某个进程3页内存,开始时内存为空,页面访问序列如下:6,5,4,3,2,1,5,4,3,6,5,4,3,2,1,6,5.(1) （2分）采用先进先出页面置换算法,缺页次数为多少?(2) （2分）采用最近最少使用页面置换算法,缺页次数为多少?(3) （2分）采用最佳页面置换算法,缺页次数为多少