(0012)《数据结构》复习思考题答案分析.pdf

（0012）《数据结构》复习思考题答案 1：[论述题] 1、算法的时间复杂度仅与问题的规模相关吗? 2、 下列程序段带标号语句的频度和时间复杂度。 ( 1 ) I=0; while (IN)(A[I]!=K) I++; //语句3 return(I); ( 2 ) n为不小于1 的整数（设k 的初值等于1） void pp ( int k) { if (k==n) //语句1 for (I=0; I 语句2 printf(a[I]); //语句3 els { for (I=k-1;I语句4 a[I]=a[I]+I; //语句5 pp(k+1); //语句6 } }//pp 3、常用的存储表示方法有哪几种? 参考答案： 1、不,事实上，算法的时间复杂度不仅与问题的规模相关，还与输入实例中的元 素取值等相关，但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关 的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。 2、 （1）这个算法完成在一维数组a[n]中查找给定值k 的功能。语句三的频度不仅 与问题的规模n 有关，还与输入实例中a 的各元素取值以及k 的取值相关，即与 输入实例的初始状态复杂有关。若a 中没有与k 相等的元素，则语句三的频度为 n；若a 中的第一个元素a[0]等于k，则语句三的频度是常数0。在这种情况下， 可用最坏情况下的时间复杂度作为时间复杂度。在此例中即为O(n)。这样做的 原因是：最坏情况下的时间复杂度是在任何输入实例上运行时间的上界。 有时,也可能选择将算法的平均(或期望)时间复杂度作为讨论目标。所谓的平均 时间复杂度是指所有可能的输入实例以等概率出现的情况下算法的期望运行时 间与问题规模的数量级的关系。此例中，以k 出现在任何位置的概率相同，都为 1/n，则语句三的执行频度为[0+1+2+…+(n-1)]/n=(n-1)/2。它决定了此程序段 的平均时间复杂度的数量级为f(n)=n,记作O(n)。 （2）在计算包含调用语句的算法的语句频度时，需考虑到调用发生时在被调用 算法中各语句的执行情况。本题所示的递归调用较之非递归调用的分析更为复 杂。 由于k等于n是算法的出口条件,不妨首先分析算法pp(n)的简单情况,这时各语 句的执行频度分别为:1,n+1,n,0,0,0; 而当k=n-1,n-2,…,1时,语句的执行情 况和调度情况,如下表所示。 不考虑调用时各语句的执行频度 K 值 调用情况 语句1 语句2 语句3 语句4 语句5 语句6 n 1 n+1 n 0 0 0 / n-1 1 0 0 3 2 1 pp(n) n-2 1 0 0 4 3 1 pp(n-1) … … … … … … … … 1 1 0 0 n+1 n 1 pp(2) 对于k=1即pp(1)而言，各语句的执行次数还须将调用pp(2)时的执行次数累计 到内，pp(2)各语句的执行次数又须将调用pp(3)时执行次数累计到内，……由 此可的语句频度如下： 语句１：1+1+…+1=n 语句２：0+0+…+0+(n+1)=n+1 语句３：0+0+…+0+n=n 语句４：(n+1)+n+…+3=(n-1)(n+4)/2 语句５：n+(n-1)+…+2=(n-1)(n+2)/2 语句６：1+1+….+1+0=n-1 算法的时间复杂度可以基于频度最大的语句，应为O(n2)。 4、 常用的存储表示方法有四种： 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结 点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存 储结构。 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑 关系是由附加的指针字