第七章：图练习题(2)

A、n B、[log2n] C、[log2(n+1)] D、「log2(n+1)

3、采用顺序查找方式查找长度为n的线性表时，平均查找长度为（ ） A、n B、n/2 C、(n+1)/2 D、(n-1)/2

4、采用折半查找方法检索长度为n的有序表，检索每个元素的平均比较次数（ ）对应判定树的高度（设高度大于等于2）。

A、小于 B、大于 C、等于 D、大于等于

5、已知有序表（13，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，查找成功的比较次数为（ ）。 A、1 B、2 C、3 D、4

6、对线性表进行折半查找时，要求线性表必须（ ）。

A、以顺序方式存储 B、以链接方式存储 C、以顺序方式存储，且结点按关键字有序排序 D、以链接方式存储，且结点按关键字有序排序 7、顺序查找法适合于存储结构为（ ）的线性表。

A、散列存储 B、顺序或链接存储 C、压缩存储 D、索引存储

8、采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（ ）个结点最佳。 A、10 B、25 C、6 D、625

9、从键盘依次输入关键字的值：t,u,r,b,o,p,a,s,c,l，建立二叉排序树，则其先序遍历序列为（ ），中序遍历序列为（ ）。

A、abcloprstu B、alcpobsrut C、trbaoclpsu D、trubsaocpl 10、折半查找和二叉排序树的时间性能（ ）。 A、相同 B、不相同

11、一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（ ）个结点。

A、2k-1-1 B、2k-1 C、2k-1+1 D、2k-1

12、利用逐点插入法建立序列{50，72，43，85，75，20，35，45，65，30}对应的二叉排序树以后，查找元素35要进行（ ）元素间的比较。 A、4次 B、5次 C、7次 D、10次

13、设Hash地址空间为0到m-1，哈希函数为h(k)=k%p，为了减少发生冲突的可能性，一般取p为（ ）。

A、小于m的最大奇数 B、小于m的最大素数 C、小于m的最大偶数D、小于m的最大合数。 二、 填空题

1、折半查找效率较高，但要求结点（ ）并且要求线性表（ ）；而对于顺序查找，则线性表的存储方式（ ）。

2、假设在有序线性表A[0]—A[9]上进行折半查找，则比较一次查找成功的结点数为（ ），比较二次查找成功的结点数为（ ），比较三次查找成功的结点数为（ ），比较四次查找成功的结点数为（ ），比较五次查找成功的结点数为（ ），平均查找长度为（ ）。 3、在n个记录的有序顺序表中进行折半查找，最大的比较次数是（ ）。 4、折半查找判定树既是一种（ ），也是一种（ ）。

5、顺序查找法的平均查找长度为（ ）；折半查找法的平均查找长度为（ ）；分块查找法（以顺序查找确定块）的平均查找长度为（ ）；分块查找法（以折半查找确定块）的平均查找长度为（ ）；哈希表查找法采用链接法处理冲突时的平均查找长度为（ ）。

6、对于长度为n的线性表，若进行顺序查找，则时间复杂度为（ ）；若进行折半查找，则时间复杂度为（ ）；若采用分块查找（假定总块数和每块长度均接近n的开方），则时间复杂度为（ ）。

7、用二分法查找一个线性表时，该线性表必须具有的特点是（ ），而分块查找法要求将待查找的表均匀地分成若干块且块中诸记录的顺序可以是任意的，但块与块之间（ ）。 8、采用散列技术来实现查找，需要解决的问题有：（ ）和（ ）。 9、在散列存储中，处理冲突有（ ）和（ ）两类方法。 10、（ ）法构造的哈希函数肯定不会发生冲突。

11、在各种查找方法中，平均查找长度与结点个数无关的查找方法为（ ）。 三、 简答题

1、 简述顺序查找、折半查找和分块检索法对被检索表中元素中的要求。若检索表中每个

元素概率相同，则对一个长度为n的表，用上面三种方法检索时平均查找长度为多少？

2、 画出长度为10的有序表进行折半查找的一棵判定树，并求其等概率下的平均查找长

度。

3、 有一个10000项线性表，若采用分区查找，问分成多少块较理想？平均查找长度为多

少？若每块为40 ，则平均查找长度为多少？

4、 输入一组关键字{17，31，13，11，20，35，25，8，4，11，24，40，27}，画出由此

生成的二叉排序树，如果对每个结点的查找概率相等，求其ASL，并分别画出下列操作后的二叉排序树。（1）插入数据9；（2）删除结点17；（3）再删除结点13。 5、 设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函

