电⼦科技⼤学
《软件技术基础》课程⾃测题⼆⼀、选择题（每题1分，共20分）
●数据结构不是⼀门研究数值计算的学科，它主要研究计算机中的（A）以及它们之间的（F）和运算等⽅⾯
A 计算机⽅法C存储D数据映像E 排列G 设备●链表不具备的特点是（C）
A 不必先准备⾜够的存储空间B 插⼊元素时不需要移动元素位置D 存储空间与长度成正⽐
●判断循环队列q为空的条件是（A）
q->front != q->rear C q->front == (q->rear + 1)%MAXNUM D q->front != (q->rear + 1)%MAXNUM●设有串S1=”STUDENT”和串S2=”TEACH”，函数add（x，y）实现将y串连接到x
串的后⾯，函数subs（s，i，j）将得到从串s中第i个字符开始的j个字符组成的⼦串，函数len（s）返回串s的长度，则add(subs(S1,3,len(S2)),subs(S2,len(S1)-4,3))的结果是（C）
A ACHUDENT
B ACHUDE D UDEACH
●某⼆叉树的先序遍历序列和后序遍历序列正好相反，则该⼆叉树⼀定是（C）
A 空⼆叉树或仅有⼀个结点B 完全⼆叉树 D 没有度为1的结点
●设X与Y是⼆叉树上的两个结点，X要在中序遍历中位于Y之前，则⼀定有（A）
B X在Y的右⽅C X在Y的上⽅D X在Y的下⽅
●⼀个具有k条边的⽆向图，采⽤邻接表存储，则共需要（B）个邻接结点
（k－1）/2 D k（k＋1）/2
●采⽤折半检索⽅式对⼀个有15个元素的有序线性表检索，元素的平均查找长度为（B）
A 10/3 C 8 D 4
●快速排序算法在（C）情况下效率最低
A 线性表元素个数过多B 线性表元素个数为偶数C
D 线性表元素个数较少●操作系统的作⽤是（B）
A 提供在磁盘上操作⽂件的功能
B 把源程序编译为⽬标程序D实现⽤户要求完成的任务●系统调⽤是指⽤户程序中调⽤（C）
A 进程
B 线程系统提供的⽂件
●设备管理功能包括：I/O操作、设备分配、（C）
A 设备安装与维护
B 缓冲区管理与分配 D 虚拟设备管理与分配●死锁产⽣的必要条件之⼀是（B）
A 程序中出现死循环B
C 进程⼀次申请所有的资源
D 进程在阻塞时将已获得的资源提供给正在执⾏的进程使⽤
●在可变分区存储管理中，最佳适应分配算法要求对空闲分区表项按（B）进⾏排列
A 按地址从低到⾼B
C 按建⽴时间从早到晚D 按回收时间从早到晚
●（C）特征不是分时系统的基本特征
A 多路性
B 独⽴性 D 交互性
●要使计算机能够⼯作起来，不能缺少下列设备中的（C）
A ⿏标B 键盘 D 光驱
●操作系统采⽤多道程序并发执⾏技术后，造成（C）
A 缩短了每个程序的执⾏时间
B 减少了程序重复执⾏的次数 D 减少了系统开销
●⼀种既有利于短⼩进程⼜兼顾到长进程的进程调度算法是（D）
A 先来先服务B 轮转
C 最⾼优先级算法●进程控制是（A）
B 控制进程获得资源C 控制进程以达到同步D 控制进程推进避免出现死锁⼆、判断题（每题1分，共10分）（F）队列的操作⽅式是先进后出。
（T）数据的最⼩单位是数据元素⽽不是数据项
（T）⼀颗含有N个结点的完全⼆叉树，它的深度是[ log2N]+1.（T）图的深度优先遍历序列和⼴度优先遍历序列不是唯⼀的
（T）简单插⼊、简单选择和冒泡排序算法所需的附加存储空间都⼀样多。（F）段表和页表都是⽤户根据作业情况⽽建⽴的（T）进程的PCB是进程存在的唯⼀标识。（T）CPU与I/O设备之间是可以并⾏⼯作的。
（F）虚拟存储器是⼀种使内存扩⼤的技术，当作业全部装⼊虚存中时，作业才能够得到运⾏。（T）分页存储管理可利⽤快表提⾼系统吞吐量三、填空题
●树和图属于⾮线性结构，栈和队列（串）属于线性结构。
●设元素⼊栈的顺序为1 2 3 4，为了得到1 3 4 2 的出栈顺序，各元素⼊栈和出栈操作的顺序是⼊栈出栈⼊栈⼊栈出栈⼊栈出栈出栈。
●散列检索⽅式中，解决冲突的⽅法可以分为两类，它们是开放地址法和链地址法。
●在⼀个图中，所有顶点的度数之和等于所有边数的2倍。
●根据数据交换⽅式，通道可分为字节多路通道、选择通道、数组多路通道●在进程的四个特征中，动态性和异步性是进程的两个最基本特征。
●进程的静态实体由程序体、数据段和进程控制块三部分组成四、简答与简单应⽤题
●简述下列术语：树的深度、图的路径、⽹络
●某图的邻接表如下所⽰，请根据该邻接表，从顶点F开始深度遍历该图和⼴度遍历该图时的顶点序列。（4分）
答：
●对⽐分时系统和实时系统的特点，它们各⾃侧重的特点是什么？
答：分时系统具有多路性、交互性和独⽴性三个特点。多路性是指分时系统⽀持多个终端⽤户同时⼯作；交互性是指系统采⽤联机服务⽅式，每个⽤户都可以在终端上与系统交互；独⽴性是指通系统分时轮流为多个⽤户服务，每个⽤户在各⾃的终端上的⼯作互不⼲扰。
实时系统具有及时响应、简单交互和⾼可靠性。及时响应是指系统必须在严格的时间限制内完成对信息接收分析处理和发送过程；简单交互是指实时系统⽀持较弱的与⽤户交互能⼒；⾼可靠性指实时系统要求有⾼的可靠性以适应特殊环境。分时系统侧重系统交互性，实时系统侧重系统及时响应性。
●进程的3个基本状态是什么？根据这3个基本状态，画出进程的状态转移图，并写出状态转移的原因。
答：进程的3个基本状态是：就绪态、执⾏态和阻塞（等待）态
就绪到执⾏：CPU空闲，进程调度
执⾏到就绪：执⾏态进程的CPU时间⽚到时，或有更⾼优先级进程进⼊就绪队列执⾏到阻塞：执⾏态进程等待系统服务或执⾏I/O操作，⽆法继续执⾏阻塞到就绪：阻塞态进程因阻塞事件释放、系统服务完成●请简要描述⼏个常⽤的进程调度算法基本原理
答：常⽤的进程调度算法有FIFS，最短CPU运⾏期优先、时间⽚轮转、最⾼优先级和多级队列反馈等。FCFS：系统按进程进⼊就绪队列的先后次序调度
最短CPU运⾏期优先：调度时选择就绪队列中需要使⽤CPU时间最短的进程；时间⽚轮转：每个进程分配⼀定的CPU使⽤时间，按照⼀定次序依次轮流调度进程最⾼优先级：每个进程具有⼀定优先级，调度时选择就绪进程中优先级最⾼的进程
多级队列反馈：按优先级⾼低将就绪集成分为多个队列，不同队列分配长度不同的时间⽚，越⾼级别越先调度，时间⽚也越⼩，在相同优先级的进程之间按照时间⽚轮转调度，进程的优先级是动态调整的，仅当⾼优先级队列中没有就绪进程时才调度低⼀级队列中的进程。
五、应⽤题
●设系统中有7个同类资源，有P1、P2、P3三个进程竞争这些资源，假设每个进程需要三个这类资源就可以运⾏完毕。（1）请证明该系统不会出现死锁
（2）有多少个进程时可能会出现死锁？请描述⼀个死锁状态答：
（1）证明，三个进程竞争7个资源，⾄少有⼀个进程能获得3个资源，从⽽推进完毕，并归还所占资源，那么系统的资源总数量能够满⾜剩下两个进程的需求，不会出现死锁
（2）有四个进程时系统可能死锁，当有3个进程申请到2个资源、⼀个进程申请得到1个资源时，系统没有空余资源，⽽每个进程的总需求都不能得到满⾜，最终系统将死锁。
●在分页式虚拟存储管理系统中，运⾏⼀个有5个页⾯的进程，该进程在系统中最多分得
4个内存块。进程执⾏时页⾯访问顺序为：1、2、3、4、1、2、5、1、2、3、4、5。问（1）在FIFO页⾯淘汰算法下，整个过程缺页中断的次数。注意包括页⾯第⼀次进⼊内存时（必须写明推导过程）
（2）在LRU（最近最久未⽤）算法下，整个过程缺页中断的次数。（必须写明推导过程）答：
因篇幅问题不能全部显示，请点此查看更多更全内容