[数据结构与算法]《数据结构与算法》第二版-陈卫卫-陆军工程大学811数据结构教材 第1-2章 参考答案

《数据结构与算法》（第二版）陈卫卫-高等教育出版社

? ? 陆军工程大学811数据结构教材? ??第1-2章 参考答案

完整答案、811真题答案请查看作者付费资源

习题1.1

1.1-1????? （1）名称、数量、特征、性质的???? ?????? （2）处理对象和计算结果

1.1-2??? （1）数据结点 ??（2）用来描述一个独立事物的名称、数量、特征、性质

1.1-3??? （1）存储结构 ??（2）物理结构 ?（3）用来存储一个数据结点，并在必要时存储该结点与其他结点之间的关系的一组存储单元 ??（4）空白结点

1.1-4??? （1）表、树、图、散列 ?（2）表结构 ?（3）1? （4）树结构 ??（5）多

????????????? （6）1?? （7）树 ?（8）散列 ?（9）表

1.1-5??? （1）解决某一特定问题的 ?

（2）有穷性、确定性、可行性、输入数据(0/多个)、输出数据(1/多个)

1.1-6~8?? A ，B??? C?? B

习题1.2

1.2-1????? （1）描述形式???? ?????? （2）程序形式???? ?????? （3）描述形式???? ?????? （4）描述形式

1.2-4????? （1）空间???? （2）T(n)≤cf(n)? （3）T(n)是否在多项式范围内。

1.2-7????? （1）T(n)=O(n2)????????? （2）S(n)=O(n)

1.2-8????? D

1.2-9????? A

1.2-10???? D

1.2-13???? （2）步骤1完成(n-k)/2 下取整?对元素交换；步骤2完成k/2 下取整?对元素交换；步骤3完成n/2 下取整 对元素交换。

每交换一对元素，需要移动3次，故

T(n)=3{(n-k)/2+k/2+n/2}

因为x/2 下取整?≤x/2，故

