数据结构 - C语言描述课后答案

第一章 绪论 一、问答题

1. 什么是数据结构？

2. 叙述四类基本数据结构的名称与含义。 3. 叙述算法的定义与特性。 4. 叙述算法的时间复杂度。 5. 叙述数据类型的概念。

6. 叙述线性结构与非线性结构的差别。 7. 叙述面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？ 9. 叙述参数传递的主要方式及特点。 10. 叙述抽象数据类型的概念。 二、判断题（在各题后填写“√”或“×”）

1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（ ） 2. 算法就是程序。（ ）

3. 在高级语言（如C或 PASCAL）中，指针类型是原子类型。（ ） 三、计算下列程序段中X=X+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】

i=1时： 1 = (1+1)×1/2 = (1+12)/2 i=2时： 1+2 = (1+2)×2/2 = (2+22)/2 i=3时： 1+2+3 = (1+3)×3/2 = (3+32)/2 …

i=n时： 1+2+3+……+n = (1+n)×n/2 = (n+n2)/2

x=x+1的语句频度为：

f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2 =[ (1+n)×n/2 + n(n+1)(2n+1)/6 ] / 2 =n(n+1)(n+2)/6 =n3/6+n2/2+n/3

区分语句频度和算法复杂度： O(f(n)) = O(n3)

四、试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(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

scanf(“%f ”,&a[i]); /*执行次数：n次 */ p=a[0];

for(i=1;i<=n;i++)

{ p=p+a[i]*x; /*执行次数：n次*/ x=x*x;} printf(“%f”,p); }

算法的时间复杂度：T(n)=O(n)

通过参数表中的参数显式传递

float PolyValue(float a[ ], float x, int n) {

float p,s; int i; p=x; s=a[0];

for(i=1;i<=n;i++)

{s=s+a[i]*p; /*执行次数:n次*/ p=p*x;} return(p); }

算法的时间复杂度：T(n)=O(n) 第二章 线性表

2.1 描述以下三个概念的区别：头指针，头结点，首元素结点。 2.2 填空：

（1） 在顺序表中插入或删除一个元素，需要平均移动＿＿一半＿＿元素，具体移动的元素个数与＿＿插入或删除的位置＿＿有关。

（2） 在顺序表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。在单链表中，逻

辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。 （3） 在带头结点的非空单链表中，头结点的存储位置由＿＿＿＿＿＿指示，首元素结点的存储位置由＿＿＿＿＿＿指示，除首元素结点外，其它任一元素结点的存储位置由＿＿其直接前趋的next域＿＿指示。

2.3 已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是：＿（4）、（1）＿。 b. 在P结点前插入S结点的语句序列是：（7）、（11）、（8）、（4）、（1）。 c. 在表首插入S结点的语句序列是：（5）、（12）。 d. 在表尾插入S结点的语句序列是：（11）、（9）、（1）、（6）。 供选择的语句有： （1）P->next=S;

（2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L;

（6）S->next= NULL; （7）Q= P;

（8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P;

2.4 已知线性表L递增有序。试写一算法，将X插入到L的适当位置上，以保持线性表L的有序性。

Status Insert_SqList(SqList &va,int x)//把x插入递增有序表va中 {

if(va.length+1>va.listsize) return ERROR; va.length++;

for(i=va.length-1;va.elem[i]>x&&i>=0;i--) va.elem[i+1]=va.elem[i]; va.elem[i+1]=x; return OK; }//Insert_SqList

2.5 写一算法，从顺序表中删除自第i个元素开始的k个元素。 [提示]：注意检查i和k的合法性。 （集体搬迁，“新房”、“旧房”）

< 方法1 > 以待移动元素下标m（“旧房号”）为中心， 计算应移入位置（“新房号”）：

for ( m= i－1+k; m<= L－>last; m++) L－>elem[ m－k ] = L－>elem[ m ];

< 方法2 > 同时以待移动元素下标m和应移入位置j为中心： < 方法2 > 以应移入位置j为中心，计算待移动元素下标：

