计算机操作系统模拟试题.doc

《计算机操作系统模拟试题.doc》由会员分享，可在线阅读，更多相关《计算机操作系统模拟试题.doc（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机操作系统模拟试题操作系统模拟试题 一一、填空题（本题共25分，每题5分）1、进程的逻辑地址到_地址的转换，称为重定位。2、分区管理分为_和_两种方式。3、处理机在执行系统程序时的状态称为_，在执行用户程序时的状态称为_。4、如果为了使所有进程都有机会运行，最好采用的调度算法是_。5、对记录式文件，操作系统为用户存取文件信息的最小单位是_。二、（本题满分为10分）以打印机为例说明SPOOLING的工作原理，系统如何利用SPOOLING技术将打印机模拟为虚拟打印机。三、（本题满分为10分） 对于如下的页面访问序列：1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5当内存块数

2、量分别为3和4时，试问：使用FIFO、LRU置换算法产生的缺页中断是多少？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）四、（本题满分为15分） 某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：页号物理块号031721138则逻辑地址0A5C(H)所对应的物理地址是什么？要求：写出主要计算过程。五、（本题满分为15分） 假定具有5个进程的进程集合PP0,P1,P2,P3,P4,系统中有三类资源A，B和C。其中A类资源有10个，B类资源有5个，C类资源有7个。假定在某时刻有如下状态：All

3、ocation Max Available A B C A B C A B C P00 1 0 7 5 3 3 3 2 P12 0 0 3 2 2 P23 0 2 9 0 2 P32 1 1 2 2 2 P40 0 2 4 3 3 试给出Need，并说明当前系统是否处于安全状态，如果是，给出安全序列。如果不是，说明理由。答案一、1、物理 2、静态分区 动态分区 3、系统态 用户态4、轮转法 5、记录二、当用户进程请求打印输出时，Spooling系统同意打印输出，但并不真正把打印机分配给该用户进程，而只为它做两件事：1，由输出进程在输出井中为之申请一空闲盘块区，并将要打印的数据送入其中；2，输出

4、进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入表中，再将该表挂到请求打印队列之上。如果还有进程要求打印输出，系统仍可以接受该请求，同样做上面的工作。如果打印机空闲，输出进程将从请求打印队列的队首取出一张请求表，根据表中的要求将要打印的数据从输出井传送到内存缓冲区，再由打印机进行打印。打印完毕，输出进程再查看请求打印队列中是否还有等待要打印的请求表，若有，再取出一张表，并根据其中的要求进行打印，如此下去，直至请求队列为空位置，输出进程才将自己阻塞起来，等待下次再由打印请求时才被唤醒。三、FIFO淘汰算法：内存块为3时，缺页中断（或称缺页次数、页面故障）为9；内存块为4时，缺

5、页中断为10。 LRU淘汰算法：内存块为3时，缺页中断为10；内存块为4时，缺页中断为8。四、125C（H）（要求写出计算步骤）分析页式存储管理的逻辑地址分为两部分：页号和页内地址。由已知条件“用户编程空间共32个页面”，可知页号部分占5位；由“每页为1KB”，1K=210，可知内页地址占10位。由“内存为16KB”，可知有16块，块号为4位。逻辑地址0A5C（H）所对应的二进制表示形式是：000 1010 0101 1100 ，根据上面的分析，下划线部分为页内地址，编码 “000 10” 为页号，表示该逻辑地址对应的页号为2。查页表，得到物理块号是4（十进制），即物理块地址为：01 00 ，

