最新数据结构第九章排序习题及答案
习题九排序
一、单项选择题
1．下列内部排序算法中：
A．快速排序 B.直接插入排序
C. 二路归并排序
D. 简单选择排序
E. 起泡排序
F. 堆排序
（1）其比较次数与序列初态无关的算法是（）
（2）不稳定的排序算法是（）
（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k< （4）排序的平均时间复杂度为O(n?logn)的算法是（）为O(n?n)的算法是（）2．比较次数与排序的初始状态无关的排序方法是( )。 A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序3．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 ( )。 A. 选择 B. 冒泡 C. 快速 D. 插入 4．下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A. 选择 B. 冒泡 C. 归并 D. 堆 5．一组记录的关键码为（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) 6．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。 A．冒泡 B. 希尔 C. 快速 D. 堆 7. 就平均性能而言，目前最好的内排序方法是( )排序法。 A. 冒泡 B. 希尔插入 C. 交换 D. 快速 8. 下列排序算法中，占用辅助空间最多的是：( ) A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序 9. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。 A. 3 B. 10 C. 15 D. 25 10. 快速排序方法在（）情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据个数为奇数 D. 要排序的数据已基本有序 11．下列四个序列中，哪一个是堆（）。 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 12. 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（） A．-1，4，8，9，20，7，15，7 B．-1，7，15，7，4，8，20，9 C．-1，4，7，8，20，15，7，9 D．A，B，C均不对。 二、填空题 1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为________的。 2.按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。 3．直接插入排序用监视哨的作用是___________________________。 4．对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为_______。 5．下面的c函数实现对链表head进行选择排序的算法,排序完毕,链表中的结点按结点值从小到大链接。请在空框处填上适当内容,每个空框只填一个语句或一个表达式： #include typedef struct node {char data; struct node *link; }node; node *select(node *head) {node *p,*q,*r,*s; p=(node *)malloc(sizeof(node)); p->link=head; head=p; while(p->link!=null) {q=p->link; r=p; while ((1)____________) { if (q->link->data q=q->link; } if ((2)___________) {s=r->link; r->link=s->link; s->link= ((3)_________); ((4)_________);} ((5)________) ; } p=head; head=head->link; free(p); return(head); } 6．下面的排序算法的思想是：第一趟比较将最小的元素放在r[1]中，最大的元素放在r[n]中，第二趟比较将次小的放在r[2]中，将次大的放在r[n-1]中，…,依次下去，直到待排序列为递增序。（注：<-->）代表两个变量的数据交换）。 void sort(SqList &r,int n) { i=1; while((1)______) { min=max=1; for (j=i+1;(2)________ ;++j) {if((3)________) min=j; else if(r[j].key>r[max].key) max=j; } if((4)_________) r[min] < ---- >r[j]; if(max!=n-i+1){if ((5)_______) r[min] < ---- > r[n-i+1]; else ((6)______); } i++; } }//sort 7．下列算法为奇偶交换排序，思路如下：第一趟对所有奇数的i,将a[i]和a[i+1]进行比较,第二趟对所有偶数的i,将a[i]和a[i+1]进行比较,每次比较时若a[i]>a[i+1],将二者交换;以后重复上述二趟过程,直至整个数组有序。 void oesort (int a[n]) {int flag,i,t; do {flag=0; for(i=1;i if(a[i]>a[i+1]) {flag=(1)______; t=a[i+1]; a[i+1]=a[i]; (2)________;} for (3)________ if (a[i]>a[i+1]) {flag=(4)________;t=a[i+1]; a[i+1]=a[i]; a[i]=t;} }while (5)_________; } 第九章排序 一、单项选择题 1．（1） DC （2）ADF （3）B （4）ACF BDE 2．D 3．A 4．C 5．C 6．C 7. D 8. A 9. C 10. D 11．C 12. C 二、填空题 1.稳定、不稳定 2.内部、外部 3．免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。 4．n(n-1)/2 5．题中为操作方便，先增加头结点（最后删除），p指向无序区的前一记录，r指向最小值结点的前驱，一趟排序结束，无序区第一个记录与r所指结点的后继交换指针。 (1)q->link!=NULL (2)r!=p (3)p->link (4)p->link=s (5)p=p->link 6．.(1)i 7．(1)1 (2)a[i]=t (3)(i=2;i<=n;i+=2) (4)1 (5)flag 数据结构课程（本科）第九章试题 一、单项选择题 1.若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（）方法比较次数最少。 A. 直接插入排序 B. 快速排序 C. 归并排序 D. 直接选择排序 2.如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。 A. 起泡排序 B. 快速排序 C. 直接选择排序 D. 堆排序 3.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作， 直到子序列为空或只剩一个元素为止。这样的排序方法是（）。 A. 直接选择排序 B. 直接插入排序 C. 快速排序 D. 起泡排序 4.对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较？ A. 8 B. 10 C. 15 D. 25 5.如果输入序列是已经排好顺序的，则下列算法中（）算法最快结束？ A. 起泡排序 B. 直接插入排序 C. 直接选择排序 D. 快速排序 6.如果输入序列是已经排好顺序的，则下列算法中（）算法最慢结束？ A. 起泡排序 B. 直接插入排序 C. 直接选择排序 D. 快速排序 7.下列排序算法中（）算法是不稳定的。 A. 起泡排序 B. 直接插入排序 C. 基数排序 D. 快速排序 8.假设某文件经过内部排序得到100个初始归并段，那么如果要求利用多路平衡归并在3 趟内完成排 序，则应取的归并路数至少是（）。 A. 3 B. 4 C. 5 D. 6 9.采用任何基于排序码比较的算法，对5个互异的整数进行排序，至少需要（）次比较。 A. 5 B. 6 C. 7 D. 8 10.下列算法中（）算法不具有这样的特性：对某些输入序列，可能不需要移动数据对象即可完成 排序。 A. 起泡排序 B. 希尔排序 C. 快速排序 D. 直接选择排序 11.使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过O(nlog2n)，必须做到（）。 数据结构课程设计 课程名称：内部排序算法比较 年级/院系：11级计算机科学与技术学院 姓名/学号： 指导老师： 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并 打印出结果。 （2）选择2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| 第10章内部排序习题练习答案 1.以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。 (1) 直接插入排序(2)希尔排序(3)冒泡排序(4)快速排序 (5) 直接选择排序(6) 堆排序(7) 归并排序(8)基数排序 上述方法中，哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。 答： (1)直接插入排序:(方括号表示无序区) 初始态: 265[301 751 129 937 863 742 694 076 438] 第一趟：265 301[751 129 937 863 742 694 076 438] 第二趟：265 301 751[129 937 863 742 694 076 438] 第三趟：129 265 301 751[937 863 742 694 076 438] 第四趟：129 265 301 751 937[863 742 694 076 438] 第五趟：129 265 301 751 863 937[742 694 076 438] 第六趟：129 265 301 742 751 863 937[694 076 438] 第七趟：129 265 301 694 742 751 863 937[076 438] 第八趟：076 129 265 301 694 742 751 863 937[438] 第九趟：076 129 265 301 438 694 742 751 863 937 (2)希尔排序(增量为5，3，1) 初始态: 265 301 751 129 937 863 742 694 076 438 第一趟：265 301 694 076 438 863 742 751 129 937 第二趟：076 301 129 265 438 694 742 751 863 937 第三趟：076 129 265 301 438 694 742 751 863 937 (3)冒泡排序(方括号为无序区) 初始态[265 301 751 129 937 863 742 694 076 438] 第一趟：076 [265 301 751 129 937 863 742 694 438] 第二趟：076 129 [265 301 751 438 937 863 742 694] 第三趟：076 129 265 [301 438 694 751 937 863 742] 第四趟：076 129 265 301 [438 694 742 751 937 863] 第五趟：076 129 265 301 438 [694 742 751 863 937] 第六趟：076 129 265 301 438 694 742 751 863 937 (4)快速排序：（方括号表示无序区，层表示对应的递归树的层数） 实验八内部排序 一、实验目的 1、掌握内部排序的基本算法； 2、分析比较内部排序算法的效率。 二、实验内容和要求 1. 运行下面程序： #include 习题九排序 一、单项选择题 1．下列内部排序算法中： A．快速排序 B.直接插入排序 C. 二路归并排序 D.简单选择排序 E. 起泡排序 F.堆排序 （1）其比较次数与序列初态无关的算法是（） （2）不稳定的排序算法是（） （3）在初始序列已基本有序（除去n 个元素中的某 k 个元素后即呈有序， k< 1．下列排序算法中，其中（）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 2．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序3．排序趟数与序列的原始状态有关的排序方法是( )排序法。 A．插入 B. 选择 C. 冒泡 D. 快速4．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中 的变化为（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是( )。 A. 选择 B. 冒泡 C. 快速 D. 插入5．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（）排序。 A. 选择 B. 快速 C. 希尔 D. 冒泡6．若上题的数据经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的 是（）排序。 A．选择 B. 堆 C. 直接插入 D. 冒泡 7．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）A．直接插入排序B．冒泡排序C．简单选择排序 8．下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 插入排序 9. 下列排序算法中，占用辅助空间最多的是：( ) A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序10．用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数 最少的是（）。 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 11. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。 A. 3 B. 10 C. 15 D. 25 12．对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确 课题：内部排序算法比较 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择 1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。 （2）选择 2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| （3.1） （II）方便快捷的操作：用户只需要根据不同的需要在界面上输入系统提醒的操作形式直接进行相应的操作方式即可！如图（3.2所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| 实验报告 （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）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| ~ 请选择操作方式： 如上图所示该系统的功能有： （1）：选择 1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。 （2）选择 2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 、 第三章系统设计 （I）友好的人机界面设计：（如图所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| ： （） 第十章内部排序 10.23 void Insert_Sort1(SqList &L)//监视哨设在高下标端的插入排序算法 { k=L.length; for(i=k-1;i;--i) //从后向前逐个插入排序 if(L.r[i].key>L.r[i+1].key) { L.r[k+1].key=L.r[i].key; //监视哨 for(j=i+1;L.r[j].key>L.r[i].key;++j) L.r[j-1].key=L.r[j].key; //前移 L.r[j-1].key=L.r[k+1].key; //插入 } }//Insert_Sort1 10.24 void BiInsert_Sort(SqList &L)//二路插入排序的算法 { int d[MAXSIZE]; //辅助存储 x=L.r.key;d=x; first=1;final=1; for(i=2;i<=L.length;i++) { if(L.r[i].key>=x) //插入前部 { for(j=final;d[j]>L.r[i].key;j--) d[j+1]=d[j]; d[j+1]=L.r[i].key; final++; } else //插入后部 { for(j=first;d[j] 一、实验目的 1、了解内排序都是在内存中进行的。 2、为了提高数据的查找速度，需要对数据进行排序。 3、掌握内排序的方法。 二、实验内容 1、设计一个程序e xp10—1.cpp实现直接插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序 过程。 （1）源程序如下所示： //文件名:exp10-1.cpp #include 数据结构实训报告 实验名称：数据结构 题目：内部排序比较 专业：班级：姓名：学号：实验日期： 一、实验目的：通过随机数据比较各内部排序算法的关键字比较次数和关键字移动的次数，以取得直观感受。训练学生综合设计算法能力。 二、实验要求：待排序长度不小于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 第9章查找 一、选择题 1.顺序查找一个共有n个元素的线性表，其时间复杂度为（），折半查找一个具有n个元素的有序表，其时间复 杂度为（）。【＊，★】 A.O(n) B. O(log2n) C. O(n2) D. O(nlog2n) 2.在对长度为n的顺序存储的有序表进行折半查找，对应的折半查找判定树的高度为（）。【＊，★】 A.n B. C. D. 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要 数据结构与算法》实验报告 一、需求分析 问题描述：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 基本要求： （l ）对以下 6 种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 （2 ）待排序表的表长不小于100000 ；其中的数据要用伪随机数程序产生；至少要用 5 组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为 3 次移动）。 （ 3 ）最后要对结果作简单分析，包括对各组数据得出结果波动大小的解释。数据测试：二．概要设计 1. 程序所需的抽象数据类型的定义： typedef int BOOL; typedef struct StudentData { } Data; typedef struct LinkList { Data Record[MAXSIZE]; int num; // 存放关键字 int Length; // 数组长度// 用数组存放所有的随机数 // 说明BOOL 是int 的别名 } LinkList int RandArray[MAXSIZE]; // 定义长度为MAXSIZE 的随机数组 void RandomNum() // 随机生成函数 void InitLinkList(LinkList* L) // 初始化链表 // 比较所有排序 2 . 各程序模块之间的层次（调用）关系： BOOL LT(int i, int j,int* CmpNum) // 比较 i 和 j 的大小 void Display(LinkList* L) // 显示输出函数 void ShellSort(LinkList* L, int dlta[], int t,int* CmpNum, int* ChgNum) void QuickSort (LinkList* L, // 快速排序 void HeapSort (LinkList* L, // 堆排序 void BubbleSort(LinkList* L, // 冒泡排序 void SelSort(LinkList* L, // 选择排序 int* CmpNum, int* ChgNum) int* CmpNum, int* ChgNum) int* CmpNum, int* ChgNum) * CmpNum, int* ChgNum) void Compare(LinkList* L,int* CmpNum, int* ChgNum) // 希尔排序 1.用二分（对半）查找表的元素的速度比用顺序法( ) A．必然快 B. 必然慢 C. 相等 D. 不能确定 2.具有12个关键字的有序表，折半查找的平均查找长度（） A. 3.1 B. 4 C. 2.5 D. 5 3．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。 A. 分块查找 B. 顺序查找 C. 折半查找 D. 基于属性4．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) 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) 5. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。 A. LL B. LR C. RL D. RR 7. 下面关于B和B+树的叙述中，不正确的是( ) A. B树和B+树都是平衡的多叉树。 B. B树和B+树都可用于文 件的索引结构。 C. B树和B+树都能有效地支持顺序检索。 D. B树和B+树都能有效地 支持随机检索。 8. m阶B-树是一棵( ) A. m叉排序树 B. m叉平衡排序树 C. m-1叉平衡排序树 D. m+1叉平衡排序树 9. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（）个记录。 A．1 B. 2 C. 3 D. 4 10.下面关于哈希(Hash，杂凑)查找的说法正确的是( ) A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B．除留余数法是所有哈希函数中最好的 C．不存在特别好与坏的哈希函数，要视情况而定 D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可 数据结构课程设计报告 题目：各种内排序性能的比较 学生姓名： 学号： 班级： 指导教师： 2012-6-10 实现部分 各个核心算法的代码： #include int a=0,b=0,k=1;//a表示元素比较的次数，b表示元素交换的次数,k 表示趟数 cout<<"插入排序的每一次的结果如下："< 第9章排序自测卷姓名班级 一、填空题 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．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为 《数据结构与算法》实验报告 一、需求分析 问题描述：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 基本要求： （l）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 （2）待排序表的表长不小于100000；其中的数据要用伪随机数程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。 （3）最后要对结果作简单分析，包括对各组数据得出结果波动大小的解释。数据测试：二．概要设计 1.程序所需的抽象数据类型的定义： typedef int BOOL; //说明BOOL是int的别名 typedef struct StudentData { int num; //存放关键字 } Data; typedef struct LinkList { int Length; //数组长度 Data Record[MAXSIZE]; //用数组存放所有的随机数 } LinkList int RandArray[MAXSIZE]; //定义长度为MAXSIZE的随机数组 void RandomNum() //随机生成函数 void InitLinkList(LinkList* L) //初始化链表 BOOL LT(int i, int j,int* CmpNum) //比较i和j 的大小 void Display(LinkList* L) //显示输出函数 void ShellSort(LinkList* L, int dlta[], int t,int* CmpNum, int* ChgNum) //希尔排序 void QuickSort (LinkList* L, int* CmpNum, int* ChgNum) //快速排序 void HeapSort (LinkList* L, int* CmpNum, int* ChgNum) //堆排序 void BubbleSort(LinkList* L, int* CmpNum, int* ChgNum) //冒泡排序 void SelSort(LinkList* L, int* CmpNum, int* ChgNum) //选择排序 void Compare(LinkList* L,int* CmpNum, int* ChgNum) //比较所有排序 数据结构作业系统_第 十章答案 10.23②试以L.r[k+1]作为监视哨改写教材10.2.1节 中给出的直接插入排序算法。其中，L.r[1..k]为待排 序记录且k 量，指示每一趟排序中进行交换的最后一个记录的位置，并 以它作为下一趟起泡排序循环终止的控制值。 实现下列函数： void BubbleSort(SqList &L); /* 元素比较和交换必须调用以下比较函数和交换函数：*/ /* Status LT(RedType a, RedType b); 比较："<" */ /* Status GT(RedType a, RedType b); 比较：">" */ /* void Swap(RedType &a, RedType &b); 交换 */ 顺序表的类型SqList定义如下： typedef struct { KeyType key; ... } RedType; typedef struct { RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元 int length; } SqList; 比较函数和交换函数: Status LT(RedType a, RedType b); // 比较函数："<" Status GT(RedType a, RedType b); // 比较函数：">" void Swap(RedType &a, RedType &b); // 交换函数 void BubbleSort(SqList &L) /* 元素比较和交换必须调用如下定义的比较函数和交换函数：*/ /* Status LT(RedType a, RedType b); 比较："<" */《数据结构》知识题汇编09第九章排序试题
数据结构课程设计(内部排序算法比较_C语言)
中南大学数据结构与算法第10章内部排序课后作业答案
数据结构实验八内部排序
数据结构第九章排序习题与答案
数据结构第十章习题课
数据结构课程设计(内部排序算法比较 C语言)
南邮数据结构上机实验四内排序算法的实现以及性能比较
数据结构课程设计(内部排序算法比较-C语言)
数据结构严蔚敏版第十章答案
数据结构内排序实验报告
数据结构内部排序比较分析
《数据结构》习题集：第9章查找(第1次更新2019-5)
数据结构(C语言版)实验报告-(内部排序算法比较)
数据结构第九章习题课
数据结构_各种内排序性能比较_课程设计报告纯代码版
数据结构 第10章排序自测题答案
数据结构(C语言版)实验报告 (内部排序算法比较)
数据结构作业系统_第十章答案教学文稿
- 数据结构第九章习题课
- 数据结构第9章排序(第25-27讲)
- 《数据结构》习题汇编09 第九章 排序 试题
- 《数据结构》习题汇编09第九章排序试题
- 数据结构第九章排序习题及答案
- 数据结构及算法第9章 学生基本信息排序
- 数据结构 第9章 查找和排序
- 第九章排序习题_数据结构
- 数据结构第九章排序习题及答案
- 《数据结构》习题汇编09 第九章 排序 试题
- 数据结构(c语言版)题集答案——第九章_查找
- (习题)数据结构第九章 排序
- 《数据结构》知识题汇编09第九章排序试题
- 最新数据结构第九章排序习题及答案
- 数据结构习题第9章
- 《数据结构》习题汇编09 第九章 排序 试题
- 数据结构第九章排序习题及答案
- 数据结构第九章内部排序
- 《数据结构》习题集：第9章查找(第1次更新2019-5)
- 《数据结构》习题汇编09第九章排序试题