【精品】(0012)《数据结构》复习思考题答案.doc

《【精品】(0012)《数据结构》复习思考题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、(0012)《数据结构》复习思考题答案常丿IJ的存储表示方法冇哪几种？常用的存储表示方法有四种：顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。散列存储方法：就是根据结点的关键字肓接计算出该结点的存储地址。二、下列程序段带标号语句的频度和时间复杂度。(1)i

2、=o；while(I

3、k相等的元素，贝IJ语句三的频度为n；若a中的第一个元素a[0]等于k,则语句三的频度是常数0。在这种情况下，可用最坏情况下的时间复杂度作为时间复杂度。在此例屮即为O(n)。这样做的原因是：最坏情况下的时间复杂度是在任何输入实例上运行时间的上界。有时，也可能选择将算法的平均(或期望)时间复杂度作为讨论H标。所谓的平均时间复杂度是指所有可能的输入实例以等概率岀现的情况下算法的期望运行时间与问题规模的数量级的关系。此例屮，以k出现在任何位置的概率相同，都为1/m贝帰句三的执行频度为[0+l+2+...+(n-l)]/n=(n-l)/2。它决定了此程序段的平均时间复

4、杂度的数量级为f(n)=n,记作O(n)o(2)在计算包含调用语句的算法的语句频度时，需考虑到调用发生时在被调用算法屮各语句的执行情况。木题所示的递归调用较之非递归调用的分析更为复杂。由于k等于n是算法的出口条件，不妨首先分析算法pp(n)的简单情况,这时各语句的执行频度分别为：1,n+1,n,0,0,0;而当k=n-l,n-2,…，1时,语句的执行情况和调度情况，如下表所不。K值不考虑调用时各语句的执行频度调用情况语句1语句2语句3语句4语句5语句6n1n+1n000/n~l100321pp(n)n-2100431pp(n-l)•••••••••••••••

5、•••••••••1100n+1n1pp(2)对于21即pp⑴而言，备语句的执行次数还须将调用pp⑵时的执行次数累计到内，pp(2)各语句的执行次数又须将调用PP⑶时执行次数累计到内，……由此可的语句频度如下：语句1:1+1+…+1二n语句2:0+0+・・・+0+(n+l)=n+l语句3:0+0+…+0+n=n语句4:(n+l)+n+・・・+3=(n-l)(n+4)/2语句5:n+(n-1)+•••+2=(n-1)(n+2)/2语句6:1+1+….+l+0=n-l算法的时间复杂度可以基于频度最大的语句，应为0(n2)o三、算法的时间复杂度仅与问题的规模相关吗？

6、不，事实上，算法的时间复杂度不仅与问题的规模相关，还与输入实例屮的元素取值等相关,但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。四、常丿\的存储表示方法冇哪几种？常用的存储表示方法有四种：顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。索引存储方法：

7、除建立存储结点信息外，还建立附加的索引表来标识结点的地址。散列存储方法：就是根据结点的关键字貞接计算出该结点的存储地址。五、确龙下列算法屮输出语句的执行次数，并给出算法的时问复杂度。(1)voidcombi(intn){intl,j,k;for(1=1;I<=n;I++)for(j=I+1;j<=n;j++)for(k=j+l;k<=n;k++)cout«I,j,k;)(2)voidbinary(intn){while(n){cout«n;n=n/2;))(1)1取值范I韦I从l~n,j取值范用从1+1〜n,k取值范

8、韦

9、从j+1〜n,情况如下表所示:I值j值

10、k值

11、输出语句的执行次数123,4,…