6、拼接块内地址10 0101 1100，得01 0010 0101 1100，即125C（H）。五、当前系统处于安全状态，安全序列如下求解：work = Available = (3 , 3 , 2 ) 寻找Needj =work=( 3 , 3 , 2 ) (j= 0 , 1 , 2 , 3 , 4) j = 1Need1 = (1 ,2 ,3 ) =(3 , 3 , 2 ) work : =(3 , 3 , 2 ) + (2 ,0 ,0 ) =(5 , 3 , 2 ) 寻找Needj =work=( 5 , 3 , 2 ) (j= 0 , 2 , 3 , 4) j = 3Need3 = (0

7、 ,1 ,1 ) =(5 , 3 , 2 ) work : =(5 , 3 , 2 ) + (2 ,1 ,1 ) = (7 , 4 , 3 ) 寻找Needj =work=(7 , 4 , 3 ) ( j = 0 , 2, 4) j = 4Need4 = (4 ,3 ,1 ) =(7 , 4 , 3 ) work : = (7 , 4 , 3 ) + (0 ,0 ,2 ) = (7 , 4 , 5) 寻找Needj =work=(7 , 4 , 5) (j = 0 , 2 ) j = 2Need2 =(6 ,0 ,0 ) =(7 , 4 , 5 ) work : = (7 , 4 , 5 )

8、+ (3 ,0 ,2 ) =(10 , 4 , 7) 寻找Needj =work=(10 , 4 , 7) ( j = 0 ) j = 0work : = (10 , 4 , 7 ) + (0 ,1 ,0 ) = (10 , 5 , 7) 所以安全序列为P1，P3，P4，P2，P0。操作系统模拟试题 二一、 填空题（本题共25分，每题5分）1、 操作系统是计算机系统的一种系统软件，它以尽量合理、有效的方式组织和管理计算机的_，并控制程序的运行，使整个计算机系统能高效地运行。2、 操作系统中，对信号量S的P原语操作定义中，使进程进入相应等待队列等待的条件是_。3、 银行家算法中，当一个进程提出的

9、资源请求将导致系统从_进入_时，系统就拒绝它的资源请求。4、 在请求页式存储管理中，若采用FIFO页面淘汰算法，则当分配的页面数增加时，_的次数可能增加也可能减少。5、 采用段式存储管理的系统中，若地址用24位表示，其中8位表示段号，则允许每段的最大长度是_。 二、（本题满分为10分）在操作系统中，P操作和V操作各自的动作是如何定义的？三、（本题满分为10分） 假设一个活动头磁盘有200道, 编号从0-199. 当前磁头正在143道上服务, 并且刚刚完成了125道的请求. 现有如下访盘请求序列(磁道号): 86, 147, 91, 177, 94, 150, 102, 175, 130 试给出

10、采用下列算法后磁头移动的顺序和移动总量(总磁道数). (1). 先来先服务(FCFS)磁盘调度算法. (2). 最短寻道时间优先(SSTF)磁盘调度算法.(3). 扫描法(SCAN)磁盘调度算法.(假设沿磁头移动方向不再有访问请求时, 磁头沿相反方向移动.)四、（本题满分为15分） 设系统中有三类资源A、B和C，又设系统中有5个进程P1，P2，P3，P4和P5.在T0时刻系统状态如下： 最大需求量 已分配资源量 剩余资源量 A B C A B C A B C P1 8 6 4 1 2 1 2 1 1 P2 4 3 3 3 1 1 P3 10 1 3 4 1 3 P4 3 3 3 3 2 2 P

11、5 5 4 6 1 1 3(1) 系统是否处于安全状态？如是，则给出进程安全序列.(2) 如果进程P5申请1个资源类A、1个资源类B和1个资源类C，能否实施分配？为什么？五、（本题满分为15分） 有n+1个进程A1, A2, .An 和 B:(1) A1,.An通过同一个缓冲区各自不断地向B发送消息, B不断地取消息, 它必 须取走发来的每一个消息. 刚开始时缓冲区为空. 试用P、V操作正确实现之. (2) 若缓冲区个数增至m个, 试用P、V操作实现正确的通讯. 答案：一、1、资源 2、S0 3、安全状态 不安全状态4、缺页中断 5、216二、在操作系统中，P操作和V操作各自的动作是如何定义的

