作业问题000讲解(10)

设n为正整数，给出下列各种算法关于n的时间复杂度和空间复杂度①voidfun1(intn){j=1;k=100;while(jn){k=k+1;j=j+2;}}②voidfun2(intb[n],n){fori=0ton-1{k=i;forj=i+1ton-1if(b[k]b[j])k=j;x=b[i];b[i]=b[k];b[k]=x;}}j取值1、3、5...n/2时间复杂度：f(n)=O(n)一个输入变量：n两个辅助变量：j、k空间复杂度：O(1)f(n)=(n-1)+(n-2+...+1=n(n-1)/2时间复杂度：f(n)=O(n2)四个辅助变量：i、k、j、xn+1个输入变量：b[n]、n空间复杂度：O(n)③voidfun3(intn){j=0;s=0;while(sn){j=j+1;s=s+j;}}④voidfun4(intb[n],n){fori=0ton-1if(b[i]n)a[n]=b[i]-n;fori=0ton-1b[i]=a[i];}s变化：1，1+2，1+2+3，...∴1+2+3+...+xn即一个输入变量：n两个辅助变量：j、s空间复杂度：O(1)f(n)=n+n时间复杂度：f(n)=O(n)n+1个输入变量：b[n]、nn+1个辅助变量：i、a[n]空间复杂度：O(n)nx(x+1)/2nxn时间复杂度：f(n)=O()2.2试写出在顺序存储结构下逆转线性表的算法，要求使用最少的附加空间。PROCEDURERevLst(v,n)m=int(n/2)fori=1tom{t=v(i);v(i)=v(n-i+1);v(n-i+1)=t;}return2.7试编写一个算法，将两个有序线性表合并成一个有序线性表PROCEDUREMergLst(v1,n1,v2,n2,v)i=j=k=1while(i=n1)and(j=n2)do{ifv1(i)v2(j)then{v(k)=v2(j);j=j+1;}else{v(k)=v1(i);i=i+1;}k=k+1}if(i=n1)fort=iton1do{v(k)=v1(t);k=k+1;}if(j=n2)fort=jton2do{v(k)=v2(t);k=k+1;}return或fori=0tom-1{t=v(i);v(i)=v(n-i-1);v(n-i-1)=t;}2.10写出逆转线性单链表的算法基本思想：将指针链逆序，结点不变ProcedureRevLst(V,Next,head)p=head;ifp=0then{print“空表”;return;}ifNext(p)=0thenreturn;q=Next(p);Next(p)=0;while(next(q)≠0)do{t=Next(q);Next(q)=p;p=q;q=t;}Head=q;Next(q)=preturn;或while(q≠0)do{t=Next(q);Next(q)=p;p=q;q=t;}Head=q;2.11设有两个有序线性单链表，头指针分别为AH与BH。试写出将这两个有序线性单链表合并为一个头指针为CH的有序线性单链表的算法。基本思想：将一个表向另一个表中插入结点，设删除BH指向的表，向AH指向的表中插入。PROCEDUREMergLst(v,next,AH,BH,CH)ifv(AH)V(BH)then{CH=AH;q=AH;AH=next(AH);}else{CH=BH;q=BH;BH=next(BH);next(q)=AH;}while(BH≠0)do{ifv(AH)v(BH)then{p=next(BH);next(BH)=AH;next(q)=BH;q=BH;BH=p}elseif(next(AH)≠0)then{q=AH;AH=next(AH);}else{next(AH)=BH);return}}return2.12设一个线性单链表，其结点值均为正整数,且按值从大到小连接。写出一个算法,将该线性单链表分解为两个线性单链表,其中一个链表中结点值均为奇数,而另一个链表结点值均为偶数,且这两个链表均按值从小到大链接基本思想：设分成两个单链表头指针基数为AH，偶数为BH，依次从原表中取出结点，判断结点值为奇还是偶，如为基数插入AH中，为偶数插入BH中PROCEDUREApaLst(v,next,head,AH,BH)p=head;AH=BH=0;while(p≠0)do{q=next(p);if(v(p)%2=0)thenif(BH=0)then{BH=p;Next(p)=0;}else{next(p)=BH;BH=p;}elseif(AH=0)then{AH=p;Next(p)=0;}else{next(p)=BH;AH=p;}p=q;}return;2.14设有一个线性单链表，其结点值均为正整数，试写出一个算法，反复找出链表中结点值最小的结点。并输出该值，然后将该结点从链表中删除，直到链表空为止。两种思想：①在链表中找最小者，找到后删除它、②找到最小者后将它交换到表第一个结点，再删除PROCEDUREPrintMin(v,next,H)ifH=0thenreturnifnext(H)=0then{outputv(H);return;}while(H≠0)do{k=next(H)while(k≠0)do{if(v(H)v(k)then{t=v(H);v(H)=v(k);v(k)=t;}k=next(k)}outputv(H)p=HH=next(H)dispose(p)return888165311537-845-6641366-272178842.15757133515233117522154-1271-975152.160900000080004000-60012341234560000-1000000000-80570030-640123456123490002.18写一算法，将给定的m×n稀疏矩阵转换成三列二维数组表示。ProcedureTurnM(V,m,n,B)k=1fori=1tomforj=1tonif(V(i,j)≠0then{k=k+1;B[k][1]=i;B[k][2]=j;B[k][3]=V(i,j);}B[1][1]=m;B[1][2]=n;B[1][3]=k;Return;-c+-dt+/syzf/xab**ghr/2.19(2)a*b+c/(d+t)-g*h/r-f(x,y/z,s)构建有序表达式树：-c+-dt+/syzf/xab**ghr/波兰表达式：ab*cdt+/+gh*r/-xyz/sf-将表达式转换成二叉树：对二叉树进行中序遍历2.20设树T的度为4，其中度为1，2，3，4的结点个数分别为4、2、1、1。问T中有多少叶子结点。结点数为：1*4+2*2+3*1+4*1+1(根结点)=15个结点叶子结点数为：15-(4+2+1+1)=7个2.21已知某二叉树前序序列为DBACFEG，中序序列为ABCDEFG。画出该二叉树，并写出该二叉树的后序序列。后序序列：ACBEGFDBDACFEG2.22设一棵完全二叉树具有1000个结点，问该完全二叉树有多少个叶子结点？有多少个度为2结点？有多少个度为1结点？若完全二叉树有1001个结点，再回答上述问题，并说明理由。由性质6，最后一个内部结点为1000/2=500有1000-500=500个叶子结点。由性质3，度为2的结点有500-1=499个度为1结点有1000-500-499=1个树有1001个结点时，叶子结点有1001-500=501个度为2的结点有501-1=500个度为1结点有1001-501-500=0个2.25若图n个结点，并用关联矩阵表示，则第k个结点度为多少？无向图：关联矩阵第k行或第k列中非零元素之和有向图：关联矩阵第k行和第k列中非零元素之和一、算法解题方案的准确完整描述，要求在有限存储空间内运行有限的时间得到正确结果。衡量一个算法好坏标准：时间复杂性、空间复杂性表示成问题规模的函数O(1)、O(n)、O(nlogn)、O(n2)等二、数据结构1、基本概念互相有关联的数据元素集合(D,R)，R反映D中数据元素之间关系。数据逻辑结构：数据元素之间的固有逻辑关系（线性结构、非线性结构）数据物理结构：数据元素及其关系在计算机中的存储方式，根据存储关系R的方式不同（顺序存储结构、链式存储结构）对编程而言，存储结构不同在于寻找前后件的方式不同数据结构的表示方法：集合、图形一个数据结构的图形表示，给出它的数据结构集合定义D={A,B,C,D,E,F}R={(B,A),(C,A),(C,E),(C,D),(D,B),(E,A),(E,C),(F,A),(F,B)}B=(D,R)BADCEF③数组长度固定线性表，不能进行插入、删除操作，只能进行查找：知道下标找地址顺序存储以行为主Adra(i,j)=Adra(1,1)+[(i-1)*n+j-1]*L以列为主Adra(i,j)=Adra(1,1)+[(j-1)*m+i-1]*L压缩存储如何压缩、如何复原；三种特殊压缩存储上（下）三角矩阵、对称矩阵、稀疏矩阵稀疏矩阵存储：顺序存储三列二维数组表示链式存储十字链表，每个结点五个域总行数总列数非零元素个数行...列...值...向下域向右域值域列域行域55811914325732444-1516537542-0270601000000407000003009123451234555341911423000000752245615000000H00000000-144735⑵非线性结构树、二叉树、图逻辑结构(结构特征)、基本概念及术语、存储结构树、二叉树①基本概念（根、叶子、父结点、子结点、结点度、树度、深度（高度）②二叉树存储顺序存储结构(添加一些空结点，使它变成为一棵完全二叉树)、链式存储结构③二叉树性质；完全二叉树、满二叉树的特点及性质④二叉树遍历：遍历概念（遵从某种规律或顺序，依次访问二叉树中的所有结点，使得每个结点都被访问且只被访问一次）遍历方法（前序遍历、中序遍历、后序遍历）遍历结果：得到二叉树所有结点的一个线性序列⑤二叉树应用：表达式的线性化，能将一般表达式化为(逆)波兰表达式(后缀表示)。图①基本概念有向图、无向图、有值图、入度、出度、度、连通图、非连通图、连通子图②图存储：顺序存储结构（关联矩阵(邻接矩阵)、求值矩阵）、链式存储结构（邻接表）111001000100101001000110101100100100BADCFEABCDEFAFBDCE60360123456ABCDEF2501502524032401③图遍历：遍历概念、遍历方法(纵向优先搜索法、横向优先搜索法）遍历结果：得到图中所有结点的一个线性序列111001000100101001000110101100100100BADCFEABCDEFAFBDCE60360123456ABCDEF2501502524032401纵向：ABCEDF横向：ABFCED