数据结构(C语言版)习题参考答案

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐数据结构(C语言版)习题参考答案数据结构（C语言版）习题参考答案

习题1

一．名称解释

（1）数据是信息的载体，是对客观事物的符号表示。

通俗的说，凡是能被计算机识别、存取和加工处理的符号、字符、图形、图象、声音、视频信号等一切信息都可以称为数据。

（2）数据结构是互相之间存在的一种或多种特定关系的数据元素的集合。简言之，数据结构是指数据之间的关系，即数据的组织形式。

（3）数据元素之间的规律关系，称为数据的规律结构。

（4）数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。

（5）线性结构是指数据元素之间存在“一对一”关系的规律结构。

（6）非线性结构是指数据元素之间存在“一对一”或“一对多”关系的规律结构。

（除了线性结构以外的树形结构和图形结构等统称为非线性结构）。

二．推断题（正确的请在前面的括号内打√；错误的打ㄨ）

（1）√（2）ㄨ（3）√（4）ㄨ（5）√（6）√

三．填空题

（1）集合线性结构树形结构图形结构非线性结构

（2）挨次存储链式存储索引存储散列存储

（3）一对一一对多多对多

（4）没有一没有多个

（5）随意多个随意多个

（6）有穷性确定性可行性输入输出

（7）操作对象关系

（8）数据元素关系

（9）规律结构存储结构算法

（10）有穷指令事先估算法事后统计法

四．挑选题

（1）A（2）C（3）C（4）D（5）D（6）B（7）A（8）B

五．试分析下列程序段的时光复杂度

（1）O(n*m)（2）O(n)（3）O(n2)

（4）O(sqrt(n))（5）O(n)（6）O(n2)

252

253

六．二元关系表示的数据结构如下，分离画出对应的规律图形，并指出它们属于何种数据结构。（1）集合

c

（2）线性结构

（3）图结构

（4）树结构

以后，凡不会对根结点引起误会的状况下，树形结构结点之间的关系普通不用带箭头

线，而直接用直线画。

习题2

一．名词解释

（1）线性表——线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列。其规律特征反映了结点间一对一的关系，是一种线性结构。

（2）挨次表——用一组地址延续的存储单元依次挨次存储线性表的数据元素（相邻结点存放在相邻的物理位置），称为挨次表。它是一种随机存取结构，可以通过公式来计算结点的存取地址。

（3）单链表——单链表的每个结点都有两个域，一个数据域和一个指针域，称之为单链表。

（4）双链表——以链表形式存储的线性表，其结点包含一个数据域和两个指针域，称之为双链表。

（5）循环链表——若线性链表的最后一个结点的指针指向头结点，使得链表头尾结点相连，就构成了循环链表。

（6）存储密度——存储密度定义为结点数据本身所占的存储量与结点结构实际分配的存储量的比值。挨次表的存储密度等于1；链表结构存储密度小于1。

二．推断题（下列各题，正确的请在前面的括号内打√；错误的打ㄨ）

（1）ㄨ（2）ㄨ（3）√（4）ㄨ（5）ㄨ

（6）√（7）ㄨ（8）ㄨ（9）√（10）√

三．填空题

1．一定

2．不必

3．有限的一对一关系

4．节约存储随机存取

5．插入删除小

6．n/2表长n和插入位置

7．（n-1）/2表长n和删除位置

8．O(1)

9．直接前驱

10．的直接前趋结点的地址O(n)

11．O(1)

12．*P的直接前驱结点的地址O(n)O(1)

13．头指针

四．挑选题

(1)B(2)A(3)B(4)C(5)A

254

(6)A(7)B(8)B(9)D(10)B

五．简答题

1．挨次存储结构的特长是节省存储空间，可以随机存取。（缺点是插入、删除要作大量移动，不易扩充）；

链表存储结构优点是插入、删除操作简单，表的扩充便利。（缺点是存储密度低）。

2．头指针——指向链表中第一个结点（头结点或无头结点时的开头结点）的指针。

头结点——在开头结点之前附加的一个结点。

开头结点——在链表中，存储第一个数据元素的结点。

