一单项选择题：1~40小题，每小题2分，共80分。在每小题给出的四个选项中，请选出一项最符合题目要求的。
　　1 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用______存储方式最节省时间。
　　A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表
　　2 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i(1<=i<=n)个元素是______。
　　A.不确定 B.n-i+1 C.i D.n-i
　　3 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为( )。
　　A.13 B.33 C.18 D.40
　　4 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是( )。
　　A.M1 B.M1+M2 C.M3 D.M2+M3
　　5 若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为( )。
　　A.n-1 B.ën/mû-1 C.é(n-1)/(m-1)ù
　　D. én/(m-1)ù-1 E.é(n+1)/(m+1)ù-1
　　6 用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为( )。
　　A.5 B.6 C.8 D.9
　　7 在用邻接表表示图时，拓扑排序算法时间复杂度为( )。
　　A.O(n) B.O(n+e) C.O(n*n) D.O(n*n*n)
　　8 当采用分快查找时，数据的组织方式为 ( )
　　A.数据分成若干块，每块内数据有序
　　B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块，考试大祝广大考研朋友考试大捷！
　　C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块
　　D.数据分成若干块，每块(除最后一块外)中数据个数需相同
　　9 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是( )，考试大。
　　A.快速排序 B.堆排序 C.归并排序 D.直接插入排序
　　10 在含有n个关键字的小根堆(堆顶元素最小)中，关键字最大的记录有可能存储在( )位置上。
　　A.ën/2û B.ën/2û -1 C.1 D.ën/2û +2
　　11 硬件和软件实现在逻辑功能上是一样的，但硬件的优势在于_______。
　　A.速度快 B.成本低
　　C.容量大 D.灵活性好
　　12 数据发生溢出的根本原因是_______。
　　A.数据的位数有限
　　B.数据运算中将符号位的进位丢弃
　　C.数据运算中将符号位的借位丢弃
　　D.数据运算中的错误
13 在页式虚拟存储器中，为了提高主存的命中率，可以采取的措施是______。
　　A.增大主存容量 B.增大辅存容量
　　C.增大Cache容量 D.将LRU替换算法改为FIFO
　　14 下列关于存储器的描述，正确的是______。
　　A.CPU访问时间由存储器容量决定
　　B.ROM和RAM在存储器中是统一编址的
　　C.ROM中任一单元可随机访问
　　D.DRAM是破坏性读出，因此需要读后重写
　　15 在相对寻址方式中，若指令中地址码为X，则操作数的地址为______。
　　A.X B(PC)+X
　　C.X+段基址 D.变址寄存器+X
　　16 指令系统中采用不同寻址方式的目的主要是______。
　　A.可直接访问内存
　　B.提供扩展操作码并降低指令译码难度
　　C.实现存储程序和程序控制
　　D.缩短指令长度，扩大寻址空间，提高编程灵活性。
　　17 在总线结构的CPU中，各个部件连接到总线上，其中(在某一时间)______。
　　A.只有一个部件可以向总线发送信息，并且只有一个部件能从总线上接收消息
　　B.只有一个部件可以向总线发送消息，但可有多个部件能同时从总线上接收消息
　　C.可以有一个以上部件向总线上发送消息，但只有一个可以从总线上接收消息
　　D.可以有一个以上部件向总线上发送消息，并且可由多个部件同时从总线上接收消息
　　18 微程序执行的顺序控制问题，实际上是如何确定下一条微指令的地址问题。通常采用的一种方法是断定方式，其基本思想是______。
　　A.用程序计数器PC来产生后继微指令地址
　　B.用微程序计数器 PC来产生后继微指令地址
　　C.通过微程序顺序控制字段或由设计者指定的判断字段控制产生后继微指令地址
　　D.通过指令中指定的一个专门字段来控制产生一个后继微程序地址
　　19 在各种异步通信握手方式中，速度最快的是______。
　　A.全互锁 B.半互锁
　　C.非互锁 D.与互锁性无关
　　20 为了对n个设备使用总线的请求进行裁决，在链式查询方式中需要使用______条控制线。
　　A.n条 B.3条
　　C.2+ D.2n+2
　　21 以下叙述错误的是______。
　　A.产生中断请求信号后，一般由硬件和中断屏蔽字完成中断的裁决和中断源识别
　　B.在多级中断中，CPU本身也有优先级
　　C.软中断是由程序员安排的指令(称为软中断指令和陷阱指令)引起的
　　D.DMA比通道具有更强的独立处理数据输入输出的功能。
　　22 磁盘设备适宜于连接到______通道。
　　A.字节多路通道或数据组多路通道
　　B.字节多路通道或选择通道
　　C.数组多路通道或选择通道
　　D.任一种
　　23 分时操作系统的主要目标是 ______。
　　A.提高计算机系统的实时性 B.提高计算机系统的利用率
　　C.提高软件的运行速度 D.提高计算机系统的交互性
　　24 并行技术可使系统的各种硬件资源尽量并行工作,这样的程序执行环境具有独立性,随机性和 ______。
　　A.封闭性 B.多发性 C.顺序性 D.资源共享性