2.6已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素 {

p=L;

while(p->next->data<=mink) p=p->next; //p是最后一个不大于mink的元素 if(p->next) //如果还有比mink更大的元素 {

q=p->next;

while(q->datanext; //q是第一个不小于maxk的元素 p->next=q; }

}//Delete_Between

2.7试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。

（1） 以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2） 以单链表作存储结构。 [方法1]:在原头结点后重新头插一遍

[方法2]:可设三个同步移动的指针p, q, r，将q的后继r改为p

2.8 假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序的排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C. [提示]：参P.28 例2-1 < 方法1 >

void merge(LinkList A; LinkList B; LinkList *C) { ……

pa=A－>next; pb=B－>next; *C=A; (*C)－>next=NULL;

while ( pa!=NULL && pb!=NULL ) { if ( pa－>data <= pb－>data ) { smaller=pa; pa=pa－>next;

smaller－>next = (*C)－>next; /* 头插法 */ (*C)－>next = smaller; } else

{ smaller=pb; pb=pb－>next;

smaller－>next = (*C)－>next; (*C)－>next = smaller; }

while ( pa!=NULL)

{ smaller=pa; pa=pa－>next; smaller－>next = (*C)－>next; (*C)－>next = smaller; }

while ( pb!=NULL)

{ smaller=pb; pb=pb－>next; smaller－>next = (*C)－>next; (*C)－>next = smaller; }

< 方法2 >

LinkList merge(LinkList A; LinkList B) { ……

LinkList C；

pa=A－>next; pb=B－>next; C=A; C－>next=NULL; …… ……

return C;

while(pa||pb) {

if(pa->datadata||!pb) {

pc=pa;q=pa->next;pa->next=pre;pa=q; //将A的元素插入新表 } else {

pc=pb;q=pb->next;pb->next=pre;pb=q; //将B的元素插入新表 }

pre=pc; }

C=A;A->next=pc; //构造新表头 }//reverse_merge

分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素.

2.9 假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。

{

int visited[MAXSIZE]; InitStack(S);

Push(S,GetVex(S,1)); //将第一个顶点入栈 visit(1); visited=1;

while(!StackEmpty(S)) {

while(Gettop(S,i)&&i) {

j=FirstAdjVex(G,i); if(j&&!visited[j]) {

visit(j); visited[j]=1;

Push(S,j); //向左走到尽头 } }//while

if(!StackEmpty(S)) {

Pop(S,j); Gettop(S,i);

k=NextAdjVex(G,i,j); //向右走一步 if(k&&!visited[k]) {

visit(k); visited[k]=1; Push(S,k); } }//if }//while

}//Straverse_Nonrecursive

分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考6.37.由于是强连通图,所以从第一个结点出发一定能够访问到所有结点.

7.11 采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径（指顶点序列中不含有重现的顶点）的算法。

[提示]：利用深度搜索，增设一个深度参数，深度超过k 则停止对该结点的搜索。

int visited[MAXSIZE];

int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径 {

if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求

else if(k>0) {

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

l=p->adjvex; if(!visited[l])

if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一 }//for

visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else

return 0; //没找到 }//exist_path_len

7.12 下图是带权的有向图G的邻接表表示法。从结点V1出发，深度遍历图G所得结点序列为（ A ），广度遍历图G所得结点序列为（ B ）；G的一个拓扑序列是（ C ）；从结点V1到结点V8的最短路径为（ D ）；从结点V1到结点V8的关键路径为（ E ）。 其中A、B、C的选择有： ① V1,V2,V3,V4,V5,V6,V7,V8 ② V1,V2,V4,V6,V5,V3,V7,V8 ③ V1,V2,V4,V6,V3,V5,V7,V8 ④ V1,V2,V4,V6,V7,V3,V5,V8 ⑤ V1,V2,V3,V8,V4,V5,V6,V7 ⑥ V1,V2,V3,V8,V4,V5,V7,V6 ⑦ V1,V2,V3,V8,V5,V7,V4,V6 D、E的选择有： ① V1,V2,V4,V5,V3,V8 ② V1,V6,V5,V3,V8 ③ V1,V6,V7,V8 V1,V2,V5,V7,V8 ④

7.13 已知一棵以二叉链表作存储结构的二叉树，试编写按层次顺序（同一层自左至右）遍历二叉树的算法。

void LayerOrder(Bitree T)//层序遍历二叉树 {

InitQueue(Q); //建立工作队列 EnQueue(Q,T);

while(!QueueEmpty(Q)) {

DeQueue(Q,p); visit(p);

if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); }

}//LayerOrder 第八章 查找

8.1 若对大小均为n的有序的顺序表和无序的顺序表分别进行查找，试在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同？

（1） 查找不成功，即表中没有关键字等于给定值K的记录。 （2） 查找成功，且表中只有一个关键字等于给定值K的记录。

（3） 查找成功，且表中有若干个关键字等于给定值K的记录，一次查找要求找出所有记录。

[提示]：均用顺序查找法。

8.2 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。

[提示]：根据P.191 ASL定义计算平均查找长度。

8.3 试推导含12个结点的平衡二叉树的最大深度并画出一棵这样的树。

[提示]：沿最左分支生长，前提是：其任一祖先的右分支与左分支等深，如不等深，则先生长右分支，而生长右分支的前提是：其任一祖先的左分支与右分支等深，如不等深，则先生长左分支，如此交互考虑，逐步生长，直到12个结点。

8.4 试从空树开始，画出按以下次序向2-3树，即3阶B-树中插入关键码的建树过程：20，30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后2-3树的状态。

8.5 选取哈希函数H(k)=(3k)，用线性探测再散列法处理冲突。试在0～10的散列地址空间中，对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求等概率情况下查找成功与不成功时的平均查找长度。 [提示]：平均查找长度参考P.225。

0 1 2 3 4 5 6 7 8 9 10 22 41 30 01 53 46 13 67 1 1 2 2 1 1 2 6

ASLsucc = (1×4 + 2×3 + 6) / 8 = 2

ASLunsucc = ( 2 + 1 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 1 ) / 11 = 40 / 11

8.6 试为下列关键字建立一个装载因子不小于0.75的哈希表，并计算你所构造的哈希表的平均查找长度。

（ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG，CHANG，CHAO，YANG，JIN） [提示]：（1）由装填因子求出表长，（2）可利用字母序号设计哈希函数， （3）确定解决冲突的方法。

8.7 试编写利用折半查找确定记录所在块的分块查找算法。

8.8 试写一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以二叉链表作存储结构，且树中结点的关键字均不同。

[提示]：检验中序遍历序列是否递增有序？

[方法1]：用非递归中序遍历算法，设双指针pre, p 一旦pre->data > p->data 则返回假

[方法2]：用递归中序遍历算法，设全局指针pre，（参中序线索化算法） 一旦pre->data > p->data 则返回假 [方法3]：用递归（中序或后序）算法

（1）空树是（2）单根树是（3）左递归真（4）右递归真 （5）左子树的右端小于根（6）右子树的左端大于根

int last=0,flag=1;

int Is_BSTree(Bitree T)//判断二叉树T是否二叉排序树,是则返回1,否则返回0 {

if(T->lchild&&flag) Is_BSTree(T->lchild);

if(T->datadata;

if(T->rchild&&flag) Is_BSTree(T->rchild); return flag; }//Is_BSTree

8.9 编写算法，求出指定结点在给定的二叉排序树中所在的层数。

8.10 编写算法，在给定的二叉排序树上找出任意两个不同结点的最近公共祖先（若在两结点A、B中，A是B的祖先，则认为A是A、B的最近公共祖先）。 [提示]：

（1） 假设A<=B，

（2） 从根开始，左走或右走，直到A在左（或根），B在右（或根）。

8.11 编写一个函数，利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性。 [提示]：（1）表中已经有x，（2）表中没有x 参P. 231

8.12 已知长度为12的表：

（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）。

（1） 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树并求其等概率的情况下查找成功的平均查找长度。 （2） 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。

（3） 按表中元素的顺序依次构造一棵平衡二叉排序树，并求其等概率的情况下查找成功的平均查找长度。

[提示]：画出判定树或排序树，根据P.191 ASL定义计算平均查找长度。

8.13 含有9个叶子结点的3阶B-树中至少有多少个非叶子结点？含有10个叶子结点的3阶B-树中至少有多少个非叶子结点？ [提示]：叶子结点对应空指针。

8.14 写一时间复杂度为O(log2n + m)的算法，删除二叉排序树中所有关键字不小于x的结点，并释放结点空间。其中n为树中的结点个数，m为被删除的结点个数。 [提示]：

（1） p=root

（2） 如果p->key大于、等于x，则删除p->rchild和p， （3） 左走一步，转（2）

（4） 如果p->key小于x，则反复右走， （5） 转（2）

（6） 直到p==NULL

void Delete_NLT(BiTree &T,int x)//删除二叉排序树T中所有不小于x元素结点,并释放空间 {

if(T->rchild) Delete_NLT(T->rchild,x);

if(T->data

T=T->lchild;

free(q); //如果树根不小于x,则删除树根,并以左子树的根作为新的树根 if(T) Delete_NLT(T,x); //继续在左子树中执行算法 }//Delete_NLT

8.15 在平衡二叉排序树的每个结点中增加一个lsize域，其值为它的左子树中的结点数加1。编写一时间复杂度为O(log n)的算法，确定树中第k个结点的位置。 [提示]：先画图手工求。 （1）sum=0,

（2）从当前根开始沿左链找sum + lsize<=k的最大结点a，

（3）沿a的右链求sum=sum + lsize，直到结点b，sum + lsize(b)>=k 重复（2）、（3），直到sum=k typedef struct {

int data; int bf;

int lsize; //lsize域表示该结点的左子树的结点总数加1 BlcNode *lchild,*rchild;

} BlcNode,*BlcTree; //含lsize域的平衡二叉排序树类型

BTNode *Locate_BlcTree(BlcTree T,int k)//在含lsize域的平衡二叉排序树T中确定第k小的结点指针 {

if(!T) return NULL; //k小于1或大于树结点总数 if(T->lsize==k) return T; //就是这个结点 else if(T->lsize>k)

return Locate_BlcTree(T->lchild,k); //在左子树中寻找

else return Locate_BlcTree(T->rchild,k-T->lsize); //在右子树中寻找,注意要修改k的值 }//Locate_BlcTree 第九章 内部排序

9.1 以关键码序列（503，087，512，061，908，170，897，275，653，426）为例，手工执行以下排序算法，写出（前三趟）每一趟排序结束时的关键码状态： （1）直接插入排序； （2）希尔排序（增量d[1]=5）； （3）快速排序； （4）堆排序； （5）归并排序； （6）基数排序。

9.2 一组关键字码，40，27，28，12，15，50，7，采用快速排序或堆排序，写出每趟排序结果。

9.3 不难看出，对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。

n=7时在最好情况下需进行多少次比较？请说明理由。 对n=7给出一个最好情况的初始排列实例。 （保证每个基准记录都是中间记录）

9.4 假设序列由n个关键字不同的记录构成，要求不经排序而从中选出关键字从大到小顺序的前k(k<

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

9.6 编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。 [提示]：（1）参快速排序（2）“水底”、“水面”相遇时结束。

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

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

while(low

change=0;

for(i=low;ia[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

9.7 编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：

采取顺序存储结构，至多使用一个记录的辅助存储空间； 算法的时间复杂度O(n)；

讨论算法中记录的最大移动次数。

[提示]：r[0]=r[1]，以0为分界值，参快速排序划分过程，但不要求对元素排序。

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

low=0;high=n-1; while(low

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

while(lowa[high]; }

}//Divide

9.8试以单链表为存储结构实现简单选择排序的算法

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.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 ）在执行某排序算法过程中，出现了排序码朝着与最终排序序列相反方向移动的现象，则称该算法是不稳定的。

本文来源：https://www.bwwdw.com/article/99dt.html