选择题(每道2分,共80分)

1,数据结构在计算机内存中的表示是指_____A,数据的存储结构B,数据结构C,数据的逻辑结构D,数据元素之间的关系2,若线性表最常用的操作时存取第i个元素及其前驱值,则采用_____存储方式节省时间A,单链表B,双链表C,单循环链表D,顺序表3,静态链表中指针表示的是____A,下一个元素的地址B,内存储器的地址C,下一个元素在数组中的位置D,左链或者右链指向的地址4,对于一个头指针为head的带头结点的单链表,判断该表为空表的条件是____Ahead==NULLBhead->next==NULLChead->next==headDhead!
=NULL5,栈在____中应用A,递归调用B,子程序调用C,表达式求值D,A,B,C6,三维数组A[4][5][6]按行优先存储方法存储在内存中,若每个元素占2个存储单元,且数组中第一个元素的存储地址为120,则元素A[3][4][5]的存储地址为____A,356B,358C,360D,3627,下面的说法正确的是___人和一棵二叉树的叶子结点在三种遍历中的相对次序不变按二叉树定义,具有三个结点的二叉树共有6种A,(1)(2)B,(1)C,(2)D,(1)(2)都错8,若一个有向图具有拓扑排序序列,则它的邻接矩阵必定为___A,对称矩阵B,稀疏矩阵C,三角矩阵D,一般矩阵9,在有向图的邻接表存储结构中,顶点v在链表中出现的次数是____A,顶点v的度B,顶点v的出度C,顶点v的入度D,依附于顶点v的边数10,散列存储中,冲突指的是____A,两个元素具有相同的序号B,不同的关键字对应于相同的存储地址C,两个记录的关键字相同D,数据元素过多11,如果要求一个线性表既能较快的查找,又能适应动态变化的要求,则可采用____查找法A,分块查找B,顺序查找C,折半查找D,基于属性的查找12.
硬件和软件实现在逻辑功能上是一样的,但硬件的优势在于_A.
速度快B.
成本低C.
容量大D.
灵活性好13.
数据溢出的根本原因是_A.
数据的位数有限B.
数据运算中将符号位的进位丢弃C.
数据运算中将符号位的借位丢弃D.
数据运算中的错误14.
在页式虚拟存储器中,为了提高主存的命中率,可以采取的措施是_A.
增大主存的容量B.
增大辅存的容量C.
增大cache的容量D.
将LRU替换算法改为FIFO15.
下列关于存储器的描述,正确的是_A.
CPU访问时间由存储器的容量决定B.
ROM和RAM在存储器中是统一编址的C.
ROM中任一单元可随机访问D.
DRAM是破坏性读出,因此需要读后重写16.
在相对寻址方式中,若指令中地址码为X,则操作数的地址为_A.
XB.
(PC)+XC.
X+段基址D.
变址寄存器+X17.
指令系统中采用不同的寻址方式的目的主要是_______.
A.
可以直接访问内存B.
提供扩展操作码并降低指令译码难度C.
实现存储程序和程序控制D.
缩短指令长度,扩大寻址空间,提高编程灵活性18.
在总线结构的CPU中,各个部件连接到总线上,其中(在某一时间)A.
只有一个部件可以向总线发送信息,并且只有一个部件能从总线上接受信息.

B.
只有一个部件可以向总线发送消息,但可有多个部件能同时从总线上接受信息.

C.
可以有一个以上的部件向总线发送消息,但只有一个可以从总线上接受信息.

D.
可以有一个以上部件向总线上发送消息,并且可由多个部件同时从总线上接受19.
微程序执行的程序控制问题,实际上是如何确定下一条微指令的地址问题.
通常采用的一种方法是断定方式,其基本思想是_______.

A.
用程序计数器PC来产生后继微指令地址B.
用微程序计数器PC来产生后继微指令地址C.
通过微程序顺序控制字段或由设计者指定的判断字段控制产生后继微指令地址D.
通过指令中指定的一个专门字段来控制产生一个后继微程序地址20.
为了对N个设备使用总线的请求进行裁决,在链式查询中需要使用___条控制线.

A.
N条B.
3条C.
2D.
2N+221.
一下叙述错误的是_______.
A.
产生中断请求信号后,一般由硬件和终端屏蔽字完成终端的裁决和中断源的识别B.
在多级中断中,CPU本身也有优先级C.
软中断是由程序员安排的指令(称为软中断指令和陷阱指令)引起的D.
DMA比通道具有更强的独立处理数据输入输出的功能22.
磁盘设备适宜于连接到________通道.
A.
字节多通道或数据组多通道B.
字节多路通道或选择通道C.
数组多通道或选择通道D.
任一种23_____不是分时系统的基本特征:同时性B、独立性C、实时性D、交互性24,现代操作系统中,____是资源分配的基本单位,____是处理机调度的基本单位进程B、线程C、管程D、例程25,同一程序经过多次创建,运行在不同的数据集上,形成了()的进程;系统动态DLL库中的系统线程,被不同的线程所调用,他们是_____的线程.

