（0012）《数据结构》复习思考题答案
1：[论述题]
1、算法的时间复杂度仅与问题的规模相关吗?
2、
下列程序段带标号语句的频度和时间复杂度。
( 1 ) I=0;
    while (I<N)&&(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
    else
    { 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、
常用的存储表示方法有四种：
顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。
链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。
索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。
散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。
 
1：[论述题]
1、何时选用顺序表、何时选用链表作为线性表的存储结构为宜?
2、为什么在单循环链表中设置尾指针比设置头指针更好?
3、确定下列算法中输出语句的执行次数，并给出算法的时间复杂度。
（1） void combi (int n)
{  int I,j,k;
    for ( I=1; I<=n; I++)
      for ( j=I+1; j<=n; j++)
        for ( k=j+1; k<=n; k++)
          cout<<I,J,K;}< st1:citation>

(2) void binary ( int n)
{  while(n){
    cout<<N;
    n=n/2;
          }}
4数据结构与算法分析答案、常用的存储表示方法有哪几种?
 
5.分析以下程序段的时间复杂度。
a=0；b=1；①
for（i=2；i〈=n；i++）②
{
s=a+b；③
b=a；④
a=S；⑤
}
6.对于一个栈，给出输入项A，B，C。如果输入项序列由A，B，C组成，试给出全部可能的输出序列
7、已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相同的元素。
 
参考答案：
1、答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：
1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。
2.基于时间的考虑。若线性表的操作主要是进行查，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。
2、答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和 rear, 查时间都是O(1)。 若用头指针来表示该链表，则查终端结点的时间为O(n)。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。