loading,90
R3:6
类似叙述题略。
65. (1)4台磁带机：平衡归并只能用2路平衡归并，需归并?log2650?=10趟。多步归并进行3路归并，按3阶广义斐波那契序列。F11<650 4步 T1 1149+181+144 T2 1149+181 T3 1T4 149 1步 T1 181+144 T2 181 T3 2步 T1 144 T2 81 3步 T1 T2 944 T3 537 T3 5 T4 3149 T4 368 T4 324 5步 p 注：m表示p个长为m单位的归并段 149 1表示149个长为1个单位的归并段。 T1 1724 T2 920 T3 513 T4 T1 1711 T2 97 T3 T4 3113 类似叙述题略 C B A E G F H D 66. (1) (2) 3 4 6 7 8 9 24 13 15 52 类似叙述题略。 67.外排序用k-路归并(k>2)是因为k越小，归并趟数越多，读写外存次数越多，时间效率 越低，故，一般应大于最少的2路归并。 若将k-路归并的败者树思想单纯用于内排 序，因其由胜者树改进而来，且辅助空间大，完全可由堆排序取代，故将其用于内排序效率并不高。 68. R1:19,48,65,74,101 R2:3,17,20,21,21,33,53,99 69．希尔排序(增量为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 五.算法设计题 1. void BubbleSort2(int a[],int n) //相邻两趟向相反方向起泡的冒泡排序算法 { change=1;low=0;high=n-1; //冒泡的上下界 while(low { change=0; //设不发生交换 for(i=low;i if(a[i]>a[i+1]){a[i]<-->a[i+1];change=1;} //有交换，修改标志change high--; //修改上界 for(i=high;i>low;i--) //从下向上起泡 if(a[i] }//BubbleSort2 [算法讨论]题目中“向上移”理解为向序列的右端，而“向下移”按向序列的左端来处理。 2. typedef struct node { ElemType data; struct node *prior,*next; }node，*DLinkedList; void TwoWayBubbleSort(DLinkedList la) //对存储在带头结点的双向链表la中的元素进行双向起泡排序。 {int exchange=1; // 设标记 DLinkedList p,temp,tail; head=la //双向链表头，算法过程中是向下起泡的开始结点 tail=null; //双向链表尾，算法过程中是向上起泡的开始结点 while (exchange) {p=head->next; //p是工作指针，指向当前结点 exchange=0; //假定本趟无交换 while (p->next!=tail) // 向下（右）起泡，一趟有一最大元素沉底 if (p->data>p->next->data) //交换两结点指针，涉及6条链 {temp=p->next; exchange=1;//有交换 p->next=temp->next;temp->next->prior=p //先将结点从链表上摘下 temp->next=p; p->prior->next=temp; //将temp插到p结点前 temp->prior=p->prior; p->prior=temp; } else p=p->next; //无交换，指针后移 tail=p; //准备向上起泡 p=tail->prior; while (exchange && p->prior!=head) //向上（左）起泡，一趟有一最小 元素冒出 if (p->data {temp=p->prior; exchange=1; //有交换 p->prior=temp->prior;temp->prior->next=p； //先将temp结点从 链表上摘下 temp->prior=p; p->next->prior=temp; //将temp插到p结 点后（右） temp->next=p->next; p->next=temp; } else p=p->prior; //无交换，指针前移 head=p; //准备向下起泡 }// while (exchange) } //算法结束 3. PROCEDURE StraightInsertSort(VAR R:listtype;n:integer); VAR i,j:integer; BEGIN FOR i:=2 TO n DO {假定第一个记录有序} BEGIN R[0]:=R[i]; j:=i-1; {将待排序记录放进监视哨} WHILE R[0].key R[j+1]:=R[0] {将待排序记录放到合适位置} END {FOR} END； 4. TYPE pointer=↑node; node=RECORD key:integer; link:pointer; END； PROCEDURE LINSORT(L:pointer); VAR t,p,q,s:pointer; BEGIN p:=L↑.link↑.link; {链表至少一个结点，p初始指向链表中第二结点（若存 在）} L↑.link↑.link=NIL; {初始假定第一个记录有序} WHILE p<>NIL DO BEGIN q:=p↑.link; {q指向p的后继结点} s=L; WHILE (s↑.link<>NIL AND s↑.link↑.key p↑.link:=s↑.link; s↑.link=p;{插入结点} p=q; {恢复p指向当前结点} END {WHILE} END; {LINSORT} 5. typedef struct { int num; float score; }RecType; void SelectSort(RecType R[51]，int n) { for(i=1; i { //选择第i大的记录，并交换到位 k=i; //假定第i个元素的关键字最大 for(j=i+1;j<=n;j++) //找最大元素的下标 if(R[j].score>R[k].score) k=j; if(i!=k) R[i] <-->R[k]; //与第i个记录交换 }//for for(i=1; i<=n; i++) //输出成绩 { printf(\if(i==0) printf(\ }//SelectSort 6. typedef struct { int key; datatype info}RecType void CountSort(RecType a[],b[],int n) //计数排序算法，将a中记录排序放入b中 { for(i=0;i if(a[j].key }//Count_Sort 2 (3) 对于有n个记录的表，关键码比较n次。 (4) 简单选择排序算法比本算法好。简单选择排序比较次数是n(n-1)/2,且只用一个交 2 换记录的空间；而这种方法比较次数是n，且需要另一数组空间。 [算法讨论]因题目要求“针对表中的每个记录，扫描待排序的表一趟”，所以比较次数2 是n次。若限制“对任意两个记录之间应该只进行一次比较”，则可把以上算法中的比较语句改为： for(i=0;i for(j=i+1;j if(a[i].key 7. [题目分析]保存划分的第一个元素。以平均值作为枢轴，进行普通的快速排序，最后枢轴的位置存入已保存的第一个元素，若此关键字小于平均值，则它属于左半部，否则属于右半部。 int partition (RecType r[],int l,h) { int i=l,j=h,avg=0; for(;i<=h;i++) avg+=R[i].key; i=l; avg=avg/(h-l+1); while (i { while (i