A、不同B、相同C、同步D、互斥26、虚拟内存的容量只受______的限制.
A.
物理内存的大小B.
磁盘空间的大小C.
数据存放的实际地址D.
计算机地址位数27、一个40G的硬盘,块的大小为1K,其FAT要占_____空间.
A.
100MB.
120MC.
140MD.
160M28、采用SPOOLing技术的目的是_____A.
提高独占设备的利用率B.
提高主机效率C.
减轻用户编程负担D.
提高程序的运行速度29.
下列文件中属于逻辑结构的文件是_____A.
连续文件B.
系统文件C.
散列文件D.
流式文件30.
,在一个多道系统中,就绪的进程数目越多,处理机的效率就______A越高B越低C不变D不能确定31.
某基于动态分区存储管理的计算机,其主存容量275MB(初始为空),采用最佳适应算法,分配和释放的顺序为:分配75,分配150,释放75,分配40,分配30,此时主存中最大空闲分区大小是______A35MBB45MBC50MBD75MB32为防止用户使用共享文件时可能造成文件被破坏,通常可采用()方法来保护文件.

A.
建立多个副本B.
定时转储文件C.
规定使用权限D.
设置口令33在OSI参考模型中,提供流量控制功能的层有______A.
2、4、5B.
2、3、4C.
1、3、5D.
4、5、634为了进行差错控制,必须对传送的数据帧进行校验.
在局域网中广泛使用的校验方法是循环冗余校验.
如果CRC的生成多项式为G(X)=X4+X+1,信息码字为10110,则计算出来的CRC校验码是_____A.
0100B.
1010C.
0111D.
111135.
若卫星信道的数据传输率为1Mbps,帧长为1000bit,利用卫星信道的两个站点从一方到另一方的传播时延为250ms.
忽略处理帧长和处理时间,而假设应答帧不出现差错,若采用回退NARQ协议,发送窗口为7,接受窗口为1,信道的利用率为_____A.
0.
078B.
0.
137C.
0.
11D.
0.
0136.
一个带宽为4kHz,信噪比为30dB,则该信道的极限信息传输速度为()A.
10kb/sB.
20kb/sC.
40kb/sD.
80kb/s37假设一个主机的IP地址为192.
168.
5.
121,子网掩码为255.
255.
255.
248,那么该主机的网络号为_____A192.
168.
5.
12B192.
168.
5.
121C192.
168.
5.
120D192.
168.
5.
3238主机甲和主机乙之间已建立了一个TCP连接,TCP最大段长度是1000字节,若主机甲的当前拥塞窗口为4000字节,在主机甲向主机乙连续发送两个最大段后,成功接收到主机乙发送的对第一个段的确认段,确认段中通告的接收窗口大小为2000字节,则此时主机甲还可以向主机乙发送的最大字节数是_____A1000B2000C3000D400039设TCP使用的最大窗口为64KB,而传输信道的带宽可认为是不受限制的,如果报文段的平均往返时延为20ms,则所得到的最大吞吐量是____A3.
2752MbpsB13.
1MbpsC26.
2MbpsD52.
4Mbps40只能发送不能接收电子邮件,则可能是_____地址错误APOP3BSMTPCHTTPDMail解答题1,(10分)有如下12个整数:23,37,7,79,29,43,73,19,31,61,23,47.
按下列方法将这组整数排序,分别写出每遍处理后的数列:泡排序(3分);②归并排序(4分);③快速排序(4分).
2,(13分)设二叉树的结点结构为(llink,data,rlink),root为指向该二叉树根节点的指针,p和q分别为指向该二叉树中的两个任意结点的指针,请编写一个算法ancestor(root,p,q,r),该算法找到p和q的最近公共祖先r.
要求:写出该算法的算法设计思想以及算法执行的详细步骤(6分).
用C、C++或java语言描述该算法(7分).
注:该题是以前的练习题中的题目,请大家再做一遍.
提示:用二叉树后续遍历的非递归算法.
3,(10分)某磁盘存储器的转速为3000转/分,共有4个记录面,每毫米5道,每道记录信息为12288B,最小磁道直径为230mm,共有275道.
问:(1)磁盘存储器的存储容量是多少(2)最大位密度,最小位密度是多少(3)磁盘数据传输率是多少(4)平均等待时间是多少给出一个磁盘地址格式方案.
4,(12分)一台处理机具有如下指令格式格式表明有8位通用寄存器(长度16位),X指定寻址模式,主存实际容量为256k字.

