数据结构——C语言描述课后答案 联系客服

发布时间 : 星期四 文章数据结构——C语言描述课后答案更新完毕开始阅读926f896627d3240c8447ef1b

p->next=s->next;s->next=q;

t=q->next;q->next=p->next->next; p->next->next=t;

} //交换q和s->next两个结点 }//for

}//LinkedList_Select_Sort

9.9假设含n个记录的序列中,其所有关键字为值介于v和w 之间的整数,且其中很多关键字的值是相同的。则可按如下方法排序:另设数组number[v...w]且令number[i]为统计关键字取整数I 的记录数,之后按number 重排序列以达到有序,编写算法实现上述排序方法,并讨论此方法的优缺点。

void Enum_Sort(int a[ ],int n)//对关键字只能取v到w之间任意整数的序列进行排序 {

int number[w+1],pos[w+1];

for(i=0;i

pos[i]=pos[i-1]+num[i]; //pos数组可以把关键字的值映射为元素在排好的序列中的位置 for(i=0;i

分析:本算法参考了第五章三元组稀疏矩阵转置的算法思想,其中的pos数组和那里的cpot数组起的是相类似的作用.

9.10 已知两个有序序列(a1, a2 ,..., am)和(am+1 , am+2 ,..., an),并且其中一个序列的记录个数少于s,且s= floor ( sqrt (n) ). 试写一个算法,用O(n)时间和O(1)附加空间完成这两个有序序列的归并。

void SL_Merge(int a[ ],int l1,int l2)//把长度分别为l1,l2且l1^2<(l1+l2)的两个有序子序列归并为有序序列 {

start1=0;start2=l1; //分别表示序列1和序列2的剩余未归并部分的起始位置 for(i=0;i

for(j=start2;j

RSh(a,start1,j-1,k);//将a[start1]到a[j-1]之间的子序列循环右移k位 start1+=k+1;

start2=j; //修改两序列尚未归并部分的起始位置 }

}//SL_Merge

void RSh(int a[ ],int start,int end,int k)//将a[start]到a[end]之间的子序列循环右移k位,算法原理参见5.18

{

len=end-start+1; for(i=1;i<=k;i++)

if(len%i==0&&k%i==0) p=i; //求len和k的最大公约数p for(i=0;i

j=start+i;l=start+(i+k)%len;temp=a[j]; while(l!=start+i) {

a[j]=temp; temp=a[l]; a[l]=a[j];

j=l;l=start+(j-start+k)%len; //依次向右移 }

a[start+i]=temp; }//for }//RSh

9.11 偶交换排序如下所述:第一趟对所有奇数i,将a[i]和a[i+1]进行比较;第二趟对所有偶数i,将a[i]和a[i+1]进行比较,若a[i]>a[i+1],则将两者交换;第一趟对所有奇数i, 第二趟对所有偶数i,…,依次类推直至整个序列有序为止。 (1) 这种排序方法的结束条件是什么?

(2) 分析当初始序列为正序或逆序两种情况下,奇偶交换排序过程中所需进行的关键字比较的次数。

(3) 写出奇偶交换排序的算法。

void LinkedList_Select_Sort(LinkedList &L)//单链表上的简单选择排序算法 {

for(p=L;p->next->next;p=p->next) {

q=p->next;x=q->data;

for(r=q,s=q;r->next;r=r->next) //在q后面寻找元素值最小的结点 if(r->next->data

x=r->next->data; s=r; }

if(s!=q) //找到了值比q->data更小的最小结点s->next {

p->next=s->next;s->next=q;

t=q->next;q->next=p->next->next; p->next->next=t;

} //交换q和s->next两个结点 }//for

}//LinkedList_Select_Sort

9.12 设计一个用链表表示的直接选择排序算法。(与9.8重)

9.13 插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后的插入排序算法。 (与9.5重复)

9.14 一个线性表中的元素为正整数或负整数。设计一个算法,将正整数和负整数分开,使线性表的前一半为负整数,后一半为正整数。不要求对元素排序,但要尽量减少交换次数。 (与9.7类似)

9.15 为什么通常使用一维数组作为堆的存放形式?

9.16 已知(k1,k2,…,kn)是堆,写一个算法将(k1,k2,…,kn,kn+1)调整为堆。按此思想写一个从空堆开始一个一个添入元素的建堆算法。

void Build_Heap(Heap &H,int n)//从低下标到高下标逐个插入建堆的算法 {

for(i=2;i

{ //此时从H.r[1]到H.r[i-1]已经是大顶堆 j=i;

while(j!=1) //把H.r[i]插入 {

k=j/2;

if(H.r[j].key>H.r[k].key) H.r[j]<->H.r[k]; j=k; } }//for

}//Build_Heap

9.17 试比较直接插入排序、简单选择排序、快速排序、堆排序、归并排序、希尔排序和基数排序的时空性能、稳定性和适用情况。

9.18 在供选择的答案中填入正确答案: 1)、排序(分类)的方法有许多种:__A_③_法从未排序序列中依次取出元素,与排序序列(初始为空)中的元素作比较,将其放入已排序列的正确位置上;__B①__法从未排序序列中挑选元素,并将其依次放入已排序序(初始时为空)的一端;交换排序法是对序列中元素进行一系列的比较,当被比较的两元素逆序时进行交换。__C_④__和__D②__是基于这类方法的两种排序方法,而__D__是比__C__效率更高的方法,利用某种算法,根据元素的关键值计算出排序位置的方法是__E_⑦_。 供选择答案 ① 选择排序 ② 快速排序 ③ 插入排序 ④ 冒泡排序

⑤ 归并排序 ⑥ 二分排序 ⑦ 哈希排序 ⑧ 基数排序 2)、一组记录的关键字为(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 3)、下列排序算法中, C 算法可能会出现下面情况:初始数据有序时,花费时间反而最多。

A、堆排序 B、冒泡排序 C、快速排序 D、SHELL 排序

9.19 判断正误:

( )在一个大堆中,最小元素不一定在最后。

( X )对n个记录采用快速排序方法进行排序,最坏情况下所需时间是o(nlog2n)。 ( X )在执行某排序算法过程中,出现了排序码朝着与最终排序序列相反方向移动的现象,则称该算法是不稳定的。