12、？答：P操作顺序执行下述两个动作：信号量的值减1，即S=S-1； 如果S0，则该进程继续执行；如果S0，则把该进程的状态置为阻塞态，把相应的PCB连入该信号量队列的末尾，并放弃处理机，进行等待（直至其它进程在S上执行V操作，把它释放出来为止）。 V操作顺序执行下述两个动作：S值加1，即S=S+1；如果S0，则该进程继续运行； 如果S0，则释放信号量队列上的第一个PCB（即信号量指量指针项所指向的PCB）所对应的进程（把阻塞态改为就绪态），执行V操作的进程继续运行。三、（1）86，147，91，177，94，150，102，175，130 （2）当前磁头在143道上： 147，150，130，1

13、02，94，91，86，175，177（3）当前磁头在143道上，并且刚刚完成125道的请求 147，150，175，177，130，102，94，91，86四、 （1） 最大需求量 已分配资源量 剩余资源量 尚需要量 A B C A B C A B C A B C P1 8 6 4 1 2 1 2 1 1 7 4 3 P2 4 3 3 3 1 1 1 2 2 P3 10 1 3 4 1 3 6 0 0 P4 3 3 3 3 2 2 0 1 1 P5 5 4 6 1 1 3 4 3 3 系统是处于安全状态，安全序列为：P4，P2，P1，P3，P5 （2）P5申请（1，1，1） 最大需求量 已分

14、配资源量 剩余资源量 尚需要量 A B C A B C A B C A B C P1 8 6 4 1 2 1 1 0 0 7 4 3 P2 4 3 3 3 1 1 1 2 2 P3 10 1 3 4 1 3 6 0 0 P4 3 3 3 3 2 2 0 1 1 P5 5 4 6 2 2 4 3 2 2 不能实施分配，因为分配后找不到安全序列，系统将处于不安全状态.五、(1) n+1个进程P1, P2, .,Pn 和 Q ，一个缓冲区Pi ( i=1,.,n): Repeat 生产消息； P(S1); 向缓冲区送消息； V(S2) Until False Q: Repeat P(S2); 从缓冲

15、区取消息； V(S1)； 处理消息； Until False S1=1, S2=0(2) k个缓冲区 Pi ( i=1,.,n): Repeat 生产消息； P(S1); P(mutex); 向BUFFERl中送消息； l:=(l+1) mod k; V(mutex); V(S2) Until False S1=k;S2=0;mutex=1;l=0;ll=0 Q: Repeat P(S2); P(mutex); 从BUFFERll取消息； ll:=(ll+1) mod k; V(mutex); V(S1) Until False 微机原理与接口技术（七）一、填空题（每题5分，共5个题，总分25

16、分）18086/8088 CPU具有两种外部中断，它们是_和_。2（234）10_2_163第二代CPU使用的电子器件是_；第三代CPU采用的电子器件是_。4EIA RS-232C 的TXD和RXD数据线上的电平逻辑1=_V；逻辑0=_V。5在8086中，段寄存器CS1200H，指令指针寄存器IPFF00H，此时指令的物理地址为：_。二、（10分）什么是中断源？8086通常的中断源有哪些？三、（10分）何为逻辑地址？何为物理地址？它们俩者之间有何关系？四、（15分）编写程序段实现如下功能：（1）将立即数17H送DL；立即数7FH送AL。（2）从DX所指的端口中读取一个字节至AL；将AX中的一个

17、字输出至DX和DX1所指的端口中。五、（15分）在1000H开始的内存中，放有1000个ASCII字符，请设计一程序，将这串ASCII字符以异步串行通信方式从8255A PB0输出，采用偶校验、一位起始位、一位终止位、波特率500 (可调用1ms软件定时程序 “D1MS”)。8255A接口连接图如下：8255A工作方式控制字如下 D7 D6 D5 D4 D3 D2 D1 D0特征位 A组方式 A口C47B组方式B口 C03答案一、1、 可屏蔽中断，非屏蔽中断2、 11101010，EA3、 半导体，集成电路4、-3-15，+3+155、21F00H二、引起中断的原因或能发出中断申请的来源称为中

