软件基础习题 答案 - 图文(6)

29．在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为( )。 A．n B．log2n C．(h+1)／2 *D．h 二、判断题

√1．分块查找方法的平均查找长度低于顺序查找，高于折半查找。

√2．若采用线性探测再散列法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置为空，因为这会影响以后的查找。

╳3．前序遍历二叉排序树的结点就可以得到排好序的结点序列。

╳4．在任一二叉排序树上查找某个结点的查找时间都小于用顺序查找法查找同样结点的线性表的查找时间。 ╳5．虽然关键字序列的顺序不一样，但依次生成的二叉排序树却是一样的。

√6．对两棵具有相同关键字集合的形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。

√7．在二叉排序树上插入新的结点时，不必移动其他结点，仅需要改动某个结点的指针，由空变为非空即可。 ╳8．在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针域置空即可。 三、填空题

1．任何结点之间都不存在_逻辑_关系，这是集合这种逻辑结构的基本特点。

2．在开散列表上查找键值等于K的结点，首先必须计算该键值的__散列地址__，然后再通过指针查找该结点。 3．在索引顺序表上，对于顺序表中的每一块，索引表中有相应的一个“索引项”。每个索引项有两个域：块内最大__元素__值和块__首__位置。

4．索引顺序表上的查找分两个阶段：一、___确定元素所在的块__；二、___在块内查找元素__。该查找方法称为__分块__查找。

5．二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值__大_于其左孩子(及其子孙)的键值且__小__于其右孩子(及其子孙)的键值。

6．在表示一棵二叉排序树的二叉链表上，要找键值比某结点X的键值__大__的结点，只需通过结点x的右指针到它的右子树中去找。

7．中序遍历一棵二叉排序树所得到的结点访问序列是键值的___递增__序列。

8．二叉排序树上的查找长度不仅与__元素个数_有关，也与二叉排序树的__输入序列__有关。

9．二叉排序的查找效率与树的形态有关。当二叉排序树退化为一棵单支树时，查找算法退化为__顺序___查找，平均查找长度上升为__（n+1）/2__。

10．__散列__查找法的平均查找长度与元素个数n无关。

11．在具有20个元素的有序表上进行折半查找，则比较一次查找成功的结点数为__1___，比较两次查找成功的结点数为__2__，比较五次查找成功的结点数为_5_。总的平均查找长度为__37/10___。 12．当所有结点的值都相等时，用这些结点构造的二叉排序树上只有___一个结点__。

13．折半查找方法仅适用于这样的表：表中的记录必须__有序__，其存储结构必须是__顺序存储___。

14．考虑具有如下性质的二叉树：除叶结点外，每个结点的值都大于其左子树上的一切结点的值，并小于或等于其右子树上的一切结点的值。现把9个数1，2，3，4，5，6，7，8，9填入如图9-1所示的二叉树中，并使之满足上述性质(圆圈旁边的数字表示插入结点的序号)。

15．设线性表L=(a1，a2，?，an)(n>2)，表中元素按值的递增顺序排列。对一个给定的值k，分别用顺序查找法和折半查找法查找与k相等的元素，比较次数分别为s和b，若查找不成功，则s和b的数量关系是_s>b_。 16．某顺序存储的表，其中有10000个元素，已按关键字的值升序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键字都不相同。用顺序查找法查找时，查找成功时的平均比较次数为__10001/2___，最大比较次数为__10000__。现把10000个元素按排列顺序划分成若干组，使得每一组中有g个元素(最后一组可能小于g)。查找时，先从第一组开始，通过比较各组的最后一个元素的关键项值，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的比较次数最小的g是__100__，此时的平均比较次数是__101__。

17．长度为225的表，采用分块查找法，每块的最佳长度是_15__，应分_15_块，若每块的长度为10，则平均查找长度为_35/2_。

26

18．已知有序表为(13,17,20,32,48,54,65,79,86,91,97)，当采用折半查找法查找86时需进行_2__次比较可确定查找成功，查找48时需进行_4_次比较可确定查找成功，查找100时需进行_4_次比较才能确定查找不成功。 四、应用题

1．已知有长度为9的表(16,29,32,5,89,41,14,65,34)，它们存储在一个哈希表中，利用线性探测再散列法，要求它在等概率情况下查找成功的平均查找长度不超过3。

(1)该哈希表的长度m应设计成多大？ (2)设计相应的哈希函数。(3)将数据填入到哈希表中。 (4)计算查找成功时的平均查找长度。

答：(1)该哈希表的长度m=12 （公式）(2)H(key)=key (3) 0 1 2 3 4 5 6 7 8 9 10 11 89 34 14 16 5 29 41 32 65 1 2 1 1 2 1 1 1 2

(4)ASL=(1+2+1+1+2+1+1+1+2)/9=12/9=4/3

2．假定有n个关键字，它们具有相同的哈希函数值，用线性探测法把这n个关键字存入到哈希表中要做多少次探测？

答：n个关键字都是同义词，因此用线性探测法解决冲突都会发生冲突，所以探测次数为：1+2+??+n=n(n+1)/2.

