数据结构第二章习题课.doc

1、 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。
答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。
链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。
头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。

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

3、 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?
答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点，删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i越接近n则所需移动的结点数越少。

4、 为什么在单循环链表中设置尾指针比设置头指针更好?
答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和 rear, 查找时间都是O(1)。
  若用头指针来表示该链表，则查找终端结点的时间为O(n)。

5、 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?
答：我们分别讨论三种链表的情况。
1) 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。
2) 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。
3) 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。

6、下述算法的功能是什么?
LinkList Demo(LinkList L){ // L是无头结点单链表
   ListNode *Q,*P;
   if(L&&L->next){
      Q=L;L=L->next;P=L;
      while (P->next) P=P->next;
      P->next=Q; Q->next=NULL;
   }
   return L;
}// Demo
答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。

7、不带头结点的单链表head为空的判定条件是（ ）。
A、head=NULL B、head->next=NULL
C、head->next=head D、head!=NULL

8、在一单链表中，已知q所指的结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（ ）。
A、s->next=p->next;p->next=s; B、p->next=s->next;s->next=p;
C、q->next=s;s->next=p; D、p->next=s;s>next=q;

9、在一个单链表中，若p所指的结点不是最后结点，在p之后插入s结点，则执行（ ）。
A、s->next=p;p->next=s; B、s->next=p->next;p->next=s;
C、s->next=p->next;p=s; D、p->next=s;s->next=p;

10、在一个单链表中，若删除p所指结点的后续结点，则执行（ ）。
A、p->next=p->next->next; B、p=p->next;p->next=p->next->next;
C、p->next=p->next; D、p=p->next->next;

11、从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需要平均比较（ ）个结点？
A、n B、n/2 C、(n-1)/2 D、(n+1)/2

12、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ）。
A、O(1) B、O(n) C、O(n2) D、O(nlog2n)
13、给定有n个元素的向量，建立一个有序单链表的时间复杂度是（ ）。
A、O(1) B、O(n) C、O(n2) D、O(nlog2n)

14、带有一个头结点的单链表head为空的条件是 .

15、对于一个具有n个结点的单链表，在已知p所指结点之后插入一个新结点的时间复杂度为 ；在给定值为x的结点后插入一个新结点的时间复杂度是 。

16、设顺序表L是一个非递减有序表，试写一算法，将x插入L中，并使L仍是一个有序表。
解： 因已知顺序表L是递增有序表，所以只要从头找起找到第一个比它大(或相等)的结点数据，把x插入到这个结点所在的位置就是了。
算法如下：
void InsertIncreaseList(Sqlist *L,Datatype x)
{  int i;
for( i=0;ilength && L->data[i]length && L->data[i]>x;i++); //查找

ListInsert(*L,i,x);        // 调用顺序表插入函数
}// InsertDecreaseList

18、写一算法在单链表上实现线性表的ListLength(L)运算。
解：求单链表长只能用遍历的方法了，从头数到尾。
算法如下：
int ListLength( LinkList L )
{  int len=0; ListNode *p;
p=L;    //设该表有头结点
while (p->next)
  { p=p->next;
   len++;
}
return len;
}// ListLength

19、已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。
解：算法如下:
LinkList Link( LinkList L1 , LinkList L2 )
{//将两个单链表连接在一起
ListNode *p, *q;
p=L1;   q=L2;
while ( p->next ) p=p->next;    //查找终端结点
p->next = q->next ;        //将L2的开始结点链接在L1之后
return L1 ;
}// LinkList Link
分析：本算法的主要操作时间花费在查找L1的终端结点上，与L2的长度无关，所以本算的法时间复杂度为：m+1=O(m)

20、删除带头结点单链表L中的元素x。
解：算法如下:
Void delete(LinkList &L,ElemType x)
{ p=L->next; pre=L;
while(p)
{ if(p->data=x) { pre->next=p->next; free(p); p=pre->next; }
else { pre=p; p=p->next; }
}
}//delete