数：H(key)=key，采用开放地址法的线性探测再散列方法解决冲突，试在0到18的Hash地址空间中对该关键字序列构造Hash表。

6、 若哈希表的地址范围为0到9，Hash函数为H(key)=(key2+2)mod 9,并采用链地址法处

理冲突，画出元素7，4，5，3，6，2，8，9依次插入哈希表以后该哈希表的状态。

答案： 一、 选择题

1AB 2D 3C 4A 5B 6C 7B 8B 9CA 10B 11D 12A 13B 二、 填空题

1、 按关键字值大小有序，顺序存储；既可以顺序存储，也可以链接存储。 2、 1，2，4，8，5，3.7 3、 log2 (n+1)

4、 二叉排序树，理想平衡树

5、 (n+1)/2, ((n+1)*log2(n+1))/n-1, (s2+2s+n)/（2s）, log2(n/s+1)+s/2, 1+a/2 (a为装填因

子)

6、 O(n), O(log2n), O(n的开平方)

7、 表中元素必须按关键字有序；必须有序，即前一块中每个元素的关键字必须大于

后一块中每个元素的关键字。

8、 选择哈希函数，设定处理冲突的方法 9、 开放定址法，链地址法 10、 直接定址 11、 哈希查找法 三、 简答题

1、对于顺序检索法，表中元素可以以任何方式存放；而采用折半检索法时要求表中元素必须是有序的，而且需要以顺序方式进行存储；若利用分块检索法，则要求表中元素需“块”间有序，但每一块内元素可任意存放。

顺序和折半查找的平均检索长度分别为：(n+1)/2和log2(n+1)-1。分块法的平均查找长度与确定所在块所采用的检索方法有关，若用顺序法确定块，则长度为(n/s+s)/2+1，若用折半法确定块，则查找长度为log2(n/s+1)+s/2，其中s为每块含有的元素个数。 2、对长度为10的有序表进行折半查找的判定树如下： 查找成功的平均查找长度为：

ASL=（1*1+2*2+3*4+4*3）/10=2.9

3、分成100块较理想。平均查找长度ASL=(b+s)/2+1=(100+100)/2+1=101。若每块长度为40，则可分250块，平均查找长度ASL=(b+s)/2+1=146。

4、相应二叉排序树如下：

平均查找长度ASL=（1*1+2*2+3*4+4*2+5*2）/12=35/12

5、依题意，m=19，线性探测再散列的下一地址计算公式为： d1=H(key)

dj+1=(dj+1)%m j=1,2,… 构造的Hash表如下： 1 2 3 4 5 6 7 8 9 10 1 地址号 0 1 14 55 27 68 19 20 84 23 11 关键字 1 2 1 4 3 1 1 3 1 1 地址计算次数 7、 将7，4，5，3，6，2，8，9依次插入杂凑表后，状态如下

12 10 3 13 77 2 14 15 16 17 18

第十章：内部排序练习题

一、 选择题

1、下述几种排序方法中，平均查找长度最小的是（ ）。 A、插入排序 B、选择排序 C、快速排序 D、归并排序

2、设关键字序列为（3，7，6，9，7，1，4，5，20），对其进行排序的最小交换次数为（ ）。

A、6 B、7 C、8 D、20

3、下列排序算法中不稳定的有（ ）。

A、直接选择排序 B、直接插入排序 C、冒泡排序 D、二叉排序

E、Shell排序 F、快速排序 G、归并排序 H、堆排序 I、基数排序

4、内部排序多个关键字的文件，最坏情况下最快的排序方法是（ ），相应的时间复杂度为（ ），该算法是（ ）排序方法。

A、快速排序 B、插入排序 C、归并排序 D、简单选择排序 E、O(nlog2n) F、O(n2) G、O(n2log2n) H、O(n) I、稳定 J、不稳定

5、对初始状态为递增的表按递增顺序排序，最省时间的是（ ）算法，最费时间的算法是（ ）。

A、堆排序 B、快速排序 C、插入排序 D、归并排序 6、下述几种排序方法中，要求内存量最大的是（ ）。 A、插入排序 B、选择排序 C、快速排序 D、归并排序

7、在下面的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ ）。 A、希尔排序 B、冒泡排序 C、插入排序 D、选择排序

8、下列排序中，排序速度与数据的初始排列状态没有关系的是（ ）。 A、直接选择排序 B、基数排序 C、堆排序 D、直接插入排序

9、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法为（ ）。

A、快速排序 B、堆排序 C、归并排序 D、直接插入排序

