数据结构习题（1,2,3章）答案

精品

第一章 绪论

一．选择题

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

二．填空题

1．数据的逻辑结构、数据的存储结构、基本操作 2．集合、线性结构、树结构、图结构 3．n、

n(n?1)、○（n2） 2三．算法分析题

1．功能：求n!

时间复杂度：○（n） 2．功能：求n!

时间复杂度：○（n2）

四．解答

略

第二章 线性表

一．选择题

1．A 2．B 3．A 4．D

精品

5．A 6．C 7．A 8．B 9．A

二、填空

1．物理位置相邻 指针 2．直接前驱 直接后继 3．顺序 链式

三、算法设计 1．①

int count(Linklist h,int x) {

int num=0; Linknode *p; p=h->next;

while(p&&p->data<=x) p=p->next; while(p)

if(p->next&&p->data==p->next->data) p=p->next; else {

num++; p=p->next; }

return num; }

② void delevenl(Linklist h,int x)

{

Linknode *p,*r; p=h->next;r=h;

while(p&&p->data

if(p->data%2==0) {

r->next=p->next; free(p); p=r->next; } else

精品

{

r=p;

p=p->next; } } }

2．

void Inverse（Linklist &h） {

Linklist p,q; p=h; h=null; while(p)

{ q=p; p=p->next; q->next=h; h=q; } }

3．

void merge(Linklist La,Linklist &Lb,Linklist &Lc) { Linknode *p; Lc=new Lnode; Lc->next=NULL; p=La->next; Lb=La; Lb->next=NULL; while(p) { La=p->next; if(p->data>0) { p->next=Lc->next; Lc->next=p; } else { p->next=Lb->next; Lb->next=p; } p=La; } } 4．

int insect(Linklist La,Linklist Lb) {

精品

Linknode *p,*q; p=La->next; while(p) { q=Lb->next; while(q) { if(p->data==q->data) break; else q=q->next; } if (!q) return 0; p=p->next; } return 1; } 5．

void change(Dublist &h) { DubLnode *p; p=h; while(p->next!=h) { p->next->prior=p; p=p->next; } h->prior=p; }

第三章 栈和队列

一、选择题

1．C 2．C 3．D 4．C 5．A 6．C 7．D

二．填空题

1．线性 任意位置 栈顶 队尾 对头