数据结构查找与排序练习题
一、选择题
1.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2
2.适用于折半查找的表的存储方式及元素排列要求为( )
A．链接方式存储，元素无序 B．链接方式存储，元素有序
C．顺序方式存储，元素无序 D．顺序方式存储，元素有序
3.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )
A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减4．有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。
A．35/12 B.37/12 C.39/12 D.43/12
5.折半查找的时间复杂性为（）
A. O（n2）
B. O（n）
C. O（nlogn）
D. O（logn）
6.对有18个元素的有序表作折半查找，则查找A[3]的比较序列的下标为（）
A.1，2，3
B.9，5，2，3
C.9，5，3
D.9，4，2，3
7.设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（）次比较后查找成功。
A.2
B. 3
C. 4
D.12
8.用n个键值构造一棵二叉排序树，最低高度为（）
A.n/2
B.、n
C.logn
D.logn+1
9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A．（100，80， 90， 60， 120，110，130）
B.（100，120，110，130，80， 60， 90）
C.（100，60， 80， 90， 120，110，130）
D.(100，80， 60， 90， 120，130，110)
10.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key% 13,散列地址为1的链中有（）个记录。A．1 B. 2 C. 3 D. 4
11.已知一采用开放地址法解决Hash表冲突，要从此Hash表中删除出一个记录，正确的做法是(）
A.将该元素所在的存储单元清空。
B.将该元素用一个特殊的元素代替
C.将与该元素有相同Hash地址的后继元素顺次前移一个位置。
D.用与该元素有相同Hash地址的最后插入表中的元素替代。
12.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( )
A．k-1次 B. k次C. k+1次D. k（k+1）/2次
13.散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。
（1）元素59存放在散列表中的地址是（）。
A． 8 B. 9 C. 10 D. 11
（2）存放元素59需要搜索的次数是（）。
A． 2 B. 3 C. 4 D. 5
14.将10个元素散列到100000个单元的哈希表中，则（）产生冲突。
A. 一定会
B. 一定不会
C. 仍可能会
15.对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K %7作为散列函数，则散列地址为0的元素有（）个。
A.1
B.2
C.3
D.4
16.下列排序方法中，哪一个是稳定的排序方法？（）
A．直接选择排序 B．直接插入排序 C．希尔排序 D．快速排序
17.在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（）。
A.直接插入排序
B.气泡排序
C. 快速排序
D.直接选择排序
18.比较次数与排序的初始状态无关的排序方法是( )。
A.直接插入排序
B.起泡排序
C.快速排序
D.简单选择排序
19.对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（）排序。
A.选择
B.快速
C.希尔
D.冒泡
20.一组记录的关键码为（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)
21.就平均性能而言，目前最好的内排序方法是( )排序法。
A.冒泡
B.希尔插入
C.交换
D.快速
22．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。
A.插入
B.选择
C.希尔
D.快速
23.用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（）。
A.94,32,40,90,80,46,21,69
B.32,40,21,46,69,94,90,80
C.21,32,46,40,80,69,90,94
D.90,69,80,46,21,32,94,40
24.直接插入排序在最好情况下的时间复杂度为（）
A.O(logn)
B.O(n)
C.O(n*logn)
D.O(n2)
25.对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是 ( )
A.l
B.4
C.3
D.2
26.对下列关键字序列用快速排序法进行排序时，速度最快的情形是（）。
A.{21,25,5,17,9,23,30}
B.{25,23,30,17,21,5,9}
C.{21,9,17,30,25,23,5} Ｄ.{5,9,17,21,23,25,30}
27.快速排序方法在（）情况下最不利于发挥其长处。
A.要排序的数据量太大
B.要排序的数据中含有多个相同值
C.要排序的数据个数为奇数
D.要排序的数据已基本有序
28.对n个记录进行希尔排序，所需要的辅助存储空间为（）。
A.O（1og2n）
B.O（n）
C.O（1）
D.O（n2）
29.下列四个序列中，哪一个是堆（）。
A.75,65,30,15,25,45,20,10
B.75,65,45,10,30,25,20,15
C.75,45,65,30,15,25,20,10
D.75,45,65,10,25,30,20,15
30.就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（）
A.堆排序〈快速排序〈归并排序
B.堆排序〈归并排序〈快速排序
C.堆排序〉归并排序〉快速排序
D.堆排序 > 快速排序>归并排序
E.以上答案都不对
二、判断题
1.查找相同结点的效率折半查找总比顺序查找高。
2.对无序表用二分法查找比顺序查找快。
3.对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。
4.二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（1）若它的左子树不空，
则左子树上所有结点的值均小于根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值。
5.在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。
6.对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。
7.二叉树中除叶结点外, 任一结点X，其左子树根结点的值小于该结点（X）的值；其右子树根结点的值≥该结点（X）的值,则此二叉树一定是二叉排序树。
8.在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同。
9.采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。
10.在散列检索中，“比较”操作一般也是不可避免的。
11.散列函数越复杂越好，因为这样随机性好，冲突概率小.
12.Hash表的平均查找长度与处理冲突的方法无关。
13.负载因子 (装填因子)是散列表的一个重要参数，它反映散列表的装满程度。
14.若散列表的负载因子α<1，则可避免碰撞的产生。
15.哈希表的平均查找长度不为0，是因为哈希函数在绝大多数情况下是多对一的映射，即
存在冲突。
16.可以创建一种查找表，其在十亿个元素中查找与在10个元素中查找所用的时间差不多。17．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。
18.内排序要求数据一定要以顺序方式存储。
19.排序算法中的比较次数与初始元素序列的排列无关。
20.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
21.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。
22.直接选择排序算法在最好情况下的时间复杂度为O（N）。
23.在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n )。
24.当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省
25.快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。
26.堆是满二叉树。
27.在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。
28.堆排序是稳定的排序方法。
29.归并排序辅助存储为O（1）。
30.冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的最坏时间复杂性是O(n*n),而快速排序算法的最坏时间复杂性是O(nlog2n),所以快速排序比冒泡排序算法效率更高。
31.快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。
32.归并排序在任何情况下都比所有简单排序速度快。
33.快速排序总比简单排序快。
三、填空题
1.顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__ __次。
2.在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__ _
3.在有序表A[1…20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是 ______。
4.有序表(12,18,24,35,47,50,62,83,90,115，134)使用二分法查找90时，需____ ___次查找成功，查100时，需____ _____次才能确定不成功。
5.平衡因子的定义是__________
6.高度为8的平衡二叉树的结点数至少有___ ___个。
7. 动态查找表和静态查找表的重要区别在于前者包含有__ __和__ __运算，而后者不包含这两种运算。
四、应用题
1.假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题：
(1).画出描述折半查找过程的判定树；
(2).若查找元素54，需依次与那些元素比较?
(3).若查找元素90，需依次与那些元素比较?
(4).假定每个元素的查找概率相等，求查找成功时的平均查找长度。
2.一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。 按照中序遍历遍历的顺序将值标上
3.依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树
(1) 试画出生成之后的二叉排序树; (2) 对该二叉排序树作中序遍历，试写出遍历序列; (3) 假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。
4.设哈希函数H （k ）=3 K mod 11，散列地址空间为0～10，对关键字序列（32,13,49,24,38,21,4,12）按下述两种解决冲突的方法构造哈希表（1）线性探测再散列
（2）链地址法，并分别求出等概率下查找成功时的平均查找长度；
5.整形数组A 的十个元素值分别是6，2，9，7，3，8，4，5，0，试用第一元素中的值6作为枢轴，试写出快速排序第一次分割后A 中的结果。
6.已知序列40，30，50，24，28，46，60，10。试画出由该输入序列构成的二叉排序树，并分别给出依次执行下列操作后的二叉排序树（共画四棵树）
（1）插入数据42和80；（2）删除数据30；（3）删除数据50。
7.写出初始数列{47，28，32，15，94，33，14，16}在shell 排序下的状态变化过程（d=4、2、1）。
8.判断下列序列是否是堆，若不是堆，请将调整为大根堆。
100，85，40，77，80，60，66，98，82，10，20
小学句子排序方法及习题 怎样排列顺序错乱的句子？ 把排列错乱的句子整理成一段通顺连贯的话，能训练对句子的理解能力、有条理表达能力和构段能力。这样的练习一般可按五步进行。 第一步，仔细阅读每句话或每组句子，理解它们的主要内容; 第二步，综合各句的意思，想想这些话主要说的是什么内容; 第三步，想想全段的内容按什么顺序排列好，即找出排列顺序的依据，如，是按事情发展顺序，还是时间顺序，或方位，还是“总分”等; 第四步，按确定的排列依据排列顺序; 第五步，按排好的顺序仔细读两遍，看排得对不对，如发现有的句子排得位置不对，就进行调整，直到这段话排得通顺连贯为止。把错乱的句子排列好，这是小学阶段语文练习中的一个重要形式，必须好好掌握。学会排列句子，不仅能提高我们的思维能力，还能提高我们的写作能力。
那么，如何学会排列好句子呢?我们可以按下列方法进行。 一、按事情发展的顺序排列。有些错乱的句子，我们在排列时，应仔细分析句与句之间的联系。常见的错乱句子，往往叙述了一件完整的事，或者活动的具体过程。那么，我们就可以按事情发展的顺序来排列。 二、按时间先后顺序排列。对一些错乱的句子，我们可以找出表示时间概念的词语，如，早晨、上午、中午、下午等词，然后按时间先后顺序进行排列句子。 三、按先总述后分述的顺序排列。根据这段话的特点，找出这句话是个中心句，其他句子都是围绕着这句话来说的。显而易见，我们可按先总后分的顺序来排列句子。 四、按空间推移的顺序排列。所谓空间推移，就是由地点的转移，表达出不同的内容。排列时，要十分注意，不要与其他的方法相混淆。 把错乱的句子排列好，这是小学阶段语文练习中的一个重要形式，必须好好掌握。学会排列句子，不仅能提高我们的思维能力，还能提高我们的写作能力。
第9章排序自测卷姓名班级 一、填空题（每空1分，共24分） 1. 大多数排序算法都有两个基本的操作：比较和移动。 2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插 入到有序表时，为寻找插入位置至少需比较6 次。 3. 在插入和选择排序中，若初始数据基本正序，则选用插入；若初始数据基本反序，则选用 选择。 4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用堆排序；若初始记录基本 无序，则最好选用快速排序。 5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是O(n2) 。若对其进行快速 排序，在最坏的情况下所需要的时间是O(n2)。 6. 对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2n)，所需要的附加空间 是O(n) 。 7．对于n个记录的表进行2路归并排序，整个归并排序需进行┌log2n┐趟（遍）。 8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则： 冒泡排序一趟扫描的结果是H C Q P A M S R D F X Y； 初始步长为4的希尔（shell）排序一趟的结果是P A C S Q H F X R D M Y ； 二路归并排序一趟扫描的结果是H Q C Y A P M S D R F X； 快速排序一趟扫描的结果是 F H C D P A M Q R S Y X； 堆排序初始建堆的结果是A D C R F Q M S Y P H X。 9. 在堆排序、快速排序和归并排序中， 若只从存储空间考虑，则应首先选取方法，其次选取快速排序方法，最后选取归并排序方法； 若只从排序结果的稳定性考虑，则应选取归并排序方法； 若只从平均情况下最快考虑，则应选取堆排序、快速排序和归并排序方法； 若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。 二、单项选择题（每小题1分，共18分） （ C ）1．将5个不同的数据进行排序，至多需要比较次。 Ａ. 8 Ｂ. 9 Ｃ. 10 Ｄ. 25 （C）2．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 Ａ. 希尔排序Ｂ. 冒泡排序Ｃ. 插入排序Ｄ. 选择排序（D）3．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为
第10 章排序练习题答案 一、填空题 1. 大多数排序算法都有两个基本的操作：比较和移动。 2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7 个记录60 插 入到有序表时，为寻找插入位置至少需比较 3 次。 3.在插入和选择排序中，若初始数据基本正序，则选用插入；若初始数据基本反序，则选用 选择。 正序时两种方法移动次数均为0，但比较次数量级不同，插入法：n-1 即O(n)，选择法：O(n2) 反序时两种方法比较次数量级相同，均为O(n2)，但移动次数不同，插入法：O(n2)，选择法：3(n-1)即O(n) 4.在堆排序和快速排序中，若初始记录接近正序或反序，则选用堆排序；若初始记录基本无 序，则最好选用快速排序。 5.对于n 个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是O(n2) 。若对其进行快速 排序，在最坏的情况下所需要的时间是O(n2) 。 6.对于n 个记录的集合进行归并排序，所需要的平均时间是O(nlog2n) ，所需要的附加空间是O(n) 。 7.对于n 个记录的表进行2 路归并排序，整个归并排序需进行┌log2n┐趟（遍）。 8.设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则： 冒泡排序一趟扫描的结果是 H C Q P A M S R D F X Y ； 二路归并排序一趟扫描的结果是H Q C Y A P M S D R F X； 快速排序一趟扫描的结果是 F H C D P A M Q R S Y X； 堆排序初始建堆的结果是Y S X R P C M H Q D F A 。（大根堆） 9.在堆排序、快速排序和归并排序中， 若只从存储空间考虑，则应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法；若只从排序结果的稳定性考虑，则应选取归并排序方法； 若只从平均情况下最快考虑，则应选取快速排序方法； 若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。 二、单项选择题 （ C ）1．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 Ａ. 归并排序Ｂ. 冒泡排序Ｃ. 插入排序Ｄ. 选择排序 （ D ）2．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为Ａ. 冒泡排序Ｂ. 归并排序Ｃ. 插入排序Ｄ. 选择排序 （ B ）3．对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。 Ａ. 从小到大排列好的Ｂ. 从大到小排列好的Ｃ. 元素无序Ｄ. 元素基本有序 （ D ）4．对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为
小学语文句子排序练习题 1 （）碧溪河从村前流过。 （）村后是一望无际的桑园。 （）我家住在碧溪河边，这是江南水乡的小村庄。 （）河里一群小鱼在水中游来游去，水面上不时溅起朵朵水花。 （）春天，桑树抽出新芽，整个桑园就像绿色的海洋。 2 （）一些不知名的小花，长在绿草中，像蓝天上缀着的星星。 （）小花园在教室的左边，长八米，宽四米。 （）花园里四周的道路上都长满了青草，好象铺了一层绿毯。 （）它紧靠短墙，由一排横、两排竖的篱笆和这面短墙围起来。 （）花是老师精心栽培的，有的长在地上，有的长在盆里，构成了一个个图案。 （）到了夏天，大的、小的、圆的、长的、各种形状的绿叶，托着红的、黄的、蓝的、白的各色各样的花儿，美丽极了！ 3 （）地上的水越来越多。 （）雨落在对面的屋顶的瓦片上。 （）像一层薄烟罩在屋顶上。 （）渐渐地连成了一条线。 （）溅起一朵朵水花。 （）雨水顺着房檐流下来。 （）汇合成一条条小溪。 （）开始像断了线的珠子。 4 （）王红同学真值得我们学习。 （）今天，老天爷一直紧绷着脸，阴沉沉的，好象跟谁生气似的。 （）就在这个时候，我看见一个女同学飞快地朝操场奔去。 （）天突然下起雨来。 （）啊！那是三年级（4）班的王红。 （）下午放学的时候，同学们背起书包正准备回家。 （）原来，她是冒雨去降国旗的。 （）红领巾在她胸前飘动，就像一束跳动的火苗。 5 （）我们坐在河边柳树下，放下了鱼钩。 （）忽然，浮标一沉，我急忙把鱼竿往上一提，一条银白色的小鱼钓上来了。 （）星期天早晨，我和小明扛着鱼竿到郊外去钓鱼。 （）浅红色的浮标漂在水面上。 （）我们高兴地把鱼竿举在空中，摇晃着，喊着：“我们钓着鱼了！” 6 （）他正想坐下时，管理员对他说：“先生，请你不要坐在这里，这里是马克思的座位。” （）管理员笑着说：“是的，很多年来，他每天都到这里来读书。” （）那个读者问：“他每天都来吗？你是说他今天一定会来？” （）话刚说完，马克思果然跨进门来了。 （）一天清早，伦敦大英博物馆里，有位读者看见有个座位空着，便走了过来。
第十章：内部排序练习题 一、选择题 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、要排序的数据中含有多个相同值。
数据结构查找排序经典试题 一、填空 1、针对有n条记录的顺序表做顺序查找，假定各记录的查找机会均等，则平均查找长度 ASL=_______。 2、在二叉平衡树中，平衡因子hl-hr的所有可能取值有____________。 3、在排序操作中，待排序的记录有n条，若采用直接插入排序法，则需进行 _________趟的 插入才能完成排序。 4、在排序操作中，待排序的记录有n条，若采用冒泡排序法，则至多需进行_________趟的 排序。 5、直接插入排序算法的时间复杂度为________________。 6、按（）遍历二叉排序树，可以得到按值递增的关键字序列，在下图 所示的二叉排序树中，查找关键字85的过程中，需和85进行比较的关键字序列为（）。 50 95 20 55 70 10 30 85 二、判断
1、平衡二叉树中子树的深度不能大于1。（） 2、快速排序法是稳定的排序方法。（） 3、任何一种排序方法都必须根据关键字值比较的结果来将记录从一个地方移动到另一个地 方。（） 4、冒泡排序法是稳定的排序方法。（） 5、折半插入排序法是稳定的排序方法。（） 三、选择 1、在排序操作中，待排序的记录有n条，若采用直接插入排序法，则需进行_________趟的 插入才能完成排序。 A、n B、(n-1)/2 C、n+1 D、n-1 2、采用顺序查找法查找长度为n的线性表时，平均查找长度为（） A、n B、(n-1)/2 C、n/2 D、(n+1)/2 3、用折半查找法在{11,33,55,77,99,110,155,166,233}中查找155需要进行（）次比较。 A、1 B、2 C、3 D、4 4、请指出在顺序表(2,5,7,10,14,15,18,23,35,41,52)中，用折半查找法查找12需做（）次比较。 A、5 B、4 C、3 D、2 5、如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，
人教版小学四年级下册语文排序专项练习题及答案（一） （）田野的尽头，连绵的山峰像海里起伏的波涛。（）溪水是那么清澈、明净；水里的小鱼儿自由自在地游来游去。 （）小溪的另一边是田野，如今黄澄澄的，正报告着丰收的喜讯。 （）一条小溪从我们村子旁静静地流过。 （）山腰上的公路，像一条银灰色的绸带飘向远方。（）小溪的一边是果园，春天，花香弥漫；秋天，硕果累累。 参考答案：5、2、4、1、6、3 （二） （）人们都说这个山村像一幅风景画。 （）村前有一口大水塘，塘水清如明镜。 （）山脚下有一个村子，村子景色秀丽。 （）塘里荷花点点，偶尔有小鱼跳出水面。 （）村后有一片青翠的竹林，林中鸟声清脆悦耳。（）水里倒映着蓝天白云。答案：6、2、1、4、5、3 （三） （）一听到这熟悉的叫声，我就猜准它一定生蛋了。（）我高兴地把蛋捡在手里，还热乎乎的呢。 （）跨进屋门，果然，一个鹅蛋似的双黄蛋躺在鸡窝里。 （）一天下午，我参加学习小组后回家，老远就听到我家的那只老母鸡“咯咯哒”、“咯咯哒”地在房子里叫个不停。 答案：2、4、3、1。 （四） （）当太阳一落山，黄昏的薄霭像轻纱一样笼罩山野的时候，青蛙便逐渐热闹起来。 （）蛙们纷纷跳入稻田去了，蛙声也暂时停息。 （）这时候，人要是从田埂上经过，就听见路两旁扑通扑通的声音。 （）但是人刚一走过，他们又扯开嗓子，放肆地叫起来。 （）乡村的夏夜，便是蛙的世界。 答案：2、4、3、5、1 （五） （）一大滴松脂从树上滴下来，把苍蝇和蜘蛛包在了里面。 （）松脂球埋在泥沙里成了化石。 （）地壳变动了，森林被海水淹没了。 （）松脂不断往下滴，盖住了原来的地方，积成了一个松脂球。 （）一个夏天的晌午，热辣辣的太阳照射着松树林。
1、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是 ( )。 A. 直接选择排序 B. 直接插入排序 C. 快速排序 D. 起泡排序 2、对5个不同的数据元素进行直接插入排序，最多需要进行 ( ) 次比较。 A. 8 B. 10 C. 15 D. 25 3、用快速排序法对n 个数据进行排序，在最好情况下的时间复杂度是 O(nlogn)，在最坏情况下的时间复杂度是 O(n 2) ，在平均情况下的时间复杂度是 O(nlogn) 。 4、用归并排序法对n 个数据进行排序，在最好情况下的时间复杂度是 O(nlogn) ，在最坏情况下的时间复杂度是 O(nlogn) ，在平均情况下的时间复杂度是 O(nlogn) 。 5、在对n 个元素进行直接插入排序的过程中，共需要进行2n 趟。（ 错 ） 快速排序在最坏情况下的时间复杂度为)(2n 。（ 对 ） 6、若一组记录的关键字为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到一次划分结构为( )。 A.40，38，46，84，56，79 B.40，38，46，56，79，84 C.40，38，46，79，56，84 D.38，40，46，56，79，84 7、下列四个序列中，哪一个是堆（ ）。 A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15 C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15 8、由无序序列{ 15，9，7，8，20，7}建立的初始小顶堆为 7,8,7,9,20,15_ 。 9、已知5个数据元素为（54，28，16，34，73），对该数列按从小到大排序，经过一趟冒泡排序后的序列为 28,16,34,54,73_ 。 10、若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的__ 比较_____和记录的___移动__。 11、直接插入排序在最好情况下的时间复杂度为( )。
第二轮排序和查找算法综合1 行政班：教学班：姓名：学号： 根据课本上的排序算法和查找算法回答1-6题： 1．【加试题】有一个数组，采用冒泡排序，第一遍排序后的结果为：4，10，5，32，6，7，9，17，24那么该数组的原始顺序不可能 ．．．的是（） A．10，5，32，6，7，9，17，24，4 B．10，5，32，6，7，9，4，17，24 C．10，5，32，4，6，7，9，17，24 D．4，10，5，32，17，9，24，6，7 2.【加试题】对下列数据序列进行冒泡升序排序，排序效率最低的序列（） A.31，29，24，20，15，10 B.10，15，20，24，29，31 C.29，10，31，15，20，24 D.24，29，31，20，15，10 3．【加试题2】数组变量d（1）到d（8）的值依次为87、76、69、66、56、45、37、23，用“对分查找”找到“69”的过程中，依次被访问到的数据是（） A．69 B．66、69 C．66、76、69 D．56、66、76、69 4.【加试题2】用对分查找法和顺序查找法在数字序列“1,2,3,5,8,13,21,34，55”中查找数字13,两种方法都能访问到的数字是（） A.3 B.5 C.8 D.34 5.【加试题2】在有序单词序列“bike，cake，data，easy，feel，great，hive，mark,sweet”中，用对分查找算法找到“easy”过程中，依次被访问到的数据为（） A.feel, data, easy B.great, data, easy C.bike, cake, dada，easy D.feel,cake,data,easy 6.【加试题2】下列有关查找的说法，正确的是（） A．进行对分查找时，被查找的数据必须已按升序排列 B．进行对分查找时，如果查找的数据不存在，则无需输出结果 C．在新华字典中查找某个汉字，最适合使用顺序查找 D．对规模为n的数据进行顺序查找，平均查找次数是21 n 7. 【加试题】实现某排序算法的部分VB程序如下：数组元素a(1)到a(5)的数据依次为“38，70，53，57，30”。经过下列程序“加工”后数组元素a(1)到a(5)的数据应该是（） For i = 1 To 1 For j = 5 To i + 1 Step -1 If a(j) > a(j - 1) Then t = a(j) a(j) = a(j - 1) a(j - 1) = t End If Next j Next i 命题：杜宗飞 A.70，57，38，53，30 B.30, 38，70，53，57 C.70，38，57，53，30 D.30, 38，57，53，70 8.【加试题】有如下程序段： For i = 1 To 2
排序练习题 1（） （）碧溪河从村前流过。 （）村后是一望无际的桑园。 （）我家住在碧溪河边，这是江南水乡的小村庄。 （）河里一群小鱼在水中游来游去，水面上不时溅起朵朵水花。 （）春天，桑树抽出新芽，整个桑园就像绿色的海洋。 2（） （）一些不知名的小花，长在绿草中，像蓝天上缀着的星星。 （）小花园在教室的左边，长八米，宽四米。 （）花园里四周的道路上都长满了青草，好象铺了一层绿毯。 （）它紧靠短墙，由一排横、两排竖的篱笆和这面短墙围起来。 （）花是老师精心栽培的，有的长在地上，有的长在盆里，构成了一个个图案。（）到了夏天，大的、小的、圆的、长的、各种形状的绿叶，托着红的、黄的、蓝的、白的各色各样的花儿，美丽极了！ 3（） （）地上的水越来越多。 （）雨落在对面的屋顶的瓦片上。 （）像一层薄烟罩在屋顶上。 （）渐渐地连成了一条线。 （）溅起一朵朵水花。 （）雨水顺着房檐流下来。 （）汇合成一条条小溪。 （）开始像断了线的珠子。 4（） （）王红同学真值得我们学习。 （）今天，老天爷一直紧绷着脸，阴沉沉的，好象跟谁生气似的。 （）就在这个时候，我看见一个女同学飞快地朝操场奔去。 （）天突然下起雨来。 （）啊！那是三年级（4）班的王红。 （）下午放学的时候，同学们背起书包正准备回家。 （）原来，她是冒雨去降国旗的。 （）红领巾在她胸前飘动，就像一束跳动的火苗。
5（） （）我们坐在河边柳树下，放下了鱼钩。 （）忽然，浮标一沉，我急忙把鱼竿往上一提，一条银白色的小鱼钓上来了。（）星期天早晨，我和小明扛着鱼竿到郊外去钓鱼。 （）浅红色的浮标漂在水面上。 （）我们高兴地把鱼竿举在空中，摇晃着，喊着：“我们钓着鱼了！” 6（） （）他正想坐下时，管理员对他说：“先生，请你不要坐在这里，这里是马克思的座位。” （）管理员笑着说：“是的，很多年来，他每天都到这里来读书。” （）那个读者问：“他每天都来吗？你是说他今天一定会来？” （）话刚说完，马克思果然跨进门来了。 （）一天清早，伦敦大英博物馆里，有位读者看见有个座位空着，便走了过来。 7（） （）我连忙站起来让老爷爷坐。 （）我刚坐下，一位老爷爷提着篮子上了车。 （）星期日，我坐汽车去奶奶家。 （）老爷爷微笑着说：“谢谢，你真是个好孩子。” （）上车后，我找到一个座位。 （）我说：“不用谢，这是我应该做的。” 8（） （）我说了声：“谢谢奶奶。”就把压岁钱交给爸爸，留着给我交学费。 （）奶奶说：“这孩子到底长了一岁，懂事多了。” （）奶奶乐呵呵地从怀里掏出一个红包，说是给我的压岁钱。 （）屋子里充满了欢声笑语。 （）我奔到奶奶身边，祝奶奶健康长寿。 9（） （）小脸蛋鼓鼓的，像嘴里含着里两个核桃。 （）身上穿着大翻领西装和蓝色直筒裤。 （）我的“小顽童”真逗人喜爱。 （）脚穿一双特大号皮鞋。 （）眉毛下两只眼睛，仿佛在转动。 （）他头上戴着一顶红白相间的西瓜帽。 10（）
第九章查找 单项选择题 1.顺序查找法适合于存储结构为的线性表。 A. 散列存储 B. 顺序存储或链接存储 C. 压缩存储 D. 索引存储 2.对线性表进行二分查找时，要求线性表必须。 A. 以顺序方式存储 B. 以顺序方式存储，且结点按关键字有序排列 C. 以链接方式存储 D. 以链接方式存储，且结点按关键字有序排列 3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 4.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为。 A. O(n2) B. O(nlog2n) C. O(n) D. O (logn) 5.二分查找和二叉排序树的时间性能。 A. 相同 B. 不相同 6.有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当二分查找值为82的结点时，次比较后查找成功。 A. 1 B. 2 C. 4 D. 8 7.设哈希表长m=14，哈希函数H(key)=key%11。表中有4个结点： addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7 其余地址为空，如用二次探测再散列处理冲突，关键字为49的结点的地址是。 A. 8 B. 3 C. 5 D. 9 8.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为。 A. 35/12 B. 37/12 C. 39/12 D. 43/12 9.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分个结点最佳地。 A. 10 B. 25 C. 6 D. 625 10.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用查找方法。 A. 分块 B. 顺序 C. 二分 D. 散列 填空题 1.顺序查找法的平均查找长度为；二分查找法的平均查找长度为；分块查找法（以顺序查找确定块）的平均查找长度为；分块查找法（以二分查找确定块）的平均查找长度为；哈希表查找法采用链接法处理冲突时的平均查找长度为。 2.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。 3.二分查找的存储结构仅限于，且是。 4.在分块查找方法中，首先查找，然后再查找相应的。 5.长度为255的表，采用分块查找法，每块的最佳长度是。 6.在散列函数H(key)=key%p中，p应取。 7.假设在有序线性表A[1..20]上进行二分查找，则比较一次查找成功的结点数为，则
习题七参考答案 一、选择题 1．内部排序算法的稳定性是指( D )。 A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对 2．下面给出的四种排序算法中，( B )是不稳定的排序。 A．插入排序B．堆排序C．二路归并排序D．冒泡排序 3. 在下列排序算法中，哪一种算法的时间复杂度与初始排序序列无关（D ）。 A．直接插入排序B．冒泡排序C．快速排序D．直接选择排序 4．关键字序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中( C )的两趟排序后的结果。 A．选择排序 B.冒泡排序 C.插入排序 D.堆排序 5．下列排序方法中，( D )所需的辅助空间最大。 A．选择排序B．希尔排序C．快速排序D．归并排序 6．一组记录的关键字为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为支点得到的一次划分结果为（C ）。 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) 7．在对一组关键字序列{70，55，100，15，33，65，50，40，95}，进行直接插入排序时，把65插入，需要比较( A )次。 A. 2 B. 4 C. 6 D. 8 8.从待排序的序列中选出关键字值最大的记录放到有序序列中，该排序方法称为( B )。 A. 希尔排序 B. 直接选择排序 C. 冒泡排序 D. 快速排序 9．当待排序序列基本有序时，以下排序方法中，( B )最不利于其优势的发挥。 A. 直接选择排序 B. 快速排序 C.冒泡排序 D.直接插入排序 10．在待排序序列局部有序时，效率最高的排序算法是( B )。 A. 直接选择排序 B. 直接插入排序 C. 快速排序 D.归并排序 二、填空题 1.执行排序操作时，根据使用的存储器可将排序算法分为内排序和外排序。 2.在对一组记录序列{50,40,95,20,15,70,60,45,80}进行直接插入排序时，当把第7个记录60插入到有序表中 时，为寻找插入位置需比较 3 次。 3.在直接插入排序和直接选择排序中，若初始记录序列基本有序，则选用直接插入排序。 4.在对一组记录序列{50,40,95,20,15,70,60,45,80}进行直接选择排序时，第4次交换和选择后，未排序记录为 {50,70,60,95,80}。 5.n个记录的冒泡排序算法所需的最大移动次数为3n(n-1)/2 ，最小移动次数为0 。 6.对n个结点进行快速排序，最大的比较次数是n(n-1)/2 。 7.对于堆排序和快速排序，若待排序记录基本有序，则选用堆排序。 8.在归并排序中，若待排序记录的个数为20，则共需要进行5 趟归并。 9.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的比较和数据元 素的移动。 10．在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的是快速排序，需要内存容量最多的是基数排序。 三、算法设计题 1．试设计算法，用插入排序方法对单链表进行排序。 参考答案: public static void insertSort(LinkList L) {
第九章查找习题 一、判断题 1.折半查找法可以用于按值有序的线性链表的查找。 2.对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。 3.任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。 4.中序遍历二叉排序树的结点就可以得到排好序的结点序列。 5.哈希表存储的基本思想是由关键码的值决定数据的存储地址。 6.哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法。 7.装载因子是散列法的一个重要参数，它反映散列表的装满程度。 8.采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置为空，因为这会影响以后的查找。 二、选择题 1.采用顺序查找方法查找长度为n的线性表，平均查找长度为 A.n B.n/2 C.(n+1)/2 D.(n-1)/2 2.对线性表采用折半查找法，该线性表必须 A.采用顺序存储结构 B.采用链式存储结构 C.采用顺序存储结构，且元素按值有序 D.采用链式存储结构，且元素按值有序 3.在按值有序的线性表(5,8,11,12,15,20,32,41,57)中采用折半查找法查找20需要进行多少次元素间的比较 A.3 B.4 C.5 D.6 4.按逐点插入法建立对应于序列(54,28,16,34,73,62,95,60,26,43)的二叉排序树后，查找62要进行多少次比较。 A.2次 B.3次 C.5次 D.6次 5.散列法存储的基本思想是根据哪个来决定存储地址。 A.散列表空间 B.元素的序号 C.装载因子 D.关键码值 6.散列法存储的冲突指的是 A.两个元素具有相同的序号 B.两个元素的关键码值不同，而非码属性相同 C.不同关键码值对应相同的存储地址 D. 装载因子过大 7.哈希地址空间为m，k为关键字，散列地址H(k)=k MOD p。为了减少发生冲突的频率，一般取p为 A.小于m的最大奇数 B.小于m的最大合数 C.小于m的最大素数 D.大于m的最小素数 8.在10阶B-树中根结点所包含的关键码 ．．．个数最多为_______，最少为________。 A. 1 B. 2 C. 9 D. 10 9．已知一个有序表为(12、18、24、35、47、50、62、83、90、115、134)，当折半查找值为90的元素时，次比较后查找成功；当折半查找值为47的元素时，次比较后查找成功。
1.画出该图的邻接矩阵和邻接表。根据邻接表从A 开始求DFS 和BFS 序列。（12分） 【答案】 011000 101000 100001 010010 000101 001010 DFS 序列BFS 序列:ABCDFE 2. 已知序列{70，73，69，23，93，18,11，68}请给出直接插入排序作升序排序每一趟的结果和快速排序作升序排序时一趟的结果。（10分） 【答案】直接插入排序 70，73，69，23，93，18,11，68 [70，73]，69，23，93，18,11，68 [70，69，73]， 23，93，18,11，68 [23,70，69，73]， 93，18,11，68 [23,70，69，73， 93]，18,11，68 [18,23,70，69，73， 93]， 11，68 [11，18,23,70，69，73， 93]， 68 [11，18,23,68,70，69，73， 93] 快速排序:[68,11,69,23,18] ,70,[93,73] 3.设有一组关键字关键码集为 {47，7，29，11，16，92，22，8，3}，哈希表表长为11， Hash(key)=key mod 11，用线性探测法处理冲突，构造哈希表，并求它成功查找的ASL 。（8分） 【答案】 ASL=5/3 4.定义有序表抽象数据类型，并据此类型设计折半查找算法。 typedef struct { int key;
float info; }JD; int binsrch(JD r[],int n,int k) { int low,high,mid,found; low=1; high=n; found=0; while((low<=high)&&(found==0)) { mid=(low+high)/2; if(k>r[mid].key) low=mid+1; else if(k==r[mid].key) found=1; else high=mid-1; } if(found==1) return(mid); else return(0); } 5. 用prim 算法求下图的最小生成树，写出最小生成树的生成过程。（5分） 6.设关键字的输入序列为{4，5，7，2，1，3，6} (1)（8分）从空树开始构造平衡二叉树，画出每加入一个新结点时二叉树的形态，若发 生不平衡，指明需做的平衡旋转类型及平衡旋转的结果。 (2)（4分）上面的数据作为待排序的数据，写出用快速排序进行一趟划分后的数据序列
第10章排序 一、选择题 1．某内排序方法的稳定性是指( D )。【南京理工大学 1997 一、10（2分）】 A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对 2．下面给出的四种排序法中( D )排序法是不稳定性排序法。【北京航空航天大学 1999 一、10 （2分）】 A. 插入 B. 冒泡 C. 二路归并 D. 堆积 3．下列排序算法中，其中（D ）是稳定的。【福州大学 1998 一、3 (2分)】 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 4．稳定的排序方法是（ B ）【北方交通大学 2000 二、3（2分）】 A．直接插入排序和快速排序 B．折半插入排序和起泡排序 C．简单选择排序和四路归并排序 D．树形选择排序和shell排序 5．下列排序方法中，哪一个是稳定的排序方法？（ B ）【北方交通大学 2001 一、8（2分）】A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序 6. 快速排序方法在（ D ）情况下最不利于发挥其长处。【燕山大学 2001 一、3 （2分）】 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据个数为奇数 D. 要排序的数据已基本有序 7. 以下序列不是堆的是( D )。【西安电子科技大学 2001应用一、5 （2分）】 A. (100,85,98,77,80,60,82,40,20,10,66) B. (100,98,85,82,80,77,66,60,40,20,10) C. (10,20,40,60,66,77,80,82,85,98,100) D. (100,85,40,77,80,60,66,98,82,10,20) 8．下列四个序列中，哪一个是堆（ C ）。【北京工商大学 2001 一、8 （3分）】 A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15 C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15 9．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。【北京航空航天大学 1999 一、8（2分）】 A. 插入 B. 选择 C. 希尔 D. 二路归并 10．比较次数与排序的初始状态无关的排序方法是( D )。【北方交通大学 2000 二、2（2分）】A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序 11．对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ B ）。 A. (2,5,12,16)26(60,32,72) B. (5,16,2,12)28(60,32,72) C. (2,16,12,5)28(60,32,72) D. (5,16,2,12)28(32,60,72) 【青岛大学 2000 三、4 （2分）】12．下列排序算法中( B )不能保证每趟排序至少能将一个元素放到其最终的位置上。 A.快速排序 B. shell排序 C. 堆排序 D.冒泡排序【合肥工业大学 2001 一、3（2分）】13．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( A )（按递增序）。【南京理工大学 1996 一、4 （2分）】 A．下面的B，C，D都不对。 B．9，7，8，4，-1，7，15，20 C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，20 14．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。【燕山大学 2001 一、4（2分）】 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) 15．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( C )排序。 A．冒泡 B. 希尔 C. 快速 D. 堆【南京理工大学 2001 一、12 （1.5分）】 16. 对初始状态为递增序列的表按递增顺序排序，最省时间的是（ C ）算法，最费时间的是（ B ）算 法。 A. 堆排序 B. 快速排序 C. 插入排序 D. 归并排序【南开大学 2000 一、5】 17. 就平均性能而言，目前最好的内排序方法是( D )排序法。【西安电子科技大学 1998 一、9 (2分）】 A. 冒泡 B. 希尔插入 C. 交换 D. 快速 18．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ D ）方法最快。
部编三年级语文句子排序实用技巧（附练习题及答案） 排序题三字经 排序题，并不难；通读题，前后看； 有代词，往前串；同话题，连一连； 找顺序，时空间；标志词，抓关键； 内容上，要映现；排完了，先浏览； 不通顺，再换换；对答案，笑开颜。 句子排序的技巧 将排列错乱的句子整理成一段通顺连贯的话，这是一项综合训练能力，可以训练我们对句子的理解能力、表达能力，及写作能力。其实这类题型并不难，很多题目都有十分明朗的线索或表明顺序的提示，只要我们找到其中的规律，就一定能化难为易。 看到题目，首先要反复阅读，不要急于求成。只有在读懂的情况下才可以弄明白句子之间的内在联系。我们可以先考虑一下几个句子重点写了什么事，有哪些步骤等，只有这样仔细阅读才可以找到句子排列的顺序，找到句与句之间的内在联系，把握句子的排列顺序。 1时间的顺序 在有的题中，几个句子虽然被打乱了，但是可以明显找到关于时间的词语：如早上、中午、下午；几天前、昨天、今天、到了晚上等，这些词语就是明显告诉了我们句子排列的顺序，只要结合这几个时间词语便可以正确排列句子。 2方位顺序 如果是介绍一个地方、一个空间或者一个物件时，有时会出现上面、下面、左边、右边、中间等方位的词语，那么这些方位词就是我们排列句子的依据，我们可以根据先上后下，先左后右，先中间后两边，从里到外等顺序排列句子。 3事情发展的顺序 如果是写事的，就会有描写事情起因的词语，如开始、后来、最后等提示，也许会先介绍事情的起因，然后是事情是怎么发展的，最后的结果等，自然我们就可以按照事情发展的顺利来排列了。
4参观的顺序或地点转换的顺序 如果是游记、参观之类的文章，就会有一个参观的顺序，先看到了什么，接着是什么，有时是过渡句中有意暗示我们，诸如“看完了某处，我们又来到了某处”之类的话语，这就是排列顺序的方法。 句子排序练习题 1 （）碧溪河从村前流过。 （）村后是一望无际的桑园。 （）我家住在碧溪河边，这是江南水乡的小村庄。 （）河里一群小鱼在水中游来游去，水面上不时溅起朵朵水花。 （）春天，桑树抽出新芽，整个桑园就像绿色的海洋。 2 （）一些不知名的小花，长在绿草中，像蓝天上缀着的星星。 （）小花园在教室的左边，长八米，宽四米。 （）花园里四周的道路上都长满了青草，好象铺了一层绿毯。 （）它紧靠短墙，由一排横、两排竖的篱笆和这面短墙围起来。 （）花是老师精心栽培的，有的长在地上，有的长在盆里，构成了一个个图案。 （）到了夏天，大的、小的、圆的、长的、各种形状的绿叶，托着红的、黄的、蓝的、白的各色各样的花儿，美丽极了！ 3 （）地上的水越来越多。 （）雨落在对面的屋顶的瓦片上。 （）像一层薄烟罩在屋顶上。 （）渐渐地连成了一条线。 （）溅起一朵朵水花。 （）雨水顺着房檐流下来。 （）汇合成一条条小溪。 （）开始像断了线的珠子。 4 （）王红同学真值得我们学习。 （）今天，老天爷一直紧绷着脸，阴沉沉的，好象跟谁生气似的。 （）就在这个时候，我看见一个女同学飞快地朝操场奔去。 （）天突然下起雨来。