4．具有24个记录的序列，采用起泡排序最少的比较次数为( )。 A．1 *B．23 C．24 D．529
5．用某种排序方法对序列(25，84，21，47，15，27，68，35，20)进行排序，记录序列的变化情况如下：25 84 21 47 15 27 68 35 20、20 15 21 25 47 27 68 35 84、15 20 21 25 35 27 47 68 84、15 20 21 25 27 35 47 68 84，则采用的排序方法是( )。 A．直接选择排序 B．起泡排序 *C．快速排序 D．2-路归并排序 6．在排序过程中，键值比较的次数与初始序列的排序顺序无关的是( )。
A．直接插入排序和快速排序 B．直接插入排序和归并排序 *C．直接选择排序和归并排序 D．快速排序和归并排序
7．( )方法是从未排序序列中依次取出元素与已经排序序列中的元素进行比较，将其放人已经排序序列的正确位置上。
A．归并排序 *B．插入排序 C．快速排序 D．选择排序
8．( )方法是从未排序序列中挑选元素，并将其依次放入已经排序序列的一端。 A．归并排序 B．插入排序 C．快速排序 *D．选择排序
9．( )方法是对序列中的元素通过适当的位置变换将有关元素一次性地放置在其最终位置上。 A．归并排序 B．插入排序 *C．快速排序 D．基数排序
10．将上万个无序并且互不相等的正数存储在顺序存储结构中，采取( )方法能够最快地找到其中最大的正整数。
A．快速排序 B．插入排序 *C．选择排序 D．归并排序 11．以下四种排序方法，要求附加内存空间最大的是( )。
A．插入排序 B．选择排序 C．快速排序 *D．归并排序 12．以下说法错误的是( )。
A．直接插入排序的空间复杂度为O(1) B．快速排序附加存储开销为O(log2n) *C．堆排序的空间复杂度为O(n) D．2-路归并排序的空间复杂度为O(n)，需要附加两倍的存储开销 13．以下不稳定的排序方法是( )。
A．直接插入排序 B．冒泡排序 *C．直接选择排序 D．2-路归并排序 14．以下稳定的排序方法是( )。
A．快速排序 *B．起泡排序 C．直接选择排序 D．堆排序 15．以下时间复杂度不是O(n2)的排序方法是( )。
A．直接插入排序 *B．2-路归并排序 C．起泡排序 D．直接选择排序 16．以下时间复杂度不是O(nlog2n)的排序方法是( )。
A．堆排序 *B．直接插入排序 C．2-路归并排序 D．快速排序 17．快速排序方法在( )情况下最不利于发挥其长处。
A．要排序的数据量太大 B．要排序的数据中含有多个相同值 *C．要排序的数据已基本有序 D．要排序的数据个数为奇数
18．设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用( )方法。
A．起泡排序 B．快速排序 *C．堆排序 D．基数排序
19．一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法以第一个记录为基准得到的一次划分结果为( )。
A．38，40，46，56，79，84 *B．40，38，46，79，56，84 C．40，38，46，56，79，84 D．40，38，46，84，56，79
20．一组记录的关键码为(46，79，56，38，40，84)，则利用堆排序的方法建立的初始堆为( )。 ·
A．79，46，56，38，40，84 *B．84，79，56，38，40，46 C．84，79，56，46，40，38 D．84，56，79，40，46，38
21．若用起泡排序法对序列(18，14，6，27，8，12，16，52，10，26，47，29，41，24)从小到大进行排序，共要进行( )次比较。 A．33 B．45 *C．70 D．91
29
二、判断题
╳1．如果某种排序算法是不稳定的，则该方法没有实际意义。
√2．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要原因之一。
╳3．对于n个记录的集合进行起泡排序，所需要的平均时间是O(nlog2n)。 √4．对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2n)。 ╳5．对于n个记录的集合进行快速排序，所需要的平均时间是O(n)。 ╳6．堆排序所需的时间与待排序的记录个数无关。 三、填空题
1．对于n个记录的集合进行归并排序，所需的附加空间为___ O(n)__。
2．设表中元素的初始状态是按键值递增的,分别用堆排序、快速排序、起泡排序、归并排序进行递增排序，则__起泡排序_最节省时间，__快速排序__最费时间。对快速排序来讲，其最好情况下的时间复杂度为__ O(nlog2n)____，最坏情况下的时间复杂度为___ O(n2)____。
3．目前以比较为基础的内部排序的时间复杂度T(n)的范围是_ O(nlog2n)~O(n2)___，其比较次数与待排序的记录的初始状态无关的是_归并排序、直接选择排序__。
4．在内部排序中要求附加的内存容量最大的是_快速排序、归并排序___，排序时不稳定的是___希尔排序、选择排序、归并排序____。
5．从时间上看，快速排序的平均性能优于其她排序方法，但从空间上看，快速排序需要一个栈空间来实现递归。若每一趟排序都将记录序列均匀地分割成长度接近的两个序列，则栈的最大深度为__log2n___；在最坏情况下，栈的深度为__n-1__。 6．堆的形状是一棵___完全二叉树__。
7．若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是_稳定__的，否则称为___不稳定__的。
8．按照排序过程涉及的存储设备的不同，排序可分为__内部__排序和__外部_排序。 9．直接插入排序是稳定的，它的时间复杂度为_ O(n2)__，空间复杂度为__ O(1)__。 10．归并排序要求待排序列由若干个___有序___的子序列组成。 11．2-路归并排序的时间复杂度是___ O(nlog2n)____。
12．在对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较__3_次。
13．在堆排序和快速排序中，若原始记录接近正序和反序，则选用__堆排序___；若原始记录无序，则最好选用____快速排序__。
14．在插入排序和选择排序中，若初始数据基本正序，则选用____插入排序___；若初始数据基本反序，则选用__选择排序__。 四、应用题
1．一组关键字(19，01，26，92，87，11，43，87，21)，进行起泡排序，试列出每一趟排序后的关键字序列，并统计每趟排序所进行的关键字比较次数。 答：略。
2．对上题给出的关键字序列，进行选择排序，列出每一趟排序后的关键字序列，并统计每趟排序所进行的关键字比较次数。 答：略。
3．从快速排序法的基本原理不难看出，对n个元素组成的线性表进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。(1)试问：当n=7时，在最好情况下需进行多少次比较?说明理由。(2)对n=7给出一个最好情况的初始排列的实例。
答：(1)当n=7，k(3趟划分)=3时，在最好情况下，第一趟6次比较，第二趟各需2次比较，共10次比较即可。(2)对n=7一个最好情况的初始排列：4，7，5，6，3，1，2。
4．对下列一组关键字(46，58，15，45，90，18，10，62)，试写出快速排序的每一趟的排序结果，并标出第一趟中各元素的移动方向。 答：略。
5．判断以下序列是否为堆，若不是，则调整为堆。
30
(1)(97，86，48，73，35，39，42，57，66，20) (2)(12，70，33，65，24，56，48，92，86，31)
(3)(103，97，56，38，66，23，42，12，30，52，06，20) (4)(05，56，20，23，40，38，29，61，35，76，28，99)
答：(1)、(3)、是大根堆；(2)不是堆，调整为小堆（12，24，33，65，31，56，48，92，86，70）；(4) 不是堆，调整为小堆（05，23，20，35，28，38，29，61，56，76，40，99）
6．设有5000个无序的元素，希望用最快的速度挑选出前10个大元素。请说明哪种算法最好，并说明理由。
答：采用堆排序。
7．用图示给出关键字序列(92，37，86，33，12，57，25)初始建堆和输出前两个最小关键字后重建堆的过程。 答：略。
操作系统练习题参考答案
(一)单项选择题
B 1.操作系统是计算机系统的一种( )。A．应用软件 B．系统软件 c．通用软件 D．工具软件
D 2．操作系统目的是提供一个供其他程序执行的良好环境，因此它必须使计算机( ) A.使用方便 B．高效工作 C.合理使用资源 D．使用方便并高效工作
A 3．允许多个用户以交互方式使用计算机的操作系统是( )。 A．分时操作系统 B．批处理单道系统 C．实时操作系统 D．批处理多道系统
C 4．下列系统中( )是实时系统。 A．计算机激光照排系统 B．办公自动化系统 C.化学反应堆控制系统 D．计算机辅助设计系统
D 5．操作系统是一种系统软件，它( )。 A．控制程序的执行 B．管理计算机系统的资源 C.方便用户使用计算机 D．管理计算机系统的资源和控制程序的执行
C 6．计算机系统把进行( )和控制程序执行的功能集中组成一种软件，称为操作系统 A．CPU管理 B．作业管理 C．资源管理 D．设备管理
D 7．批处理操作系统提高了计算机系统的工作效率，但( )。 A.不能自动选择作业执行 B．无法协调资源分配 c．不能缩短作业执行时间 D在作业执行时用户不能直接干预
B 8．分时操作系统适用于( )。 A．控制生产流水线 B．调试运行程序 c．大量的数据处理 D．多个计算机资源共享
C 9．在混合型操作系统中，“前台”作业往往是指( )。 A．由批量单道系统控制的作业 B．由批量多道系统控制的作业 c．由分时系统控制的作业 D．由实时系统控制的作业 B 10.在批处理兼分时的系统中，对( )应该及时响应，使用户满意。A．批量作业 B.前台作业 c．后台作业 D．网络通信
C 11．实时操作系统对可靠性和安全性要求极高，它( )。 A．十分注重系统资源的利用率 B．不强调响应速度 c．不强求系统资源的利用率 D．不必向用户反馈信息
D 12．分布式操作系统与网络操作系统本质上的不同之处在于( )。 A．实现各台计算机之间的通信 B．共享网络个的资源 c．满足较大规模的应用 D．系统中若干台计算机相互协作完成同一任务
B 13．( )为用户分配主存空间，保护主存中的程序和数据不被破坏，提高主存空间的利用率。 A处理器管理 B．存储管理 c．文件管理 D．作业管理
A 14．在现代计算机系统层次结构中，最内层是硬件,最外层是使用计算机的人，人与硬件之间是( )。 A．软件系统 B．操作系统 c．支援软件 D．应用软件
B 15.财务管理软件是一种专用程序,它属于( ) A．系统软件 B．应用软件 c接口软件 D．支援软件
C 16.在多道程序设计技术的计算机系统中，中央处理器( )。 A.只能被一个程序占用 B．可以被多个程序同时占用 c．可以被多个程序交替占用 D．可以被操作系统和另一个程序同时占用
31
D 17．( )不是一种永久性的存储设备，当电源被切断时，其中的信息就会消失。 A．硬盘 B.磁带 c.软盘 D.主存储器
C l8．中央处理器可以直接存取( )中的信息。A．光盘 B．软盘 c．主存储器 D．硬盘
B 19．中央处理器存取寄存器中信息的速度与使用主存储器和辅存储器信息相比( )。 A.比较快 B.最快 c.差不多 D．最慢
D 20．存放在( )信息只能顺序存取，无法随机访问。A．硬盘 B．软盘 c．光盘 D．磁带
B 21．在操作系统的层次结构中．( )是操作系统的核心部分，它位于最内层。 A．存储管理 B．处理器管理 C．设备管理 D．作业管理
C 22.在操作系统的层次结构中，各层之间( )。A.互不相关 B．内、外层互相依赖 c．外层依赖内层 D．内层依赖外层
C 23．多道程序设计系统中，让多个计算问题同时装入计算机系统的主存储器( )。 A并发执行 B．顺序执行 c.并行执行 D．同时执行
B 24.引入多道程序设计技术后，处理器的利用率( )。 A．有所改善 B．极大地提高 c.降低了 D．无变化，仅使程序执行方便
C 25．计算机系统采用多道程序设计技术后，（ )。 A．缩短了每个程序的执行时间 B．系统效率随并行工作道数成比例增长 c．提高了系统效率 D．使用设备时不会发生冲突 D 26．进程是( )。 A．一个系统软件 B．与程序概念等效 c．存放在内存中的程序 D．执行中的程序
A 27.进程的( )和并发性是两个很重要的属性。 A．动态性 B.静态性 c．易用性 D．顺序性
C 28．已经获得除( )以外所有运行所需资源的进程处于就绪状态。 A主存储器 B．打印机 C．CPU D．磁盘空间
C 29．在一个单处理器系统中，处于运行态的进程( )。 A．可以有多个 B．不能被打断 c．只有一个 D．不能请求系统调用
D 30.对于一个单处理器系统来说,允许若干进程同时执行，轮流占用处理器．称它们为（ )的。 A.顺序执行 B.同时执行 c.并行执行 D.并发执行
B 31．操作系统根据( )控制和管理进程，它是进程存在的标志。 A．程序状态字 B．进程控制块 c．中断寄存器 D．中断装置
D 32．若干个等待占有cPU并运行的进程按一定次序链接起来的队列为( )。A．运行队列 B．后备队列 c．等待队列 D．就绪队列
A 33. 中断优先级是按照中断事件的重要性和紧迫程度来确定的，是在( )。 A硬件设计时固定下来的 B作业说明书中申请的 c．动态分配的 D．由中断装置确定的
C 34．存储管理的目的是( ) A、方便用户 B．提高主存空间利用率 C．方便用户和提高主存利用率 D．增加主存实际容量
B 35.为了实现存储保护，对共享区域中的信息( )。A．既可读，又可写 B．只可读，不可修改 c．能执行，可修改 D.既不可读,也不可写
A 36．提高主存利用率主要是通过( )实现的。 A．内存分配 B．内存保护 c．地址转换 D．内存扩充
C 37．采用虚拟存储器的前提是程序的两个特点，—是程序执行时某些部分是互斥的、二是程序
的执行往往具有( )。 A．顺序性 B．并发性 C局部性 D．并行性 B 38．虚拟存储器的容量是由计算机的地址结构决定的，若cPu有32位地址，则它的虚地址空间
为( )字节。 A．2G B．4G C．100K D．640K A 39．操作系统对文件实行统一管理，最基本的是为用户提供( )功能。A．按名存取 B．文件共享 C．文件保护 D．提高文件的存取速度
C 40．采取哪种文件存取方式，主要取决于( )。 A．用户的使用要求 B．存储介质的特性 C．用户的使用要求和存储介质的特性 D．文件的逻辑结构
B 41．文件系统的按名存取主要是通过( )实现的。 A．存储空间管理 B．目录管理 C．文件安全性管理 D．文件读写管理
32
相关推荐：
loading