资源描述：
《大连海事大学数据结构习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章1、一元稀疏多项式的求导算法写出一元稀疏多项式的求导算法，用带表头结点的单链表存储该一元稀疏多项式，Lb为头指针，用类C语言描述该求导算法，不另行开辟存储空间，删除无用结点，并分析算法的时间复杂度。该链表的数据结构如下：typedefstructLNode{floatcoe;//系数intexp;//指数structLNode*next;//指针}LNode,*LinkList;求导算法如下：voidDifferential(LinkList&Lb){//求导算法pre=Lb;p=pre->next;while(p){if(p->exp!=0)//指数不
2、等于零{p->coe=p->coe*p->exp;p->exp=p->exp–1;pre=pre->next;}else//指数等于零{pre->next=p->next;free(p);}p=pre->next;}}//时间复杂度为:O(n)、第5章数组和广义表广义表练习题1、已知广义表A=((a,(b,c)),(a,(b,c),d))，则运算head(head(tail(A)))的结果是。A.aB.(b,c)C.(a,(b,c),d)D.d2、利用广义表的Head(L)和Tail(L)的运算，将元素c从广义表L=((((a，b)，e,(c，d))))中分离
3、出来，其运算表达式为。A．Head(Head(Tail(Tail(Head(Head(L))))))B．Head(Tail(Head(Tail(L))))C．Head(Head(Tail(Head(L))))D.都不对2、单链表存储结构的排序算法排序算法：将一组整数排序成非递减有序序列。用带头结点的单链表存储，L为头指针，用类C语言写出该排序算法，不另行开辟存储空间，并分析算法的时间复杂度。该单链表的数据结构如下：typedefstructLNode{intdata;//数据域structLNode*next;//指针域}LNode,*LinkList;voi
4、dSort(LinkList&L){//排序算法如下：将L排序成非递减单链表q=L;p=q->next->next;q->next->next=NULL;while(p){While(q->next&&p->data>=q->next->data)q=q->next;s=p->next;p->next=q->next;q->next=p;p=s;q=L;}}//sortLL20151854035^151854035^20^qps第3章1、分析递归算法Fun（10）执行过程中的所有输出，请将分析结果填入下表。intFun(intx){inty;if(x<=0){
5、y=x/3-1;}else{y=Fun(x-3)+x;}printf(y);return(y);}递归执行第i次12345xy=Fun(x)Fun(10)的执行结果为：解：递归执行第i次12345x10741-2y=Fun(x)211140-1Fun(10)的执行结果为：-1041121因为：Fun(10)=Fun(10-3)+10Fun(7)=Fun(7-3)+7Fun(4)=Fun(4-3)+4Fun(1)=Fun(1-3)+1Fun(-2)=-2/3–1=-1所以：Fun(-2)=-2/3–1=-1输出：-1Fun(1)=Fun(1-3)+1=-1+1=
6、0输出：0Fun(4)=Fun(4-3)+4=0+4=4输出：4Fun(7)=Fun(7-3)+7=4+7=11输出：11Fun(10)=Fun(10-3)+10=11+10=21输出：21因此：Fun(10)的执行结果为：-10411212、简述下列算法的功能voidSplit(Lnode*s,Lnode*q){Lnode*p;p=s;while(p->next!=q)p=p->next;p->next=s;}voidAtoBB(Lnode*pa,Lnode*pb){//pa和pb分别指向单循环链表(结点数>1)中的两个结点.split(pa,pb);spl
7、it(pb,pa);}解：该算法的功能为：将原单循环链表从pa和pb所指向的结点断裂，即原来指向pb结点的链，转向指pa，而原来指向pa结点的链，转向指pb。这样就形成两个独立的单循环链表。8820151854035papbpapb88201518540353、试读下列栈和队列操作的算法，请给出调用并执行testit(3)后的所有输出结果。//Stack为栈，Queue为队列//InitStack(S)为构造一个空栈，InitQueue(Q)为构造一个空队列。//EnQueue(Q,nb)表示入队列操作；DeQueue(Q)表示出队列操作。voidtestit
8、(intm){StackS;Queue