(1)假设不用通用寄存器也能直接访问主存中的每一个单元,并假设操作码域OP=6位,请问地址码域应分配多少位指令字长度应有多少位(2)假设X=11时,指定的那个通用寄存器用做基值寄存器,请提出一个硬件设计规划,使得被指定的通用寄存器能访问1M主存空间中的每一个单元.

5,(8分)在一个批处理系统中,可以同时容纳2道作业进入内存,现在有5个作业先后到达系统,其到达时间和估计运行时间如下作业到达时间估计运行时间103521030315454202053030系统的作业调度采用高响应比优先的调度算法(响应比=1+等待时间/估计运行时间)进程调度采用的是可抢占式的短进程优先调度算法,请问(1)、画出各作业运行时间的甘特图(2)、列出各作业的运行时间(即列出每个作业占有CPU的时间段)(3)、计算这批作业的平均周转时间6,(7分)设系统有三种类型的资源,数量为(4,2,2),系统中有进程A,B,C按如下顺序请求资源:进程A申请(3,2,1)进程B申请(1,0,1)进程A申请(0,1,0)进程C申请(2,0,0)请你给出一个防止死锁的资源剥夺分配策略,完成上述请求序列,并列出资源分配过程,指明哪些进程需要等待,哪些资源被剥夺.

7,(9分)某A类网络10.
0.
0.
0的子网掩码255.
224.
0.
0,请确定可以划分的子网个数,写出每个子网的子网号及每个子网的主机范围.

参考答案选择题:1~5ADCCD6~10BBCCB11~15AAAAC16~20BDBDB21~25DCCABAB26~30DCADC31~35BCBDB36~40CCAA解答题:1,(10分)有如下12个整数:23,37,7,79,29,43,73,19,31,61,23,47.
按下列方法将这组整数排序,分别写出每遍处理后的数列:起泡排序(3分);②二路归并排序(4分);③快速排序(4分).
答:起泡排序a,23,7,37,43,73,19,31.
61,23,47,79b,7,23,2937,43,19,31,61,23,47,73,79c,7,23,29,37,19,31,43,23,47,61,73,79d,7,23,29,19,31,37,23,43,47,61,73,79e,7,23,19,29,31,23,37,43,47,61,73,79f,7,19,23,29,31,23,37,43,47,61,73,79g,7,19,23,29,23,31,37,43,47,61,73,79h,7,19,23,23,29,31,37,43,47,61,73,79I,7,19,23,23,29,31,37,43,47,61,73,79二路归并排序a,23,37,7,79,29,43,19,73,31,61,23,47b,7,23,37,79,19,29,43,73,23,31,47,61c,7,19,23,29,37,43,73,79,23,31,47,61d,7,19,23,23,29,31,37,43,47,61,73,79快速排序a,19,7,23,79,29,43,73,37,31,61,23,47b,7,19,23,79,29,43,73,37,31,61,23,47c,7,19,23,29,43,73,37,31,61,23,47,79d,7,19,23,29,43,73,37,31,61,23,47,79e,7,19,23,23,29,73,37,31,61,43,47,79f,7,19,23,23,29,73,37,31,61,43,47,79g,7,19,23,23,29,73,37,31,61,43,47,79h,7,19,23,23,29,73,37,31,61,43,47,79I,7,19,23,23,29,47,37,31,61,43,73,79J,7,19,23,23,29,47,37,31,61,43,73,79K,7,19,23,23,29,43,37,31,47,61,73,79l,7,19,23,23,29,31,37,43,47,61,73,79m,7,19,23,23,29,31,37,43,47,61,73,79n,7,19,23,23,29,31,37,43,47,61,73,79o,7,19,23,23,29,31,37,43,47,61,73,792,(13分)设二叉树的结点结构为(llink,data,rlink),root为指向该二叉树根节点的指针,p和q分别为指向该二叉树中的两个任意结点的指针,请编写一个算法ancestor(root,p,q,r),该算法找到p和q的最近公共祖先r.
要求:写出该算法的算法设计思想以及算法执行的详细步骤(6分).
用C、C++或java语言描述该算法(7分)解:后序遍历最后访问根节点,即在递归算法中,根是压在栈底的.
采用后序非递归遍历,栈中存放二叉树结点的指针,当访问到某结点时,栈中所有元素均为该结点的祖先.
本题要找p和q的最近公共祖先结点r,不失一般性,设p在q的左边.
后序遍历必然先遍历到p,栈中元素均为p的祖先.
将栈拷入另一辅助栈中.
再继续遍历到结点q时,将栈中元素从栈顶开始逐个到辅助栈中去匹配,第一个匹配的元素就是结点p和q的最近公共祖先.