3．主要是简化操作。因为表的操作常在表的两端举行，所以对单循环链表，当知道其尾指针rear后，其另一端的头指针是rear->next->next（表中代头结点），仅转变两个指针值即可，运算时光为O(1)。

六．（1）返回结点*p的直接前趋结点地址。

（2）交换结点*p和结点*q（p和q的值不变）。

七．程序设计题

1．解：voidShow(ListNode*P)

{ListNode*t=P;

do

{printf("%c",t->data);

t=t->rear;

}

while(t!=P);

}

2．解：voiddelete(ListNode*L)

{ListNode*p=L,*q;

if(L->next->data==X)

{printf(“值为x的结点是第一个结点，没有直接前趋结点可以删除”);

return;

}

for(;p->next->data!=X;q=p,p=p->next);

//删除指针p所指向的结点

q->next=p->next;

deletep;

}

255

3．解voidDel(SeqList*L,inti,intk)

{intj=i-1+k;

for(j=0;jdata[i-1+j]=L->data[i+k-2+j];

if(i+k-2+j>L->last)

break;

}

}

4．解：本题是遍历该链表的每个结点，每碰到一个结点，结点个数加1，结点个数存储在变量n中。实现本题功能的函数如下：

intcounter(head)

node*head；

{node*p;

intn＝0;

p=head；

while(p!=NULL)

{if(p->data==x)n++；

p=p->next;

}

return(n);

}

5．解：本题的算法思想是：先找到两链表的尾指针，将第一个链表的尾指针与其次个链表的头结点链接起来，使之成为循环的。函数如下：

node*link(head1,head2)

node*head1,*head2;

{node*p,*q;

p=head1;

while(p->next!=head1)p=p->next;

q=head2;

while(q->next!=head2)q=q->next;

p->next=head2;

q->next=head1;

return(head1);

}

256

6．解：假设输入一组多项式的系数和指数，以输入系数为标志结束，在建立多项式链表时，总是根据指数从大到小挨次罗列的。两个多项式链表A和B，其头指针分离是heada和headb，这两个多项的多项式链表为C，其头指针为headc。实现本题功能的函数如下：structpnode*padd(heada，headb)

structpnode*heada,*headb；

{structpnode*headc,*p,*q,*s;

intx;

p=heada;q=headb;

headc＝(structpnode*)malloc(sizeof(structpndoe));

r=headc;

while(p!=NULL

if(x!=0)

{s＝(structpnode*)malloc(sizeof(structpnode));

s->coef＝s;

s->exp=p->exp;

r->link＝s;

r=s;

}

p=p->link;

q=q->link;

}

else//两结点的指数不相等时，将其中较小系数的结点复制成一新结点插入C中

if(p->expexp)

{

s=(structpnode*)malloc(sizeof(structpnode));

s->coef=q->coef;

s->exp=q->exp;

r->link=s;

r=s;

q=q->link;

}

else

{

s＝(structpnode*)malloc(sizeof(structpnode));

s->coef=p->coef;

s->exp=p->exp;

257

r->link=s;

r=s;

p=p->link;

}

}

while(p!=NULL)//复制A的余下部分

{

s=(structpnode*)malloc(sizeof(structpnode));//复制一个结点s

s->coef=p->coef;

s->exp=p->exp;

r->link=s;//把s链接到C中

r=s;

p=p->link;

}

while(q!=NULL)//复制B的余下部分

{

s=(structpnode*)malloc(sizeof(structpnode));//复制一个结点s

s->coef=q->coef;

s->exp=q->exp;

r->link=s;//把s链接到C中

r=s;

q=q->link;

}

r->link=NULL;//最后结点的link域置空

s=headc;//删除C的头结点

headc=headc->link;

free(s);

return(headc);

}

习题3

一.名词解释

（1）栈——只允许在一端举行插入或删除操作的线性表称为栈。其最大的特点是“后进先出”。

（2）挨次栈——采纳挨次存储结构的栈称为挨次栈。

（3）链栈——采纳链式存储结构的栈称为链栈。

258

二．推断题（下列各题，正确的请在前面的括号内打√；错误的打ㄨ）

