软件基础习题所有题目和答案-未精简的 - 下载本文

4.有一个400项的表,欲采用索引顺序查找方法进行查找,问:

(1)分成多少块最为理想? (2)每块的理想长度是多少? (3)平均查找长度是多少?

答:(1)分成20最为理想? (2)每块的理想长度是20 (3)平均查找长度是(20+1)/2+(20+1)/2=21

5.设有一组关键字(19,05,21,24,45,20,68,27,70,11,10),用哈希函数H(key)=key%13,采用线性探测再散列方法解决冲突,试在0—14的散列地址空间中对该关键字序列构造哈希函数,并求查找成功和查找不成功时的平均查找长度。 答: 0 1 27 1 2 3 68 1 4 5 05 1 6 19 1 7 45 2 8 21 1 9 20 3 10 70 6 11 24 1 12 11 2 13 10 4 14 查找成功ASL=(1+1+1+1+2+1+3+6+1+2+4)/11=23/11 查找不成功ASL=(1+2+1+2+1+10+9+8+7+6+5+4+3+2+1)/15=62/15

6.线性表的关键字集合(47,26,120,08,39,68,96,23,70,63,57),已知散列函数为H(key)=key%13,采用链地址法处理冲突。设计出这种链表结构,并计算该表的查找成功和查找不成功时的平均查找长度。 答:图略。

查找成功ASL=(1*6+2*4+3*1)/11=17/11

查找不成功ASL=(3+1+1+3+1+4+1+1+3+1+2+2+1)/13=24/13

7.分别画出在线性表(06,10,19,24,37,42,50,83)中进行折半查找,查找关键字10和30的过程。 答:图略。查找关键字10:2次和30:3次。

8.将(for,case,while,switch,break,do,define,const,if,int)中的关键字依次插入初始状态为空的二叉排序树(按字母在字母表中的序号排序)中,请画出所得到的树T。然后画出删除for之后的二叉排序树T,若再将for插入到T中得到二叉排序树T”,问T”与T是否相同? 答:图略。T”与T不同

9.设二叉排序树中的关键字由1—100内的整数构成,现要查找关键字为63的结点,下述关键字序列哪一个是不可能在二叉排序树上查找到的序列?

(1) 12,25,7,68,33,34,37,63 (2) 92,20,91,24,88,25,36,63 (3) 95,22,91,24,94,25,63 (4) 21,89,77,29,36,38,41,47,63 答:(3) 是不可能在二叉排序树上查找到的序列

10.给定表(25,18,48,07,76,52,81,70,92,15)。试按元素在表中的次序将它们依次插入一棵初始状态为空的二叉排序树,画出插入完成之后的二叉排序树。 答:图略。

11.二叉排序树中的关键字互不相同,则其中最小元素无左孩子,最大元素无右孩子,此命题是否正确?最小元素和最大元素一定是叶子吗?一个新结点总是插在二叉排序树的某叶子上吗?

答:最小元素无左孩子,最大元素无右孩子,此命题正确。最小元素和最大元素不一定是叶子。一个新结点不一定总是插在二叉排序树的某叶子上。

26

第八节 排序

一、选择题

1.在文件局部有序或文件较小的情况下,最佳的排序方法是( )。

*A.直接插入排序 B.直接选择排序 C.起泡排序 D.归并排序

2.初始序列已经按键值有序时,用直接插入算法进行排序,需要比较的次数为( )。 *A.n-1 B.log2n C.2log2n D.n*n 3.快速排序在最坏情况下的时间复杂度是( )。

A、O(log2n) B.O(nlog2n) *C.O(n2) D.O(n3)

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

27

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 二、判断题

╳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给出一个最好情况的初始排列的实例。

28

答:(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.判断以下序列是否为堆,若不是,则调整为堆。 (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.可以被操作系统和另一个程序同时占用

D 17.( )不是一种永久性的存储设备,当电源被切断时,其中的信息就会消失。 A.硬盘 B.磁带 c.软盘 D.主存储器

C l8.中央处理器可以直接存取( )中的信息。A.光盘 B.软盘 c.主存储器 D.硬盘

B 19.中央处理器存取寄存器中信息的速度与使用主存储器和辅存储器信息相比( )。 A.比较快 B.最快 c.差不多 D.最慢

29

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.文件读写管理

B 42.文件管理实际上是对( )的管理。 A.主存空间 B.辅助存储空间 C.逻辑地址空间 D.物理地址空间

C 43.逻辑文件可分为流式文件和( )两类。A.索引文件 B.链接文件 C.记录式文件 D.只读文件 A 44.由一串信息组成,文件内信息不再划分可独立的单位,这是指( )。A.流式文件 B.记录式文件 C.连续文件 D.串联文件

B 45.磁盘机属于( )。 A字符设备 B.存储型设备 c.输入输出型设备 D.虚拟设备

D 46.对存储型设备,输入输出操作的信息是以( )为单位传输的。 A.位 B.字节 C.字 D.块 B 47.对输入输出设备,输入输出操作的信息传输单位为( )。 A.位 B.字符 C.字 D.块 C 48.用户要求计算机处理的一个计算问题称为一个( )。 A.进程 B程序 C.作业 D系统调度 D 49.一个作业的完成要经过若干加工步骤,这每个步骤称为( )。A.作业流 B.子程序 C.子进程 D.作业步 (二)填空题

1.计算机系统是按用户要求接收和存储信息,自动进行___数据处理____并输出结果信息的系统。 2.计算机是由硬件系统和__软件_系统组成。 3.软件系统由各种__程序__和数据组成。

30