3．地址空间为0—14的哈希表中，对关键字序列(JAN，FEB，MAR，APR，MAY，JUN，JUL，AUG，SEP，OCT，

NOV，DEC)构造哈希函数H(key)=└i／2┘，其中i为关键字中第一个字母在字母表中的序号。用线性探测法和链地址法分别求出这两个哈希表在等概率情况下查找成功和查找不成功的平均查找长度。 答：(1) 用线性探测法 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 APR AUG DEC FEB JAN MAR MAY JUN JUL SEP OCT NOV 1 2 1 1 1 1 2 4 5 2 5 6 查找成功ASL=(1+2+1+1+1+1+2+4+5+2+5+6)/12=31/12 查找不成功ASL=(5+4+3+2+1+9+8+7+6+5+4+3+2+1+1)/15=61/15 (2) 链地址法：图略。

查找成功ASL=(1*7+2*4+3*1)/12=18/12=3/2

查找不成功ASL=(3+1+2+2+1+4+3+3+1+2+1+1+1+1+1)/15=27/15=9/5 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 2 3 4 5 6 7 8 9 10 11 12 13 14 27 68 05 19 45 21 20 70 24 11 10 1 1 1 1 2 1 3 6 1 2 4 查找成功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的结点，下述关键字序列哪一个是不可能在二叉排序树上查找到的序列？

27

(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．二叉排序树中的关键字互不相同，则其中最小元素无左孩子，最大元素无右孩子，此命题是否正确？最小元素和最大元素一定是叶子吗？一个新结点总是插在二叉排序树的某叶子上吗？

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

第八节 排序

一、选择题

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)进行排序，记录序列的变化情况如下：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．基数排序

28

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

╳1．如果某种排序算法是不稳定的，则该方法没有实际意义。

√2．当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要原因之一。

╳3．对于n个记录的集合进行起泡排序，所需要的平均时间是O(nlog2n)。 √4．对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2n)。 ╳5．对于n个记录的集合进行快速排序，所需要的平均时间是O(n)。 ╳6．堆排序所需的时间与待排序的记录个数无关。 三、填空题

1．对于n个记录的集合进行归并排序，所需的附加空间为___ O(n)__。

2．设表中元素的初始状态是按键值递增的,分别用堆排序、快速排序、起泡排序、归并排序进行递增排序，则__起泡排序_最节省时间，__快速排序__最费时间。对快速排序来讲，其最好情况下的时间复杂度为__

2

O(nlog2n)____，最坏情况下的时间复杂度为___ O(n)____。

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．判断以下序列是否为堆，若不是，则调整为堆。

29

(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．最慢

D 20．存放在( )信息只能顺序存取，无法随机访问。A．硬盘 B．软盘 c．光盘 D．磁带 (二)填空题

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

4．计算机系统把进行_资源管理_和控制程序执行的功能集中组成一种软件称为操作系统。

30

5．操作系统使用户合理__共享资源__，防止各用户间相互干扰。

6．使计算机系统使用方便和__高效地工作_是操作系统的两个主要设计目标。 7．批处理操作系统、__分时操作系统_和实时操作系统是基本的操作系统。 8．用户要求计算机系统中进行处理的一个计算机问题称为__作业__。 9．批处理操作系统按照预先写好的__作业说明书__控制作业的执行。

10．在多道操作系统控制下，允许多个作业同时装入__主存储器___，使中央处理器轮流地执行各个作业。 11．批处理操作系统提高了计算机系统的__工作效率__，但在作业执行时用户不能直接干预作业的执行。 12．在分时系统中，每个终端用户每次可以使用一个由__时间片__规定的cPu时间。 13分时系统具有同时性、独立性、及时性和__交互性___等特点。

14．在批处理兼分时系统中，往往把由分时系统控制的作业称为__前台__作业，把由批处理系统控制的作业称为__后台 __作业。

l5．实时系统要求有__高可靠性和安全性 __,不强求系统资源的利用率。 (三)简答题

1.什么是计算机系统?它由哪几部分组成?

计算机系统是按用户的要求接收和存储信息，自动进行数据处理并输出结果信息的系统。计算机系统由硬件系统和软件系统组成。硬件系统是计算机系统赖以工作的实体，软件系统保证计算机系统按用户指定的要求协调地工作。

2．计算机系统的资源包括哪些?

计算机系统的资源包括两大类:硬件资源和软件资源。硬件资源主要有中央处理器、主存储器、辅助存储器和各种输入输出设备。软件资源有编译程序、编辑程序等各种程序以及有关数据。 3.简述操作系统的定义。

操作系统是计算机系统的一种系统软件，它统一管理计算机系统的资源和控制程序的执行。 4．为计算机设计操作系统要达到什么目的?设计时应考虑哪些目标?

操作系统是一种系统程序，其目的是为其他程序的执行提供一个良好的环境。它有两个主要设计目标：一是使计算机系统使用方便，二是使计算机系统能高效地工作。 5．从操作系统提供的服务出发，操作系统可分哪几类?

从操作系统提供的服务出发，操作系统可分为：批处理操作系统、分时操作系统、实时操作系统、网络操作系统和分布式操作系统。

6．简述操作系统的五大功能。

从资源管理的观点出发，操作系统具有五大功能：(1)处理器管理。为用户合理分配处理器时间，提高处理器工作效率。(2)存储管理。为用户分配主存空间，保护主存中的程序和数据不被破坏，提高主存空间的利用率。(3)文件管理。管理用户信息，为用户提供按文件名存取功能，合理分配文件的存储空间。(4)设备管现。负责设备的分配、启动以及虚拟设备的实现等.(5)作业管理。实现作业调度和控制。

31

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库软件基础习题 答案 - 图文(6)在线全文阅读。