18、断源。 通常中断源有以下几种： （1）一般的输入输出设备。如键盘、行打印机等。 （2）数据通道中断源。如磁盘、磁带等。 （3）实时时钟。 （4）故障源。如电源掉电等。三、物理地址是存储器的实际地址，一个存储单元的物理地址是惟一，逻辑地址为程序设计中所使用的存储器地址，它由段基址和地内偏移地址两部份构成，物理地址=段基址16偏移地址，可见一个存储单元的逻辑地址可以有若干个四、（1）MOV DL,17HMOV AL,7FH（2）IN AL,DXOUT DX,AX五、MOV SI ,1000HMOV CX ,1000MOV DX ,30FH MOV AL ,10000000B OUT DX,AL M

19、OV DX,30DHMOV AL ,0FFH OUT DX ,ALCALL D1MSCALL D1MSL1: MOV BL ,8MOV AL ,0OUT DX ,AL CALL D1MSCALL D1MSMOV AL ,SIAND AL ,ALJP L2OR AL ,80HL2: OUT DX ,ALCALL D1MSCALL D1MSROR AL,1DEC BLJNZ L2MOV AL ,0FFHOUT DX ,ALCALL D1MSCALL D1MSINC SI LOOP L1HLT；微机原理与接口技术（九）一、填空题（每题5分，共5个题，总分25分）1、数制转换：247.86= H =_

20、BCD2、8086CPU中典型总线周期由_个时钟周期组成，其中T1期间，CPU输出_信息。3、异步串行通信数据格式由起始位、 位、 位和 位等4部分组成。4、如果一个程序在执行前（CS）=0A7F0H，（IP）=2B40H，该程序的起始物理地址是_ 。5、用4K4bit的存储器芯片构成32KB的存储器, 所需要的芯片数是 片。二、（10分）EU与BIU各自的功能是什么？如何协同工作？三、（10分）8086如何响应一个可屏蔽中断请求？简述响应过程。四、（15分）用其他指令完成和下列指令一样的功能:(1) REP MOVSB (2) REP LODSB (3) REP STOSB (4) REP

21、SCASB五、（15分）已知某8255A在系统中占用888BH号端口地址，现欲安排其PA，PB，PC口全部为输出，PA，PB口均工作于方式0模式，并将PC6置位，使PC3复位，试编写出相应的初始化程序。答案一、1、F7.DCH 001001000111.10000110 BCD 2、4个 地址 3、数据 奇偶校验 停止 4、0AAA40H 5、16二、EU是执行部件，主要的功能是执行指令。BIU是总线接口部件，与片外存储器及I/O接口电路传输数据。EU经过BIU进行片外操作数的访问，BIU为EU提供将要执行的指令。EU与BIU可分别独立工作，当EU不需BIU提供服务时，BIU可进行填充指令队列

22、的操作。三、当8086收到INTR的高电平信号时，在当前指令执行完且IF=1的条件下，8086在两个总线周期中分别发出INTA#有效信号；在第二个INTA#期间，8086收到中断源发来的一字节中断类型码；8086完成保护现场的操作，CS、IP内容进入堆栈，请除IF、TF；8086将类型码乘4后得到中断向量表的入口地址，从此地址开始读取4字节的中断处理程序的入口地址，8086从此地址开始执行程序，完成了INTR中断请求的响应过程。四、(1) LOOP1:MOV AL,BYTE PTR SIMOV ES:BYTE PTR DI, ALINC SI 或: DEC SIINC DI 或: DEC DI

23、LOOP LOOP1(2) LOOP1:MOV AL, BYTE PTR SIINC SI 或: DEC SILOOP LOOP1(3) LOOP1:MOV ES:BYTE PTR DI, ALINC DI 或: DEC DILOOP LOOP1(4) LOOP1:CMP AL,ES:BYTE PTR DIJE EXITINC DI 或: DEC DILOOP LOOP1EXIT:五、MOV AL， 80H OUT 8BH，AL MOV AL，ODH OUT 8BH，AL MOV AL，06HOUT 8BH，AL 微机原理与接口技术（十）一、填空题（每题5分，共5个题，总分25分）1、1011

