数据结构课后习题解答第十章 内部排序

第十章内部排序

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]

d[j-1]=d[j];

d[(j-2)%MAXSIZE+1]=L.r[i].key;

first=(first-2)%MAXSIZE+1; //这种形式的表达式是为了兼顾first=1的情况 }

}//for

for(i=first,j=1;d[i];i=i%MAXSIZE+1,j++)//将序列复制回去

L.r[j].key=d[i];

}//BiInsert_Sort

10.25

void SLInsert_Sort(SLList &L)//静态链表的插入排序算法

{

L.r[0].key=0;L.r[0].next=1;

L.r[1].next=0; //建初始循环链表

for(i=2;i<=L.length;i++) //逐个插入

{

p=0;x=L.r[i].key;

while(L.r[L.r[p].next].key

p=L.r[p].next;

q=L.r[p].next;

L.r[p].next=i;

L.r[i].next=q;

}//for

p=L.r[0].next;

for(i=1;i

{

while(p

q=L.r[p].next;

if(p!=i)

{

L.r[p]<->L.r[i];

L.r[i].next=p;

}

p=q;

}//for

}//SLInsert_Sort

10.26

void Bubble_Sort1(int a[ ],int n)//对包含n个元素的数组a进行改进的冒泡排序{

change=n-1; //change指示上一趟冒泡中最后发生交换的元素

while(change)

{

for(c=0,i=0;i

if(a[i]>a[i+1])

a[i]<->a[i+1];

c=i+1; //c指示这一趟冒泡中发生交换的元素

}

change=c;

}//while

}//Bubble_Sort1

10.27

void Bubble_Sort2(int a[ ],int n)//相邻两趟是反方向起泡的冒泡排序算法

{

low=0;high=n-1; //冒泡的上下界

change=1;

while(low

{

change=0;

for(i=low;i

if(a[i]>a[i+1])

{

a[i]<->a[i+1];

change=1;

}

high--; //修改上界

for(i=high;i>low;i--) //从下向上起泡

if(a[i]

{

a[i]<->a[i-1];

change=1;

}

low++; //修改下界

}//while

}//Bubble_Sort2

10.28

void Bubble_Sort3(int a[ ],int n)//对上一题的算法进行化简,循环体中只包含一次冒泡{

int b[ 3 ]; //b[0]为冒泡的下界,b[ 2 ]为上界,b[1]无用

d=1;b[0]=0;b[ 2 ]=n-1; //d为冒泡方向的标识,1为向上,-1为向下

change=1;

while(b[0]

change=0;

for(i=b[1-d];i!=b[1+d];i+=d) //统一的冒泡算法

if((a[i]-a[i+d])*d>0) //注意这个交换条件

{

a[i]<->a[i+d];

change=1;

}

b[1+d]-=d; //修改边界

d*=-1; //换个方向

}//while

}//Bubble_Sort3

10.29

void OE_Sort(int a[ ],int n)//奇偶交换排序的算法{

change=1;

while(change)

{

change=0;

for(i=1;i

if(a[i]>a[i+1])

{

a[i]<->a[i+1];

change=1;

}

for(i=0;i

if(a[i]>a[i+1])

{

a[i]<->a[i+1];

change=1;

}

}//while

}//OE_Sort

分析:本算法的结束条件是连续两趟比较无交换发生10.30

typedef struct {

int low;

int high;

} boundary; //子序列的上下界类型

void QSort_NotRecurve(int SQList &L)//快速排序的非递归算法

{

low=1;high=L.length;

InitStack(S); //S的元素为boundary类型

while(low

{

if(high-low>2) //如果当前子序列长度大于3且尚未排好序

{

pivot=Partition(L,low,high); //进行一趟划分

if(high-pivot>pivot-low)

{

Push(S,{pivot+1,high}); //把长的子序列边界入栈

high=pivot-1; //短的子序列留待下次排序

}

else

{

Push(S,{low,pivot-1});

low=pivot+1;

}

}//if

else if(low

Easy_Sort(L,low,high); //直接进行比较排序

low=high; //当前子序列标志为已排好序

}

else //如果当前子序列已排好序但栈中还有未排序的子序列

{

Pop(S,a); //从栈中取出一个子序列

low=a.low;

high=a.high;

}

}//while

}//QSort_NotRecurve

int Partition(SQList &L,int low,int high)//一趟划分的算法,与书上相同

{

L.r[0]=L.r[low];

pivotkey=L.r[low].key;

while(low

{

while(low=pivotkey)

high--;

L.r[low]=L.r[high];

while(low

low++;

L.r[high]=L.r[low];

}//while

L.r[low]=L.r[0];

return low;

}//Partition

void Easy_Sort(SQList &L,int low,int high)//对长度小于3的子序列进行比较排序{

if(high-low==1) //子序列只含两个元素

if(L.r[low].key>L.r[high].key) L.r[low]<->L.r[high];

else //子序列含有三个元素

{

if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1];

if(L.r[low+1].key>L.r[high].key) L.r[low+1]<->L.r[high];

if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1];

}

}//Easy_Sort

10.31

void Divide(int a[ ],int n)//把数组a中所有值为负的记录调到非负的记录之前{

low=0;high=n-1;

while(low

{

while(low=0) high--; //以0作为虚拟的枢轴记录

a[low]<->a[high];

while(low

a[low]<->a[high];

}

}//Divide

10.32

typedef enum {RED,WHITE,BLUE} color; //三种颜色

void Flag_Arrange(color a[ ],int n)//把由三种颜色组成的序列重排为按照红,白,蓝的顺序排列

{

i=0;j=0;k=n-1;

while(j<=k)

switch(a[j])

{

case RED:

a[i]<->a[j];

i++;

j++;

break;

case WHITE:

j++;

break;

case BLUE:

a[j]<->a[k];

k--; //这里没有j++;语句是为了防止交换后a[j]仍为蓝色的情况

}

}//Flag_Arrange

分析:这个算法中设立了三个指针.其中,j表示当前元素;i以前的元素全部为红色;k以后的元素全部为蓝色.这样,就可以根据j的颜色,把其交换到序列的前部或者后部.

10.33

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

10.34

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

10.35

void TriHeap_Sort(Heap &H)//利用三叉树形式的堆进行排序的算法

{

for(i=H.length/3;i>0;i--)

Heap_Adjust(H,i,H.length);

for(i=H.length;i>1;i--)

{

H.r[1]<->H.r[i];

Heap_Adjust(H,1,i-1);

}

}//TriHeap_Sort

void Heap_Adjust(Heap &H,int s,int m)//顺序表H中,H.r[s+1]到H.r[m]已经是堆,把H.r[s]插入并调整成堆

{

rc=H.r[s];

for(j=3*s-1;j<=m;j=3*j-1)

{

if(j

if(j

H.r[s]=H.r[j];

s=j;

}

H.r[s]=rc;

}//Heap_Adjust

分析:本算法与课本上的堆排序算法相比,只有两处改动:1.建初始堆时,i的上限从

H.length/3开始(为什么?) 2.调整堆的时候,要从结点的三个孩子结点中选择最大的那一个,最左边的孩子的序号的计算公式为j=3*s-1(为什么?)

10.36

void Merge_Sort(int a[ ],int n)//归并排序的非递归算法

{

for(l=1;l

for(i=0;(2*i-1)*l

{

start1=2*l*i; //求出待归并的两段的上下界

end1=start1+l-1;

start2=end1+1;

end2=(start2+l-1)>(n-1)?(n-1):(start2+l-1);//注意end2可能超出边界

Merge(a,start1,end1,start2,end2); //归并

}

}//Merge_Sort

void Merge(int a[ ],int s1,int e1,int s2,int e2)//将有序子序列a[s1]到a[e1]和a[s2]到a[e2]归并为有序序列a[s1]到a[e2]

{

int b[MAXSIZE]; //设立辅助存储数组b

for(i=s1,j=s2,k=s1;i<=e1&&j<=e2;k++)

{

if(a[i]

else b[k]=a[j++];

}

while(i<=e1) b[k++]=a[i++];

while(j<=e2) b[k++]=a[j++]; //归并到b中

for(i=s1;i<=e2;i++) //复制回去

a[i]=b[i];

}//Merge

10.37

void LinkedList_Merge_Sort1(LinkedList &L)//链表结构上的归并排序非递归算法

{

for(l=1;l

for(p=L->next,e2=p;p->next;p=e2)

{

for(i=1,q=p;i<=l&&q->next;i++,q=q->next);

e1=q;

for(i=1;i<=l&&q->next;i++,q=q->next);

e2=q; //求出两个待归并子序列的尾指针

if(e1!=e2) LinkedList_Merge(L,p,e1,e2); //归并

}

}//LinkedList_Merge_Sort1

void LinkedList_Merge(LinkedList &L,LNode *p,LNode *e1,LNode *e2)//对链表上的子序列进行归并,第一个子序列是从p->next到e1,第二个是从e1->next到e2

{

q=p->next;r=e1->next; //q和r为两个子序列的起始位置

while(q!=e1->next&&r!=e2->next)

{

if(q->datadata) //选择关键字较小的那个结点接在p的后面

{

p->next=q;p=q;

q=q->next;

}

else

{

p->next=r;p=r;

r=r->next;

}

}//while

while(q!=e1->next) //接上剩余部分

{

p->next=q;p=q;

q=q->next;

}

while(r!=e2->next)

{

p->next=r;p=r;

r=r->next;

}

}//LinkedList_Merge

10.38

void LinkedList_Merge_Sort2(LinkedList &L)//初始归并段为最大有序子序列的归并排序,采用链表存储结构

{

LNode *end[MAXSIZE]; //设立一个数组来存储各有序子序列的尾指针

for(p=L->next->next,i=0;p;p=p->next) //求各有序子序列的尾指针

if(!p->next||p->data>p->next->data) end[i++]=p;

while(end[0]->next) //当不止一个子序列时进行两两归并

{

j=0;k=0; //j:当前子序列尾指针存储位置;k:归并后的子序列尾指针存储位置

for(p=L->next,e2=p;p->next;p=e2) //两两归并所有子序列

{

e1=end[j];e2=end[j+1]; //确定两个子序列

if(e1->next) LinkedList_Merge(L,p,e1,e2); //归并

end[k++]=e2; //用新序列的尾指针取代原来的尾指针

j+=2; //转到后面两个子序列

}

}//while

}//LinkedList_Merge_Sort2

void LinkedList_Merge(LinkedList &L,LNode *p,LNode *e1,LNode *e2)//对链表上的子序列进行归并,第一个子序列是从p->next到e1,第二个是从e1->next到e2

{

q=p->next;r=e1->next;

while(q!=e1->next&&r!=e2->next)

{

if(q->datadata)

{

p->next=q;p=q;

q=q->next;

}

else

{

p->next=r;p=r;

r=r->next;

}

}//while

while(q!=e1->next)

{

p->next=q;p=q;

q=q->next;

}

while(r!=e2->next)

{

p->next=r;p=r;

r=r->next;

}

}//LinkedList_Merge,与上一题完全相同

10.39

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

k=j-start2; //k为要向右循环移动的位数

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

10.40

书后给出的解题思路在表述上存在问题,无法理解.比如说,"把第一个序列划分为两个子序列,使其中的第一个子序列含有s1个记录,0<=s1

10.41

void Hash_Sort(int a[ ])//对1000个关键字为四位整数的记录进行排序

{

int b[10000];

for(i=0;i<1000;i++) //直接按关键字散列

{

for(j=a[i];b[j];j=(j+1)%10000);

b[j]=a[i];

}

for(i=0,j=0;i<1000;j++) //将散列收回a中

if(b[j])

{

for(x=b[j],k=j;b[k];k=(k+1)%10000)

if(b[k]==x)

{

a[i++]=x;

b[k]=0;

}

}//if

}//Hash_Sort

10.42

typedef struct {

int gt; //大于该记录的个数

int lt; //小于该记录的个数

} place; //整个序列中比某个关键字大或小的记录个数

int Get_Mid(int a[ ],int n)//求一个序列的中值记录的位置

{

place b[MAXSIZE];

for(i=0;i

for(j=0;j

{

if(a[j]>a[i]) b[i].gt++;

else if(a[j]

}

mid=0;

min_dif=abs(b[0].gt-b[0].lt);

for(i=0;i

if(abs(b[i].gt-b[i].lt)

return mid;

}//Get_Mid

10.43

void Count_Sort(int a[ ],int n)//计数排序算法

{

int c[MAXSIZE];

for(i=0;i

{

for(j=0,count=0;j

if(a[j]

c[i]=count;

}

for(i=0;i

{

min=0;

for(j=0;j

if(c[j]

a[i]<->a[min]; //与第i个记录交换

c[min]=INFINITY; //修改该记录的c值为无穷大以便下一次选取

}

}//Count_Sort

10.44

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

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

for(i=0;i

for(pos[0]=0,i=1;i

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

c[pos[a[i]]++]=a[i];

for(i=0;i

a[i]=c[i];

}//Enum_Sort

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

10.45

typedef enum {0,1,2,3,4,5,6,7,8,9} digit; //个位数类型

typedef digit[3] num; //3位自然数类型,假设低位存储在低下标,高位存储在高下标

void Enum_Radix_Sort(num a[ ],int n)//利用计数实现基数排序,其中关键字为3位自然数,共有n个自然数

{

int number ,pos ;

num c[MAXSIZE];

for(j=0;j<3;j++) //依次对个位,十位和百位排序

{

for(i=0;i

for(pos[0]=0,i=1;i

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

for(i=0;i

c[pos[a[i][j]]++]=a[i];

for(i=0;i

a[i]=c[i];

}//for

}//Enum_Radix_Sort

分析:计数排序是一种稳定的排序方法.正因为如此,它才能够被用来实现基数排序. 10.46

typedef struct {

int key;

int pos;

} Shadow; //影子序列的记录类型

void Shadow_Sort(Rectype b[ ],Rectype &a[ ],int n)//对元素很大的记录序列b进行排序,结果放入a中,不移动元素

{

Shadow d[MAXSIZE];

{

d[i].key=b[i].key;

d[i].pos=i;

}

for(i=n-1,change=1;i>1&&change;i--) //对影子序列执行冒泡排序 {

change=0;

for(j=0;j

if(d[j].key>d[j+1].key)

{

d[j]<->d[j+1];

change=1;

}

}//for

for(i=0;i

}//Shadow_Sort

数据结构课后习题答案

第1章绪论 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。 3．简述逻辑结构的四种基本关系并画出它们的关系图。

数据结构第十章习题课

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个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确

中南大学数据结构与算法第10章内部排序课后作业答案

第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)快速排序：（方括号表示无序区，层表示对应的递归树的层数）

数据结构第10章 习题答案

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进行划分，写出其快速排序第一遍的排序过程。

严蔚敏版数据结构课后习题答案-完整版

第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据

类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={} 基本操作： InitComplex(&C,re,im) 操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C)

数据结构第八章习题及答案

习题八查找 一、单项选择题 1．顺序查找法适合于存储结构为（）的线性表。 A．散列存储 B. 顺序存储或链式存储 C. 压缩存储 D. 索引存储 2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 3．适用于折半查找的表的存储方式及元素排列要求为( ) A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 4．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( ) A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减5．当采用分块查找时，数据的组织方式为 ( ) A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 6．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（）。 A．正确 B. 错误 7. 二叉查找树的查找效率与二叉树的(（1） )有关, 在 (（2） )时其查找效率最低。 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 8．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。 A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性 9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。 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) 10．下图所示的4棵二叉树,( )是平衡二叉树。 （A）（B）（C）（D） 11．散列表的平均查找长度（）。 A．与处理冲突方法有关而与表的长度无关 B．与处理冲突方法无关而与表的长度有关 C．与处理冲突方法有关且与表的长度有关 D．与处理冲突方法无关且与表的长度无关 12. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（）个

数据结构课后习题答案

数据结构习题集答案 第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据

类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解：ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={} 基本操作： InitComplex(&C,re,im) 操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C) 操作结果：销毁复数C Get(C,k,&e) 操作结果：用e 返回复数C 的第k 元的值

数据结构第九、十章 作业答案

第九章 查找 一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。 2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索 表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。 3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。 解：显然，平均查找长度＝O （log 2n ）<5次（25）。但具体是多少次，则不应当按照公式 )1(log 12++=n n n ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。因为这是在假设n ＝2m -1 的情况下推导出来的公式。应当用穷举法罗列： 全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！ 4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它 将依次与表中元素 28，6，12，20 比较大小。 5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。 6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。 7. 有一个表长为m 的散列表，初始状态为空，现将n （n

目前最完整的数据结构1800题包括完整答案 第十章 排序

第10章排序 一、选择题 1．某内排序方法的稳定性是指( )。【南京理工大学 1997 一、10（2分）】A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对 2．下面给出的四种排序法中( )排序法是不稳定性排序法。【北京航空航天大学 1999 一、 10 （2分）】 A. 插入 B. 冒泡 C. 二路归并 D. 堆积 3．下列排序算法中，其中（）是稳定的。【福州大学 1998 一、3 (2分)】 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 4．稳定的排序方法是（）【北方交通大学 2000 二、3（2分）】 A．直接插入排序和快速排序 B．折半插入排序和起泡排序 C．简单选择排序和四路归并排序 D．树形选择排序和shell排序 5．下列排序方法中，哪一个是稳定的排序方法？（）【北方交通大学 2001 一、8（2分）】 A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序 B．归并排序 C．冒泡排序）。 【北京邮电大学 2001 一、5（2分）】 7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（）就是不稳定的排序方法。【清华大学 1998 一、3 (2分）】 A．起泡排序 B．归并排序 C．Shell排序 D．直接插入排序 E．简单选择排序 8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。 A．直接插入 B．直接选择 C．堆 D．快速 E．基数【中科院计算所 2000 一、5（2分）】 9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序【中国科技大学 1998 二、4（2分）】【中科院计算所 1998 二、4（2分）】 10．下面的排序算法中，不稳定的是（）【北京工业大学 1999 一、2 (2分)】 A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E.基数排序 F.堆排序。 11．下列内部排序算法中：【北京工业大学 2000 一、1 (10分每问2分)】A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序F. 堆排序 （1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<

数据结构习题课(2012)

复习重点 1.数据结构的概念，逻辑结构、物理结构的概念及各自包含的内容 2.算法的特性、设计要求，如何度量算法的时间效率。 3.线性表的顺序/链式存储结构的特点，插入、删除算法。 4.栈和队列的逻辑特性，顺序栈的入栈/出栈、循环队列的入队/出队算法。 5.以三元组顺序表存放的稀疏矩阵的转置算法。 6.二叉树的性质及其四种遍历算法。 7.森林与二叉树的相互转换。 8.WPL、前缀编码的概念，哈夫曼树的构造算法。 9.图的相关概念，邻接矩阵及邻接表的存储结构。 10.图的深度优先/广度优先遍历算法。 11.最小生成树的两种算法。 12.拓扑排序的意义和算法。 13.最短路径算法。 14.顺序表、有序表的查找算法。 15.二叉排序树的性质、插入/删除算法、平衡二叉树的性质、插入算法。 16.哈希表的相关概念，常用的冲突处理方法。 17.直接插入排序、希尔排序、快速排序、堆排序、归并排序的算法。 注意： 1.上述每个知识点可能会以任何题型出现，复习的时候别把它们当做“简答题” 来复习。 2.红色（下划线）标识的知识点或算法，只要求对给出的初始数据，能画出结 果则可。其他的算法则可能会出现在“算法题”中。 自测题 第1章绪论 一、判断 1.顺序存储方式只能用于存储线性结构。（错） 2.顺序查找法适用于存储结构为顺序或链式存储的线性表。（对） 二、选择 1.计算机算法必须具备输入、输出、（ B ）等5个特性。

A.可行性、可移植性和可扩展性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、安全性和稳定性 2.算法在发生非法操作时可以作出处理的特性称为（C ）。 A.正确性 B.易读性 C.健壮性 D.可靠性 3.数据结构是一门研究非数值计算的程序设计问题中计算机的（A ）以及它们之间 的（ B ）和运算的学科。 A.操作对象 B.计算方法 C.逻辑存储 D.数据映像 A.结构 B.关系 C.运算 D.算法 4.在数据结构中，逻辑上数据结构可分为：（B ） A.动态结构和静态结构 B.线性结构和非线性结构 C.紧凑结构和非紧凑结构 D.内部结构和外部结构 5.数据结构主要研究数据的（D ） A.逻辑结构 B.存储结构 C.逻辑结构和存储结构 D.逻辑结构和存储结构及其运算的实现 6.为了描述n个人之间的同学关系，可用（C ）结构表示 A.线性表 B.树 C.图 D.队列 7.下面的程序段违反了算法的（A ）原则 void sam() { int n=2; while (!odd(n)) n+=2; printf(n); } A.有穷性 B.确定性 C.可行性 D.健壮性 三、问答 1.什么是逻辑结构和物理结构？各自包含哪几种？ 2.线性结构和树型结构的特点分别是什么？ 3.简述顺序存储结构与链式存储结构在表示数据元素之间关系上的只要区别。 4.简述算法的5个特性。 第2章线性表 一、选择 1.线性表是具有n个（C ）的有限序列 A.表元素 B.字符 C.数据元素 D.数据项 E.信息项 2.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ A ） A.n B.2n-1 C.2n D.n-1 3.下述哪一条是顺序存储结构的优点？（ A ） A．物理上相邻的元素在逻辑上也相邻B．插入运算方便 C．删除运算方便D．可方便地用于各种逻辑结构的存储表示

数据结构Ch10习题答案

第十章内部排序 一、择题 1．用直接插入排序法对下面四个表进行（由小到大）排序，比较次数最少的是（B）。A．（94，32，40，90，80，46，21，69） 插32，比2次 插40，比2次 插90，比2次 插80，比3次 插46，比4次 插21，比7次 插69，比4次 B．（21，32，46，40，80，69，90，94） 插32，比1次 插46，比1次 插40，比2次 插80，比1次 插69，比2次 插90，比1次 插94，比1次 C．（32，40，21，46，69，94，90，80） 插40，比1次 插21，比3次 插46，比1次 插69，比1次 插94，比1次 插90，比2次 插80，比3次 D．（90，69，80，46，21，32，94，40） 插69，比2次 插80，比2次 插46，比4次 插21，比5次 插32，比5次 插94，比1次 插40，比6次 2．下列排序方法中，哪一个是稳定的排序方法（BD）。 A．希尔排序 B．直接选择排序 C．堆排序 D．冒泡排序 下列3题基于如下代码： for(i=2;i<=n;i++) { x=A[i]; j=i-1; while(j>0&&A[j]>x) { A[j+1]=A[j]; j--; } A[j+1]=x

} 3．这一段代码所描述的排序方法称作（A）。 A．插入排序 B．冒泡排序 C．选择排序 D．快速排序 4．这一段代码所描述的排序方法的平均执行时间为（D） A．O(log2n) B．O(n) C． O(nlog2n) D．O(n2) 5．假设这段代码开始执行时，数组A中的元素已经按值的递增次序排好了序，则这段代码的执行时间为（B）。 A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2) 6．在快速排序过程中，每次被划分的表（或了表）分成左、右两个子表，考虑这两个子表，下列结论一定正确是（B）。A．左、右两个子表都已各自排好序 B．左边子表中的元素都不大于右边子表中的元素 C．左边子表的长度小于右边子表的长度 D．左、右两个子表中元素的平均值相等 7．对n个记录进行堆排序，最坏情况下的执行时间为（C）。 A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2) 8、设待排序关键码序列为（25、18、9、33、67、82、53、95、12、70），要按关键码值递增的顺序排序，采取以第一个关键码为分界元素的快速排序法，第一趟排序完成后关键码表33被放到了第几个位置（D）。 A．3 B．5 C．7 D．9 9．若对一个已经排好了序的序列进行排序，在下列四方法中，哪种方法比较好（C）。 A．冒泡排序法 B．直接选择排序法 C．直接插入排序法 D．堆排序法 10．快速排序的时间复杂度是（A） A．O(nlog2n) B．O(n2) C． O(n3) D．O(log2n) 11．以下关键字序列用快速排序法进行排序，速度最慢的是（C） A．{23，27，7，19，11，25，32} B．{23，11，19，32，27，35，7}

最全数据结构课后习题答案(耿国华版[12bb]

第1章绪论工程大数电习题答案册工程大数电习题答案 册 2.(1)×(2)×(3)√ 3.（1）A（2）C（3）C 5.计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 6.编写算法，求一元多项式p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法 （1）通过参数表中的参数显式传递 （2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数 PolyValue() { int i,n; float x,a[],p; printf(“\nn=”); scanf(“%f”,&n); printf(“\nx=”); scanf(“%f”,&x); for(i=0;i

数据结构第10章 内部排序习题

第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．对下列关键字序列用快速排序法进行排序，速度最快的情形是

数据结构课后习题答案清华大学出版社殷人昆

1-1什么是数据? 它与信息是什么关系? 【解答】 什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。 什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。 1-2什么是数据结构? 有关数据结构的讨论涉及哪三个方面? 【解答】 数据结构是指数据以及相互之间的关系。记为：数据结构= { D, R }。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。 有关数据结构的讨论一般涉及以下三方面的内容： ①数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构； ②数据成员极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构； ③施加于该数据结构上的操作。 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。 1-3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、 队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？ 【解答】 线性结构的特点是：在结构中所有数据成员都处于一个序列中，有且仅有一个开始成员和一个终端成员，并且所有数据成员都最多有一个直接前驱和一个直接后继。例如，一维数组、线性表等就是典型的线性结构 非线性结构的特点是：一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如，树、图或网络等都是典型的非线性结构。 1-4．什么是抽象数据类型？试用C++的类声明定义“复数”的抽象数据类型。要求 (1) 在复数内部用浮点数定义它的实部和虚部。 (2) 实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。 (3) 定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。

数据结构课后习题解答第十章 内部排序

第十章内部排序 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]

for(i=first,j=1;d[i];i=i%MAXSIZE+1,j++)//将序列复制回去 L.r[j].key=d[i]; }//BiInsert_Sort 10.25 void SLInsert_Sort(SLList &L)//静态链表的插入排序算法 { L.r[0].key=0;L.r[0].next=1; L.r[1].next=0; //建初始循环链表 for(i=2;i<=L.length;i++) //逐个插入 { p=0;x=L.r[i].key; while(L.r[L.r[p].next].keyL.r[i]; L.r[i].next=p; } p=q; }//for }//SLInsert_Sort 10.26 void Bubble_Sort1(int a[ ],int n)//对包含n个元素的数组a进行改进的冒泡排序{ change=n-1; //change指示上一趟冒泡中最后发生交换的元素 while(change) { for(c=0,i=0;ia[i+1])

数据结构第十章习题课

1 .下列排序算法中，其中（ ）是稳定的。 A.堆排序，冒泡排序 B.快速排序，堆排序 C.直接选择排序，归并排序 D.归并排序，冒泡排序 2.若需在O （nlog 2n ）的时间内完成对数组的排序，且要求排序是稳定的，贝U 可选 择的排序方法是（ ）。 A.快速排序 B.堆排序 C.归并排序 D.直接插入排序 3.排序趟数与序列的原始状态有关的排序方法是（）排序法。 A .插入 B.选择 C.冒泡 D.快速 15， 21）排序，数据的排列次序在排序的过程中 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84则采用的排序是 （ ） A.选择 B.冒泡 5. 对序列｛15，9，7，8，20，-1, 4｝进行排序，进行一趟后数据的排列变为｛4, 9, -1，8，20，7，15｝;则采用的是（ A.选择 B.快速 6. 若上题的数据经一趟排序后的排列为 ｛9，15，7，8, 是（ ）排序。 A .选择 B.堆 C.直接插入 D.冒泡 7. 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ） A .直接插入排序 B .冒泡排序 C .简单选择排序 8. 下列排序算法中，（ ）算法可能会出现下面情况：在最后一趟开始之前, 所有元素都不在其最终的位置上。 A.堆排序 B.冒泡排序 C.快速排序 D.插入排序 9. 下列排序算法中，占用辅助空间最多的是: A.归并排序 B.快速排序 10. 用直接插入排序方法对下面四个 序列进行排序（由小到大），元素比较次数 最少的是（ ）O 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｝从大到小排序，需进行 （ ） 4.对一组数据（84，47，25, 的变化为（1） 84 47 25 15 21 C.快速 D.插入 ）排序。 C.希尔 D.冒泡 20, -1 , 4｝，则采用的 C.希尔排序 D.堆排序