　25 假设就绪进程中有10个进程,系统将时间片设为200ms,CPU进行进程切换要花费10ms，则系统开销所占的比率为______。
　　A.1% B.5% C.10% D.20%
　　26 在操作系统中,对信号量S的v原语操作定义中,进程从相应等待队列中出列并进入就绪队列中的条件是______。
　　A.s<=0 B.s=0 C.s<0 D.s≠0
　　27 系统抖动是指______。
　　A.使用机器时，屏幕闪烁的现象
　　B.系统盘有问题，至使系统不稳定的现象
　　C.由于内存分配不当，偶然造成内存不够的现象
　　D.被调出的页面又立刻被调入形成的频繁调入调出现象
　　28 下列哪一种属于操作系统中以空间换取时间的技术______。
　　A.SPOLLing技术 B.虚拟存储技术 C.覆盖和交换技术 D.通道技术
　　29 在文件系统中,下列关于当前目录(工作目录)的叙述中,不正确的是______。
　　A.提高文件目录的检索速度 B.减少启动硬盘次数
　　C.利用全路径查找文件 D.当前目录可以改变
　　30 下列那种磁盘调度算法只考虑了公平性?______
　　A.先来先服务 B.最短寻道时间优先 C.先来先服务和扫描 D.前3个都是
　　31 系统为了管理文件,设置了专门的数据结构文件控制块(FCB),FCB是在执行下列哪一个系统调用时建立的? ______
　　A.create B.open C.read D.write
　　32 在下列叙述中正确的是 ______。
　　A.在设备I/O中引入缓冲技术的目的是为了节省内存
　　B.指令中的地址结构和外存容量是决定虚存作业地址空间的两个因素
　　C.处于阻塞状态的进程被唤醒后,可直接进入运行状态
　　D.在虚拟页式管理中,FIFO置换算法的内存利用率是较高的
　　33 波特率等于
　　A.每秒传输的比特
　　B.每秒钟可能发生的信号变化的次数
　　C.每秒传输的周期数
　　D.每秒传输的字节数
　　34 一种编码的检错能力和纠错能力取决于它的海明距离。为了检测出d个比特错，需要使用海明距离为_______的编码。
　　A.d B.d+1 C.d+2 D.2d+1
　　35 下列不属于数据链路层功能的是_______。
　　A.帧同步功能 B.电路管理功能
　　C.差错控制功能 D.流量控制功能
　　36 IEEE802.11MAC层具有多种功能，其中分布式协调功能采用的是_______协议
　　A .CSMA/CA B .CSMA/CB C. CSMA/CC D. CSMA/CD
　37 HDLC是一种_________协议。
　　A.面向比特的同步链路控制 B.面向字节数的异步链路控制
　　C.面向字符的同步链路控制 D.面向比特的异步链路控制
　　38 下面关于网桥的说法中不正确的是_______。
　　A.网桥工作在数据链路层，对网络进行分段，并将整个物理网络连接成一个逻辑网络。
　　B.网桥可以通过对数据进行过滤，有效地组织广播数据
　　C.网桥可以连接数据链路层协议不同的局域网
　　D.网桥要处理器接收到的数据，增加了传播时延
　　39 在距离矢量路由选择协议中，下列哪项最可能导致路由回路(rooting loop)问题?_______
　　A.由于网络带宽的限制，某些路由更新数据包被丢弃
　　B.由于路由器不知道整个网络的拓扑结构信息，当收到一个路由更新时，又将该更新信息发回向自己发送该路由信息的路由器
　　C.当一个路由器发现自己的一条直接相邻链路断开时，没能将这个变化报告给其他路由器
　　D.慢收敛导致路由器接受了无效的路由信息
　　40 PING使用了哪个协议?_______
　　A.ICMP B.TCP C.UDP D.HTTP
　　二综合应用题：41~47小题，共70分
　　1 设哈希函数H(k)=3 K mod 11，散列地址空间为0～10，对关键字序列(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分)采用最佳页面置换算法,缺页次数为多少?
　　6 什么是AND信号量?试利用AND信号量写出生产者-消费者问题的解法。(9分)
　　7 在数据传输速率为50kb/s的卫星信道上发送长度为1kb的帧。假设确认总是由数据帧捎带。帧头很短，帧序号的长度为3比特。对于下列三种协议可以取得的最大利用率是多少?(假设卫星信道端到端的单向传播延迟时间为270ms)
　　(1) (3分)停止等待协议;
　　(2) (3分)后退N滑动窗口协议;
　　(3) (3分)选择重发滑动窗口协议。