24、1B用十六进制数表示为 H，八进制数表示为 O。2、微机的系统总线是连接CPU、存储器及I/O的总线，AB表示 总线，DB表示 总线，CB表示 总线。3、8086CPU是一个 位的微处理器，具有 位数据总线， 位地址总线，可寻址空间为 。4、8086CPU可分为 、 两大部分。5、用8k1位的存储芯片，组成8k16位的存储器，需用 扩展，要用 片。二、（10分）8086基本总线周期是如何组成的？各状态中完成什么基本操作？三、（10分）设采用8251A进行串行异步传输，每帧信息对应1个起始位，7个数据位，1个奇/偶校验位，1个停止位，波特率为4800，则每分钟能传输的最大字符数为多少个？四、（1

25、5分）某系统中8253占用地址为100H103H。初始化程序如下： MOV DX， 103HMOV AL， 16HOUT DX， ALSUB DX， 3OUT DX， AL问：1、此段程序是给8253的哪一个计数器初始化？安排工作在哪种工作方式？2、若该计数器的输入脉冲的频率为1MHZ，则其输出脉冲的频率是多少？五、（15分）根据下列要求编写一个汇编语言程序:：代码段的段名为COD_SG数据段的段名为DAT_SG堆栈段的段名为STK_SG变量HIGH_DAT所包含的数据为95将变量HIGH_DAT装入寄存器AH，BH和DL程序运行的入口地址为START答案一、1、11，212、地址，数据，系统

26、3、16，16，16，64KB4、RAM，ROM5、分段，2二、基本总线周期由4个时钟(CLK)周期组成，按时间顺序定义为T1、T2、T3、T4。在T1期间8086发出访问目的地的地址信号和地址锁存选通信号ALE；T2期间发出读写命令信号RD#、WR#及其它相关信号；T3期间完成数据的访问；T4结束该总线周期。三、每帧占1+7+1+1=10位，波特率为4800 bit/s,故每分钟能传送的最大字符数为4800*60/10=28800个四、计数器0 工作于方式3 45.454KHZ 五、DAT_SG SEGEMNTHIGH_DAT DB 95DAT_SG ENDS;STK_SG SEGMENT

27、DW 64 DUP(?)STK_SG ENDS;COD_SG SEGMENTMAIN PROC FARASSUME CS: COD_SG, DS: DAT_SG, SS: STK_SGSTART: MOV AX, DAT-SG MOV DS, AX MOV AH, HIGH_DAT MOV BH, AHMOV DL, AHMOV AH, 4CHINT 21HMAIN ENDPCOD_SG ENDS END START数据结构（八）一、填空题（本大题共有5个题，每题5分，共25分，将正确答案填在空格处）1.设栈的输入序列是1，2，n，若输出序列的第一个元素是n,则第i个输出元素是 。2.广义表（

28、a，b，c，d）的表尾是 。3.有一棵非空的二叉树（假设第0层为根结点）,其第i层上至多有 个结点。4.已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半法查找时90时，需进行 次查找可确定成功。5.已知二维数组A10.205.10,每个数组元素占4个存储单元，若按行优先顺序存放数据元素，a105的存储地址是1000，则a189的存储地址是 。二、（本题满分为10分）证明：树中的结点数等于所有结点的度数加1。三、（本题满分为10分）如图所示有向图，采用dijkstra算法求出从顶点0到其它顶点的最短路径，并说明整个计算过程。四、（本题满分为15分）已

29、知，一棵二叉树中根遍历的结点序列为DCBGEAHFIJK，先根遍历的结点序列为ABCDEGFHJIK，画出对应的二叉树，并写出后根遍历的结点序列。五、（本题满分为15分）试写出希尔排序的算法。答案：一、1.n-i+1 2.（） 3.2i 4.2 5.1208二、根据树的定义，在一棵树中，除树根结点外，每个结点有且仅有一个前驱结点，也就是说，每个结点与指向他的一个分支一一对应，所以除树根之外的结点数等于所有结点的分支数（度数），从而可得树中的结点数等于所有节点的度数加1.三、 （1）选4 （2）选1 （3）选4 （4）选6 （5）选7 （6）选8或选6四、五、见课本数据结构（九）一、填空题（本大

