软件基础答案

《软件基础答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、电子科技大学软件工程硕士研究生入学试题参考答案（2009）考试科目：软件基础《操作系统》部分一、是非题，正确的划V,错的划X,并改正（共15分，每小题1・5分）1.进程执行唤醒原语以后，该进程由就绪状态转入执行状态。（X）2.以优先级为基础的进程调度算法，总是调度等待队列中优先级最高的进程。（X）3.从物理概念上讲，信号量值大于零表示阻塞进程数，小于零的绝对值表示可用资源数。（X）4.设备独立性是指在用户程序中要执行I/O操作时，只需用逻辑设备名提出1/0请求，而不必局限于某个特定的物理设备。（J）5.在循环首次适应算法中，空闲区按大小递增顺序链成空闲

2、区链。（X）6.文件的逻辑结构是指一个文件在外存上的存储组织形式。（X）7.页表屮实现地址映射的最基木内容是该页的虚页号所对应的物理块号。（J）&作业曲后备状态转变为运行状态是曲进程调度程序完成的。（X）9.SPOOLING技术的实质是将物理上的独享设备改造为逻辑上的共享设备。（J）10.动态重定位的主耍优点是地址变换不需要硬件地址变换机构,而由软件实现。（X）二、简答题（共15分）1.（7分）在Windows2000/XP'

3、'采用请求分页式存储管理方式，当线程产生一次缺页屮断吋，内存管理器将引发屮断的页面及其后续少量页面装入内存，为什么？答：这是采

4、用群页式调页策略，由于线程在执行过程屮，一般相邻页面逻辑上具有较密切的联系，当线程产生一•次缺页屮断时，内存管理器将引发屮断的页面及其后续少量页面装入内存，可以有效地降低缺页率。2.（8分）比较DMA控制方式与通道控制方式的异同。答：DMA控制方式与通道控制方式都是以内存为屮心，实现设备与内存直接交换数据的控制方式。两者的主要区别是：（1）由于通道是小型的处理机，有自己的指令系统，所以在通道控制方式下，CPU只要发出启动指令，可启动通道执行相应的通道指令，完成I/O操作。而DMA方式则是由DMA控制器识别CPU发出的I/O指令，控制I/O过程，但数据传

5、送方向（I/O）存放数据的内存始址及传送数据的长度等都由CPU控制。因此，与DMA方式相比，通道方式所需的CPU干预更少。⑵DMA方式传送数据的单位是一个数据块（若干个字节），而通道方式传送数据的单位是多个数据块。因此，通道方式传送数据的效率更高。三、（10分）画出具有挂起状态的进程状态图。四、（10分）下面是生产者与消费者进程的算法描述，请改正算法中的错误并说明错误原因Varmutex,empty,full：semaphore:=1,n,0；buffer：array

6、0..n-11ofmessage;in,out:integer:=0,0beginp

7、arbeginProducer:beginrepeatP(empty)P(mutex)buffer(in):=m;in:=(in+l)modn;V(full)V(mutex)untilfalseend;consumer:beginrepeatP(full)P(mutex)m:=buffer(out);out:=(out+l)modn;V(mutex)V(empty)untilfalseend;parendend答：在生产者与消费者进程中，两个P操作应交换，否则可能产生死锁。《数据结构》部分五、简答题（共20分，每题5分）1•有XYZ三个元索，已知它们的

8、入栈顺序为XYZ,现给定栈空间为只能存放两个元索,利用此栈，你能调度出哪些出栈序列？答：四种XYZ,XZY,YXZ,YZXo2.简述二叉树的两种常用的存储方法。答：顺序结构（一维数组）和链式结构（二叉链表）。3.简述顺序查找、折半查找方法对初始表各有什么耍求。答：顺序查找：等概率，任意表。折半查找：等概率，有序表4.说明线性表的顺序结构和链式结构各H的优缺点。答：顺序结构：优点：随机访问容易，辅助空间用得少缺点：数据元索插入和删除时有许多元索的存储位置耍移动，空间的扩展性并。链式结构：优点：数据元索插入和删除时操作简单，空间的扩展性好缺点：随机访问不容

9、易，辅助空间用得较多。六、（10分）说明任意三个结点可构造多少种树？多少种二叉树？图示Z。答：树2种二叉树5种七、（20分）以字母A、B、C、D、E、F、G、H为结点构造一棵完全二叉树（图示）。1、写出此二叉树先序、中序、后序遍历和层次遍历的结果。2、用类C语言或伪Pascal语言写出先序遍历的算法。答：构造的完全二叉树如下图（字母顺序不唯一）1、先序遍历：中序遍历：后序遍历：ABDEGCFHGDBEAFCHGDEBFHCAABCDEFHG层次遍历：2、先序遍历的算法(类C)：voidpreorder(pointptr)if(!ptr){visit(p

10、tr->data);preorder(prr->lchild);preorder(prr->r