查找排序习题
一、
1.对线性表进行二分查找时，要求线性表必须( )。
A.以顺序方式存储
B.以链接方式存储
C.以顺序方式存储，且结点按关键字有序排序
D.以链接方式存储，且结点按关键字有序排序
2.直接存取文件的特点是( )。
A.记录按关键字排序
B.记录可以进行顺序存取
C.存取速度快，但占用较多的存储空间
D.记录不需要排序，存取效率高
3.文件存储的基本单位是( )。
A.记录
B.数据项
C.属性
D.关键字
4.一组记录的排序码为(47、78、61、33、39、80)，则利用堆排序的
方法建立的初始堆为( )。
A.78、47、61、33、39、80
B.80、78、61、33、39、47
C.80、78、61、47、39、33
D.80、61、78、39、47、33
6.快速排序算法在最好情况下的时间复杂度为( )
A. O(n)
B. O(nlog2n)
C. O(n2)
D. O(log2n)
7.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )
A.堆排序
B.冒泡排序
C.快速排序
D.直接插入排序
8.散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。因为散列函数不是一对一的关系，所以选择好的( )方法是散列文件的关键。
A.散列函数
B.除余法中的质数
C.冲突处理
D.散列函数和冲突处理
9.对于大文件的排序要研究在外设上的排序技术，即( )
A.快速排序法
B.内排序法
C.外排序法
D.交叉排序法
10.设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大的元素，最好选用( )法。
A.冒泡排序
B.快速排序
C.堆排序
D.基数排序
11．用某种排序方法对关键字序列（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．快速排序12．不定长文件是指（）
A．文件的长度不固定 B．记录的长度不固定
C．字段的长度不固定 D．关键字项的长度不固定
二、
1.散列技术既是一种_________方式，又是一种_________方法。
(1)存储(2)查找
2.在索引非顺序文件中，记录不按关键字顺序排列，因此对每个记录
要建立一个索引项，这样的索引表称为_________索引。.稠密
3.文件的修改包括：_________、_________和更新记录三种操作。
(1)删除(2)插入
4.与磁带存储器相比，磁盘存储器的优点是存取速度快，既适应于
_________存取，又适应于_________存取。.(1)顺序(2)随机
5.直接插入排序需要_________个记录的辅助空间。1个
6.在插入和选择排序中，若初始数据基本正序，则选用_________；
若初始数据基本反序，则选用_________。.
(1)插入排序(2)选择排序
7.采用散列技术实现散列表时，需要考虑的两个主要问题是：构造________和解决________。(1)散列函数(2)冲突
8.索引顺序表上的查找分两个阶段：(1)________；(2)________。
(1)确定待查元素所在的块(2)在块内查找待查的元素。
9.就文件而言，按用户的观点所确定的基本存储单元称为________。
按外设的观点所确定的基本存储单元称为________。
(1)逻辑结构(2)物理结构
10.文件的检索有三种方式：________存取、________存取和按关键字存取。(1)顺序(2)直接
11.最简单的交换排序方法是________排序。冒泡排序
12．在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为。2
三、
1.已知序列{15,18,60,41,6,32,83,75,95}。请给出采用冒泡排序法对该序列作升序排序时的每一趟的结果。
初始序列：15，18，60，41， 6，32，83，75，95
第一趟： 15，18，41， 6，32，60，75，83，95
第二趟： 15，18， 6，32，41，60，75，83，95
第三趟： 15， 6，18，32，41，60，75，83，95
第四趟： 6，15，18，32，41，60，75，83，95
第五趟： 6，15，18，32，41，60，75，83，95
2.将下面顺序表建成一个小头堆。
(70，12，20，31，1，5，44，66，61，200，30，80，150，4，28)
2.小头堆：
1 1
2 4 31 30 5 20 66 61 200 70 80 150 44 28 3.有初始的无序序列为{98,65,38,40,12,51,100,77,26,88},给出对其进行归并排序(升序)的每一趟的结果。
初始无序序列：98 65 38 40 12 51 100 77 26 88 ｛98｝｛65｝｛38｝｛40｝｛12｝｛51｝｛100｝｛77｝｛26｝｛88｝第一次归并：｛65 98｝｛38 40｝｛12 51｝｛77 100｝｛26 88｝第二次归并：｛38 40 65 98｝｛12 51 77 100｝｛26 88｝第三次归并：｛12 38 40 51 65 77 98 100｝｛26 88｝第四次归并：｛12 26 38 40 51 65 77 88 98 100｝
4.已知线性表的关键字集合{87, 25, 310, 08, 27, 132, 68, 95, 187, 123, 70, 63, 47}，已知散列函数为H(k)=k MOD 13，采用链地址法处理冲突，设计出该散列表的结构。
.散列地址 指针
5
其散列函数为h(key)=key%13, 处理冲突的方法为双重散列法，探查序列为： h i =(h(key)+i *h1(key))%m i =0,1,…，m －1
其中
h1(key)=key%11+1
回答下列问题：
（1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？
（2）该散列表在等概率查找时查找成功的平均查找长度为多少？
（１）对关键字35、20、33和48进行查找的比较次数为３、２、１、１； （２）平均查找长度ASL =++++=32112595
6.设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77},采用散列函数：H(key)=key MOD 13, 采用线性探测法解决冲突，试在0～18的散列地址空间中对该关键字序列构造散列表。
构造过程如下：
H(19)=19 MOD 13=6
H(01)=01 MOD 13=1
H(23)=23 MOD 13=10
H(14)=14 MOD 13=1(冲突)
H(14)=(1+1) MOD 19=2
H(55)=55 MOD 13=3
H(20)=20 MOD 13=7
H(84)=84 MOD 13=6 (冲突)
H(84)=(6+1) MOD 19=7 (仍冲突)
H(84)=(6+2) MOD 19=8
H(27)=27 MOD 13=1 (冲突)
H(27)=(1+1) MOD 19=2 (冲突)
H(27)=(1+2) MOD 19=3 (仍冲突)
H(27)=(1+3) MOD 19=4
H(68)=68 MOD 13=3 (冲突)
H(68)=(3+1) MOD 19=4 (仍冲突)
H(68)=(3+2) MOD 19=5
H(11)=11 MOD 13=11
H(10)=10 MOD 13=10 (冲突)
H(10)=(10+1) MOD 19=11 (仍冲突)
H(10)=(10+2) MOD 19=12
H(77)=77 MOD 13=12 (冲突)
H(77)=(12+1) MOD 19=13
因此，各关键字相应的地址分配如下：
address(01)=1
address(14)=2
address(55)=3
address(27)=4
address(68)=5
address(19)=6
address(20)=7
address(84)=8
address(23)=10
address(11)=11
address(10)=12
address(77)=13
其余的地址中为空。
7．阅读下列函数arrange()
int arrange(int a[],int 1,int h,int x)
{//1和h分别为数据区的下界和上界
int i,j,t；
i=1；j=h；
while(i while(i while(i if(i { t=a[j]；a[j]=a[i]；a[i]=t；} } if(a[i] else return i－1； } （1）写出该函数的功能； （2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。 （1）该函数的功能是：调整整数数组a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥x的元素落在a[i＋1..h]上。 （2）int f(int b[],int n) 或 int f(int b[],int n) { { int p,q； int p,q； p=arrange(b,0,n－1,0)； p=arrange(b,0,n－1,1)； q= arrange(b,p+1,n－1,1)； q= arrange(b,0,p,0)； return q－p； return p－q； } } 8.已知长度为7的表为： （cat,be,for,more,at,he,can） 按表中元素的次序依次插入，画出插入完成后的二叉排序树，并求其在等概率情况下查找成功的平均查找长度 思考题： 1、某百货公司仓库中电视机的价格和数量信息，按其价格从低到高存储在一个带头结点的循环链表中。链表中的结点由价格、数量和链 现新到m台价格 储的电视机信息的算法，并进行算法分析。 2、 设有序表r长度为n，欲在表中查找键值为Kn的某元素。若查找成功，则返回该元素在有序表r中的位置，若不成功，则返回0值。用二分查找法，编写一算法完成上述操作，并给出该算法的平均查找长度。该有序表存储结构定义如下：(8分) typedef struct { keytype key; Elemtype data; }rec; typedef struct { rec item［maxsize+1］; int n; }sqtable; 第十章：内部排序练习题 一、选择题 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个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j]， 则需要移动元素的次数为（）。 A. j-i B. i-j-1 C. i-j D. i-j+1 2.在对n个元素进行直接插入排序的过程中，共需要进行（）趟。 A. n B. n+1 C. n-1 D. 2n 3.在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（）。 A. O(1) B. O(log2n) C. O(n2) D. O(n) 4.在对n个元素进行快速排序的过程中，若每次划分得到的左、右两个子区间中元素的个数相等 或只差一个，则排序的时间复杂度为（）。 A. O(1) B. O(nlog2n) C. O(n2) D. O(n) 5.在对n个元素进行直接插入排序的过程中，算法的空间复杂度为（）。 A. O(1) B. O(log2n) C. O(n2) D. O(nlog2n) 6.设一组初始记录关键字序列(5，2，6，3，8)，利用冒泡排序进行升序排序，且排序中从后往前 进行比较，则第一趟冒泡排序的结果为（）。 (A) 2，5，3，6， 8(B) 2，5，6，3，8 (C) 2，3，5，6， 8 (D) 2，3，6，5，8 7.对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中 需要移动元素次数最多的序列为（）。 A. 1, 3, 5, 7, 9 B. 9, 7, 5, 3, 1 C. 5, 1, 3, 7, 9 D. 5, 7, 9, 3, 1 8.在对n个元素进行堆排序的过程中，时间复杂度为（）。 A. O(1) B. O(log2n) C. O(n2) D. O(nlog2n) 9.以下序列不可以构成小跟堆的是（）。 A. 12, 9, 7, 5, 3, 1 B. 1, 3, 5, 9, 7, 12 C. 1, 5, 3, 7, 9, 12 D. 1, 5, 3, 9, 12, 7 10.设一组初始记录关键字序列(5，8，6，3，2)，以第一个记录关键字5为基准进行一趟从大到小 快速排序的结果为（）。 A. 2，3，5，8，6 B. 2，3，5，6，8 C. 3，2，5，8，6 D. 3，2，5，8，6 11.假定对元素序列（7, 3, 5, 9, 1, 12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆 为（）。 A. 1, 3, 5, 7, 9, 12 B. 1, 3, 5, 9, 7, 12 C. 1, 5, 3, 7, 9, 12 D. 1, 5, 3, 9, 12, 7 12.假定一个初始堆为(1, 5, 3, 9, 12, 7, 15, 10)，则进行第一趟堆排序后，再重新建堆得到的结果为 （）。 A. 3, 5, 7, 9, 12, 10, 15, 1 B. 3, 5, 9, 7, 12, 10, 15, 1 常见内部排序算法比较 排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，究竟各有什么特点呢？本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序，直接插入排序，简单选择排序，快速排序，堆排序，针对关键字的比较次数和移动次数进行测试比较。 问题分析和总体设计 ADT OrderableList { 数据对象：D={ai| ai∈IntegerSet,i=1,2,…,n,n≥0} 数据关系：R1={〈ai-1，ai〉|ai-1, ai∈D, i=1,2,…,n} 基本操作： InitList(n) 操作结果：构造一个长度为n，元素值依次为1，2，…，n的有序表。Randomizel(d,isInverseOrser) 操作结果：随机打乱 BubbleSort( ) 操作结果：进行起泡排序 InserSort( ) 操作结果：进行插入排序 SelectSort( ) 操作结果：进行选择排序 QuickSort( ) 操作结果：进行快速排序 HeapSort( ) 操作结果：进行堆排序 ListTraverse(visit( )) 操作结果：依次对L种的每个元素调用函数visit( ) }ADT OrderableList 待排序表的元素的关键字为整数.用正序,逆序和不同乱序程度的不同数据做测试比较,对关键字的比较次数和移动次数(关键字交换计为3次移动)进行测试比较.要求显示提示信息,用户由键盘输入待排序表的表长(100-1000)和不同测试数据的组数(8-18).每次测试完毕,要求列表现是比较结果. 要求对结果进行分析. 详细设计 1、起泡排序 算法：核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。 bubblesort(struct rec r[],int n) { int i,j; struct rec w; unsigned long int compare=0,move=0; for(i=1;i<=n-1;i++) for(j=n;j>=i+1;j--) { if(r[j].key 排序习题参考标准答案 ————————————————————————————————作者：————————————————————————————————日期： 习题七参考答案 一、选择题 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．试设计算法，用插入排序方法对单链表进行排序。 参考答案: 【程序改错】 功能：在一个已按升序排列的数组中插入一个数，插入后，数组元素仍按升序排列。 #define N 11 main() { int i,j,t,number,a[N]={1,2,4,6,8,9,12,15,149,156}; printf("please enter an integer to insert in the array:\n"); /**********FOUND**********/ scanf("%d",&number) printf("The original array:\n"); for(i=0;i #include for(j=i-dk;j>0&&L.r[0] 习题九排序 一、单项选择题 1．下列内部排序算法中： A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序 （1）其比较次数与序列初态无关的算法是（） （2）不稳定的排序算法是（） （3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k< 人教版小学四年级下册语文排序专项练习题及答案（一） （）田野的尽头，连绵的山峰像海里起伏的波涛。（）溪水是那么清澈、明净；水里的小鱼儿自由自在地游来游去。 （）小溪的另一边是田野，如今黄澄澄的，正报告着丰收的喜讯。 （）一条小溪从我们村子旁静静地流过。 （）山腰上的公路，像一条银灰色的绸带飘向远方。（）小溪的一边是果园，春天，花香弥漫；秋天，硕果累累。 参考答案：5、2、4、1、6、3 （二） （）人们都说这个山村像一幅风景画。 （）村前有一口大水塘，塘水清如明镜。 （）山脚下有一个村子，村子景色秀丽。 （）塘里荷花点点，偶尔有小鱼跳出水面。 （）村后有一片青翠的竹林，林中鸟声清脆悦耳。（）水里倒映着蓝天白云。答案：6、2、1、4、5、3 （三） （）一听到这熟悉的叫声，我就猜准它一定生蛋了。（）我高兴地把蛋捡在手里，还热乎乎的呢。 （）跨进屋门，果然，一个鹅蛋似的双黄蛋躺在鸡窝里。 （）一天下午，我参加学习小组后回家，老远就听到我家的那只老母鸡“咯咯哒”、“咯咯哒”地在房子里叫个不停。 答案：2、4、3、1。 （四） （）当太阳一落山，黄昏的薄霭像轻纱一样笼罩山野的时候，青蛙便逐渐热闹起来。 （）蛙们纷纷跳入稻田去了，蛙声也暂时停息。 （）这时候，人要是从田埂上经过，就听见路两旁扑通扑通的声音。 （）但是人刚一走过，他们又扯开嗓子，放肆地叫起来。 （）乡村的夏夜，便是蛙的世界。 答案：2、4、3、5、1 （五） （）一大滴松脂从树上滴下来，把苍蝇和蜘蛛包在了里面。 （）松脂球埋在泥沙里成了化石。 （）地壳变动了，森林被海水淹没了。 （）松脂不断往下滴，盖住了原来的地方，积成了一个松脂球。 （）一个夏天的晌午，热辣辣的太阳照射着松树林。 习题七参考答案 一、选择题 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) { 07排序 【单选题】 1. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（A）排序法。 A、直接插入 B、简单选择 C、希尔 D、二路归并 2. 直接插入排序在最好情况下的时间复杂度为（B）。 A、O(logn) B、O(n) C、O(n*logn) D、O(n2) 3. 设有一组关键字值（46,79,56,38,40,84），则用堆排序的方法建立的初始堆为（B）。 A、79,46,56,38,40,80 B、84,79,56,38,40,46 C、84,79,56,46,40,38 D、84,56,79,40,46,38 4. 设有一组关键字值（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 5. 将两个各有n个元素的有序表归并成一个有序表，最少进行（A）次比较。 A、n B、2n-1 C、2n D、n-1 6. 下列排序方法中，排序趟数与待排序列的初始状态有关的是（C）。 A、直接插入 B、简单选择 C、起泡 D、堆 7. 下列排序方法中，不稳定的是（D）。 A、直接插入 B、起泡 C、二路归并 D、堆 8. 若要在O(nlog2n)的时间复杂度上完成排序，且要求排序是稳定的，则可选择下列排序方法中的（C）。 A、快速 B、堆 C、二路归并 D、直接插入 9. 设有1000个无序的数据元素，希望用最快的速度挑选出关键字最大的前10个元素，最好选用（C）排序法。 A、起泡 B、快速 C、堆 D、基数 10. 若待排元素已按关键字值基本有序，则下列排序方法中效率最高的是（A）。 A、直接插入 B、简单选择 C、快速 D、二路归并 内部排序算法的实现与 比较 Company Document number：WUUT-WUUY-WBBGB-BWYTT-1982GT 实验四：内部排序算法的实现与比较 一、问题描述 1．实验题目：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大致执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 2．基本要求：（1）对常用的内部排序算法进行比较：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序。 （2利用随机函数产生N（N=30000）个随机整数，作为输入数据作比较；比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。 （3)对结果作出简要分析。 3．测试数据：随机函数产生。 二、需求分析 1．程序所能达到的基本可能：通过随机数据产生N个随机数，作为输入数据作比较；对常用的内部排序算法：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序进行比较：比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。最后结果输出各种排序算法的关键字参加的比较次数和关键字的移动次数，并按从小到大排列。 2．输入的形式及输入值范围：随机函数产生的N（N=30000）个随机整数。 3．输出的形式：输出各种排序算法的关键字参加的比较次数和关键字的移动次数。并按从小到大排列。 4．测试数据要求：随机函数产生的N（N=30000）个随机整数。 三、概要设计 1. 所用到得数据结构及其ADT 为了实现上述功能，应以一维数组表示集合数据类型。 int s[N]; int compare[6]={0},move[6]={0},D[N]={0},RS[N]={0}; 基本操作： 数组赋值： for(i=1;i 第二轮排序和查找算法综合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 公共部门人力资源管理练习题 （） 一、选择题（每题2分，30题共计60分，每题至少有一个答案，多选或者少选均不能得分） 74. 对于公共部门人才所要测评的要素来说，（A）是最基本的测评方式，具有重要的把关作用。 A. 笔试 B. 资质测试 C. 评价中心技术 D. 无领导小组讨论 83. 美国哈佛大学威廉·詹姆斯教授，在实地调查中发现一个人平常表现的能力水平，与经过激发可能达到的能力水平之间存在着大约（ A ）左右的差距。 A. 60％ B. 50％ C. 80％ D. 70％ 89. （ A）是绩效管理的重要环节，也是传统的绩效管理模式与现代模式的本质区别之一。 A. 持续沟通 B. 实施绩效评价 C. 提供绩效反馈 D. 绩效改进指导 53. 第一个被公认的现代人事管理部门是1902年在（B）现金出纳公司设立的劳工部门，它的工作内容包括工资行政、诉怨、雇用工作情况和工作改善等。 A. 英国 B. 美国 C. 德国 D. 比利时 57. 我国古代社会中按官职高低授予不同政治待遇以表明官员等级尊卑的制度是（B）。 A. 俸禄 B. 品秩 C. 致仕 D. 回避 58. 《中华人民共和国公务员法》于（B）开始施行。 A. 2006年10月1日 B. 2006年1月1日 C. 2007年10月1日 D. 2007年1月1日 62. 我国劳动力市场体系已初步形成，（B）在人力资源配置中的主导地位也已初步确立。 A. 政府部门 B. 市场机制 C. 第三部门 D. 三资企业 70. （ B）是一种以工作为中心的工作分析方法，是对管理工作进行定量化测试的方法，适用于不同组织内管理层次以上职位的分析。 A. 职位分析问卷 B. 管理职位描述问卷 C. 体能分析问卷 D. 心理分析问卷 77. 公共部门人力资源招募与选录工作只有在（ B ）分析的基础上，才能确定公共职位空缺的数量、结构、任职资格条件、具体的招募途径以及甄选方法等。 A. 劳动力市场的供需状况 B. 内部环境 C. 外部环境 D. 经济环境 80. ( B )是公职人员职业生涯开始时或任新职时所经历的第一种类型的培训。 A. 技能培训 B. 初任培训 C. 专业培训 D. 知识更新培训 85. 我国古代的"卧薪尝胆"、"破釜沉舟"的故事充分说明了( B )的重大作用。 A. 情感激励 B. 危机激励 C. 荣誉激励 D. 目标激励 86. 目前，大多数公共管理部门所采取的考评模式均属于（ B）。 A. 发展型评估 B. 判断型评估 C. 参与型评估 D. 专项型评估 88. 实践证明，采用（B）的考核方法，很难区分不同部门之间公务员业绩的差别和同一部门内工作性质差别不太大的公务员工作业绩的高下，也很难根据考核结果客观、完整地评价一个公务员。 A. 定量分析 B. 定性分析 C. 360度绩效分析 D. 平衡记分卡 106. 公共部门人力资源部内培训的最大优点在于( B)。 A.有助于增进部门之间的相互联系和信息交流，并有助于节省培训经费 B.针对性较强、容易实施，也比较容易取得实效 C.有助于人们开阔视野，增强应对所面对的现实问题的能力 D.有利于部门工作经验的传授和良好人际关系的维系，也有利于保持部门的优良传统和工作的连续性 67. ( C )是公务员交流最为常见的方式。 A. 调任 B. 聘任 C. 转任 D. 挂职锻炼 107. （C）是目前公职人员培训中普遍采用的方法。 A. 讲授式培训法 B. 研讨式培训法 C. 案例分析培训法 D. 合作研究培训法 1（） （）碧溪河从村前流过。 （）村后是一望无际的桑园。 （）我家住在碧溪河边，这是江南水乡的小村庄。 （）河里一群小鱼在水中游来游去，水面上不时溅起朵朵水花。 （）春天，桑树抽出新芽，整个桑园就像绿色的海洋。 2（） （）一些不知名的小花，长在绿草中，像蓝天上缀着的星星。 （）小花园在教室的左边，长八米，宽四米。 （）花园里四周的道路上都长满了青草，好象铺了一层绿毯。 （）它紧靠短墙，由一排横、两排竖的篱笆和这面短墙围起来。 （）花是老师精心栽培的，有的长在地上，有的长在盆里，构成了一个个图案。（）到了夏天，大的、小的、圆的、长的、各种形状的绿叶，托着红的、黄的、蓝的、白的各色各样的花儿，美丽极了！ 3（） （）地上的水越来越多。 （）雨落在对面的屋顶的瓦片上。 （）像一层薄烟罩在屋顶上。 （）渐渐地连成了一条线。 （）溅起一朵朵水花。 （）雨水顺着房檐流下来。 （）汇合成一条条小溪。 （）开始像断了线的珠子。 4（） （）王红同学真值得我们学习。 （）今天，老天爷一直紧绷着脸，阴沉沉的，好象跟谁生气似的。 （）就在这个时候，我看见一个女同学飞快地朝操场奔去。 （）天突然下起雨来。 （）啊！那是三年级（4）班的王红。 （）下午放学的时候，同学们背起书包正准备回家。 （）原来，她是冒雨去降国旗的。 （）红领巾在她胸前飘动，就像一束跳动的火苗。 5（） （）我们坐在河边柳树下，放下了鱼钩。 （）忽然，浮标一沉，我急忙把鱼竿往上一提，一条银白色的小鱼钓上来了。（）星期天早晨，我和小明扛着鱼竿到郊外去钓鱼。 （）浅红色的浮标漂在水面上。 （）我们高兴地把鱼竿举在空中，摇晃着，喊着：“我们钓着鱼了！” 6（） （）他正想坐下时，管理员对他说：“先生，请你不要坐在这里，这里是马克思的座位。” （）管理员笑着说：“是的，很多年来，他每天都到这里来读书。” （）那个读者问：“他每天都来吗？你是说他今天一定会来？” （）话刚说完，马克思果然跨进门来了。 （）一天清早，伦敦大英博物馆里，有位读者看见有个座位空着，便走了过来。 7（） （）我连忙站起来让老爷爷坐。 （）我刚坐下，一位老爷爷提着篮子上了车。 （）星期日，我坐汽车去奶奶家。 （）老爷爷微笑着说：“谢谢，你真是个好孩子。” （）上车后，我找到一个座位。 （）我说：“不用谢，这是我应该做的。” 8（） （）我说了声：“谢谢奶奶。”就把压岁钱交给爸爸，留着给我交学费。（）奶奶说：“这孩子到底长了一岁，懂事多了。” （）奶奶乐呵呵地从怀里掏出一个红包，说是给我的压岁钱。 （）屋子里充满了欢声笑语。 （）我奔到奶奶身边，祝奶奶健康长寿。 9（） （）小脸蛋鼓鼓的，像嘴里含着里两个核桃。 （）身上穿着大翻领西装和蓝色直筒裤。 （）我的“小顽童”真逗人喜爱。 （）脚穿一双特大号皮鞋。 （）眉毛下两只眼睛，仿佛在转动。 （）他头上戴着一顶红白相间的西瓜帽。 10（） （）找到字典“部首目录”那页。从2画中找到“讠”，看看后面的页码。（）老师让我们用部首查字法查出“诚”字。 （）再数一数除去部首还有6画。 （）我翻到有“讠”的那一页，从6画中找到“诚”字，根据页码就可以查到“诚”字。 （）我先确定“诚”的部首是“讠”，共2画。 实验四：内部排序算法的实现与比较 一、问题描述 1．实验题目：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大致执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。2．基本要求：（1）对常用的内部排序算法进行比较：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序。 （2利用随机函数产生N（N=30000）个随机整数，作为输入数据作比较；比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。 （3)对结果作出简要分析。 3．测试数据：随机函数产生。 二、需求分析 1．程序所能达到的基本可能：通过随机数据产生N个随机数，作为输入数据作比较；对常用的内部排序算法：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序进行比较：比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。最后结果输出各种排序算法的关键字参加的比较次数和关键字的移动次数，并按从小到大排列。 2．输入的形式及输入值范围：随机函数产生的N（N=30000）个随机整数。 3．输出的形式：输出各种排序算法的关键字参加的比较次数和关键字的移动次数。并按从小到大排列。 4．测试数据要求：随机函数产生的N（N=30000）个随机整数。 三、概要设计 1. 所用到得数据结构及其ADT 为了实现上述功能，应以一维数组表示集合数据类型。 int s[N]; int compare[6]={0},move[6]={0},D[N]={0},RS[N]={0}; 基本操作： 数组赋值： for(i=1;i 排序练习题 1（） （）碧溪河从村前流过。 （）村后是一望无际的桑园。 （）我家住在碧溪河边，这是江南水乡的小村庄。 （）河里一群小鱼在水中游来游去，水面上不时溅起朵朵水花。 （）春天，桑树抽出新芽，整个桑园就像绿色的海洋。 2（） （）一些不知名的小花，长在绿草中，像蓝天上缀着的星星。 （）小花园在教室的左边，长八米，宽四米。 （）花园里四周的道路上都长满了青草，好象铺了一层绿毯。 （）它紧靠短墙，由一排横、两排竖的篱笆和这面短墙围起来。 （）花是老师精心栽培的，有的长在地上，有的长在盆里，构成了一个个图案。（）到了夏天，大的、小的、圆的、长的、各种形状的绿叶，托着红的、黄的、蓝的、白的各色各样的花儿，美丽极了！ 3（） （）地上的水越来越多。 （）雨落在对面的屋顶的瓦片上。 （）像一层薄烟罩在屋顶上。 （）渐渐地连成了一条线。 （）溅起一朵朵水花。 （）雨水顺着房檐流下来。 （）汇合成一条条小溪。 （）开始像断了线的珠子。 4（） （）王红同学真值得我们学习。 （）今天，老天爷一直紧绷着脸，阴沉沉的，好象跟谁生气似的。 （）就在这个时候，我看见一个女同学飞快地朝操场奔去。 （）天突然下起雨来。 （）啊！那是三年级（4）班的王红。 （）下午放学的时候，同学们背起书包正准备回家。 （）原来，她是冒雨去降国旗的。 （）红领巾在她胸前飘动，就像一束跳动的火苗。 5（） （）我们坐在河边柳树下，放下了鱼钩。 （）忽然，浮标一沉，我急忙把鱼竿往上一提，一条银白色的小鱼钓上来了。（）星期天早晨，我和小明扛着鱼竿到郊外去钓鱼。 （）浅红色的浮标漂在水面上。 （）我们高兴地把鱼竿举在空中，摇晃着，喊着：“我们钓着鱼了！” 6（） （）他正想坐下时，管理员对他说：“先生，请你不要坐在这里，这里是马克思的座位。” （）管理员笑着说：“是的，很多年来，他每天都到这里来读书。” （）那个读者问：“他每天都来吗？你是说他今天一定会来？” （）话刚说完，马克思果然跨进门来了。 （）一天清早，伦敦大英博物馆里，有位读者看见有个座位空着，便走了过来。 7（） （）我连忙站起来让老爷爷坐。 （）我刚坐下，一位老爷爷提着篮子上了车。 （）星期日，我坐汽车去奶奶家。 （）老爷爷微笑着说：“谢谢，你真是个好孩子。” （）上车后，我找到一个座位。 （）我说：“不用谢，这是我应该做的。” 8（） （）我说了声：“谢谢奶奶。”就把压岁钱交给爸爸，留着给我交学费。 （）奶奶说：“这孩子到底长了一岁，懂事多了。” （）奶奶乐呵呵地从怀里掏出一个红包，说是给我的压岁钱。 （）屋子里充满了欢声笑语。 （）我奔到奶奶身边，祝奶奶健康长寿。 9（） （）小脸蛋鼓鼓的，像嘴里含着里两个核桃。 （）身上穿着大翻领西装和蓝色直筒裤。 （）我的“小顽童”真逗人喜爱。 （）脚穿一双特大号皮鞋。 （）眉毛下两只眼睛，仿佛在转动。 （）他头上戴着一顶红白相间的西瓜帽。 10（）第十章：内部排序练习题
排序练习题(答案)(新)
几种常见内部排序算法比较
排序习题参考标准答案
排序练习题
内部排序代码
数据结构第九章排序习题及答案
人教版小学四年级下册语文排序专项练习题及答案69730
第7章 排序 习题参考答案
数据结构排序习题
内部排序算法的实现与比较
2018年浙江省选考信息技术查找与排序强化习题一答案
公共部门人力资源管理练习题 排序
二年级语文排序练习题
内部排序算法的实现与比较
二年级语文下册 排序练习题
相关主题
文本预览