21、已知：Aa1,a2,……,an-1,an) B=(b1,b2,……,bn-1,bn)均为顺序表，试编写一个比较A、B大小的算法。
解：算法目标是分析两表的大小，所以不应破坏原表。表的大小指的是“词典顺序”，而非表的长度。
基本操作为：同步比较两个表中相应的数据元素。
假设：int compare(SqList La,SqList Lb)
循环条件：(i<=La.Length)&&( i<=Lb.Length)
主要操作为：if (La.elem[i]==Lb.elem[i]) i++;
else if (La.elem[i]urn -1;
else return 1;
循环结束时可能有三种情况：
l (i> La.Length)&&( i>Lb.Length) return 0;
l (i<=La.Length)&&(i>Lb.Length) return 1;
l (i>La.Length)&&(i<=Lb.Length) return -1;

22、删除有序表中所有其值大于minval且小于maxval的数据元素。
解：while(p&&p->data<=minval) { pre=p; p=p->next; }
if (p)
{ while (p&&p->datanext;
q=pre->next; pre->next=p;
while(q!=p) //q==p时，删除的为一个元素
{ s=q; q=q->next; free(s); } //释放中间结点

23、写一算法将单链表中值重复的结点删除，使所得结果表中各结点值均不相同。
解：本题可以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。
第二种算法是将单链表按值的大小排序，排好后的结点按相同的删除。
具体算法略。

24、试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。
void delete（Linklist &L）
[题目分析] 本题要求在单链表中删除最小值结点。单链表中删除结点，为使结点删除后不出现“断链”，应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。
LinkList Delete（LinkList L）
∥L是带头结点的单链表，本算法删除其最小值结点。
{ p=L->next； ∥p为工作指针，指向待处理结点。假定链表非空
pre=L； ∥pre指向最小值结点的前驱。
q=p； ∥q指向最小值结点，初始假定第一元素结点是最小值结点。
while（p->next!=null）
{if（p->next->datadata）{pre=p；q=p->next；}∥查最小值结点
p=p->next； ∥指针后移。
}
pre->next=q->next；∥从链表上删除最小值结点
free（q）； ∥释放最小值结点空间
}∥算法结束
[算法讨论] 算法中函数头是按本教材类C描述语言书写的。原题中void delete（linklist &L），是按C++的“引用”来写的，目的是实现变量的“传址”，克服了C语言函数传递只是“值传递”的缺点。

25、已知非空线性链表由list指出，链结点的构造为（data,link）。请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。
[题目分析] 本题要求将链表中数据域值最小的结点移到链表的最前面。首先要查找最小值结点。将其移到链表最前面，实质上是将该结点从链表上摘下（不是删除并回收空间），再插入到链表的最前面。
LinkList delinsert（LinkList list）
∥list是非空线性链表，链结点结构是（data，link），data是数据域，link是链域。本算法将链表中数据域值最小的那个结点移到链表的最前面。
{p=list->link；∥p是链表的工作指针
pre=list； ∥pre指向链表中数据域最小值结点的前驱
q=p； ∥q指向数据域最小值结点，初始假定是第一结点
while （p->link!=null）
{if（p->link->datadata）{pre=p；q=p->link；} ∥找到新的最小值结点
p=p->link；
}
if (q!=list->link) ∥若最小值是第一元素结点，则不需再操作
{pre->link=q->link； ∥将最小值结点从链表上摘下；
q->link= list->link；∥将q结点插到链表最前面。
list->link=q；
}
}∥算法结束
[算法讨论] 算法中假定list带有头结点，否则，插入操作变为q->link=list；list=q。

26、已知递增有序的单链表A,B分别存储了一个集合，请设计算法以求出两个集合A和B 的差集A-B（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。
[题目分析] 求两个集合A和B的差集A-B，即在A中删除A和B中共有的元素由于集合用单链表存储，问题变成删除链表中的结点问题。因此，要记住被删除结点的前驱，以便顺利删除被删结点。两链表均从第一元素结点开始，直到其中一个链表到尾为止。
void Difference（LinkList A，B，*n）
∥A和B均是带头结点的递增有序的单链表，分别存储了一个集合，本算法求两集合的差集，存储于单链表A中，*n是结果集合中元素个数，调用时为0
{ p=A->next； ∥p和q分别是链表A和B的工作指针
q=B->next； pre=A； ∥pre为A中p所指结点的前驱结点的指针
while（p!=null && q!=null）
if（p->datadata）{ pre=p；p=p->next；*n++；} ∥A链表中当前结点指针后移
else if（p->data>q->data）q=q->next； ∥B链表中当前结点指针后移
else {pre->next=p->next； ∥处理A，B中元素值相同的结点，应删除
u=p； p=p->next； free（u）；} ∥删除结点
}∥Difference

27、请写一个算法将顺序存储结构的线性表（a1...an）逆置为(an...a1)。
类似本题的另外叙述有：
(1) 设有一带头结点的单链表,编程将链表颠倒过来.要求不用另外的数组或结点完成.
(2) 设有一个带头结点的单向链表，数据项递减有序。写一算法，重新排列链表，使数据项递增有序，要求算法时间复杂度为O（n）。（注：用程序实现）
(3) 试编写求倒排循环链表元素的算法。
(4) 请设计算法将不带头结点的单链表就地逆置。
(5) 试编写算法 ，将不设表头结点的、不循环的单向链表就地逆转。
(6) 有一个单链表L（至少有1个结点），其头结点指针为head，编写一个过程将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。
[题目分析] 顺序存储结构的线性表的逆置，只需一个变量辅助空间。算法核心是选择循环控制变量的初值和终值。
void SeqInvert（ElemType a[ ]，int n）
∥a是具有n个元素用一维数组存储的线性表，本算法将其逆置。
{for（i=0；i<=（n-1）/2；i++）
{t=a[i]；a[i]= a[n-1-i]；a[n-1-i]=t；}
}∥SeqInvert
[算法讨论] 算法中循环控制变量的初值和终值是关键。C中数组从下标0开始，第n个元素的下标是n-1。因为首尾对称交换，所以控制变量的终值是线性表长度的一半。当n为偶数，“一半”恰好是线性表长度的二分之一；若n是奇数，“一半”是小于n/2的最大整数，这时取大于1/2的最小整数的位置上的元素，恰是线性表中间位置的元素，不需要逆置。
类似本题的其它题的解答：
这一组选了6个题，都是单链表（包括单循环链表）的逆置。链表逆置的通常作法是：将工作指针指向第一个元素结点，将头结点的指针域置空。然后将链表各结点从第一结点开始直至最后一个结点，依次前插至头结点后，使最后插入的结点成为链表的第一结点，第一个插入的结点成为链表的最后结点。