2013秋西南大学《数据结构》第二次作业

一、何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： 1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。

二、为什么在单循环链表中设置尾指针比设置头指针更好? 答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear-next-next 和 rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。 三、确定下列算法中输出语句的执行次数，并给出算法的时间复杂度。 （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;}  

(2) void binary ( int n) {  while(n){     cout<<n;     n=n/2;           }}  

(1)I取值范围从1～n，j取值范围从I+1~n，k取值范围从j+1~n，情况如下表所示：I值 j值 k值

输出语句的执行次数 1

2 3, 4, … ,n n-2 … … … n-1 n

1 n / / 2

3 4,5,…,n n-3 … … … n-1 n

1 n

/

/… … … … n-2

n-1 n

1 n / / n-1 n / / n

/

/

/… … … … n-2

n-1 n

1 n / / n-1 n / / n

/

/

/

所以，输出语句共执行次数为((n-2)+(n-3)+…+1)+((n-3)+(n-4)+…+1)+…+1 = (n-1)(n-2)/2+(n-2)(n-3)/2+…+1

= (((n-1)2+(n-2)2+(n-3)2+…+12)-((n-1)+(n-2)+(n-3)+….+1))/2 =((n-1)n(2n-1)/6-n(n-1)/2)/2

=(n(n-1)(2n-4))/12=n(n-1)(n-2)/6 (2) ceil(log2n);  

四、常用的存储表示方法有哪几种? 常用的存储表示方法有四种： 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。

链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。 五、分析以下程序段的时间复杂度。 a=0；b=1；①

for（i=2；i〈=n；i++）② {

s=a+b；③ b=a；④ a=S；⑤ } 解：

因为，语句①的频度是2； 语句②的频度是n； 语句③的频度是n-1； 语句④的频度是n-1； 语句⑤的频度是n-1；

故，该程序段的时间复杂度T（n）=2+n+3*（n-1）=4n-1=O（n）。  

六、对于一个栈，给出输入项A、B、C，如果输入项序列由ABC组成，试给出所有可能的输出序列。

A进 A出 B进 B出 C进 C出         ABC

A进 A出 B进 C进 C出 B出         ACB

A进 B进 B出 A出 C进 C出         BAC

A进 B进 B出 C进 C出 A出         BCA

A进 B进 C进 C出 B出 A出         CBA

不可能产生输出序列CAB

七、已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相同的元素。  解：  

本题的算法思想是：由于顺序表中元素已按元素值非递减有序排列，值相同的元素比为相邻的元素，因此依次比较相邻两个元素，若值相等，则删除其中一个，否则继续向后查找，直到最后一个元素。实现本题功能的函数如下： voiddel ( seqlist*a ) {

int i=0, j;

while ( i<a-length)

if ( a-data[i]!= a-data[i+1])i++;  else   {

for ( j=i; j<a-length; j++) a-data[j]=a-data[j+1];   a-length--;  } }