10、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列正确位置上的方法，称为（ ）。 A、希尔排序 B、冒泡排序 C、插入排序 D、选择排序

11、 每次把待排序的元素划分为左右两个子区间，其中左区间中元素的关键字均小于等于基准元素的关键字，右区间中元素的关键字均大于基准元素的关键字，则此排序方法为（ ）。 A、堆排序 B、快速排序 C、冒泡排序 D、Shell排序

12、排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ ）。

A、希尔排序 B、归并排序 C、插入排序 D、选择排序

13、n个记录的直接插入排序所需记录关键码的最大比较次数为（ ）。 A、nlog2n B、n2/2 C、(n+2)(n-1)/2 D、n-1

14、n个记录的直接插入排序所需的记录最小移动次数为（ ）。 A、2(n-1) B、n2/2 C、(n+3)(n-2)/2 D、2n

15、快速排序在（ ）情况下最不利于发挥其长处，在（ ）情况下最易发挥其长处。 A、被排序的数据量很大 B、被排序的数据已基本有序 C、被排序的数据完全有序 D、被排序的数据中最大与最小值相差不大 E、要排序的数据中含有多个相同值。

16、直接插入排序和冒泡排序的平均时间复杂度为（ ），若初始数据有序（正序），则时间复杂度为（ ）。

A、O(n) B、O(log2n) C、O(nlog2n) D、O(n2)

17、一组记录的关键字为（45，80，55，40，42，85），则利用堆排序的方法建立的初始堆为（ ）。

A、（80，45，55，40，42，85） B、（85，80，55，40，42，45） C、（85，80，55，45，42，40） D、（85，55，80，42，45，40）

二、填空题

1、在直接插入和直接选择排序中，若初始数据基本有序，则选用（ ），若初始数据基本反序，则选用（ ）。

2、在对一组记录（50，40，95，20，15，70，60，45，80）进行冒泡排序时，第一趟需进行相邻记录的交换的次数为（ ），在整个排序过程中共需进行（ ）趟才可完成。 3、n个记录的冒泡排序算法所需最大移动次数为（ ），最小移动次数为（ ）。 4、对n个结点进行快速排序，最大比较次数为（ ）。

5、在对一组记录（50，40，95，20，15，70，60，45，80）进行（大根）堆排序时，根据初始记录构成初始堆后，最后4条记录为（ ）。

6、对于直接插入排序、冒泡排序、简单选择排序、堆排序、快速排序有：（1）当文件“局部有序”或文件长度较小时，最佳的内部排序方法是（ ）。（2）快速排序在最坏情况下时间复杂度是（ ）比（ ）性能差；（3）就平均时间而言，（ ）最佳。

7、在堆排序、快速排序和归并排序中，若只从存储时间考虑，则应首先选取（ ）方法，其次选用（ ）方法，最后选用（ ）方法；若只从排序结果的稳定性考虑，则应选取（ ）方法；若只从平均情况下排序最快考虑，则应选取（ ）方法，若只从最坏情况下排序最快并节省内存，则应选取（ ）方法。 三、 简答题

1、 简要回答下列问题：

（1） 什么是内部排序、外部排序？（2）什么是排序方法的稳定性？

2、 已知序列（70，83，100，65，10，32，7，9），请给出采用插入排序、快速排序和冒

泡排序方法对该序列做升序排序的每一趟的结果。

3、 有如下一组关键字（25，67，78，24，38，64，55，22，15，48），判定其是否为

堆，若不是堆，请调整为一个小根堆，使堆排序将按关键字从大到小排列，写出调整过程。

习题答案

一、 选择题

1C 2A 3AEFH 4CEI 5CB 6D 7D 8B 9C 10C 11B 12D 13C 14A 15BC 16DA 17B 18BD 二、填空题

1、 直接插入排序、直接选择排序 2、 6，7

3、 3n(n-1)/2,0 4、 n(n-10)/2 5、 (50,60,40,20)

6、 (1)直接插入排序 （2）O(n2) ，堆排序 (3)快速排序

7、 堆排序，快速排序，归并排序，归并排序，快速排序，堆排序 三、简答题 1、 P263

2、 采用插入排序的各趟结果如下：

（1）（70，83），100，65，10，32，7，9 （2）（70，83，100），65，10，32，7，9 （3）（65，70，83，100），10，32，7，9 （4）（10，65，70，83，100），32，7，9 （5）（10，32，65，70，83，100），7，9 （6）（7，10，32，65，70，83，100），9 （7）（7，9，10，32，65，70，83，100） 其他排序略 3、略

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第七章：图练习题(2)在线全文阅读。