Typedefstruct{BiTreet;Inttag;}stack;//tag=0表示结点的左子女已经访问,tag=1表示结点的右子女已经访问Stacks[],s1[];BiTreeAncestor(BiTreeROOT,p,q,r){Top=0;While(bt!
=null||top>0){While(bt!
=null&&bt!
=p&&bt!
=q)//结点入栈{S[++top].
t=bt;S[top].
tag=0;bt=bt->lchild;//沿左分支向下}If(bt==p)For(i=1;i0;i++){Pp=s[i].
t;For(j=top1;j>0;j--)If(s1[j].
t==p){Printf("p和q最近公共祖先已找到");Returnpp;}}While(top!
=0&&s[top].
tag==1)//出栈top--;If(top!
=0){S[top].
tag=1;Bt=s[top].
t->rchild;//沿右分支向下遍历}Returnnull;}}3,(10分)某磁盘存储器的转速为3000转/分,共有4个记录面,每毫米5道,每道记录信息为12288B,最小磁道直径为230mm,共有275道.
问:(1)磁盘存储器的存储容量是多少(2)最大位密度,最小位密度是多少(3)磁盘数据传输率是多少(4)平均等待时间是多少给出一个磁盘地址格式方案.
磁盘存储器的存储容量是多少4*275*12288=13516800B最大位密度,最小位密度是多少最大位密度:最小位密度:最大磁道直径为230+(275/5)*2=340mm磁盘数据传输率是多少(3000*12288)/60=614400B/s4,(12分)一台处理机具有如下指令格式格式表明有8位通用寄存器(长度16位),X指定寻址模式,主存实际容量为256k字.

(1)假设不用通用寄存器也能直接访问主存中的每一个单元,并假设操作码域OP=6位,请问地址码域应分配多少位指令字长度应有多少位(2)假设X=11时,指定的那个通用寄存器用做基值寄存器,请提出一个硬件设计规划,使得被指定的通用寄存器能访问1M主存空间中的每一个单元.

(1)答:如果要访问直接访问主存.
主存容量为256K,那么地址长度应该为18位.

所以,地址码域要分配18位.
指令字长为6+18=24位.
(2)答:由于内存有1M个单元,所以,主存需要用20位长的地址表示.
由于通用寄存器只有16位.
所以,对于每个内存地址都要进行加法得到.
在内存的地址译码器之前加一个加法器.
基值寄存器保存地址的高位,另一个通用寄存器保存地址的地位.
他们的和相加得到完整的地址.
基值寄存器提供内存地址的高4位,通用寄存器提供低16位.
他们的和能够访问1M容量的内存.

5,(8分)在一个批处理系统中,可以同时容纳2道作业进入内存,现在有5个作业先后到达系统,其到达时间和估计运行时间如下作业到达时间估计运行时间103521030315454202053030系统的作业调度采用高响应比优先的调度算法(响应比=1+等待时间/估计运行时间)进程调度采用的是可抢占式的短进程优先调度算法,请问(1)、画出各作业运行时间的甘特图(2)、列出各作业的运行时间(即列出每个作业占有CPU的时间段)(3)、计算这批作业的平均周转时间答:略(2)作业占用CPU时间退出CPU时间110:0010:35210:5511:25311:5512:40410:3010:50511:2511:55(3).
平均周转时间:75分.
6,(7分)设系统有三种类型的资源,数量为(4,2,2),系统中有进程A,B,C按如下顺序请求资源:进程A申请(3,2,1)进程B申请(1,0,1)进程A申请(0,1,0)进程C申请(2,0,0)请你给出一个防止死锁的资源剥夺分配策略,完成上述请求序列,并列出资源分配过程,指明哪些进程需要等待,哪些资源被剥夺.

答:(1).
分配策略为:当进程Pi申请ri类资源时,检查ri中有无可分配的资源:有则分配给Pi;否则将Pi占有的资源全部释放而进入等待状态.
(Pi等待原占有的所有资源和新申请的资源)(2).
资源分配过程:剩余资源进程A:(3,2,1)(1,0,1)进程B:(1,0,1)(0,0,0)进程A:(0,1,0)(不满足)(3,2,1)A的所有资源被剥夺,A处于等待进程C:(2,0,0)(1,2,1)C,B完成之后,A可完成.
7,(9分)某A类网络10.
0.
0.
0的子网掩码255.
224.
0.
0,请确定可以划分的子网个数,写出每个子网的子网号及每个子网的主机范围.

答:由子网掩码可以判断出主机地址部分被划分出2个二进制作为子网地址位,所以可以划分出2*2-2=2个子网.