30、题共有5个题，每题5分，共25分，将正确答案填在空格处）1.在一个长度为n的顺序表中删除第i个元素（0in-1）时，需向前移动 个元素。2.广义表（a）,(b),c),(d)）的长度是 。3.深度为K的完全二叉树至少有 个结点。4.在一棵二叉树中，度为零的结点的个数为n0,度为2的结点的个数为n2，则有n0。5.长度为255的表，采用分块查找法，每块的最佳长度是 。二、（本题满分为10分）有7个带权结点，其权值分别为：4，7，8，2，5，16，30，试以它们为叶子结点构造一棵哈夫曼树（要求按每个结点的左子树根结点的权值小于等于右子树根结点的权值的次序构造）三、（本题满分为10分）在带头结点的单

31、链表中查找数据域为x的结点，并返回首次找到的节点的序号。四、（本题满分为15分）设有一组关键字（19，01，23，14，55，20，84，27，68，11，10，77），采用散列函数H(key)=key%13，采用开放定址法的二次探测再散列方法解决冲突，试在0到18的形式列地址空间中对该关键字序列构造散列表。五、（本题满分为15分）二叉树采用链式存储结构，试设计一个算法计算一棵给定二叉树的所有结点数。答案：一、1.n-i-1 2.3 3.2k-1 4. n2 5.15二、构造的哈夫曼树为：三、int locate(SNode *p,ElemType x) int i=0;SNode *q=pn

32、ext;while(q!=null&qdata!=x) q=qnext; i+;if(q=null)return(-1);else return(i); 四、计算散列地址：H(19)=19%13=6 H(01)=01%13=1 H(23)=23%13=10H(14)=14%13=1(冲突) H1=(1+12)%19=2 H(55)=55%13=3 H(20)=20%13=7 H(84)=84%13=6(冲突) H1=(6+12)%19=7（冲突） H2=(6-12)%19=5H(27)=27%13=1（冲突） H1=(1+12)%19=2（冲突） H2=(1-12)%19=0 H(68)=68

33、%13=3（冲突） H1=(3+12)%19=4H(11)=11%13=11 H(10)=10%13=10（冲突） H1=(10+12)%19=11（冲突） H2=(10-12)%19=9H(77)=77%13=12 散列表为：012345678910-1112131415161718270114556884192010231177 ASL=（7*1+2*2+3*3）/12=20/12=5/3五、int nodes(BTree *b) int num1,num2; If(b=null)return(0)；elsenum1=nodes(bleft);num2=nodes(bright);retu

34、rn(num1+num2+1); 数据结构（十）一、填空题（本大题共有5个题，每题5分，共25分，将正确答案填在空格处）1.设某二叉树前序为abdcef, 中序为dbaecf，则此二叉树的后序为 。2.具有4个顶点的无向完全图有 条边。3.已知二维数组A1020,每个数组元素占1个存储单元，若按列优先顺序存放数据元素，a00的存储地址是200，则a612的存储地址是 。4.具有n个结点的完全二叉树的深度为 。5. 已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半法查找时47时，需进行 次查找可确定成功。二、（本题满分为10分）（1）将图（a）中给定的树转换成二叉树（2）将图（b）中给定的二叉树转换成树（3）将图（c）中给定的森林转换成二叉树 三、（本题满分为10分）求以数据集（4，5，6，7，10，12，18）为结点权值所构造的哈夫曼树，并且计算出其带权路径长度。四、（本题满分为15分）假设查找表以单链表的形式存储，试写出对此单链表进行顺序查找时的实现算法。五、（本题满分为15分）写出一趟快速排序的算法。答案：一、1. dbefca2.63.3324. log2n+15.4二、（1） （2） （3）三、（4+5）*4+（10+6+7）*3+(18+12)*2=165四、struct Elemtype /数据元素的数据类型定义key