数据结构复习题（附答案）

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->dataprior->data) //交换两结点指针，涉及6条链

{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) } //算法结束

49. 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

50. [题目分析]以Kn为枢轴的一趟快速排序。将上题算法改为以最后一个为枢轴先从前向

后再从后向前。

int Partition(RecType K[]，int l，int n)

{ //交换记录子序列K[l..n]中的记录，使枢轴记录到位，并返回其所在位置， //此时，在它之前（后）的记录均不大（小）于它 int i=l; j=n; K[0] = K[j]; x = K[j].key; while(i

{ while(i

while(i=x) j--; if (i

K[i]=K[0]; return i; }//Partition 51. [题目分析]把待查记录看作枢轴，先由后向前依次比较，若小于枢轴，则从前向后，直到查找成功返回其位置或失败返回0为止。

int index (RecType R[],int l,h,datatype key) { int i=l,j=h; while (i

{ while (i<=j && R[j].key>key) j--; if (R[j].key==key) return j; while (i<=j && R[i].key

printf(“Not find”) ; return 0; }//index

52.void BiInsertSort(RecType R[]，int n)

{//二路插入排序的算法

int d[n+1]; //辅助存储 d[1]=R[1];first=1;final=1; for(i=2;i<=n;i++)

{ if(R[i].key>=d[1].key) //插入后部 { low=1;high=final;

while (low<=high) //折半查找插入位置

{ m=(low+high)/2;

if(R[i].key< d[m].key) high=m-1; else low=m+1; }//while

for (j=final;j>=high+1;j--) d[j+1] = d[j];//移动元素 d[high+1]=R[i]; final++; //插入有序位置 }

else //插入前部

{ if(first==1){ first=n; d[n]=R[i];}

else{ low=first;high=n;

while (low<=high)

{ m=(low+high)/2;

if(R[i].key< d[m].key) high=m-1; else low=m+1; }//while

for (j=first;j<=high;j++) d[j-1] = d[j]; //移动元素 d[high]=R[i]; first--; }//if }//if }//for

R[1] =d[fisrt];

for(i=first%n+1,j=2;i!=fisrt;i=i%n+1,j++) R[j] =d[i]; //将序列复制回去 }//BiInsertSort