第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)快速排序：（方括号表示无序区，层表示对应的递归树的层数）
初始态：[265 301 751 129 937 863 742 694 076 438]
第二层：[076 129] 265 [751 937 863 742 694 301 438] 第三层：076 [129] 265 [438 301 694 742] 751 [863 937] 第四层：076 129 265 [301] 438 [694 742] 751 863 [937] 第五层：076 129 265 301 438 694 [742] 751 863 937
第六层：076 129 265 301 438 694 742 751 863 937 (5)直接选择排序：(方括号为无序区)
初始态[265 301 751 129 937 863 742 694 076 438]
第一趟：076 [301 751 129 937 863 742 694 265 438]
第二趟：076 129 [751 301 937 863 742 694 265 438]
第三趟：076 129 265[ 301 937 863 742 694 751 438]
第四趟：076 129 265 301 [937 863 742 694 751 438]
第五趟：076 129 265 301 438 [863 742 694 751 937]
第六趟：076 129 265 301 438 694 [742 751 863 937]
第七趟：076 129 265 301 438 694 742 [751 863 937]
第八趟：076 129 265 301 438 694 742 751 [937 863]
第九趟：076 129 265 301 438 694 742 751 863 937
(6)堆排序：（通过画二叉树可以一步步得出排序结果）
初始态[265 301 751 129 937 863 742 694 076 438]
建立初始堆：[937 694 863 265 438 751 742 129 075 301]
第一次排序重建堆：[863 694 751 765 438 301 742 129 075] 937
第二次排序重建堆：[751 694 742 265 438 301 075 129] 863 937
第三次排序重建堆：[742 694 301 265 438 129 075] 751 863 937
第四次排序重建堆：[694 438 301 265 075 129] 742 751 863 937
第五次排序重建堆：[438 265 301 129 075] 694 742 751 863 937
第六次排序重建堆：[301 265 075 129] 438 694 742 751 863 937
第七次排序重建堆：[265 129 075] 301 438 694 742 751 863 937
第八次排序重建堆：[129 075]265 301 438 694 742 751 863 937
第九次排序重建堆：075 129 265 301 438 694 742 751 863 937
(7)归并排序（为了表示方便，采用自底向上的归并，方括号为有序区）
初始态：[265] [301] [751] [129] [937] [863] [742] [694] [076] [438]
第一趟：[265 301] [129 751] [863 937] [694 742] [076 438]
第二趟：[129 265 301 751] [694 742 863 937] [076 438]
第三趟：[129 265 301 694 742 751 863 937] [076 438]
第四趟：[076 129 265 301 438 694 742 751 863 937]
(8)基数排序（方括号内表示一个箱子共有10个箱子，箱号从0到9）
初始态：265 301 751 129 937 863 742 694 076 438
第一趟：[] [301 751] [742] [863] [694] [265] [076] [937] [438] [129]
第二趟：[301] [] [129] [937 438] [742] [751] [863 265] [076] [] [694]
第三趟：[075] [129] [265] [301] [438] [] [694] [742 751] [863] [937]
在上面的排序方法中，直接插入排序、冒泡排序、归并排序和基数排序是稳定的，其他排序算法均是不稳定的，现举实例如下：以带*号的表示区别。
希尔排序：[8,1,10,5,6,*8]
快速排序：[2,*2,1]
直接选择排序：[2,*2,1]
堆排序：[2,*2,1]
2.上题的排序方法中，哪些易于在链表(包括各种单、双、循环链表)上实现?
答：
上题的排序方法中，直接插入排序、冒泡排序、直接选择排序、基数排序和归并排序等方法易于在链表上实现。
3.当R[low..high]中的关键字均相同时，Partion返回值是什么?此时快速排序的的运行时间是多少?能否修改Partion,使得划分结果是平衡的(即划分后左右区间的长度大致相等)?
答：
此时Partion 返回值是low.此时快速排序的运行时间是
(high-low)(high-low-1)/2=O((high-low)^2),可以修改Partion ，将其中RecType pivot=R[i];句改为：RecType pivot=R[(j+i)/2]；也就是取中间的关键字为基准，这样就能使划分的结果是平衡的。
4.若文件初态是反序的，则直接插入，直接选择和冒泡排序哪一个更好?
答：
应选直接选择排序为更好。分析如下：
(1)在直接插入排序算法中，反序输入时是最坏情况，此时：
关键字的比较次数：Cmax=(n+2)(n-2)/2;
记录移动次数为：Mmax=(n-1)(n+4)/2;
Tmax=n^2-4n-3 (以上二者相加)
(2)在冒泡排序算法中，反序也是最坏情况，此时：
Cmax=n(n-1)/2; Mmax=3n(n-1)/2
Tmax=2n^2-2n
(3)在选择排序算法中，
Cmax=n(n-1)/2 Mmax=3(n-1)
Tmax=n^2/2-5n/2-3
由此可见，虽然它们的时间复杂度都是O(n^2),但是选择排序的常数因子为1/2，因此选择排序最省时间。
5.若文件初态是反序的，且要求输入稳定，则在直接插入、直接选择、冒泡和快速排序中就选选哪种方法为宜?
答：
这四种排序算法中，直接选择、快速排序均是不稳定的，因此先予以排除，剩下两种算法中，由于直接插入算法所费时间比冒泡法更少(见上题分析)，因此选择直接排序算法为宜。
6.有序数组是堆吗?
答：
有序数组是堆。因为有序数组中的关键字序列满足堆的性质。若数组为降序，则此堆为大根堆，反之为小根堆。
7.高度为h的堆中，最多有多少个元素?最少有多少个元素?在大根堆中，关键字最小的元素可能存放在堆的哪些地方?
答：
高度为h的堆实际上为一棵高度为h的完全二叉树，因此根据二叉树的性质可以算出，它最少应有2h-1个元素；最多可有2h-1个元素(注意一个有括号，一个没有)。在大根堆中，关键字最小的元素可能存放在堆的任一叶子结点上。
8.判别下列序列是否为堆(小根堆或大根堆)，若不是，则将其调整为堆：
(1) (100,86,73,35,39,42,57,66,21);
(2) (12,70,33,65,24,56,48,92,86,33);
(3) (103,97,56,38,66,23,42,12,30,52,06,20);
(4) (05,56,20,23,40,38,29,61,35,76,28,100).
答：
堆的性质是：任一非叶结点上的关键字均不大于(或不小于)其孩子结点上的关键字。据此我们可以通过画二叉树来进行判断和调整：
(1) 此序列是大根堆。
(2) 此序列不是堆，经调整后成为小根堆：
(12，24，33，65，33，56，48，92，86，70)
(3) 此序列是一大根堆。
(4) 此序列不是堆，经调整后成为小根堆：
(01，05，20，23，28，38，29，56，35，76，40，100)
9.将两个长度为n的有序表归并为一个长度为2n的有序表，最小需要比较n次，最多需要比较2n-1次，请说明这两种情况发生时，两个被归并的表有何特征?
答：
前一种情况下，这两个被归并的表中其中一个表的最大关键字不大于另一表中最小的关键字，也就是说，两个有序表是直接可以连接为有序的，因此，只需比较n次就可将一个表中元素转移完毕，另一个表全部照搬就行了。
另一种情况下，是两个被归并的有序表中关键字序列完全一样，这时就要按次序轮流取其元素归并，因此比较次数达到2n-1.
10.设关键字序列为(0.79，0.13，0.16，0.64，0.39，0.20，0.89，0.53，0.71，0.42)，给出桶排序的结果。
答：
桶排序的结果如图：
B[0..9]
┌──┐
0│ ∧│
├──┤
1│→ 0.13→0.16→ ∧
├──┤
2│→0.20→ ∧
├──┤
3│→0.39→ ∧
├──┤
4│→0.42→ ∧
├──┤
5│→0.53→ ∧
├──┤
6│→0.64→ ∧
├──┤
7│→0.71→0.79→ ∧
├──┤
8│→0.89→ ∧
├──┤
9│ ∧│
└──┘
结果为：0.13 0.16 0.20 0.39 0.42 0.53 0.64 0.71 0.79 0.89
11.若关键字是非负整数、快速排序、归并、堆和基数排序啊一个最快?若要求辅助空间为O(1)，则应选择谁? 若要求排序是稳定的，且关键字是实数，则应选择谁?
答：
若关键字是非负整数，则基数排序最快；若要求辅助空间为O(1)，则应选堆排序；若要求排序是稳定的，且关键字是实数，则应选归并排序，因为基数排序不适用于实数，虽然它也是稳定的。
12.对于8.7节的表8.2，解释下述问题：
(1)当待排序的关键字序列的初始态分别为正序和反序时，为什么直接选择排序的时间基本相同?若采用本书8.4.1节的算法，这两种情况下的排序时间是否基本相同?
(2)为什么数组的初态为正序时，冒泡和直接插入排序的执行时间最少?
(3)若采用8.3.2节的快速排序，则数组初态为正序和反序时，能得到与表8.2类似的结果吗?
答：
(1)由于在直接选择排序中，主要的操作是比较操作和移动操作。无论文件的初始状态如何，若文件有n 个记录，则都要进行n-1趟直接选择排序，第i趟直接选择排序中都要做n-i次比较才能选出最小关键字的记录。所以总的比较次数都为O(n2)。至于记录的移动次数，初始文件为正序时，移动次数为0，当文件初始时为反序，总的移动次数为3(n-1)。因此当待排序的关键字序列的初始态分别为正序和反序时，直接选择排序的时间基本相同，为O(n2)。若采用本书8.4.1节的算法，这两种情况下的排序时间基本相同。
(2)当冒泡排序是正序时，只需做一趟冒泡排序就可完成，共做n-1次比较，移动次数为0，所以执行时间最少。而直接插入排序时，若初始为正序，则做了n-1趟直接插入排序，但每趟排序只做了一次比较，共做n-1次比较。移动次数为0。所以当数组初态为正序，直接插入排序时间也最少。
(3)不能，其中辅助空间不同
13. 将哨兵放在R[n]中，被排序的记录放在R[0..n-1]中，重写直接插入排序算法。
解：
重写的算法如下：
void InsertSort(SeqList R)
{//对顺序表中记录R[0..n-1]按递增序进行插入排序
int i,j;
for(i=n-2;i>=0;i--) //在有序区中依次插入R[n-2]..R[0]
if(R[i].key>R[i+1].key) //若不是这样则R[i]原位不动
{
R[n]=R[i];j=i+1; //R[n]是哨兵
do{ //从左向右在有序区中查找插入位置
R[j-1]=R[j]; //将关键字小于R[i].key的记录向右移
j++;
}while(R[j].key R[j-1]=R[n]; //将R[i]插入到正确位置上 }//endif }//InsertSort. 14.以单链表作为存储结构实现直接插入排序算法。 解： #define int KeyType //定义KeyType 为int型 typedef struct node{ KeyType key; //关键字域 OtherInfoType info; //其它信息域， struct node * next; //链表中指针域 }RecNode; //记录结点类型 typedef RecNode * LinkList ; //单链表用LinkList表示 void InsertSort(LinkList head) {//链式存储结构的直接插入排序算法,head是带头结点的单链表RecNode *p,*q,*s; if ((head->next)&&(head->next->next))//当表中含有结点数大于1 { p=head->next->next;//p指向第二个节点 head->next=NULL; q=head;//指向插入位置的前驱节点 while(p)&&(q->next)&&(p->key q=q->next; if (p) {s=p;p=p->next;// 将要插入结点摘下 s->next=q->next;//插入合适位置：q结点后 q->next=s; } } } 15.设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前。请分析算法的时间复杂度。 解： 因为只需将负数关键字排在前面而无需进行精确排列顺序，因此本算法采用两端扫描的方法，就象快速排序采用的方法一样，左边扫描到正数时停止，开始扫描右边，遇到负数时与左边的当前记录交换，如此交替进行，一趟下来就可以完成排序。 void ReSort(SeqList R) {//重排数组，使负值关键字在前 int i=1,j=n; //数组存放在R[1..n]中 while (i { while(i i++; R[0]=R[i]; //R[0]为辅助空间 while(i j--; R[i++]=R[j];R[j--]=R[0];//交换当前两个元素并移动指针 }//endwhile }//ReSort 本算法在任何情况下的比较次数均为n(每个元素和0)相比，交换次数少于n/2，总的来说，时间复杂度为O(n). *16.写一个双向冒泡排序的算法，即在排序过程中交替改变扫描方向。解： 算法如下： void BubbleSort(SeqList R) {//R[1..n]是待排序文件，双向扫描冒泡排序 int i,j,k; Boolean exchange; //交换标记 i=n;j=1; exchange=TRUE; while (i>j)&&(exchange) {k=i-1;exchange=FALSE; while (k>=j)//由下往上扫描 {if (r[k]>r[k+1]) {r[0]=r[k];r[k]=r[k+1];r[k+1]=r[k];exchange=TRUE;//交换 }//endif k--; }//endwhile if (exchange) {exchange=FALSE; j++;k=j+1; while(k<=i)//由上往下扫描 {if (r[k] {r[0]=r[k];r[k]=r[k-1];r[k-1]=r[k];exchange=TRUE;//交换 }//endif k++; }endwhile i--; }//endif }endwhile }//endsort 17.下面是一个自上往下扫描的冒泡排序的伪代码算法，它采用lastExchange 来记录每趟扫描中进行交换的最后一个元素的位置，并以它作为下一趟排序循环终止的控制值。请仿照它写一个自下往上扫描的冒泡排序算法。 void BubbleSort(int A[],int n) //不妨设A[0..n-1]是整型向量 int lastExchange,j,i=n-1; while (i>0) lastExchange=0; for(j=0;j if(A[j+1] 交换A[j]和A[j+1]; lastExchange=j; } i=lastExchange;//将i置为最后交换的位置 }//endwhile }//BubbleSort 解：算法如下： void BubbleSort(int A[],int n) //不妨设A[0..n-1]是整型向量 int lastExchange,j,i=0; while (i lastExchange=n; for(j=n-1;j>i;j--)//从下往上扫描A[0..i] if(A[j-1] 交换A[j]和A[j-1]; lastExchange=j; } i=lastExchange;//将i置为最后交换的位置 }//endwhile }//BubbleSort 18.改写快速排序算法，要求采用三者取中的方式选择划分的基准记录；若当前被排序的区间长度小于等于3时，无须划分而是直接采用直接插入方式对其排序。 解： 改写后的算法如下： void QuickSort(SeqList R,int low ,int high) {//对R[low..high]快速排序 int pivotpos; if(high-low<=2)//若当前区内元素少于3个 {//则进行直接插入排序 InsertSort(R,low,high); } else { pivotpos=midPartion(R,low,high); QuickSort(R,low,pivotpos-1); QuickSort(R,pivotpos+1，high); } }//QuickSort int midPartion(SeqList R,int i, int j) {//三者取中规则定基准 if(R[(i+j)/2].key>R[i].key) { 交换R[(i+j)/2]和R[i];} if(R[i].key>R[j].key) { 交换R[i]和R[j];} if(R[i].key) { 交换R[i]和R[(i+j)/2];} //以上三个if语句就使区间的第一个记录的key值为三个key的中间值 return Partion(R,i,j);//这样我们就可以仍使用原来的划分算法了 } 19.对给定的j(1≤j≤n ),要求在无序的记录区R[1..n]中找到按关键字自小到大排在第j个位置上的记录(即在无序集合中找到第j个最小元)，试利用快速排序的划分思想编写算法实现上述的查找操作。 答： int QuickSort(SeqList R,int j,int low,int high) { //对R[low..high]快速排序 int pivotpos；//划分后的基准记录的位置 if(low pivotpos=Partition(R，low，high)；//对R[low..high]做划分 if (pivotpos==j) return r[j]; else if (pivotpos>j) return(R,j,low,pivotpos-1); else return quicksort(R,j,pivotpos+1,high); } } //QuickSort 20.以单链表为存储结构，写一个直接选择排序算法。 答： #define int KeyType //定义KeyType 为int型 typedef struct node{ KeyType key; //关键字域 OtherInfoType info; //其它信息域， struct node * next; //链表中指针域 }RecNode; //记录结点类型 typedef RecNode * LinkList ; //单链表用LinkList表示 void selectsort(linklist head) {RecNode *p,*q,*s; if(head->next)&&(head->next->next) {p=head->next;//p指向当前已排好序最大元素的前趋 while (p->next) {q=p->next;s=p; while(q) {if (q->key q=q->next; }//endwhile 交换s结点和p结点的数据； p=p->next; }//endwhile }//endif }//endsort 21.写一个heapInsert(R,key)算法，将关键字插入到堆R中去，并保证插入R后仍是堆。提示：应为堆R 增加一个长度属性描述(即改写本章定义的SeqList类型描述，使其含有长度域)；将key先插入R中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，然后从下往上调整，使插入的关键字满足性质。请分析算法的时间。 答： #define n 100//假设文件的最长可能长度 typedef int KeyType; //定义KeyType 为int型 typedef struct node{ KeyType key; //关键字域 OtherInfoType info; //其它信息域， }Rectype; //记录结点类型 typedef struct{ Rectype data[n] ; //存放记录的空间 int length;//文件长度 void heapInsert(seqlist *R,KeyType key) {//原有堆元素在R->data[1]~R->data[R->length], //将新的关键字key插入到R->data[R->length+1]位置后， //以R->data[0]为辅助空间，调整为堆(此处设为大根堆) int large;//large指向调整结点的左右孩子中关键字较大者 int low,high;//low和high分别指向待调整堆的第一个和最后一个记录 int i; R->length++；R->data[R->length].key=key;//插入新的记录 for(i=R->length/2;i>0;i--)//建堆 { low=i;high=R->length; R->data[0].key=R->data[low].key;//R->data[low]是当前调整的结点 for(large=2*low;large<=high;large*=2){ //若large>high，则表示R->data[low]是叶子，调整结束； //否则令large指向R->data[low]的左孩子 if(large large++;//若R->data[low]的右孩子存在 //且关键字大于左兄弟，则令large指向它if (R->data[0].key { R->data[low].key= R->data[large].key; low=large;//令low指向新的调整结点 } else break;//当前调整结点不小于其孩子结点的关键字，结束调整}//endfor R->data[low].key=R->data[0].key;//将被调整结点放入最终的位置上}//end of for }end of heapinsert 设文件长度为n,则该算法需进行n/2趟调整，总的时间复杂度与初建堆类似，最坏时间复杂度为 O(nlgn)，辅助空间为O(1). 22.写一个建堆算法：从空堆开始，依次读入元素调用上题中堆插入算法将其插入堆中。 答： void BuildHeap(seqlist *R) { KeyType key; R->length=0;//建一个空堆 scanf("%d",&key);//设MAXINT为不可能的关键字 while(key!=MAXINT) { heapInsert(R,key); scanf("%d",&key); } } 23.写一个堆删除算法：HeapDelete(R,i),将R[i]从堆中删去，并分析算法时间，提示：先将R[i]和堆中最后一个元素交换，并将堆长度减1，然后从位置i开始向下调整，使其满足堆性质。 答： void HeapDelete(seqlist *R,int i) {//原有堆元素在R->data[1]~R->data[R->length], //将R->data[i]删除，即将R->data[R->length]放入R->data[i]中后， //将R->length减1，再进行堆的调整， //以R->data[0]为辅助空间，调整为堆(此处设为大根堆) int large;//large指向调整结点的左右孩子中关键字较大者 int low,high;//low和high分别指向待调整堆的第一个和最后一个记录 int j; if (i>R->length) Error("have no such node"); R->data[i].key=R->data[R->length].key; R->length--；R->data[R->length].key=key;//插入新的记录 for(j=i/2;j>0;j--)//建堆 { low=j;high=R->length; R->data[0].key=R->data[low].key;//R->data[low]是当前调整的结点 for(large=2*low;large<=high;large*=2){ //若large>high，则表示R->data[low]是叶子，调整结束； //否则令large指向R->data[low]的左孩子 if(large large++;//若R->data[low]的右孩子存在 //且关键字大于左兄弟，则令large指向它 if (R->data[0].key { R->data[low].key= R->data[large].key; low=large;//令low指向新的调整结点 } else break;//当前调整结点不小于其孩子结点的关键字，结束调整 }//endfor R->data[low].key=R->data[0].key;//将被调整结点放入最终的位置上 }//end of for }end of HeapDelete 24.已知两个单链表中的元素递增有序，试写一算法将这两个有序表归并成一个递增有序的单链表。算法应利用原有的链表结点空间。 答： typedef struct node{ KeyType key; //关键字域 OtherInfoType info; //其它信息域， struct node * next; //链表中指针域 1．下列排序算法中，其中（ D ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 2．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( A )（按递增序）。 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 3.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ B ）。 A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序 4．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ D ）方法最快。 A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序 5．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。 A. 插入 B. 选择 C. 希尔 D. 二路归并 6. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（ A ）。 A. 选择 B. 冒泡 C. 插入 D. 堆 7. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（ C ）次比较。 A. 3 B. 10 C. 15 D. 25 8. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是 ( B ) A. l B. 4 C. 3 D. 2 9. 堆排序是（ E ）类排序 A. 插入 B. 交换 C. 归并 D. 基数 E. 选择 10．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端；交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法，而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。 （1）--（5）: A．选择排序 B．快速排序 C．插入排序 D．起泡排序 E．归并排序 F．shell排序 G．堆排序 H．基数排序 10.1C 5 2A 3D 4B 5G 1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的__ ____和记录的_____。比较,移动 2．分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是______算法。冒泡,快速 3. 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需__________趟，写出第一趟结束后，数组中数据的排列次序__________。3,(10,7,-9,0,47,23,1,8,98,36) 4．对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。 第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．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为 第十章：内部排序练习题 一、选择题 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、要排序的数据中含有多个相同值。 第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套） 一、一、填空题（20分，每空1分） 1．双极型三极管是控制器件，当其工作在放大区时发射结需要加偏置，集电结需要加偏置。场效应管是控制器件。 2．在有源滤波器中，运算放大器工作在区；在滞回比较器中，运算放大器工作在区。 3．在三极管多级放大电路中，已知A u1＝20，A u2＝－10，A u3＝1，则可知其接法分别为：A u1是放大器，A u2是放大器，A u3是放大器。 4．在双端输入、单端输出的差动放大电路中，发射极R e公共电阻对信号的放大作用无影响，对信号具有抑制作用。差动放大器的共模抑制比K CMR ＝。 5．设某一阶有源滤波电路的电压放大倍数为200 1 200 f j A + = & ，则此滤波器为滤波器，其通带放大倍数为，截止频率为。 6．如图所示的功率放大电路处于类工作状态；其静态损耗为；电路的最大输出功率为；每个晶体管的管耗为最大输出功率的 倍。 二、基本题：（每题5分，共25分） 1．如图所示电路中D为理想元件，已知u i = 5sinωt V ，试对应u i画出u o的波形图。 2．测得电路中NPN型硅管的各级电位如图所示。试分析管子的工作状态（截止、饱和、放大）。 3．已知BJT管子两个电极的电流如图所示。求另一电极的电流，说明管子的类型（NPN 或PNP）并在圆圈中画出管子。 4．如图所示电路中，反馈元件R7构成级间负反馈，其组态为； 其作用是使输入电阻、放大电路的通频带变。 三、如图所示电路中，β＝100， Ω = ' 100 b b r，试计算：(15分) 1．放大电路的静态工作点；（6分） 第10章排序 一、填空题 1. 大多数排序算法都有两个基本的操作：和。 2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7 个记录60插入到有序表时，为寻找插入位置至少需比较次。 3. 在插入和选择排序中，若初始数据基本正序，则应选用排序算法；若初始数据基 本反序，则应选用排序算法。 4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用；若初始记录基本 无序，则最好选用。 5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是。若对其进 行快速排序，在最坏的情况下所需要的时间是。 6. 对于n个记录的集合进行归并排序，所需要的平均时间是，所需要的附加空间 是。 7．对于n个记录的表进行2路归并排序，整个归并排序需进行趟（遍）。 8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排 列，则：冒泡排序一趟扫描的结果是；初始步长为4的希尔（shell）排序一趟的结果是；归并排序一趟扫描的结果是；快速排序一趟扫描的结果是；堆排序初始建堆的结果是。 9. 分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表进行排序，则最省 时间的是算法，最费时间的是算法。 10、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为。 二、单项选择题 1、下列四个序列中，（）是堆。 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 2．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（） Ａ. 希尔排序Ｂ. 冒泡排序Ｃ. 插入排序Ｄ. 选择排序 3．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为（） Ａ. 希尔排序Ｂ. 归并排序Ｃ. 插入排序Ｄ. 选择排序 4．对ｎ个不同的排序码进行冒泡排序，在下列（）情况下比较的次数最多。 模拟电子技术基础试卷及答案 一、填空（18分） 1．二极管最主要的特性是 单向导电性 。 3．差分放大电路中，若u I1=100μV ，u I 2 =80μV 则差模输入电压u Id = 20μV ；共模输入电压 u Ic =90 μV 。 4．在信号处理电路中，当有用信号频率低于10 Hz 时，可选用 低通 滤波器；有用信号频率高于10 kHz 时，可选用 高通 滤波器；希望抑制50 Hz 的交流电源干扰时，可选用 带阻 滤波器；有用信号频率为某一固定频率，可选用 带通 滤波器。 6．乙类功率放大电路中，功放晶体管静态电流I CQ 0 、静态时的电源功耗P DC = 0 。这类功放的能量转换效率在理想情况下，可达到 78.5% ，但这种功放有 交越 失真。 二、选择正确答案填空（20分） 1．在某放大电路中，测的三极管三个电极的静态电位分别为0 V ，-10 V ，-9.3 V ，则这只三极管是（ A ）。 A ．NPN 型硅管 B.NPN 型锗管 C.PNP 型硅管 D.PNP 型锗管 2．某场效应管的转移特性如图所示，该管为（ D ）。 A ．P 沟道增强型MOS 管 B 、P 沟道结型场效应管 C 、N 沟道增强型MOS 管 D 、N 沟道耗尽型MOS 管 3．通用型集成运放的输入级采用差动放大电路，这是因为它的（ C ）。 A ．输入电阻高 B.输出电阻低 C.共模抑制比大 D.电压放大倍数大 6.RC 桥式正弦波振荡电路由两部分电路组成,即RC 串并联选频网络和（ D ）。 A. 基本共射放大电路 B.基本共集放大电路 C.反相比例运算电路 D.同相比例运算电路 7.已知某电路输入电压和输出电压的波形如图所示,该电路可能是（ A ）。 A.积分运算电路 B.微分运算电路 C.过零比较器 D.滞回比较器 8．与甲类功率放大方式相比，乙类互补对称功放的主要优点是( C )。 a ．不用输出变压器 b ．不用输出端大电容 c ．效率高 d ．无交越失真 9．稳压二极管稳压时，其工作在( C )，发光二极管发光时，其工作在( A )。 a ．正向导通区 b ．反向截止区 c ．反向击穿区 三、放大电路如下图所示，已知：V CC 12V ，R S 10k Ω，R B1 120k Ω， R B2 39k Ω，R C 3.9k Ω ， R E 2.1k Ω， R L 3.9k Ω ， r bb’ Ω，电流放大系数β50，电路中电容容量足够 大，要求： 1．求静态值I BQ ，I CQ 和U CEQ (设U BEQ 0.6V )； 0 i D /mA -4 u GS /V 5 + u O _ u s R B R s +V CC V C + R C R i O t u I t u o 4题图 7题图 R L 第十章内部排序 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套） 一、一、填空题（20分，每空1分） 1．双极型三极管是 控制器件，当其工作在放大区时发射结需要加 偏置，集电结需要加 偏置。场效应管是 控制器件。 2． 在有源滤波器中，运算放大器工作在 区；在滞回比较器中，运算放大器工作在 区。 3． 在三极管多级放大电路中，已知A u1＝20，A u2＝－10，A u3＝1，则可知其接法分别为：A u1是 放大器，A u2是 放大器，A u3是 放大器。 4． 在双端输入、单端输出的差动放大电路中，发射极R e 公共电阻对 信号的放大作用无影响，对 信号具有抑制作用。差动放大器的共模抑制比K CMR ＝ 。 5． 设某一阶有源滤波电路的电压放大倍数为 2001200f j A += ，则此滤波器为 滤波器， 其通带放大倍数为 ，截止频率为 。 6． 如图所示的功率放大电路处于 类工作状态；其静态损耗为 ；电路的最大输出功率为 ；每个晶体管的管耗为最大输出功率的 倍。 二、基本题：（每题5分，共25分） 1．如图所示电路中D 为理想元件，已知u i = 5sin ωt V ，试对应u i 画出u o 的波形图。 2．测得电路中NPN型硅管的各级电位如图所示。试分析管子的工作状态（截止、饱和、放大）。 3．已知BJT管子两个电极的电流如图所示。求另一电极的电流，说明管子的类型（NPN 或PNP）并在圆圈中画出管子。 4．如图所示电路中，反馈元件R7构成级间负反馈，其组态为； 其作用是使输入电阻、放大电路的通频带变。 三、如图所示电路中，β＝100， Ω = ' 100 b b r，试计算：(15分) 1．放大电路的静态工作点；（6分） 2．画出放大电路的微变等效电路；（3分） 3．求电压放大倍数A u、输入电阻R i和输出电阻R o；（6分） 第10章排序（参考答案） 18. 对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列并不满足。 20. 本题为步长为3的一趟希尔排序。 24.枢轴是73。 49. 小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于n/2的结点上。 64. 因组与组之间已有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时间下界为O(klog2k),全部时间下界为O(nlog2k)。 部分答案解释如下： 5. 错误。例如冒泡排序是稳定排序，将4,3,2,1按冒泡排序排成升序序列，第一趟变成3,2,1,4，此时3就朝向最终位置的相反方向移动。 12. 错误。堆是n个元素的序列，可以看作是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉排序树，更不会是平衡二叉树。 22. 错误。待排序序列为正序时，简单插入排序比归并排序快。 三、填空题 1. 比较,移动 2.生成有序归并段（顺串）,归并 3.希尔排序、简单选择排序、快速排序、堆排序等 4. 冒泡,快速 5. (1)简单选择排序 (2)直接插入排序（最小的元素在最后时） 6. 免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。 7. n(n-1)/2 8.题中p指向无序区第一个记录，q指向最小值结点，一趟排序结束，p和q所指结点值交换，同时向后移p指针。(1)!=null (2)p->next (3)r!=null (4)r->data 第十章排序 一、名词解释 1.排序 2.内部排序 3.外部排序 4.堆 5.堆排序 二、填空 1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为 ________的。 2.按照排序过程涉及的存储设备的不同，排序可分为________排序和 ________排序。 3.按排序过程中依据的不同原则对内部排序方法进行分类，主要有： ________、________、________、 ________等四类。 4.在排序算法中，分析算法的时间复杂性时，通常以________和________为标准操作。评价排序的另一个主要标准是执行算法所需要的________。 5.常用的插入排序方法有________插入排序、________插入排序、________插入排序和________插入排序。 6.以下为直接插入排序的算法。请分析算法，并在________上填充适当的语句。 void straightsort(list r); {for(i=___________;i<=n;i++) {r[0]=r[i];j=i-1; while(r[0].key 第10章排序 一、基础知识题 10.1 基本概念：内排序，外排序，稳定排序，不稳定排序，顺串，败者树，最 佳归并树。 【解答】⑴内排序和外排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序适用于记录个数不多的文件，不需要访问外存，而外部排序适用于记录很多的大文件，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。 ⑵稳定排序和不稳定排序假设待排序记录中有关键字K i=K j（i≠j），且在排序前的序列中R i领先于R j。经过排序后，R i与R j的相对次序保持不变（即R i仍领先于R j），则称这种排序方法是稳定的，否则称之为不稳定的。 ⑶顺串外部排序通常经过两个独立的阶段完成。第一阶段，根据内存大小，每次把文件中一部分记录读入内存，用有效的内部排序方法（如快速排序、堆排序等）将其排成有序段，这有序段又称顺串或归并段。 ⑷败者树败者树为提高外部排序的效率而采用的，是由参加比赛的n个元素作叶子结点而得到的完全二叉树。每个非叶（双亲）结点中存放的是两个子结点中的败者数据,而让胜者去参加更高一级的比赛。另外,还需增加一个结点,即结点0,存放比赛的全局获胜者。 ⑸最佳归并树在外部排序的多路平衡归并的k叉树中，为了提高效率减少对外存的读写次数，按哈夫曼树构造的k叉树称最佳归并树。这棵树中只有度为0和度为k的结点。若用m表示归并段个数，用n k表示度为k的个数，若 (m-1)%(k-1)=0，则不需增加虚段，否则应附加k-(m-1)%(k-1)-1个虚段（即第一个k路归并使用(m-1)%(k-1)+1个归并段）。 10.2设待排序的关键字序列为(15， 21， 6， 30， 23， 6′， 20， 17)，试 分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次比较。 (1) 直接插入排序(2) 希尔排序(增量为5，2，1) (3) 起泡排序 (4) 快速排序(5) 直接选择排序 (6) 锦标赛排序 (7) 堆排序(8) 二路归并排序 (9) 基数排序 【解答】 (1) 直接插入排序 初始关键字序列： 15，21，6，30，23，6′，20，17 第一趟直接插入排序：【15，21】 第二趟直接插入排序：【6，15，21】 第三趟直接插入排序：【6，15，21，30】 第四趟直接插入排序：【6，15，21，23，30】 第五趟直接插入排序：【6，6′，15，21，23，30】 第六趟直接插入排序：【6，6′，15，20，21，23，30】 第10章内部排序 一、单项选择题 1．若要尽可能地完成对实数数组得排序，且要求排序是稳定的，则应选______。 A．快速排序 B．堆排序 C．归并排序 D．基数排序 2．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用______方法最快。 A．冒泡排序 B．快速排序 C．希尔排序 D．堆排序 E．简单选择排序 3．将两个各有N个元素的有序表归并成一个有序表，其最小的比较次数是______。 A．N B．2N-1 C．2N D．N-1 4．就平均性能而言，目前最好的内排序方法是______排序法。 A．冒泡排序 B．希尔排序 C．插入排序 D．快速排序 5．若需要在O(nlog2n)的时间内完成对数据的排序，且要求排序是稳定的，则可选择的排序方法是______。 A．快速排序 B．堆排序 C．归并排序 D．直接插入排序 6．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是______。 A．选择排序法 B．插入排序法 C．快速排序法 D．堆排序法 7．数据序列｛8，9，10，4，5，6，20，1，2｝只能是下列排序算法中的（）的两趟排序后的结果。 A．选择排序 B．冒泡排序 C．插入排序 D．堆排序 8．对一组数据｛84，47，25，15，21｝排序，第一趟的排序结果为15，47，25，84，21；第二趟排序的结果为15，21，25，84，47；第三趟排序的结果为15，21，25，47，84，则采用排序的方法是______。 A．选择排序 B．冒泡排序 C．快速排序 D．插入排序 9．下列排序算法中______排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A．选择排序 B．冒泡排序 C．归并排序 D．堆排序 10．在下面的排序方法中，辅助空间为O（n）的是______。 A．希尔排序 B．堆排序 C．选择排序 D．归并排序 11．直接插入排序在最好的情况下的时间复杂度为______。 A．O（log2n） B．O(n) C． O(nlog2n) D．O(n2) 12．若用冒泡排序方法对序列{10，14，26，29，41，52}从大到小排序，需进行______次比较。 A．3 B．10 C．15 Ｄ．25 13．对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经过一趟后序列变为{15，-1，4，8，20，9，7}，则该次采用的增量是 ______。 A．1 B．4 C．3 D．2 14．对下列关键字序列用快速排序法进行排序，速度最快的情形是 第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 ）方法最快。 2.分别改正下图所示各电路中的错误，使它们有可能放大正弦波信号。要求保留电路原 （a）静态时，发射结正偏，集电结反偏，-VCC改为+VCC (b) 没有RB发射结会烧坏，集电结不能反偏 （c）没有RB1当ui=0时发射结两端电压为零，VBB反过来。 （d）没有RB在交流通路中，VBB短路，交流信号加不进来。 3.放大电路及三极管输出特性如下图所示。 ①在输出特性曲线上画出直流负载线。如要求I CQ=2mA，确定此时的静态工作点，并确 定此时的R b的值； ②利用图解法分别求出R L=∞和R L=3kΩ时的最大不失真输出电压U om（有效值）； ③若R b调至150kΩ且i B的交流分量i b（t）=20sinωt(μA)，画出i C和u CE的波形图，这时出现什么失真？ 解：（1）直流负载线 12 ,.4,0====-=Ce C c ce C c CC ce U O I I U R I V U 作负载线得：I CQ =40μA Ω =≈+=k R U R I V b CE b B CC 30004 .012 （2）R L =∞直流负载线与交流负载线重合Uom=6/1.414=4.23V R L =3K ?,R L //R C =1.5 K ? 当 U CEQ +1.5*I CQ =9 ,Uom=1.5*I CQ/1.414=2.12V (3) 当RB=150K ?时，IBQ=80Ma 4.电路如图P2.7所示，晶体管的β=80 ，'100bb r =Ω。分别计算L R =∞和3L R k =Ω时的Q 点、u A 、i R 和o R 。 解：在空载和带负载情况下，电路的静态电流、be r 均相等，它们分别为： 1 习题1——直流电路 1、 解1： 结点a ：I 1+I 2=I 3 回路1：R 1I 1–R 2I 2+U S2–U S1=0 回路2：R 2I 2+ R 3I 3–U S2=0 图1 习题1的图 联立求解，得：I 1= –0.2A ，I 2= 1.6A ，I 3= 1.4A U s1起负载作用，其功率P 1= U s1 I 1= –2.4W U s2起电源作用，其功率P 2= U s2 I 2=24W 2、 解2：I 1 、I 2 、I 3 、I 4如图所示。 结点a ：I 1+I +I 2=0 结点b ：I 1+I =I 3+I 4 回路1：4I –8I 1=0 回路2：5I 2+9–4I 4–4I =0 回路3：2I 3=4I 4 图2 习题2的图 联立求解，得： I = 2/3A ，I 1= 1/3A ，I 2= –1A ，I 3= 2/3A ，I 4= 1/3A 3Ω 6 V 3Ω 1Ω 5Ω I 1 + - I 1a I 1b 3、 解3：①电压源单独作用时， I 1= –(I 1a + I 1b )= –(1+1) = –2A ②电流源单独作用时， I 2= –(I 2a + I 2b )= –(–1+3) = –2A 由叠加定理，I = I 1+ I 2= –4A 电压源单独作用 电流源单独作用 4、 图4 习题4的图 解4：①当开关在位置1时，电流源I S 单独作用时，毫安表读数I=K 1I S = 40mA ； ②当开关在位置2时，电流源I S 和电压源U S1同时作用，利用叠加定理有： I=K 1I S +K 2U S1 代入数据有：-60=40+ 10K 2 解得: K 2= -10 ③当开关在位置3时，电流源I S 和电压源U S2同时作用， U S1 I 1 S 2 3 U S2 R 5 + - - + U S2 I S R 4 R 3 R 2 R 1 A 3Ω 6 A 3Ω 1Ω 5Ω I 2 I 2a I 2b 第十章排序 一、单项选择题 1.有一组序列48,36,68,99,75,24,58,52进行快速排序，要求结果按从小到大排序，则进行一次划分之后结果为_____。 A. (24 28 36) 48 (52 68 75 99) B. (28 36 24) 48 (75 99 68 52) C. (36 68 99) 48 (75 24 28 52) D. (28 36 24) 48 (99 75 68 52) 2.已知两个有序表，若要将它们组合成一个新的有序表，最好的方法是_____。 A. 希尔排序 B. 二分插入排序 C. 合并排序 D. 冒泡排序 3.排序译意风稳定的和不稳定的之分，下列四个说法中，只有______是正确的。 A. 快速排序是稳定的排序方法 B. 堆排序是不稳定的排序方法 C. 希尔排序是稳定的排序方法 D. 冒泡排序是不稳定的排序方法 4. 下列排序方法中，____方法是不稳定的。 A. 冒泡排序 B. 希尔排序 C. 冒泡排序 D. 直接插入排序 5. 下列排序方法中，在待排序的数据已经有序时，花费时间反而最多的是______。 A.快速排序 B. 希尔排序 C. 冒泡排序 D. 堆排序 6. 快速排序方法在最好情况下的时间复杂度为______。 A. O(n) B. O(n2) C. O(nlog2n) D.(log2n) 7. 下列排序方法中，时间复杂度不受数据初始状态影响，恒为O(n2)的是_______。 A. 堆排序 B.冒泡排序 C. 直接选择排序 D.快速排序 8. 依次将待排序序列中的元素和有序子序列合并为一个新的有序子序列的排序方法是____。 A. 快速排序 B.插入排序 C. 冒泡排序 D. 堆排序 9. 在表R中排序前已按键值递增顺序排序，则_____方法的比较次数最少。 A. 直接插入排序 B. 快速排序 C. 归并排序 D. 选择排序 10. 已知表A中每个元素距其最终位置不远，采用______方法最节省时间。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 直接选择排序 11. 在下列排序方法中，字比较的次数与记录的初始排列次序无关的是______。 A. 希尔排序 B. 冒泡排序 C. 插入排序 D. 选择排序 12. 快速排序方法在_____情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 13. 一组记录的关键字经一趟二路归并排序后得到含有５个长度为２的有序表：[25,48],[16,35],[79,82], [23,40],[36,72]，在此基础上按二路归并排序方法再对该序列进行一趟归并后的结果为______。 A. 16,25,35,48,23,40,79,82,36,72 B. 16,25,35,48,79,82,23,36,40,72 C. 16,25,48,35,79,82,23,36,40,72 D. 16,25,35,48,79,23,36,40,72,82 14. 一组记录的关键码为(46,74,18,53,14,20,40,38,86,65)，利用堆排序的方法建立的初始堆为____。 A. (14,18,38,46,65,40,20,53,86,74) B. (14,38,18,46,65,20,40,53,86,74) C. (14,18,20,38,40,46,53,65,74,86)数据结构第10章 习题答案
第10章排序自测题答案
第十章：内部排序练习题
中南大学数据结构与算法第10章内部排序课后作业答案
中南大学模电试题(卷)与答案解析-成考类
第10章 排序 作业
模电模拟试卷及答案
数据结构严蔚敏版第十章答案
中南大学模电试卷及答案
第10章 排序答案
第十章 排序
第10章 排序
数据结构第10章 内部排序习题
第十章排序答案
中南大学模电第二章作业答案解析
中南大学电工学习题册习题答案 (1)
第10章 排序
相关主题
文本预览