数据结构排序部分练习题
一、单选题
12．设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大的元素，最好选用( )法。A．冒泡排序B．快速排序C．堆排序D．归并排序
1．已知持排序的n个元素可分为n/k个组，每个组包含k个元素，各组间分块有序，若采用基于比较的排序，其时间下界应为：( )
A．O(nlog2n) B．O(nlog2k) C．O(klog2n) D．O(klog2k)
)且稳定的排序方法是( )。
2．最好和最坏时间复杂度均为O(n
nlog
2
A．快速排序B．堆排序C．归并排序D．基数排序
3．下列排序算法中，当初始数据有序时，花费时间反而最多的是( )。
A．起泡排序B．希尔排序C．堆排序D．快速排序
4．若需在O（nlog2n）的时间内完成排序，且要求稳定，则可选择（）
A．快速排序B．堆排序C．归并排序D．直接插入排序
5．排序趟数与序列的原始状态有关的排序方法是( )排序法。
A．插入B．选择C．希尔D．快速
6．已知数据表每个元素距离其最终位置不远，则最省时间的排序算法是( )。
A．堆排序B．直接插入排序C．快速排序D．直接选择排序
7．关键字比较次数与数据的初始状态无关的排序算法是( )。
A．直接选择排序B．冒泡排序C．直接插入排序D．希尔排序
8. 若一个元素序列基本有序，则选用（）方法较快。
A．直接插入排序B．直接选择排序C．堆排序D．快速排序
9. 若要从1000个元素中得到4个最小值元素，最好采用（）方法。
A．直接插入排序B．直接选择排序C．堆排序D．快速排序
10. 若要对1000个元素排序，要求既快又稳定，则最好采用（）方法。
A．直接插入排序B．归并排序C．堆排序D．快速排序
11. 若要对1000个元素排序，要求既快又节省存储空间，则最好采用（）方法。
A．直接插入排序B．归并排序C．堆排序D．快速排序
12. 在下列排序方法中，空间复杂性为O(log2n)的方法为（）。
A．直接选择排序B．归并排序C．堆排序D．快速排序
13. 在平均情况下速度最快的排序方法为（）。
A．直接选择排序B．归并排序C．堆排序D．快速排序
14、设有关键字初始序列{Q,H,C,Y,P,A,M,S,R,D,F,X}，则用下列哪种排序方法进行第一趟扫描的结果为{F,H,C,D,P,A,M,Q,R,S,Y,X}？
A．直接插入排序B．二路归并排序
C．以第一元素为基准的快速排序D．基数排序
15．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。
A．插入B．选择C．希尔D．二路归并
16．下面排序法中，( )排序法是不稳定的。
A．插入B．冒泡C．二路归并D．堆
17.下列排序方法中，不稳定的是（）
A．直接插入排序B．冒泡排序C．归并排序D．直接选择排序
18. 在直接插入排序的第i趟排序前，有序表中的元素个数为（）。
A．i B．i+1 C．i-1 D．1
19. 在直接插入排序的第i趟排序时，为寻找插入位置最多需要进行（）次元素的比较，假定第0号元
素作监视哨。
A．i B．i-1 C．i+1 D．1
20. 若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j]，则需要移动元素的次数为（）。
A．j-i B．i-j-1 C．i-j D．i-j+1
21. 对n个元素进行直接插入排序，则各趟排序中寻找插入位置的平均时间复杂性为（）。
A．O(1) B．O(n) C．O(n2) D．O(log2n)
22. 在对n个元素进行直接插入排序的过程中，共需要进行（）趟。
A．n B．n+1 C．n-1 D．2n
23. 对n个元素进行直接插入排序时间复杂性为（）。
A．O(1) B．O(n) C．O(n2) D．O(log2n)
24、n个记录直接插入排序时所需的记录最小比较次数是( )
A．n-1 B．n C．n(n-1)/2 D．n(n+1)/2
25. 对n个元素进行直接插入排序，空间复杂性为（）。
A．O(1) B．O(log2n) C．O(n2) D．O(nlog2n)
26. 对n个元素进行冒泡排序，第一趟至多需要进行（）对相邻元素之间的交换。
A．n B．n-1 C．n+1 D．n/2
27. 对n个元素进行冒泡排序，最好情况下的时间复杂性为（）。
A．O(1) B．O(log2n) C．O(n2) D．O(n)
28. 对n个元素进行冒泡排序，至少需要（）趟完成。
A．1 B．n C．n-1 D．n/2
6．快速排序的记录移动次数（）比较次数，其总执行时间为0（nlog2n）。
A）大于B）大于等于C）小于等于D）小于
29. 对n个元素进行快速排序，第一次划分最多需要移动（）次元素，假定包括基准和临时量之间的移动。
A．n/2 B．n-1 C．n D．n+1
30.对序列（3, 7, 5, 9, 1）进行快速排序，则第一次划分时需要移动元素的次数为（），假定不包括基准和临时量之间的移动。
A．1 B．2 C．3 D．4
31. 对n个元素进行快速排序，最好情况下需要进行（）趟。
A．n B．n/2 C．log2n D．2n
32. 对n个元素进行快速排序，最坏情况下需要进行（）趟。
A．n B．n-1 C．n/2 D．log2n
33. 对n个元素进行快速排序，平均情况下的时间复杂性为（）。
A．O(1) B．O(log2n) C．O(n2) D．O(nlog2n)
34. 对n个元素进行快速排序，最坏情况下的时间复杂性为（）。
A．O(1) B．O(log2n) C．O(n2) D．O(nlog2n)
35. 对n个元素进行快速排序，平均情况下的空间复杂性为（）。
A．O(1) B．O(log2n) C．O(n2) D．O(nlog2n)
36. 对n个元素进行快速排序，最坏情况下的空间复杂性为（）。
A．O(1) B．O(log2n) C．O(n2) D．O(nlog2n)
37. 对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（）。
A ．1, 3, 5, 7, 9
B ． 9, 7, 5, 3, 1
C ．5, 3, 1, 7, 9
D ．5, 7, 9, 1, 3
38. 假定对元素序列（7, 3, 5, 9, 1, 12, 8, 15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（ ）。
A ．2
B ．3
C ．4
D ．5
39．对n 个元素进行直接选择排序，需要进行（ ）趟选择和交换。
A ．n
B ．n+1
C ．n-1
D ．n/2
40．对n 个元素进行直接选择排序，在第i 趟需要从（ ）个元素中选择最小者。
A ．n-i+1
B ．n-I
C ．I
D ．i+1
41. 对n 个元素进行直接选择排序，则各趟寻找最小值元素所需时间复杂性为（ ）。
A ．O(1)
B ．O(log 2n)
C ．O(n 2)
D ．O(n)
5．堆排序在最坏情况下，其时间复杂性为（ ）。
A ）)log (2n n O
B ）)(2n O
C ）)(log 22n O
D ）)(log 2n O
42. 对n 个元素进行堆排序，在构成初始堆的过程中需要进行（ ）次筛运算。
A ．1
B ．n/2
C ．n
D ．n-1
43. 对n 个元素进行堆排序，建初始堆后，还要进行( )次筛选运算。
A ．n+1
B ．n/2
C ．n
D ．n-1
44. 对n 个元素进行堆排序，每次筛运算的时间复杂性为( )。
A ．O(1)
B ．O(log 2n)
C ．O(n 2)
D ．O(n)
45. 对n 个元素进行堆排序，时间复杂性为（ ）。
A ．O(1)
B ．O(log 2n)
C ．O(n 2)
D ．O(nlog 2n)
46. 对n 个元素进行堆排序，空间复杂性为（ ）。
A ．O(1)
B ．O(log 2n)
C ．O(n 2)
D ．O(nlog 2n)
12．对排序码(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
47. 假定用小根堆对（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
48. 假定初始堆为(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
A ．3, 7, 5, 9, 12, 10, 15, 1
B ．3, 5, 7, 12, 9, 10, 15, 1
49．将两个各有n 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）
A ．n
B ．2n －1
C ．2n
D ．n-1
50. 若对n 个元素进行归并排序，则进行归并的趟数为（ ）。
A ．n
B ．n-1
C ．n/2
D ．?log 2n ?
51. 若对n 个元素进行归并排序，则进行每一趟归并的时间复杂性为（ ）。
A ．O(1)
B ．O(log 2n)
C ．O(n)
D ．O(n 2)
二、判断题
如果某种排序算法是不稳定的，则该方法没有实际的应用价值。
对数据按关键字进行排序能够有效地提高查找速度。
直接插入排序是稳定的，而Shell 排序就是调用若干趟直接插入排序，所以也是稳定的。
用直接选择排序方法分别对序列S1=(1,2,3,4,5,6,7)和序列S2=(7,5,3,2,4,1,6)进行排序，两者的比较次数不相同。
直接选择排序的比较次数与序列的初始状态无关。
堆排序法在最好和最坏情况下时间复杂性都是O(nlog2n)。
堆的存储表示是顺序的。
以中序方式遍历一个堆，则得到一个有序序列。
二路归并排序的核心操作是把两个有序序列合并为一个有序序列。
快速排序法总是效率最高的排序法。
顾名思义，快速排序法是在所有情况下，速度最快的排序方法。
三、填空题
11．最简单的交换排序方法是________________排序。
11．直接插入排序需要___________个记录的辅助空间。
12．在插入和选择排序中，若初始数据基本正序，则选用___________；若初始数据基本反序，则选用___________。
1．评价排序效率的主要标准是________。
2．在时间复杂性为O(n2)的所有排序方法中，____直接选择____排序方法是不稳定的。
3．在所有排序方法中，____快速____排序方法采用的是二分法的思想。
4．在所有排序方法中，____堆排序____方法使数据的组织采用的是完全二叉树的结构。
5．在所有排序方法中，____归并排序____方法采用的是两两有序表合并的思想。
3．采用冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递增，则排序过程中记录的比较次数为____3___。若A初始状态为递减排列，则记录的交换次数为____4___。
6．____冒泡____排序方法使键值大的记录逐渐下沉，使键值小的记录逐渐上浮。
7．____直接插入____排序方法能够每次使无序表中的第一个记录插入到有序表中。
8．____直接选择____排序方法能够每次从无序表中顺序查找出一个最小值。
9．每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做__插入__排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做__选择__排序。10．每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做__交换__排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做__归并__排序。
11．对n个数据进行直接插入排序，最少比较次数为_________。
12. 若对一组记录(46,79,56,38,40,80,35,50,74)进行直接插入排序，当把第8个记录插入到前面已排序的有序表时，为寻找插入位置需比较____4____次。
13．取增量为3，对记录(46,79,56,38,40,80,35,50,74)进行一趟希尔排序的结果为＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。
14. 对n个记录进行冒泡排序时，最多比较次数为_______、最少的比较次数为__ n-1__，最少的趟数为____1___。
15．用起泡法对n个关键码排序，在最好情况下，只需做n-1 次比较和0 次移动；在最坏的情况下要做_________次比较。
16.两个序列：L1={25,57,48,37,92,86,12,33}、L2={25,37,33,12,48,57,86,92}
用冒泡排序方法分别对序列L1和L2进行排序，交换次序较少的是序列____________。
17. 对(46,79,56,38,40,84)进行冒泡排序，第一趟排序后的结果为__(46,56,38,40,79,84)__。
18. 对(46,79,56,64,38,40,84,43)进行冒泡排序，第一趟排序时，元素79将最终下沉到其后第__4__个元素的位置。
19. 快速排序的平均时间复杂性为__O(nlog2n)__，最坏时间复杂性为____O(n2)____。
20．快速排序的平均空间复杂性为__O(log2n)__，最坏空间复杂性为____O(n)____。
21．快速排序每次划分时，是从当前待排序区间的__两端__向__中间__依次查找出处于逆序的元素并交换之，最后将基准元素交换到一个确定位置，从而以该位置把当前区间划分为前后两个子区间。
22. 对(46,79,56,38,40,80)进行快速排序，对应判定树的深度为_____，分支结点数为_____。
23. 对(46,79,56,38,40,80)进行快速排序，共需要____3____趟排序。
24. 对(46,79,56,38,40,80)进行快速排序，含有两个或两个以上元素的排序区间的个数为____4____个。
25. 对(46,79,56,25,76,38,40,80)进行快速排序，第一次划分后，右区间内元素的个数为_____4_____。26．对(46,79,56,38,40,80)进行快速排序，第一次划分后的结果为__[40 38]46[56 79 80]__。
27．在直接选择排序中，记录比较次数的时间复杂度为__O(n2)__，记录移动次数的时间复杂度为__O(n)__。
28. 对记录(46,79,56,38,40,80,35,50,74)进行直接选择排序，用k表示最小值元素的下标，k初值为1，则在第一趟选择最小值的过程中，k的值被修改__2__次。
29. 在堆排序的过程中，对n个记录建立初始堆需要进行__?n/2?__次筛运算，由初始堆到堆排序结束，需要对树根结点进行__n-1__次筛运算。
30．在堆排序的过程中，对任一分支结点进行筛运算的时间复杂性为__O(log2n) _____，整个堆排序过程的时间复杂性为__O(nlog2n) __。
31．对n个元素建立初始堆时，最多进行_____次关键字比较。
32．对(46,79,56,38,40,84)进行堆排序，初始小根堆为__(38,40,56,79,46,84)__，大根堆为___________________。33．对(76,38,62,53,80,74,83,65,85)进行堆排序，已知除第一个元素外，以其余元素为根的子树都已是堆，则对第一个元素进行筛运算时，它将最终被筛到下标为__8__的位置。
34．假定一个堆为(38,40,56,79,46,84)，则利用堆排序方法进行第一趟交换和对根结点筛运算后得到的结果为__(40,46,56,79,84,38)__。
35．在一个堆的顺序存储中，若一个元素的下标为i，则它的左孩子元素的下标为__2i__，右孩子元素的下标为__2i+1__。
36．在一个小根堆中，堆顶结点的值是所有结点中的__最小的__，在一个大根堆中，堆顶结点的值是所有结点中的__最大的__。
37.将长度分别为m和n（m>n）的有序表归并成一个有序表，至少进行__n__次键值比较。
38．在二路归并排序中，对n个记录进行归并的趟数为__?log2n?__。
39. 在归并排序中，进行每趟归并的时间复杂性为__O(n) __，整个排序过程的时间复杂性为__O(nlog2n)__，空间复杂性为__O(n)__。
40．对20个记录进行归并排序时，共需要进行__5__趟归并，在第三趟归并时是把长度为__4__的有序表两两归并为长度为__8__的有序表。
41．假定一组记录为(46,79,56,38,40,80,46,75)，对其进行归并排序的过程中，第二趟归并后的第2个子表为__[40 46 75 80]__。
42．假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，第二趟归并后的子表个数为__3__。
43．假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，第三趟归并后的第2个子表为__[28 46]__。
44．假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，供需要__4__趟完成。45．假定一组记录为(46,79,56,38,40,80)，对其进行归并排序的过程中，第二趟归并后的结果为__[38 46 56 79][40 80]__。
46. 在时间复杂性为O(nlog2n)的所有排序方法中，__归并__排序方法是稳定的。
四、应用题、综合题
1．试给出由5个数据{1，2，3，4，5}组成的一个序列，使得在快速排序的第一趟划分时，移动次数最多。2．试给出由5个数据{1，2，3，4，5}组成的一个序列，使得用直接选择排序时，移动次数最多。
3、设有50个值不同的元素存于内存一片连续单元中，若用顺序选择的方法，选出这50个元素的最大值和最小值则至少需要97次比较。请给出另一种选出最大值和最小值的方法，其比较次数一定少于97次，说明该方法的操作过程和比较次数。
4、快速排序在什么情况下，所需记录之关键码的比较次数为最多？此时记录之关键码比较次数应为多少？
5. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用直接插入排序法进行排序时每一趟的排序结果。
(0) [46] 74 53 14 26 38 86 65 27 34
(1) [46 74] 53 14 26 38 86 65 27 34
(2) [46 53 74] 14 26 38 86 65 27 34
(3) [14 46 53 74] 26 38 86 65 27 34
(4) [14 26 46 53 74] 38 86 65 27 34
(5) [14 26 38 46 53 74] 86 65 27 34
(6) [14 26 38 46 53 74 86] 65 27 34
(7) [14 26 38 46 53 65 74 86] 27 34
(8) [14 26 27 38 46 53 65 74 86] 34
(9) [14 26 27 34 38 46 53 65 74 86]
6. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用冒泡排序法进行排序时每一趟的排序结果。
(0) [46 74 53 14 26 38 86 65 27 34]
(1) [46 53 14 26 38 74 65 27 34] 86
(2) [46 14 26 38 53 65 27 34] 74 86
(3) [14 26 38 46 53 27 34] 65 74 86
(4) [14 26 38 46 27 34] 53 65 74 86
(5) [14 26 38 27 34] 46 53 65 74 86
(6) [14 26 27 34] 38 46 53 65 74 86
(7) [14 26 27 34] 38 46 53 65 74 86
7. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用快速排序法进行排序时每一趟的排序结果。
(0) [46 74 53 14 26 38 86 65 27 34]
(1) [34 27 38 14 26] 46 [86 65 53 74]
(2) [26 27 14] 34 38 46 [74 65 53] 86
(3) 14 26 27 34 38 46 [53 65] 74 86
(4) 14 26 27 34 38 46 53 65 74 86
8. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用直接选择排序法进行排序时每一趟的排序结果。
(0) [46 74 53 14 26 38 86 65 27 34]
(1) 14 [74 53 46 26 38 86 65 27 34]
(2) 14 26 [53 46 74 38 86 65 27 34]
(3) 14 26 27 [46 74 38 86 65 53 34]
(4) 14 26 27 34 [74 38 86 65 53 46]
(5) 14 26 27 34 38 [74 86 65 53 46]
(6) 14 26 27 34 38 46 [86 65 53 74]
(7) 14 26 27 34 38 46 53 [65 86 74]
(8) 14 26 27 34 38 46 53 65 [86 74]
(9) 14 26 27 34 38 46 53 65 74 [86]
9. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用堆排序法进行排序时每一趟的排序结果。
构成初始堆（即建堆）的过程：
1 2 3 4 5 6 7 8 9 10
(0) 46 74 53 14 26 38 86 65 27 34
(1) 46 74 53 14 26 38 86 65 27 34
(2) 46 74 53 14 26 38 86 65 27 34
(3) 46 74 38 14 26 53 86 65 27 34
(4) 46 14 38 27 26 53 86 65 74 34
(5) 14 26 38 27 34 53 86 65 74 46
进行堆排序的过程：
(0) 14 26 38 27 34 53 86 65 74 46
(1) 26 27 38 46 34 53 86 65 74 [14]
(2) 27 34 38 46 74 53 86 65 [26 14]
(3) 34 46 38 65 74 53 86 [27 26 14]
(4) 38 46 53 65 74 86 [34 27 26 14]
(5) 46 65 53 86 74 [38 34 27 26 14]
(6) 53 65 74 86 [46 38 34 27 26 14]
(7) 65 86 74 [53 46 38 34 27 26 14]
(8) 74 86 [65 53 46 38 34 27 26 14]
(9) 86 [74 65 53 46 38 34 27 26 14]
10. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用归并排序法进行排序时每一趟的排序结果。
(0) [46][74][53][14][26][38][86][65][27][34]
(1) [46 74][14 53][26 38][65 86][27 34]
(2) [14 46 53 74][26 38 65 86][27 34]
(3) [14 26 38 46 53 65 74 86][27 34]
(3) [14 26 27 34 38 46 53 65 74 86]
数据结构课程设计(内部排序算法比较_C语言)
数据结构课程设计 课程名称：内部排序算法比较 年级/院系：11级计算机科学与技术学院 姓名/学号： 指导老师： 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。
第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并 打印出结果。 （2）选择2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------|
数据结构第九章排序习题与答案
习题九排序 一、单项选择题 1．下列内部排序算法中： A．快速排序 B.直接插入排序 C. 二路归并排序 D.简单选择排序 E. 起泡排序 F.堆排序 （1）其比较次数与序列初态无关的算法是（） （2）不稳定的排序算法是（） （3）在初始序列已基本有序（除去n 个元素中的某 k 个元素后即呈有序， k< 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、二路归并 11. 数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（C）的两趟排序后的结果。 A、选择排序 B、冒泡排序 C、插入排序 D、堆排序 12. （A）占用的额外空间的空间复杂性为Ｏ(1)。 A、堆排序算法 B、归并排序算法 C、快速排序算法 D、以上答案都不对 2019年考研《计算机数据结构》考试试题 一、选择题(24分) 1.下列程序段的时间复杂度为( )。 i=0，s=0; while (s (A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2) 2.设某链表中最常用的操作是在链表的尾部插入或删除元素，则 选用下列( )存储方式最节省运算时间。 (A) 单向链表(B) 单向循环链表 (C) 双向链表(D) 双向循环链表 3.设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为( )。 (A) s->next=p->next;p->next=-s; (B) q->next=s; s->next=p; (C) p->next=s->next;s->next=p; (D) p->next=s;s->next=q; 4.设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为( )。 (A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1 (C) 3，1，2，5，4，6 (D) 1，5，4，6，2，3 5.设有一个10阶的下三角矩阵A(包括对角线)，按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为( )。 (A) 10 (B) 19 (C) 28 (D) 55 6.设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数为m的结点，则该树中共有( )个叶子结点。 (A) (B) (C) (D) 7. 二叉排序树中左子树上所有结点的值均( )根结点的值。 (A) < (B) > (C) = (D) != 8. 设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度 为( )。 (A) 129 (B) 219 (C) 189 (D) 229 9. 设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做( )次线性探测。 (A) n2 (B) n(n+1) (C) n(n+1)/2 (D) n(n-1)/2 10.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有( )个结点。 (A) 2n (B) n+l (C) 2n-1 (D) 2n+l 11.设一组初始记录关键字的长度为8，则最多经过( )趟插入排序可以得到有序序列。 (A) 6 (B) 7 (C) 8 (D) 9 12.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是( )。 (A) F，H，C，D，P，A，M，Q，R，S，Y，X (B) P，A，C，S，Q，D，F，X，R，H，M，Y 数据结构试卷1 一、单选题 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放 位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚 注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中， 现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 n） D. O（n2） A. O（1） B. O（n） C. O（1og 2 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选 用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通 图。 A.5 B.6 C.7 D.8 二、填空题 1.通常从四个方面评价算法的质量：_________、_________、_________和 _________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含 的结点数为__________个，树的深度为___________，树的度为_________。 4.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应 的后缀算式为_______________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩 子的两个指针。在这种存储结构中，n个结点的二叉树共有________个指针 数据结构中的排序算法及性能分析 一、引言 排序（sorting ）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。为了查找方便通常希望计算机中的表是按关键字有序的。因为有序的顺序表可以使用查找效率较高的折半查找法。 在此首先明确排序算法的定义： 假设n 个记录的序列为 { 1R ，2R ，…n R } （1） 关键字的序列为： { 1k ，2k ，…，n k } 需要确定1，2，…，n 的一种排列：12,n p p p ，…，使（1）式的序列成为一个按关键字有序的序列： 12p p pn k k k ≤≤≤… 上述定义中的关键字Ki 可以是记录Ri （i=1,2，…，n ）的主关键字，也可以是记录i R 的次关键字，甚至是若干数据项的组合。若在序列中有关键字相等的情况下，即存在i k =j k （1,1,i n j n i j ≤≤≤≤≠），且在排序前的序列中i R 领先于j R 。若在排序后的序列中Ri 仍领先于j R ，则称所用的排 序方法是稳定的；反之若可能使排序后的序列中j R 领先于i R ，则称所用的排序方法是不稳定的。 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法的时间与算法中语句执行次数成正比，那个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。 在刚才提到的时间频度中，n 称为问题的规模，当n 不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n 的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n 趋近于无穷大时，T （n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。 HUNAN UNIVERSITY 课程实习报告 题目：排序算法的时间性能学生姓名 学生学号 专业班级 指导老师李晓鸿 完成日期 设计一组实验来比较下列排序算法的时间性能 快速排序、堆排序、希尔排序、冒泡排序、归并排序(其他排序也可以作为比较的对象） 要求 (1)时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间性能等。 (2)实验数据应具有说服力，包括：数据要有一定的规模（如元素个数从100到10000）；数据的初始特性类型要多，因而需要具有随机性；实验数据的组数要多，即同一规模的数组要多选几种不同类型的数据来实验。实验结果要能以清晰的形式给出，如图、表等。 (3)算法所用时间必须是机器时间，也可以包括比较和交换元素的次数。 (4)实验分析及其结果要能以清晰的方式来描述，如数学公式或图表等。 (5)要给出实验的方案及其分析。 说明 本题重点在以下几个方面： 理解和掌握以实验方式比较算法性能的方法；掌握测试实验方案的设计；理解并实现测试数据的产生方法；掌握实验数据的分析和结论提炼；实验结果汇报等。 一、需求分析 (1) 输入的形式和输入值的范围：本程序要求实现各种算法的时间性能的比 较，由于需要比较的数目较大，不能手动输入，于是采用系统生成随机数。 用户输入随机数的个数n，然后调用随机事件函数产生n个随机数，对这些随机数进行排序。于是数据为整数 (2) 输出的形式：输出在各种数目的随机数下，各种排序算法所用的时间和 比较次数。 (3) 程序所能达到的功能：该程序可以根据用户的输入而产生相应的随机 数，然后对随机数进行各种排序，根据排序进行时间和次数的比较。 （4）测试数据：略 二、概要设计 南 京 邮 电 学 院 2005年攻读硕士学位研究生入学考试 数 据 结 构 试 题 一、单选题（每题3分，共30分） 1. 设使用某算法对n 个元素进行处理，所需的时间是 T(n) = 100n log 2n + 200n + 2000 则该算法的渐进时间复杂度为 。 A. O(1) B. O(n) C. O(200n) D. O(nlog 2n) 2. 设顺序表的长度为n ，并设从表中删除元素的概率相等。则在平均情况下，从表中删除一个元素需要移动的元素个数是 。 A. (n －1)/2 B. n/2 C. n(n －1)/2 D. n(n ＋1)/2 3. 如果只保存一个n 阶对称矩阵a 的下三角元素（含对角线元素），并采用行主序存储在一维数组b 中，a[i][j]（或a[i, j]）存于b[k]，则对i 课题：内部排序算法比较 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择 1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。 （2）选择 2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| （3.1） （II）方便快捷的操作：用户只需要根据不同的需要在界面上输入系统提醒的操作形式直接进行相应的操作方式即可！如图（3.2所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| 排序算法操作 课程名称：数据结构研究 论文题目：排序算法操作 院系： 学生姓名： 学号： 专业班级： 年月日 数据结构之排序算法操作 摘要：本文通过对数据结构中排序算法深入研究,实现了排序算法中的直接插入排序、快速排序和简单选择排序操作，进一步加深了对数据结构中排序算法的理解，得到的算法可以应用到以后的编程实践中。 关键词：排序时间复杂度空间复杂度稳定性 1.引言 排序是日常生活和工作中的一个常见问题，其目的是将一组原本无序的数据元素（或记录）序列，按照人们所需要的顺序，排列成有规律的按关键字有序的序列。 在现实生活中，人们要用到排序。如：学生成绩往往需要按照成绩高低或按学号从前到后排序；在图书馆众多的图书中，需要按照各个学科将书籍归类；排队时从高到低的顺序排队等问题。同样，排序也是计算机程序设计中的一个非常重要的操作，在计算机软件设计中占有极其重要的地位。本文将对排序算法中直接插入排序、快速排序和简单选择排序三种算法的实现做一些研究。 2.算法的实现 直接插入排序算法中，第i趟进行的操作为：在含有i-1个记录的有序子序列r[1…i-1]中插入一个记录r[i]后，变成含有i个记录的有序子序列r[1….i]；并且为了在查找插入位置的过程中避免数组下标出界，在r[0]处设置监视哨，在自i-1起往前搜索的过程中，可以同时后移记录。 算法1 直接插入排序算法 Step1:从第二个记录起逐个进行关键字与前面关键字的比较并判断是否把该记录作为哨兵 for ( i=2; i<=L.length; ++i ) if(LT(L.r[i].key, L.r[i-1].key)) 数据结构各种排序算法总结 2009-08-19 11:09 计算机排序与人进行排序的不同：计算机程序不能象人一样通览所有的数据，只能根据计算机的"比较"原理，在同一时间内对两个队员进行比较，这是算法的一种"短视"。 1. 冒泡排序 BubbleSort 最简单的一个 public void bubbleSort() { int out, in; for(out=nElems-1; out>0; out--) // outer loop (backward) for(in=0; in swap(out, min); // swap them } // end for(out) } // end selectionSort() 效率：O(N2) 3. 插入排序 insertSort 在插入排序中，一组数据在某个时刻实局部有序的，为在冒泡和选择排序中实完全有序的。 public void insertionSort() { int in, out; for(out=1; out 2018计算机考研：计算机数据结构测试题(九) 2018考研，计算机专业课考试科目为：计算机组成原理、数据结构、操作系统以及计算机网络等，需要大家记忆的知识点有很多，但是不能死机硬背，还是要理解为主的，融会贯通才能把题做好，拿到高分，小编就为大家分享计算机数据结构测试题及参考答案，希望计算机考研的考生在复习之余能够认真做题，巩固知识。 计算机数据结构测试题(九) 一、选择题(24分) 1.下面关于线性表的叙述错误的是( )。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 2.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有( )个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m 3.设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为( )。 (A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M 4.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为( )。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 5.设某完全无向图中有n个顶点，则该完全无向图中有( )条边。 (A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1 6.设某棵二叉树中有2000个结点，则该二叉树的最小高度为( )。 (A) 9 (B) 10 (C) 11 (D) 12 7.设某有向图中有n个顶点，则该有向图对应的邻接表中有( )个表头结点。 (A) n-1 (B) n (C) n+1 (D) 2n-1 8.设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为( )。 (A) 2，3，5，8，6 (B) 3，2，5，8，6 (C) 3，2，5，6，8 (D) 2，3，6，5，8 二、填空题(24分) 1. 1. 为了能有效地应用HASH查找技术，必须解决的两个问题是 ____________________和__________________________。 2. 2. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。 typedef struct {int s[100]; int top;} sqstack; void push(sqstack &stack,int x) 数据结构-各类排序算法总结 原文转自： https://www.wendangku.net/doc/7d6505678.html,/zjf280441589/article/details/38387103各类排序算法总结 一. 排序的基本概念 排序(Sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素 某个项值有序的序列。 有n 个记录的序列{R1，R2，…，Rn}，其相应关键字的序列是{K1，K2，…，Kn}，相应的下标序列为1，2，…，n。通过排序，要求找出当前下标序列1，2，…，n 的一种排列p1，p2，…，pn，使得相应关键字满足如下的非递减（或非递增）关系，即：Kp1≤Kp2≤…≤Kpn，这样就得到一个按关键字有序的记录序列{Rp1，Rp2，…，Rpn}。 作为排序依据的数据项称为“排序码”，也即数据元素的关键码。若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一的；若关键码是次关键码，排序结果可 能不唯一。实现排序的基本操作有两个： （1）“比较”序列中两个关键字的大小； （2）“移动”记录。 若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。 二.插入类排序 1.直接插入排序直接插入排序是最简单的插入类排序。仅有一个记录的表总是有序的，因此，对n 个记录的表，可从第二个记录开始直到第n 个记录，逐个向有序表中进行插入操作，从而得到n个记录按关键码有序的表。它是利用顺序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。 实验报告 （2015 / 2016学年第二学期） 课程名称数据结构A 实验名称内排序算法的实现以及性能比较 实验时间2016 年 5 月26 日 指导单位计算机科学与技术系 指导教师骆健 学生姓名耿宙班级学号B14111615 学院(系) 管理学院专业信息管理与信息系统 —— 实习题名:内排序算法的实现及性能比较 班级 B141116 姓名耿宙学号 B14111615 日期2016.05.26 一、问题描述 验证教材的各种内排序算法，分析各种排序算法的时间复杂度；改进教材中的快速排序算法，使得当子集合小于10个元素师改用直接插入排序；使用随即数发生器产生大数据集合，运行上述各排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。系统时钟包含在头文件“time.h”中。 二、概要设计 文件Sort.cpp中包括了简单选择排序SelectSort()，直接插入排序InsertSort()，冒泡排序BubbleSort()，两路合并排序Merge()，快速排序QuickSort()以及改进的快速排序GQuickSort()六个内排序算法函数。主主函数main的代码如下图所示： 三、详细设计 1.类和类的层次设计 在此次程序的设计中没有进行类的定义。程序的主要设计是使用各种内排序算法对随机 生成的数列进行排列，并进行性能的比较，除此之外还对快速排序进行了改进。下图为主函 数main的流程图： —— main() 2.核心算法 1)简单选择排序： 简单选择排序的基本思想是：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到 数据结构各种排序算法总结 计算机排序与人进行排序的不同：计算机程序不能象人一样通览所有的数据，只能根据计算机的"比较"原理，在同一时间内对两个队员进行比较，这是算法的一种"短视"。 1. 冒泡排序BubbleSort 最简单的一个 public void bubbleSort() { int out, in; for(out=nElems-1; out>0; out--) // outer loop (backward) for(in=0; in 3. 插入排序insertSort 在插入排序中，一组数据在某个时刻实局部有序的，为在冒泡和选择排序中实完全有序的。public void insertionSort() { int in, out; for(out=1; out 一.选择题篇 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1）它必须具备（2）这三个特性。【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 数据结构实训报告 实验名称：数据结构 题目：内部排序比较 专业：班级：姓名：学号：实验日期： 一、实验目的：通过随机数据比较各内部排序算法的关键字比较次数和关键字移动的次数，以取得直观感受。训练学生综合设计算法能力。 二、实验要求：待排序长度不小于100，数据可有随机函数产生，用五组不同输入数据做比较，比较的指标为关键字参加比较的次数和关键字移动的次数；对结果做简单的分析，包括各组数据得出结果的解释；设计程序用顺序存储。 三、实验内容 1、待排序表的表长不小于100；至少要用5组不同的输入数据作比较；排序算法不少于3种； 2 、待排序的元素的关键字为整数； 3 、比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换以3次计)。 4、演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标的列表，以便比较各种排序的优劣。 5、最后要对结果作简单的分析。 6、测试数据：用伪随机数产生程序产生。 四、实验编程结果或过程： 1. 数据定义 typedef struct { KeyType key; }RedType; typedef struct { RedType r[MAXSIZE+1]; int length; }SqList; 2. 函数如下，代码详见文件“排序比较.cpp” int Create_Sq(SqList &L) void Bubble_sort(SqList &L)//冒泡排序void InsertSort(SqList &L)//插入排序 void SelectSort(SqList &L) //简单选择排序int Partition(SqList &L,int low,int high) void QSort(SqList &L,int low,int high)//递归形式的快速排序算法 void QuickSort(SqList &L) void ShellInsert(SqList &L,int dk)//希尔排序 void ShellSort(SqList &L,int dlta[ ]) 3. 运行测试结果，运行结果无误，如下图语速个数为20 数据结构排序超级总结 一、插入排序(Insertion Sort) 1. 基本思想： 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。 2. 排序过程： 【示例】： [初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97] 1 2Procedure InsertSort(Var R : FileType); 3//对R[1..N]按递增序进行插入排序, R[0]是监视哨// 4Begin 5for I := 2 To N Do //依次插入 R[2],...,R[n]// 6begin 7R[0] := R; J := I - 1; 8While R[0] < R[J] Do //查找R的插入位置// 9begin 10R[J+1] := R[J]; //将大于R的元素后移// 11J := J - 1 12end 13R[J + 1] := R[0] ; //插入R // 14end 15End; //InsertSort // 复制代码 二、选择排序 1. 基本思想： 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 第一章绪论 一、填空题（每空1分，共33分） 1. 一个计算机系统包括硬件系统和软件系统两大部分。 2. 一台计算机中全部程序的集合，称为这台计算机的软件资源/（系统）。 3. 计算机软件可以分为系统软件和应用软件两大类。科学计算程序包属于应用软 件，诊断程序属于系统软件（工具）。 4. 一种用助忆符号来表示机器指令的操作符和操作数的语言是汇编语言。 5. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 6. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 7. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 8. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 9. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 10．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 11. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 12. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 13．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 14. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 15. 一个算法的效率可分为时间效率和空间效率。 16. 任何一个C程序都由一个主函数和若干个被调用的其它函数组成。 二、单项选择题（每小题1分，共15分） （ B ） 1. 通常所说的主机是指∶ A) CPU B) CPU和内存C) CPU、内存与外存D) CPU、内存与硬盘 （ C ）2. 在计算机内部，一切信息的存取、处理和传送的形式是∶ A) ACSII码B) BCD码C)二进制D)十六进制 （ D ）3. 软件与程序的区别是∶ A)程序价格便宜、软件价格昂贵； B)程序是用户自己编写的，而软件是由厂家提供的； C) 程序是用高级语言编写的，而软件是由机器语言编写的； D) 软件是程序以及开发、使用和维护所需要的所有文档的总称，而程序只是软件的一部分。 （ C ）4. 所谓“裸机”是指∶ A) 单片机B)单板机C) 不装备任何软件的计算机D) 只装备操作系统的计算机 （ D ）5. 应用软件是指∶ A)所有能够使用的软件B) 能被各应用单位共同使用的某种软件 C)所有微机上都应使用的基本软件D) 专门为某一应用目的而编制的软件数据结构排序习题
2019年考研《计算机数据结构》考试试题
计算机考研数据结构试卷一(练习题含答案)
数据结构中的内部排序算法及性能分析
数据结构各种排序算法的时间性能
南京邮电大学2005年数据结构考研试卷
数据结构课程设计(内部排序算法比较 C语言)
数据结构之排序算法操作论文
数据结构 各种排序算法
2018计算机考研：计算机数据结构测试题(九)
数据结构-各类排序算法总结
南邮数据结构上机实验四内排序算法的实现以及性能比较
数据结构各种排序算法总结
计算机考研数据结构真题汇总
数据结构内部排序比较分析
数据结构排序超级总结
考研资料数据结构试题汇总
- 数据结构_各种内排序性能比较_课程设计报告纯代码版
- 数据结构课程设计--内部排序算法的比较
- 数据结构教程李春葆课后答案内排序
- 数据结构实验八内部排序
- 数据结构内部排序比较分析
- 数据结构(c语言版)题集答案——第十章_内部排序
- 《数据结构》内部排序 (1)
- 南邮数据结构上机实验四内排序算法的实现以及性能比较
- 南邮数据结构上机实验四内排序算法的实现以及性能比较
- 数据结构严蔚敏 内部排序资料
- 中南大学数据结构与算法第10章内部排序课后作业答案要点
- 数据结构内部排序比较
- 数据结构课程设计(内部排序算法比较_C语言)
- 数据结构内排序实验报告
- 数据结构 内排序外排序详细解析
- 数据结构 内部排序算法比较
- 数据结构内部排序比较
- 数据结构课程设计(内部排序算法比较 C语言)
- 数据结构(C语言版)实验报告-(内部排序算法比较)
- 数据结构内部排序