欢迎来到天天文库
浏览记录
ID:6723322
大小:1.42 MB
页数:31页
时间:2018-01-23
《严飞_《软件技术基础》沈被娜习题解答》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第二章2.1什么是数据结构?它对算法有什么影响?数据结构是指同一数据对象中各数据元素间存在的关系。数据结构对算法的影响:算法的实现必须借助程序设计语言中提供的数据类型及其运算。一个算法的效率往往与数据的表达形式有关,因此数据结构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的基本部分,它对程序的质量影响很大。2.2何谓算法?它与程序有何区别?广义地说,为解决一个问题而采取的方法和步骤,就称为“算法”。计算机算法是通过计算机能执行的算法语言来表达的。和程序的区别:一个程序包括两个方面的内容:(1)对数据的描述,即数据结构。(
2、2)对操作的描述,即算法。所以算法是程序的一个要素。2.3何谓频度,时间复杂度,空间复杂度?说明其含义。频度:在某个算法中某个语句被重复执行的次数就是此语句的频度。时间复杂度:是用来估算一个算法的执行时间的量,以算法中频度最大的语句来度量。空间复杂度:指在算法中所需的辅助空间的单元,而不包括问题的原始数据占用的空间。2.4试编写一个求多项式Pn=anxn+an-1xn-1+a1x+a0的值Pn(x0)的算法,要求用乘法次数最少,并说明算法中主要语句的执行次数及整个算法的时间复杂度。A=(a0,a1……an)mul=1//sum=a0fo
3、ri=1tonmul=mul*x//xsum=A[i]*mul+sum//求和end(i)进行了n次时间复杂度为:2n2.5计算下列各片段程序中X←X+1执行次数(1)fori=1tonforj=1toifork=1tojx←x+1end(k)end(j)end(i)执行次数:n*n*n(2)i←1whilei4、么?数据的存储结构:向量和链表。本质区别:向量是连续存放的,其存储空间是静态分配的,以存放顺序来表达元素的前后件的关系。链式存储结果不需要一组连续的存储单元,其数据元素可以分散存放在存储空间中,其元素关系由指针来指向。2.8已知线性表L(a1,a2,…,an)元素按递增有序排列。用向量作为存储结构,试编写算法:删除表中值在c与d之间(c<=d)的元素大于等于c序号4大于d序号11a1a2a3a4a5a6a7a8a9a10a11a12a130a14a15找到第1个大于等于c的元素,序号为s找到第一个大于d的元素,序号为tL[s]←L[t]5、L[s+1]←L[t+1]…L[s+m]←L[t+m]//s+m=t-1m=t–s-1L[s+i]←L[t+i]//i=0tot-s-1i=1;//i从1循环到ns=-1;//第1个大于等于c的元素序号t=-1;//第1个大于d的元素序号fori=1tonstep-1ifs==-1andL[i]>=c//找到第1个大于等于c的元素s=iift==-1andL[i]>d//找到第1个大于d的元素t=i;end(i)ifs!=-1andt!=-1i=swhilei6、elsereturn(错误没有找到元素在c和d之间)end(if)forj=cton-d+cL[j]<--L[j+d-c]//把j+d-c项给jEnd(j)N<--n-d+c//所有项数减少Return2.9线性表A,B中的元素为字符串类型,用向量结构存储,试编写算法,判断B是否为A的子序列(例如A=ENGLISH,B=LIS,则B为A的子序列)A[m]B[n]a1a2a3a4a5a6a7a8a9a10a11a12a130a14a15A:b1b2b3b4b5b6B:i=1检查A中第1个元素开始的字符串是否与B匹配i=2检查A中第2个元素7、开始的字符串是否与B匹配……i=m–n+1检查A中第(m-n+1)个元素开始的字符串是否与B匹配A[m]B[n]if(mnthenreturn(A字符串中第i个字符开始的子串与B匹配)end(i)renturn(找不到匹配的子串)设A,B两个线性表的元素个数为m,nIf(m<=n)then{return}Fori=0ton-1a=A[i]forj=0tom-18、if(a=B[j])then{b++}end(j)end(i)if(b=m)then{B为A的子集}return2.11写一个将向量L(a1,a2,an)倒置的算法。a1a2a3a4a5a6a7a8a9a1
4、么?数据的存储结构:向量和链表。本质区别:向量是连续存放的,其存储空间是静态分配的,以存放顺序来表达元素的前后件的关系。链式存储结果不需要一组连续的存储单元,其数据元素可以分散存放在存储空间中,其元素关系由指针来指向。2.8已知线性表L(a1,a2,…,an)元素按递增有序排列。用向量作为存储结构,试编写算法:删除表中值在c与d之间(c<=d)的元素大于等于c序号4大于d序号11a1a2a3a4a5a6a7a8a9a10a11a12a130a14a15找到第1个大于等于c的元素,序号为s找到第一个大于d的元素,序号为tL[s]←L[t]
5、L[s+1]←L[t+1]…L[s+m]←L[t+m]//s+m=t-1m=t–s-1L[s+i]←L[t+i]//i=0tot-s-1i=1;//i从1循环到ns=-1;//第1个大于等于c的元素序号t=-1;//第1个大于d的元素序号fori=1tonstep-1ifs==-1andL[i]>=c//找到第1个大于等于c的元素s=iift==-1andL[i]>d//找到第1个大于d的元素t=i;end(i)ifs!=-1andt!=-1i=swhilei6、elsereturn(错误没有找到元素在c和d之间)end(if)forj=cton-d+cL[j]<--L[j+d-c]//把j+d-c项给jEnd(j)N<--n-d+c//所有项数减少Return2.9线性表A,B中的元素为字符串类型,用向量结构存储,试编写算法,判断B是否为A的子序列(例如A=ENGLISH,B=LIS,则B为A的子序列)A[m]B[n]a1a2a3a4a5a6a7a8a9a10a11a12a130a14a15A:b1b2b3b4b5b6B:i=1检查A中第1个元素开始的字符串是否与B匹配i=2检查A中第2个元素7、开始的字符串是否与B匹配……i=m–n+1检查A中第(m-n+1)个元素开始的字符串是否与B匹配A[m]B[n]if(mnthenreturn(A字符串中第i个字符开始的子串与B匹配)end(i)renturn(找不到匹配的子串)设A,B两个线性表的元素个数为m,nIf(m<=n)then{return}Fori=0ton-1a=A[i]forj=0tom-18、if(a=B[j])then{b++}end(j)end(i)if(b=m)then{B为A的子集}return2.11写一个将向量L(a1,a2,an)倒置的算法。a1a2a3a4a5a6a7a8a9a1
6、elsereturn(错误没有找到元素在c和d之间)end(if)forj=cton-d+cL[j]<--L[j+d-c]//把j+d-c项给jEnd(j)N<--n-d+c//所有项数减少Return2.9线性表A,B中的元素为字符串类型,用向量结构存储,试编写算法,判断B是否为A的子序列(例如A=ENGLISH,B=LIS,则B为A的子序列)A[m]B[n]a1a2a3a4a5a6a7a8a9a10a11a12a130a14a15A:b1b2b3b4b5b6B:i=1检查A中第1个元素开始的字符串是否与B匹配i=2检查A中第2个元素
7、开始的字符串是否与B匹配……i=m–n+1检查A中第(m-n+1)个元素开始的字符串是否与B匹配A[m]B[n]if(mnthenreturn(A字符串中第i个字符开始的子串与B匹配)end(i)renturn(找不到匹配的子串)设A,B两个线性表的元素个数为m,nIf(m<=n)then{return}Fori=0ton-1a=A[i]forj=0tom-1
8、if(a=B[j])then{b++}end(j)end(i)if(b=m)then{B为A的子集}return2.11写一个将向量L(a1,a2,an)倒置的算法。a1a2a3a4a5a6a7a8a9a1
此文档下载收益归作者所有