厦大数据结构习题及解答.doc

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

1、1.数据元素是数据的基本单位，有些情况下也称为元素、结点、顶点、记录等。2何谓算法?它与程序有何区别?算法是解决某一特定类型问题的有限运算序列。程序＝数据结构＋算法3.算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机运行时间的长短和占据空间的大小。4.何谓频度、时间复杂度、空间复杂度？说明其含义。算法中语句的重复次数称为该语句的频度。时间复杂度是算法执行所需要的时间，也就是算法中每一个语句的执行次数乘以每一次执行所需的时间的总和。空间复杂度是算法对空间占用的量度。（一般在考虑空间复杂度时，只估算算法所需增添的辅

2、助空间，而对问题中原始数据所占的空间，由于与算法无关，不予考虑。）5.时间复杂度的计算：语句2的频度为n-l，语句4的额度为(n-1)(2n+1)＝2n2-n-l，因此时间复杂度T(n)＝O(n2)。语句3的频度为n，语句7的频度为n2，因此时间复杂度为T(n)＝O(n2)。【解】语句3的频度不仅与n有关，而且和x及数组A中各分量的值有关。这时通常考虑最坏的情况，由于while循环的最大次数为n-1，因此时间复杂度为T(n)＝O(n)。i=1;while(i<=n)i=i*5;【解】设语句“i=i*5;”的频度为x，则5x

3、<=n，x<=log5n，O(log5n)i=0;s=0;while(s

4、D.顺序表（D）8.写出带头结点的双向循环链表L为空表的条件（假设结点包括data,next,prior三个域）：(L==L->Next)&&(L==L->Prior)注：L->Next==L->Prior不行，因为表长为1时该条件也成立。9.判断对错：顺序存储的线性表不可以随机存取。（*）10.判断对错：线性表的长度是线性表所占用的存储空间的大小。（*）11.写出带头结点的单链表和不带头结点的单链表的插入、删除算法，并比较。/*带头结点的插入算法。将s结点插入到数据域为x的结点之前。假设链表中存在该结点。*/voidin

5、s(head,s,x)structnode*head,*s;intx;{structnode*p;p=head;while(p->next!=NULL)if(p->next->data==x){s->next=p->next;p->next=s;return;}elsep=p->next;}/*不带头结点的插入算法。返回插入后的链表的头指针*/structnode*ins(head,s,x)structnode*head,*s;intx;{structnode*p;if(head->data==x)/*插在第一个结点之前*

6、/{s->next=head;return(s);}p=head;while(p->next!=NULL)if(p->next->data==x){s->next=p->next;p->next=s;return(head);}elsep=p->next;}/*带头结点的删除算法。删除数据域为x的结点。假设链表中存在该结点。*/voiddel(head,x)structnode*head;intx;{structnode*p,*q;p=head;while(p->next!=NULL)if(p->next->data==x

7、){q=p->next;p->next=q->next;free(q);return;}elsep=p->next;}/*不带头结点的删除算法。返回删除后的链表的头指针。*/structnode*del(head,x)structnode*head;intx;{structnode*p,*q;if((head->data==x)&&(head->next==NULL))/*在仅有一个结点的表中删第一个结点*/{free(head);return(NULL);}if(head->data==x)/*在不只一个结点的表中删第一

8、个结点*/{q=head->next;free(head);return(q);}p=head;while(p->next!=NULL)if(p->next->data==x){q=p->next;p->next=q->next;free(q);return(head);}elsep=p->next;}