（1）√（2）√（3）ㄨ（4）ㄨ（5）ㄨ（6）ㄨ

三.填空题

（1）后进先出

（2）栈顶栈底

（3）栈空栈满

（4）O（1）O（1）

（5）必需全都

（6）栈

（7）栈空

（8）p->next=toptop=p

（9）--++

（10）LS->next首

四.单选题

（1）B（2）C（3）A（4）D（5）B

（6）C（7）D（8）B（9）A（10）A

五.求下列表达式的后缀表达式（要求写出过程）

（1）AB^C^D/

（2）0A–BC*+DE/+

（3）ABC+*D*E-

（4）AB+C*EFGH/+/-D-

（5）852+/6-

六．算法设计题

1．解：用一整型变量top表示栈顶指针，top为0时表示栈为空。栈中元素从S[1]开头存放元素。

（1）入栈算法：

voidpush(charx)

{

if((top+M)>MAXLEN-1)

printf(“堆栈溢出！”);

else

{

if(top==0)

{

top++;

S[top]=x;

}

else

259

{

top=top+M;

S[top]=x;

}

}

}

（2）出栈算法：

voidpop(charx)

{

if(top==0)

printf(“堆栈为空栈！”);

else

{

if(top==1)

{

x=S[top];

top––;

}

else

{

x=S[top];

top=top–M;

}

}

}

2．解：设表达式在字符数组a[]中，使用一堆栈S来协助推断。

intcorrect(chara[])

{

stacks;

InitStack(s);//调用初始化栈函数

for(i=0;iNULL

10．队尾指针写入

四、单项挑选题

（1）A（2）C（3）A（4）D（5）A

（6）A（7）B（8）A（9）C（10）A

261

五．简答题

答：n个（同类）数据元素的有限序列称为线性表。线性表的特点是数据元素之间存在“一对一”的关系。栈和队列都是操作受限制的线性表，它们和线性表一样，数据元素之间都存在“一对一”的关系。

不同之处是：栈是只允许在一端举行插入或删除操作的线性表，其最大的特点是“后进先出”；队列是只允许在一端举行插入，另一端举行删除操作的线性表，其最大的特点是“先进先出”。

六．算法设计题

1．解：用一个循环数组Queue[0，n-1]表示该循环队列，头指针为front，计数器count用来记录队列中结点的个数。

（1）入队算法：

voidinqueqe(intx)

{inttemp;

if(count==n)

printf(“队列上溢出\n”);

else

{count++

temp=(front+count)%n;

Queue[temp]=x

}

}

（2）出队算法：

intoutqueue()

{inttemp;

if(count==0)

printf(“队列下溢出\n”);

else

{temp=Queue[front];

front=(front+1)%n;

count--;

returntemp;

}

}

2．解：队列为空：count==0,front==1

队列为满：count=MAXLEN

队列尾的第一个元素位置==(front+count)%MAXLEN

队列首的第一个元素位置==(front+1)%MAXLEN

constMAXLEN=100;

intqueue[MAXLEN];

intfront,count;//定义队头和计算器

262

voidinit()//初始化队列

{

front=1;

count=0;

}

intempty()//判定队列是否为空

{

if(count==0)return(1);

elsereturn(0);}

voidoutqueue(intqueue[],x)//取队列头元素给x

{

if(count==0)printf(“下溢出\n”);

else

{

front=(front+1)%MAXLEN;

x=queue[front];

}

}

voidinqueue(intqueue[],intx)//x入队列

{

intplace;

if(count==MAXLEN)printf(“上溢出\n”);

else

{

count++;

place=(front+count)%MAXLEN;

queue[MAXLEN]=x;

}

}

voidoutqueue(intqueue[])//删除队列头元素

{

if(count==0)printf(“队列下溢出\n”);

else

{

front=(front+1)%MAXLEN;

count--;

}

}

3．

（1）解：定义本题队列的结点类型如下：

typedefstructlinknode

263

{

intdata;

structlinknode*next;

}qu;

qu*rear;

inqueue(intx)//向队列插入结点x

{

qu*head,*s;

s=(qu*)malloc(size(qu));//创建一个新结点

s->data=x;

if(rear＝＝NUlL)//循环队列为空，则建立一个结点的循环队列{

rear＝s;

rear->next＝s;

}

else//循环队列不为空，则将s插到后面{

head=rear->next；

rear->next＝s;

rear=s;//rear始终指向最后一个结点

rear->next＝head;

}

}

