数据结构期末综合练习四(算法分析题)

《数据结构期末综合练习四(算法分析题)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构（本科）期末综合练习四（算法分析题）1.指出算法的功能并求出其时间复杂度。intfun(intn){inti=1,s=1;while(s

2、N;k++)c[i][j]+=a[i][k]*b[k][j];}功能为：时间复杂性为：3.针对如下算法，回答问题：若数组A[n]={12,24,0,38,0,0,0,0,29,0,45,0},n=12，给出算法执行后数组A[n]的状态。templatevoidunknown(TA[],intn){intfree=0;for(inti=0;i

3、h()const;//计算表长度并返回，若表为空则返回0TRemove();//删除当前表项并返回其值，置下一表项为当前表项TFirst();//取表中第一个表项的值并返回，并置为当前表项TNext();//取当前表项后继表项的值并返回，//并把此后继表项置为当前表项若顺序表中存放的数据为{29,38,47,16,95,64,73,83,51,10,0,26}，表的长度为12，参数值s=10,t=30，说明算法执行后顺序表的状态和长度的变化。#include#include“SeqList.h”template

4、>voidunknown(SeqList&L,Ts,Tt){if(!L.Length()

5、

6、s>=t){cerr<<“表为空或参数值有误!”<=s&&temp<=t)L.Remove();else{temp=L.Next();i++;}}算法执行后顺序表中的数据：算法执行后顺序表的长度：5.设字符串String具有下列操作：intLength()const;//计算字符串的长度chargetData(k);//提取

7、字符串第k个字符的值若字符串Tar的值为“ababcabcacbab”，Pat的值为“abcac”时，给出算法执行后函数返回的结果。#include“String.h”intunknown(String&Tar,String&Pat)const{for(inti=0;i<=Tar.Length()–Pat.Length();i++){intj=0;while(j

8、eturn-1;}算法执行的结果是：6.阅读下列算法，并补充所缺内容。voidpurge_linkst(ListNode*&la){//从头指针为la的有序链表中删除所有值相同的多余元素，并释放被删结点空间ListNode*p,*q;if(la==NULL)return;q=la;p=la->link;while(p){if(p&&___(1)___){q=p;p=p->link;}else{q->link=___(2)___;delete(p);p=___(3)___;}}//while}//purge_linkst(1)(2)(3)7.设单链表

9、的存储结构为ListNode=(data,link)，表头指针为LH，所存线性表L=(‘a’,’b’,’c’,’d’,’e’,’f’,’g’)，若执行unknown(LH)调用下面程序，则写出执行结束后的输出结果。voidunknown（LinkNode*Ha）{//Ha为指向单链表的头指针if(Ha){unknown(Ha->link);cout<data;}}8.设单链表结点的结构为LNode=(data,link)，阅读下面的函数，指出它所实现的功能。intAA(LNode*Ha){//Ha为指向带表头附加结点的单链表的表头指针in

10、tn=0;LNode*p=Ha->link;while(p){n++;p=p->link;}return(n);28}算法