软件技术基础网络三答案

1、电子科技大学软件技术基础一、选择题（每题1分，共20分）在数据结构中，从逻辑上可以把数据结构分成（D）A动态结构和静态结构B紧缩结构和稀疏结构C外部结构和内部结构D线 性结构和非线性结构与单向链表相比，双向链表的优点是（B）A可以进行随机访问B更灵活地访问相邻结点C不需要表头或表尾指针D 插入、删除操作更简便假设n个元素按照一定的顺序进栈和出栈，已知第一个出栈的元素是最后 一个进栈的元素，则（C）是正确的A第i个出栈的元素是第i个入栈的元素B第i个出栈的元素是第n-i个入栈的元素C第i个出栈的元素是第n-i +1个入栈的元素D不能确定循环队列q当前队列中元素的个数为（B）A （rear - f

2、ront） %m B （rear - front + m）%m C rear - front +1D rear - front - 1 一个10X10的对称矩阵釆用压缩存储方式，以行优先方式，第一行只存 储一个元素，则第5行第8列的元素放位置距离第一个元素为（D）个单元A 58 B 85 C 23 D 32具有k层的二叉树只有度为0和度为2的结点，则该二义树上最多有（C）结点A 2k B 2k+l C 2 kl D 2（kl） -1在一个有向图中，所有顶点的入度之和与所有顶点的出度之和之间有（C）关系A二分之一 B两倍C相等D不确定就图的邻接矩阵而言，（C）是正确的。A第i行的非零元素个数与第

3、i列的非零元素个数一定相等B矩阵中非零元 素的个数等于图中的边数C笫i行非零元素个数为对应顶点的出度D零元素的个 数为顶点个数的两倍二义排序树为（C）形态时，查找效率最高。A所有结点的左子树均为空B所有结点的右子树均为空C具有最小深度D 具有最大深度 一个长度为n的顺序表中，在第i个元素前插入一个新元素时，需要向后 移动（B）个元素A ni B ni + 1 C ni 1 D i在文件系统中，用户使用文件是（A）A按名存取B按内容存取C按类型存取D按时间存取进程同步原语P操作的意义是（B）A释放资源B申请资源C阻塞进程D唤醒进程评价操作系统的性能主要从以下（D）方面A并发性、共享性B分时与实时

4、C CPU速度、内存容量D可靠性、吞吐 量、响应时间 CPU与外设的并行工作能力是由（A）提供的A硬件B系统软件C应用软件D数据库临界区是（B）A 一段数据B 一段程序C页表一项 D PCB的一项系统出现死锁时一定同时保持了四个必要条件，对资源采用按序分配算法 后可破坏其中的（D）条件。A互斥B不剥夺条件C部分分配条件D环路条件下列事件必定会引起进程调度的是（B）A新创建的进程进入就绪态B进程从执行态进入等待态C进程从等待状态 进入就绪状态D进程访问页面时因缺页而产生缺页中断多任务系统得以实现的前提是（A）A处理器可以与外设并行操作B可以进行进程控制C有足够多的设备供多 个任务使用D每个任务一

5、个不同的标识号存储管理中，分页式虚拟存储管理的页面淘汰算法有（C）A最佳适应B分时调度C FIFO算法D动态重定位下列关于分段存储管理描述正确的是（A）A以段为单位分配存储空间，段内空间必须连续B以段为单位分配存储空 间，每段长度相等C程序分为多段，各段之间一定不连续D程序分为多段，各段 之间一定连续二、判断题（每题1分，共10分）（F）线性表的链接存储结构优于线性存储结构。（T）任何一个二义树的叶子结点在先序、中序和后序遍历序列中的相对次序 是不会改变的（F）将一棵树转换为二义树后，根结点不一定没有右子树（F）邻接表只能用于存储无向图。（T）如果图的邻接矩阵是一个三角矩阵，则该图中不存在回路

6、。（F）虚拟存储管理技术主要突破了程序指令必须在内存中才能执行的限制（T）操作系统是程序的集合。（F）分时系统的出现是解决批处理系统CPU利用率低的问题。（F）进程与程序之间是一一对应的关系。（F）生产者和消费者之间主要是竞争消息资源的关系。三、填空题数据结构是讨论计算机系统中数据的组织形式及相互关系 。把客观事物采用计算机进行识别、存储和加工所进行的描述，统称为数据 。在有n个顶点的有向图中，每个顶点的度最大可达2(n-l) o在简单插入和简单选择排序中，如果待排序序列已基本正序，则选 择简单插入算法比较高效，如果待排序序列基本是反序，则选择简单选 择算法比较高效。普通用户可以通过命令接口控

7、制计算机，而程序员可以通过在程序中调用系统调用控制计算机进程至少有三种基本状态： 等待态、执行态和就绪态常见的内存管理方法有分区管理 、分页管理、 分段管理和段页式管理在分页存储管理中，程序逻辑地址与程序装入后的内存物理地址之间的映 射是由页表和地址转换机构完成的。四、简答与简单应用题根据数据结构的二元描述法，画出结点逻辑关系图B= (K, R)K=kl,k2,k9R =<kl, k3>, <kl, k8>, <k2, k4>, <k2, ko>, <k3, k9>, <k5, k6>, <k8, k9>, &

8、lt;k9, k7>, <k4, k7> ,<k4, k6>, <k2, k3»答:写一个算法求循环链表的元素个数，设循环链表表首指针为head int take_count(head)count = 0;辻(head 二二 NULL)return count;p = head;count +二 1;while(p->next != head)count +二 1;p = p->next;return count;操作系统有哪些特征，请简要描述这些特征的含义？答：操作系统的特征有：并发性、共享性、虚拟性和不确定性（异步性）。并发性是指：

9、多个程序同时在系统中并发执行；共事性指多个进程共同使用 有限的资源；虚拟性指系统通过一定的技术将一个物理设备变成多个逻辑对应物， 如虚拟内存、虚拟设备等；不确定性指进程在系统中“走走停停”，它们系统中的 执行顺序和执行时间是不确定的。并发性和共事性是基本特征，虚拟性和不确定性是并发和共卒的必然结果。简述分页式存储管理和分段式存储管理的区别答：（1） “分页”是系统活动，用户无法介入，页的大小固定；“分段” 是用户可见的，段大小可变（2）页是信息的物理单位，不是完整的逻辑单位；段是完整的逻辑信息单位（3）分页的作业空间是一维的，是单一线性空间；分段的作业空间是二维 的。设备驱动程序应具有哪些功能

10、？答：设备驱动程序应具备以下功能：（1）接收用户I/O服务请求，校验是否符合要求（2）确认设备状态，是否能执行相应的I/O操作（3）启动设备执行相应的I/O操作（4）响应设备中断，完成相应处理五、应用题将一棵树变换成二叉树，然后写出先、中、后序遍历次序答：变换后的二叉树中序遍历顺序：5268973 10 41后序遍历顺序：59876 10 4321某分页式存储管理系统存放了一个具有6个页面的作业，页面按页号从小到大存放的块号分别为5, 10, 3, 6, 20, 2设每页大小为4096字节。问：（1）请画出该作业的页表（2）每块页面在内存中的起始地址（3）作业中语句MOV12345, 2345将使用哪块页面，哪个地址的内存单元答:(1) (2)页号块号起始地址0520480110409602312288362