查找排序习题及答案.doc

查找 排序 习题及答案一、 选择题1 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( C )。 A (n-1)/2 B. n/2 C. (n+1)/2 D. n2 用二分（对半）查找表的元素的速度比用顺序法( D )A必然快 B. 必然慢 C. 相等 D. 不能确定3 下面关于m阶B树说法正确的是( B ) 每个结点至少有两棵非空子树； 树中每个结点至多有m一1个关键字; 所有叶子在同一层上; 当插入一个数据项引起B树结点分裂后，树长高一层。A B. C. D. 4 将10个元素散列到100000个单元的哈希表中，则（ C ）产生冲突。A. 一定会 B. 一定不会 C. 仍可能会5 下列内部排序算法中： A快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序（1） 其比较次数与序列初态无关的算法是（ C，D ）（2）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，kn）的情况下，排序效率最高的算法是（ B ）（3）排序的平均时间复杂度为O(nlogn)的算法是（A,C,F）为O(nn)的算法是（B,D,E）6 下列序列中，（ C ）是执行第一趟快速排序后所得的序列。 A. 68，11，18，69 23，93，73 B. 68，11，69，23 18，93，73 C. 93，73 68，11，69，23，18 D. 68，11，69，23，18 93，737 下列四个序列中，哪一个是堆（ C ）。 A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,158 排序方法有许多种，（1）C法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）A法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端； 交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）B和（4）D是基于这类方法的两种排序方法， 而（4）D是比（3）B效率更高的方法；（5）G法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。 （1）-（5）: A选择排序 B快速排序 C插入排序 D起泡排序 E归并排序 Fshell排序 G堆排序 H基数排序二、 填空题1 在有序表A1.20中，按二分查找方法进行查找，查找长度为5的元素个数是_5_2 哈希表是通过将查找码按选定的_(1) 哈希函数_和 _(2) 解决冲突的方法_，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是_(3) 选择好的哈希函数_和 _(4) 处理冲突的方法_。一个好的哈希函数其转换地址应尽可能_(5) 均匀_，而且函数运算应尽可能_(6)_ 简单_。3 分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成_30_块最好：若分成25块，其平均查找长度为_31.5（块内顺序查找）_。4 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_比较_和记录的_移动_。5 设用希尔排序对数组98，36，-9，0，47，23，1，8，10，7进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需_3_趟，写出第一趟结束后，数组中数据的排列次序_ (10,7,-9,0,47,23,1,8,98,36)_。三、 应用题1 设哈希(Hash)表的地址范围为017，哈希函数为：H (K)=K MOD 16, K为关键字，用线性探测再散列法处理冲突，输入关键字序列: (10,24,32,17,31,30,46,47,40,63,49)造出哈希表，试回答下列问题： (1) 画出哈希表示意图； (2) 若查找关键字63，需要依次与哪些关键字比较?(3) 若查找关键字60，需要依次与哪些关键字比较?(4) 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。答：（1）散列地址01234567891011121314151617关键字3217634924401030314647比较次数11631211133（2）查找关键字63，H（k）=63 MOD 16=15，依次与31，46，47，32，17，63比较。（3）查找关键字60，H（k）=60 MOD 16=12，散列地址12内为空，查找失败。（4）ASLsucc=23/112 输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题。（1） 按次序构造一棵二叉排序树BS。(2) 依此二叉排序树，如何得到一个从大到小的有序序列？（2） 画出在此二叉排序树中删除“66”后的树结构。3 在查找和排序算法中，监视哨的作用是什么？答：监视哨的作用是免去查找过程中每次都要检测整个表是否查找完毕，提高了查找效率。4 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程： (1) 归并排序 每归并一次书写一个次序。 (2) 快速排序 每划分一次书写一个次序。(3) 堆排序 先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。 答：(1)2路归并 第一趟:18,29,25,47,12,58,10,51；第二趟:18,25,29,47,10,12,51,58；第三趟:10,12,18,25,29,47,51,58(2)快速排序 第一趟:10,18,25,12,29,58,51,47；第二趟:10,18,25,12,29,47,51,58；第三趟:10,12,18,25,29,47,51,88(3)堆排序 建大堆:58,47,51,29,18,12,25,10；51,47,25,29,18,12,10,58；47,29,25,10,18,12,51,58；29,18,25,10,12,47,51,58；25,18,12,10,29,47,51,58；18,10,12,25,29,47,51,58；12,10,18,25,29,47,51,58；10,12,18,25,29,47,51,585 给出如下关键字序列321，156，57，46，28，7，331，33，