数据结构复习通.doc

《数据结构复习通.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题11．解释以下概念：逻辑结构，存储结构，操作，数据结构，数据结构的表示，数据结构的实现，抽象数据类型，算法，算法的时间代价，算法的空间代价，大O表示法。2．理解以下关系：算法与数据结构的关系；数据结构与抽象数据类型的关系；算法和数据结构与问题求解的关系。3.写出下列程序段的平均情况下的时间代价O表示式。(1)a=b+c;d=a+e(2)sum=0;for(i=0;i<3;i++)for(j=0;j=(y+1)*(y+1))y++;(4)

2、s=0;if(even(n))for(i=0;i0){if(x>lO0){x=x-10;n=n-1;}elsex=x+1;}4．对于给定的n个元素，可以构造出的逻辑结构有，，，四种。5.按增长率由小到大的顺序排列下列各函数：2100,()n,()n,()n,nn,n,n!,n,log2n,n/log2n习题22.1已知L是无头结点的单链表，且p结点既不是第一个结点，也不是最后一个结点，试从下列提供的语句中选出合适的

3、语句序列：(1)在p结点之后插入s结点：(2)在p结点之前插入s结点：(3)在单链表L首插入s结点：(4)在单链表L后插入s结点：提供的语句：①p->next＝s；②p->next＝p->next->next；③p->next=s->next；④s->next=p->next；⑤s->next＝L；⑥s->next=p；⑦s->next=NULL；⑧q＝p；⑨while(p->next!=q)p=p->next；⑩while(p->next!=NULL)p=p->next；⑾p=q；⑿p=L；⒀L＝s；

4、⒁L＝p；2.2已知p结点是某双向链表的中间结点，试从下列提供的语句中选出合适的语句序列。(1)在p结点之后插入s结点：(2)在p结点之前插入s结点：(3)删除p结点的直接后继结点：(4)删除p结点的直接前驱结点：提供的语句：①p->next＝p->next->next；②p->prior=p->prior->prior；③p->next=s；④p->prior=s；⑤s->next=p；⑥s->prior＝p；⑦s->next=p->next；⑧s->prior=p->prior；⑨p->prior-

5、>next=p->next；⑩p->prior->next＝p；⑾p->next->prior＝p；⑿p->next->prior＝s；⒀p->prior->next=s；⒁p->next->prior=p->prior；⒂q=p->next；⒃q=p->prior；⒄free(p)；⒅free(q)；2.3试编写一个计算头结点指针为L的单链表长度的算法。2.4试编写一个将单循环链表逆置的算法。2.5已知一顺序表A，其元素值非递减有序排列，编写一个算法，删除顺序表中多余的值相同的元素。习题33.1简述栈

6、和线性表的区别。简述栈和队列的相同点和不同点。栈有两种存储方式，其中一种是线性存储，而线性表只有线性存储一种方式，可以说线性存储的栈是只在表尾进行插入和删除操作的线性表。栈、队列相同点：同为一种特殊的线性表，不同是：栈是先进后出，队列是先进先出。3.2如果进栈的数据元素序列为1、2、3、4、5、6，能否得到4、3、5、6、1、2和1、3、5、4、2、6的出栈序列?并说明为什么得不到或如何得到。第一组不可以：因为最后出栈1、2则2必在1前出栈；而第二组可以：1进1出，2、3进3出，4、5进5出4出，2出，

7、6进6出；3.3利用两个栈模拟一个队列的入队、出队和判断队列空的运算。两个栈共同一个线表，base1top1出栈入栈base2top2top1=top2时栈为空3.4写一算法，将一个顺序栈中的元素依次取出，并打印元素值。#include#include"malloc.h"#defineMAXSIZE100typedefstruct{intdate[MAXSIZE];inttop;}seqstack;voidposeqstack(seqstack*s){while(s->top!=-1)

8、printf("%d",s->date[s->top--]);}voidmain(){inti;seqstack*s;s=(seqstack*)malloc(sizeof(seqstack));for(i=0;i<6;i++)s->date[i]=i+10;s->top=5;poseqstack(s);}3.5写一算法，将一个非负十进制整数转换成二进制。#include#include"malloc.h"#defineMA