(2)解：

voiddelqueue(rear)

{

if(rear==NULL)printf(“下溢出!\n”);

else

{head=rear->next;//head指向队首结点

if(head==rear)rear=NULL//惟独—个结点，则直接删除该结点

elserear->next=head->next//否则删除第一个结点

free(head)；//释放队首结点

}

}

习题5

一．名词解释

串：

264

串（string）是由零个或多个字符组成的有限序列。普通记为

S＝“a1a2...an”（n≥0）

其中，S是串名，用双引号或单引号括起来的字符序列是串的值，ai（1≤i≤n）称为串的元素，它可以是字母、数字、空格或其他字符。串中字符的个数n称为串的长度。广义表：

广义表（GeneralizedLists）是n（n≥0）个数据元素a1,a2,…，ai…，an的有序序列，普通记作：

ls=（a1，a2,…，ai,…，an）

其中：ls是广义表的名称，n是它的长度。每个ai（1≤i≤n）是ls的成员，它可以是单个元素，称为广义表ls的原子，也可以是一个广义表，称为广义表的子表。当广义表ls非空时，称第一个元素a1为ls的表头（head），称其余元素组成的表（a2,…,ai,…，an）为ls的表尾(tail)。广义表的定义是递归的。

二．推断题（下列各题，正确的请在前面的括号内打√；错误的打ㄨ）

（1）ㄨ（2）√（3）ㄨ（4）ㄨ（5）√（6）√（7）ㄨ（8）√（9）ㄨ（10）√三．填空题(10个)

1．长度

2．空串零

3．挨次存储

4．数据指针数据指针

5．模式匹配

6．挨次存储和链式存储

7．（a）(((b),c),(((d))))

8．广义表

四．挑选题

1．B2．D3．B4．C5．C6．A7．B8．A

五．简答题

1．简述串的存储结构及各自的特点。

串的存储方式有主要有挨次存储、堆分配存储和链式存储。

挨次结构：用一组地址延续的存储单元存储串的字符序列，构成串的挨次存储，简称为挨次串。

特点：这种结构是根据预设大小，为每个定义的串变量分配一个固定长度的存储区。因此存在存储空间的越界或铺张的问题。对于操作如查找但是操作容易便利。

堆分配存储结构：在内存中开拓地址延续的存储空间作为串的可利用存储空间，称为堆空间，按照每个串的长度，动态地为每个串在堆空间里申请相应大小的存储区域的一种存储结构。

特点：以一组地址延续的存储单元存放串的字符序列，但其存储空间是在算法执行过程中动态分配得到的，串也是挨次存储在所申请的存储区域中。因为堆分配存储结构的串既有挨次存储结构的特点，又没有造成对存储空间的铺张和对串长加以限制，使

265

用十分灵便。

链式存储结构：是将存储区域分成一系列大小相同的结点，每个结点有两个域即数据域data和指针域next。其中数据域用于存放字符串元素，指针域用于存放下一个结点的地址。

特点：在串中使用链式存储结构同样是在插入、删除等操作中没有移动元素所带来的时光耗费，存储空间的扩展简单；但结点的容量会带来存储空间的利用率降低。

2．广义表具有哪些性质？

(1)广义表是一种多层次的数据结构。广义表的元素可以是原子，也可以是子表，而

子表的元素还可以是子表。

(2)广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以

是其自身的子表。例如表E就是一个递归的表。

(3)广义表可以为其他表所分享。例如D=（A,B,C）时，表A、B、C是表D的分享

子表。在D中可以不必列出子表的值，而用子表的名称来引用。

六．下述算法的功能是什么

（1）实现串S和串T的衔接运算。

（2）返回串S中从第n1个字符开头取n2个字符组成的子串。

七．程序设计题

1．写一个递归算法来实现字符的逆序存储，要求不另设存储空间。

