数据结构习题课1.ppt

《数据结构习题课1.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构习题第1章吉林大学计算机科学与技术学院谷方明感谢二班、三班的学委把作业按学号排序。这是一种积极的习惯。课堂练习求下述计算f=1！+2！+3！+…+n！的算法的时间复杂性voidfactorsum(intn){inti,j；intf,w；f=0；for(i=1;i<=n;i++){w=1；for(j=1;j<=i;j++)w=w*j;f=f+w;}return；}参考答案以乘法为基本运算最坏时间复杂度为T(n)=n(n+1)/2，渐近表示法O(n2)（或算法是n2阶的）1-2设数据的逻辑结构为L=(N,R)，其中，N={a,b,c,

2、d,e}R={r},r={,,,,,}请画出对应的逻辑结构，说明是何种结构图型结构：a有多个后继，e有多个前驱参考答案aedbc作业情况正确率：超过80%用圆圈表示结点，用直线箭头表示边结点名一般写在圆圈内有问题的画法无向边边共用线交叉：尽量避免作业1－4题目描述：【3】【10分钟】用反证法证明是无理数。参考答案假设不是无理数，那么一定是有理数，即存在p、q，使得=p/q，p、q互质。整理得p2=2*q2，因此p是偶数。设p=2*k，则有q2=2*k2，因此q也是偶数。这与p、q

3、互质矛盾。因此是无理数。其它做法有一种证法：p、q互质得到p2、q2互质。由p2=2*q2，可得p2、q2有公约数q2。（需要说明q不是1）唯一分解定理：2班李百林三种证法的同学：3班徐文峰（几何法）。作业情况正确率70%左右有问题的说法因为不是有理数或找不到分数、循环小数表示因为是无理数？（p,q）=2：改成p、q有公约数2表示成p/q，p、q互为质数，q>1或q>0等等作业1－5题目描述试用ADL语言编写一个算法，判断任一整数n是否为素数考察知识点用ADL描述算法特殊情况判断初始化核心处理步骤后处理算法的正确性证明很难，但验证较容易。

4、用边界条件和特殊数据验证，人工模拟算法执行。分析算法的效率参考答案1算法S(n.flag)/*判断整数n是否为素数，将结果保存到变量flag*/S1[n≤1？]IF(n≤1)THEN(flag←false.RETURN.)S2[初始化]i←2.flag←true.S3[求余判断]WHILE(i≤n-1)DO(IF(nMODi)=0THEN(flag←false.RETURN.)i←i+1.)▌参考答案2算法S(n.flag)/*判断整数n是否为素数，将结果保存到变量flag*/S1[n≤1？]IF(n≤1)THEN(flag←false.

5、RETURN.)S2[初始化]i←2.flag←true.S3[求余判断]WHILE(i≤nDIV2)DO(IF(nMODi)=0THEN(flag←false.RETURN.)i←i+1.)▌参考答案3算法S(n.flag)/*判断整数n是否为素数，将结果保存到变量flag*/S1[n≤1？]IF(n≤1)THEN(flag←false.RETURN.)S2[初始化]i←2.flag←true.S3[求余判断]WHILE(i≤n1/2)DO(IF(nMODi)=0THEN(flag←false.RETURN.)i←i+1.)▌作业情况正

6、确率不到50%有问题的做法特殊情况没有处理：1和2.不理解程序语句？For处理：IF(n%i==0)THENflag←0.ELSEflag←1.无返回值:RETURN.FORTODOIF……DO用ADL描述算法输入输出参数的确定：临时变量不是参数符号“.”的应用分隔输入输出参数一条语句的结束；能判断语句结束的问题可略去符号“▌”的应用：标志算法结束混杂C++语言FORi=2TOn-1STEPi++DO步骤说明有且精[]1-6分析下面程序段的时间复杂性ints=0,i,j,k;for(i=0;i<=n;i++)for(j

7、=0;j<=i;j++)for(k=0;k

8、,O(n2+1),O(n3-n2)按由低到高的顺序排列。其中，n是输入数据的规模。参考答案O(log2n)