T(n)≤3(n/2-k/2+k/2+n/2）

?????????????????????????????????????????????????????????????????=3n

1.2-17

????????????? i=2;

????????????? while(n!=1){

???????????????????? if(n%i==0){

??????????????????????????? cout<<i<<“*”; n=n/i;? i--;}

???????????????????? i++;? }

习题2.1

2.1-1????? （1）6，9，7，8 ?????? （2）4?? ?????? （3）(2*3+4*12)/14=27/7

2.1-2???? [log2 n]+1? log2(n+1)-1

2.1-3????? （1）A???????? （2）C

2.1-4???? C

2.1-5????? A

2.1-6???? A

2.1-7????? （1）D???????? （2）B

2.1-8????? C

2.1-9???? B

2.1-12?? (1)i=1,j=0,k=0? (2)i<M&&j<N?? (3)c[k++]=b[j++]?? (4)while(i<M)

????????????? (5)while(j<N)??

2.1-13?? (1)left<=right?? (2)mid? (3)left=mid+1? (4)a[j+1]=a[j]? (5)a[left]

2.1-14?? (1)j=0,k=0???? (2)m&&? (3)c[k++]=a[i++]=b[j++]

????????????? (4)while(i<m)?? (5)while(j<n)

2.1-15???? 答：（1）--avtop （2）i>=k?? （3）a[i]? （4）av[avtop++]?? （5）n—

2.1-18

习题2.2 ?

2.2-5????? （1）当n为偶数时

h1： 1，3，5……，n-1

h2： 2，4，6……，n

（2）当n为奇数时

h1： 1，3，5……，n

h2： 2，4，6……，n-1

2.2-7???? A

2.2-8???? B

2.2-9????? （1）B ?（2）C

2.2-10??? A

2.2-11???? （1）A? （2）B

2.2-12??? C

2.2-13???? （1）C? （2）??? A

2.2-14??? A

2.2-15???? （1）B????????? （2）C

2.2-16??? D

2.2-17???? B

2.2-18??? C

2.2-19???? B

2.2-20??????????? （1）k=1????? （2）s=ha->next? （3）k++????? （4）t=p

（5）q->next=s??? （6）s=hb->next? （7）p->next=h

2.2-21????? （1）sizeof(snode) ??? （2）hb->next???? （3）s!=NULL???? （4）s=s->next

（5）break??? （6）retuen hb????? （7）q==NULL?????????? (8)hb->next

2.2-22??????????? （1）p=h???????????? （2）s!=NULL 或s??????????? （3）q=s

（4）p->next?????? （5）s=s->next

2.2-23??????????? (1)h=???????????? (2)ha=ha->next???????????? (3)hb=hb->next??????????? (4)s->next=ha

?(5)h=h->next

2.2-24??????????? （1）h=??????? （2）ha=ha->next?????? （3）hb=hb->next

（4）s->next=NULL?? （5）h=h->next?? （6）p= new snode

2.2-25??????????? 答：（1）h=takeoff( )??? （2）a[h1].link=h2^h?? （3）a[p].link=h1^q

（4）a[h1].link^h2^p?? （5）q=p????? （6）r!=h1??? （7）r=a[p].link^q

2.2-28（9）关于加头有序循环链表。

#include? <stdio.h>

const int MAX=9999;?????????? ???????????????????? //定义无穷大

typedef? struct? linkednode

?{ int? data;

??? struct? linkednode? *next;

?}? snode, *ptr;

void? insert(ptr &h, int? x)? ????????????? ?????? //插入函数

{? ptr f,s,p;

?? p=new snode,p->data=x;

?? f=h,s=h->next;

?? while(s->data<x) f=s,s=s->next;

?? p->next=s;f->next=p;return;

}

ptr? creatlinked( )???????? ??????????????????????????? //构造加头有序循环链表

{ ptr? head; int x;

?? head=new snode;

?? head->data=MAX, head->next=head;

?? printf("请输入链表元素，0：结束。\n");

?? scanf("%d",&x);

?? while(x)

??? { insert(head,x);

???? scanf("%d",&x);

??? }

?? return? head;

}

void insertA(ptr h)??????? ??????????????????????????? //插入的主控函数

{? int x;

??? printf("请输入要插入的元素，x=");

??? scanf("%d",&x);

?? insert(h, x);

}

void del(ptr h,int x)?????? ??????????????????????????? //删除函数

{? ptr f,s;

?? if(h==h->next){printf("链表空，不能删除。\n");return; }

?? f=h,s=h->next;

?? while(s->data<x)f=s,s=s->next;

?? if(s->data==x)

??? { f->next=s->next;delete s; printf("删除成功！\n");return;}

? printf("表中没有%d 删除失败！\n",x);

}

void delA(ptr &h)???????? ??????????????????????????? //删除的主控函数

? {? int x;

?? printf("请输入要删除的元素，x=");

?? scanf("%d",&x);

?? del(h,x);

? }

void search(ptr h,int x)?? ???????????????????? ?????? //查找函数

{? if(h==h->next){printf("链表空，不能查找\n");? return;}

?? h=h->next;

?? while(h->data<x)h=h->next;

?? if(h->data==x)printf("找到%d\n",x);else printf("没找到%d\n",x);

}

void searchA(ptr h)?????? ??????????????????????????? //查找的主控函数

{ int x;

? printf("请输入要查找的元素，x=");

? scanf("%d",&x);

? search(h, x);

}

void? print(ptr? h) ??????????? ???????????????????? //输出加头循环链表

{ ptr? p;

? if(h==h->next){printf("表为空!\n"); return;}

?? p=h->next;

??? while(p!=h)

????? {? printf("%4d",p->data);

???????? p=p->next;

????? }

?? printf("\n");

}

void main( )?????????? ?????????????????????????????????? //主函数

{? ptr? h;?? int d;

? h=creatlinked();

? printf("所建链表：");

? print(h);

? while(1)

? { printf("请输入操作码d，1：查找，2：插入，3：删除，4：输出，其他：结束操作 d=");

?? scanf("%d",&d);

?? if(d==1){searchA(h);continue;}

?? if(d==2){insertA(h); continue;}

?? if(d==3){delA(h);continue;}

?? if(d==4)print(h); else break;

? }

? printf("程序结束\n");

}