#include"stdio.h"

#includeMAXSIZE80

charnext[MAXSIZE80];/*串的最大长度*/

voidreverse(intn)/*递归函数实现逆置*/

{

if(n

#defineMAXSIZE80

typedefstruct

{charch[MAXSIZE];

intlen;

}SEQSTRING;

SEQSTRINGS,T,S1;

voidreplace(SEQSTRINGS,inti,intj,SEQSTRINGT)/*替换操作函数*/

{SEQSTRINGS1;

inth,k;

if(i

#include

#defineNULL0

typedefstructCHUNK

{chardata;

structCHUNK*next;

}LinkList;

voiddelx(LinkList*s,charx)/*从串s中删除全部取值为x的函数*/

{LinkList*p,*q,*r;

intw;

p=s;

w=1;/*是否第一个节点的标志位*/

while(p->next!=NULL)

268

{if(w==1)/*处理第一个节点*/

if(p->data==x)/*假如第一个节点取值为x*/

{

s=p->next;

free(p);

p=s;

}

else/*假如第一个节点取值不是x*/

{

q=p;

p=p->next;

w=0;

}

else/*处理其它节点*/

{

if(p->data==x)/*删除值为x的节点*/

{q->next=p->next;

free(p);

p=q->next;

}

else

{q=p;

p=p->next;

}

}

}

p=s;

printf("\n处理结果为:\n");/*输出结果以便观看*/

while(p->next!=NULL)

{printf("%c",p->data);

p=p->next;

}

printf("\n");

}

main()/*主函数*/

{inti,j;

charch,x;

269

LinkList*s,*p,*r;

p=malloc(sizeof(LinkList));/*申请链的头结点*/

p->data='';

p->next=NULL;

s=p;/*存放结果的指针变量指向它*/

ch='';

j=0;

printf("请输入字符串中的元素值,以’#’号结束输入!\n");

while(ch!='#')

{scanf("%c",getchar();

r=malloc(sizeof(LinkList));/*为输入的字符申请存储空间并由r指向它*/

r->data=ch;/*在新空间中存入信息*/

r->next=NULL;

p->next=r;

p=r;

j++;/*字符串长度是否为空标志，j不为0表示非空串*/}

p=s;

while(p->next!=NULL)/*输出原串结果以便观看*/

{printf("%c",p->data);

p=p->next;

}

if(j>1)/*假如串值不为空，调用删除字符处理函数*/

{printf("inputx");

scanf("%c",

printf("\n");

delx(s,x);/*以串s和字符x值调用删除字符处理函数*/

}

}

4．编写算法，求串S中所含不同字符的总数和每种字符的个数。

#include

#defineMAXSIZE80

typedefstruct

{charch[MAXSIZE];

intlen;

}SEQSTRING;

SEQSTRINGS,T;

270

SEQSTRINGInputStr()/*输入字符串函数*/

{inti;

T.len=0;

printf("请输入字符串:\n");

gets(T.ch);

for(i=0;T.ch[i]!='\0';i++)

T.len++;

returnT;

}

main()

{charz[10];

inti=0,j=0,m=0,l;

intn=0;

intr[10]={0};/*存储重复字符个数*/

intlog[10]={0};/*存放重复字符标志*/

S.len=0;

S=InputStr();/*输入字符*/

l=S.len;

while(i

#include

#defineMAXSIZE80

typedefstruct

{charch[MAXSIZE];

intlen;

}SEQSTRING;

voidpubstr(SEQSTRINGstr1,SEQSTRINGstr2)

{inti,j,k,p;

SEQSTRINGt;//合并后的字符串

t.len=0;

//以下双层for循环功能：查找s1,s2中公共字符，并将公共字符依次放入串t中

for(i=0;ilchild

count(t->lchild);

count(t->rchild);

}

}

2．求二叉树中值为最大的元素。

intmaxnode(BTt,intmax)

{if(t)

{if(t->data>max)max=t->data;

max=maxnode(t->lchild,max);

max=maxnode(t->rchild,max);

280

}

}

3．将二叉树各结点存储到一维数组中。

voidcreate(BTt,inta[],inti)

{if(t)

{a[i]=t->data;

create(t->lchild,a,2*i);

create(t->rchild,a,2*i+1);

}

}

4．前序输出二叉树中各结点及其结点所在的层号。

voidpreorderlevel(BTt,inth)//t的层数为h

{if(t!=NULL)

{printf(“%d,%d”,t->data,h);

preorderlevel(t->lchild,h+1);

preorderlevel(t->rchild,h+1);

}

}

5.求二叉树的宽度

思想：按层遍历二叉树，采纳一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。

intWidth(BT*T)

{intfront=-1,rear=-1;//队列初始化

intflag=0,count=0,p;

//p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值if(T!=Null)

{rear++;

q[rear]=T;

flag=1;

p=rear;

}

while(front{front++;

T=q[front];

281

if(T->lchild!=Null)

{rear++;

q[rear]=T->lchild;

count++;

}

if(T->rchild!=Null)

{rear++;

q[rear]=T->rchild;

count++;

}

if(front==p)//当前层已遍历完毕

{if(flag-1)

{T=stack[top];

top--;

if(T->child!=Null||T->rchild!=Null)

{//交换结点的左右指针

temp=T->lchild;

T->lchild=T->rchild;

T->rchild=temp;

282

}

if(T->lchild!=Null)

{top++;

stack[top]=T->lchild;

}

if(T->rchild!=Null)

{top++;

stack[top]=T->rchild;

}

}

}

}

main()

{intI,j,k,l;

printf(“\n”);

root=CreateBinTree();

Inorder(root);

i=CountNode(root);

j=CountLeafs(root);

k=Depth(root);

l=Width(root);

printf(“\nTheNode’sNumber:%d”,i);

printf(“\nTheLeafs’sNumber:%d”,j);

printf(“\nTheDepthis:%d”,k);

printf(“\nThewidthis:%d”,l);

Swap(root);

Printf(“\nTheswapTreeis:”);

Inorder(root);

}

7．

解：

inth=-1,lh=1,count=0;charx=’c’;//赋初值

Level(BinTreeT,inth,intlh)//求X结点在树只的层树

{if(T==Null)h=0;

elseif(T->data==x)

283

{h=lh;

count=h;

}

else

{h++;

Level(T->lchild,h,lh);

If(h==-1)Level(T->rchild,h,lh);

}

}

main()

{BinTree*(*newroot);

Printf(“\n”);

Root=CreateBinTree();

Inorder(root);

Printf(“\n”);

Level(root,h,lh);

Printf(“%d”,count);

}

习题7

一．名称解释

（1）有向图——在一个图中，假如每条边都有方向，则称该图有向图。

（2）无向图——在一个图中，假如每条边都没有方向，则称该图为无向图。

（3）彻低有向图——在一个有向图中，假如随意两顶点之间都有方向互为相反的两条弧相衔接，则称该图为有向彻低图。（在一个含有n个顶点的有向彻低图中，有n(n-1)条弧。）

（4）最小生成树——若无向连通图是一个网，则它的全部生成树中必有一棵边的权值之和为最小的生成树，简称为最小生成树。

二．推断题（下列各题，正确的请在前面的括号内打√；错误的打ㄨ）（1）√（2）√（3）ㄨ（4）√（5）ㄨ（6）ㄨ（7）√（8）ㄨ

三．填空题

284

285

（1）邻接矩阵邻接表深度优先遍历广度优先遍历（2）没有2n（3）有弧（4）顶点（5）出度

（6）O(n2

)（7）邻接表邻接矩阵（8）有向（9）不是

（10）O(n2

)

（11）n（n-1）/2（12）所有

四．挑选题

（1）C（2）B（3）B（4）C（5）C（6）B（7）A（8）A（9）D（10）A（11）B（12）D

五．简答题1．解

（1）邻接矩阵

12345

???????

???01

000

0000110000010001011

054321

（2）邻接表

2862

从顶点0动身的深度优先搜寻遍历的结点序列：012345

（不惟一）。从顶点0动身的广度优先搜寻遍历的结点序列：012453（不惟一）

。

3．解

（1）（2）深度优先搜寻：

abdce（或abdec）

广度优先搜寻：abedc

4．解

六．编程题

1．本题思想：逐个扫描邻接矩阵的各个元素，若第i行第j列的元素为1，则相应的邻接

表的第i个单链表上增强严格j结点。voidtrans(intedges[n][n],Adjlistadj){inti,j;edgenode*p;for(i=0;iadjvex=j;

p->next=adj[i].link;

adj[i].link=p;

}

}

}

2．

（1）求出度的思想：计算出邻接表中第i个单链表的结点数即可。

intoutdegree(adjlistadj,intv)

{intdegree=0;

edgenode*p;

p=adj[v].link;

while(p!=NULL)

{degree++;

p=p->next;

}

returndegree;

}

voidprintout(adjlistadj,intn)

{inti,degree;

printf("TheOutdegreeare:\n");

for(i=0;iadjvex==v)

287

degree++;

p=p->next;

}

}

returndegree;

}

voidprintin(adjlistadj,intn)

{inti,degree;

printf("TheIndegreeare:\n");

for(i=0;imaxdegree)

{maxdegree=degree;

maxv=i;

}

}

printf("maxoutdegree%d,maxvertex=%d",maxdegree,maxv);}

（3）求度为0的顶点数的算法

intoutzero(adjlistadj,intn)

{intnum=0,i;

for(i=0;ip->key)p=p->link;

elseif(x==p->key)returnp;else{

p=NULL;returnp;

}}

2．解：算法思想是：首先计算要删除的关键字为k的记录所在的位置，将其置为空(即删除)，然后利用线性探测法查找是否有与k发生矛盾而存储到下一地址的记录，假如有则将

记录移到本来k所在的位置，直至表中没有与k矛盾的记录为止。实现本题功能的算法如下：

voiddelete(sqlistr，intn，intk)

{

inth,h0,h1;

h=k%n;

while(r[h].key!=k)

h=(h+1)％n;

r[h]=NULL;

h0=h;

hl=(h+1)％n;

while(hl!=h)

{

while(r[h1].key％n!=h)

hl=(hl+1)％n;

r[h0]=r[h1];

r[h1]=NULL;

h0=h1;

h1=(hl+1)％n;

}

}

3．解：本题的算法思想：先计算地址H(R.key)，假如没有矛盾，则直接填入;否则利用线性探测法求出下一地址，直到找到一个为零的地址，然后填入。实现本题功能的函数如下：voidinsert(recordH,intm,recordR)

{

inti;

I=H(R.key);

if(H[i]==NULL)

H[i]=R;

else

{

while(H[i]!=NULL)

{

i=(i+1)%(m+1);

}

H[i]=R;

}

293

}

习题9

一.名词解释

（1）排序——将数据元素的随意序列，重新罗列成一个按关键字有序的序列，称为排序。（2）内排序——排序的所有过程都在内存举行的排序称为内排序。

（3）外排序——待排序的数据元素量大，以致内存一次不能容纳所有记录，在排序过程中不得不拜访外存储器的排序过程称为外排序。

（4）稳定排序——若对随意的数据元素序列，使用某个排序办法，对它按关键字举行排序，若相同关键字元素间的位置关系，排序前与排序后保持全都，称此排序办法是稳定的。

（5）堆——堆是一个彻低二叉树，它的每个结点对应于原始数据的一个元素，且规定假如一个结点有子结点，则此结点数据必需大于或等于其全部子结点数据。

二．推断题（下列各题，正确的请在前面的括号内打√；错误的打ㄨ）

（1）√（2）ㄨ（3）√（4）ㄨ（5）√

（6）ㄨ（7）ㄨ（8）√（9）√（10）√

三．填空题

1．时光复杂度算法所需的辅助空间

2．内排序外排序

3．3

4．希尔排序挑选排序迅速排序

5．迅速排序

6．插入排序

7．O(n2)n-1

8．迅速排序

9．L2

10．冒泡

四．挑选题

294

(1)D(2)A(3)A(4)C(5)D(6)C(7)D(8)C

(9)B(10)C(11)D(12)A(13)D(14)B(15)D

五．排序过程分析

1.解/p>