数据结构 第二章：线性表

1、第二章线性表：习题习题一、选择题L是线性表，已知Length（L）的值是5,经运算?Delete（L, 2）后，length（L）的值是（c）。一5 B.0 C.4 D.6线性表中，只有一个直接前驱和一个直接后继的是（）。首元素B.尾元素C.中间的元素 D.所有的元素+3.带头结点的单链表为空的判定条件是（）。head= =NULL B. head-next= =NULLC. head-next=head D. head!=NULL不带头结点的单链表head为空的判定条件是（）。A. head=NULL B. head-next =NULLC.head-next=head D. head!=N

2、ULL非空的循环单链表head的尾结点P满足（）。A. p-next = =NULL B. p=NULLC. p-next=head D. p= =head线性表中各元素之间的关系是（c）关系。A.层次 B.网状C.有序 。.集合在循环链表的一个结点中有（）个指针。A. 1 B. 2 C. 0 D. 3在单链表的一个结点中有（）个指针。A. 1B. 2 C. 0 D. 3在双链表的一个结点中有（）个指针。A. 1B. 2 C. 0 D. 3在一个单链表中，若删除p所指结点的后继结点，则执行（）。p-next= p-next -next;p=p-next; p-next=p-next-next;

3、p-next= p-next;p=p-next-next;指针P指向循环链表L的首元素的条件是（）。A. P= =L B. P-next= =L C. L-next=P D. P- next= =NULL在一个单链表中，若在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;在一个单链表中，已知q是p的前驱结点，若在q和p之间插入 结点s,则执行（）。A. s-next= p-next; p-next=s; B.

4、p-next=s-next; s-next=p;?C. q-next=s; s-next=p; D. p-next=s; s-next=q;假设双链表结点的类型如下：typedef struct linknode（ int data; / 数据域struct linknode *llink; /指向前驱结点的指针域struct linknode *rlink; /指向后继结点的指针域bnode现将一个q所指新结点作为非空双向链表中的p所指结点的前驱 结点插入到该双链表中，能正确完成此要求的语句段是（）。q-rlink=p;q-llink=p-llink; p-llink=q; p-llink-

5、rlink=q;p-llink=q;q-rlink=p; p-llink-rlink=q; q-llink=p-llink;q-llink=p-rlink; q-rlink=p； p-link-rlink=q; p-llink=q;以上都不对在一个长度为n（n1）的单链表上，设有头和尾两个指针，执行（） 操作与链表的长度无关。删除单链表中的第一个元素删除单链表中最后一个元素在单链表第一个元素前插入一个新元素在单链表最后一个元素后插入一个新元素二、填空题 在线性表的顺序存储中，元素之间的逻辑关系是通过决定的；在线性表的链式存储中，元素之间的逻辑关系是通过 决定的。在一个单链表中，指针p所指结点为

6、最后一个结点的条件是O在一个单链表最后一个结点r之后插入结点s，则需执行的3条语句是； r=s; r-next= NULLo对于一个具有n个结点的单链表，在已知p所指结点后插入一 个新结点的时间复杂度是;在值域为给定值的结点后插入一个新结点的时间复杂度是O 单链表是的链接存储表示。 单链表中设置头结点的作用是o一7.在单链表中，除首元结点外，任一结点的存储位置由指示。在非空双向循环链表中，在结点q的前面插入结点p的过程如下：p-prior; q-prior; q-prior-next-;p; TOC o 1-5 h z p-next=q; ； 在双向链表中，每个结点有两个指针域，一个指向，另一

7、个指向。顺序表中逻辑上相邻的元素的物理位置紧邻。单链表中逻辑上相邻的元素的物理位置紧邻。三、简答题在单链表和双向链表中，能否从当前结点出发访问到任一结点？线性表的顺序存储结构具有3个不足：插入或删除过程中需要移动大量的数据元素。在顺序存储结构下，线性表的存储空间不便扩充。线性表的顺序存储结构不便于对存储空间的动态分配。线性表的链式存储结构是否一定都能够克服上述3点不足，请说 明之。用线性表的顺序存储结构描述一个城市的设计和规划是否合适？ 为什么？若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用 哪种存储结构？为什么？简述以下算法的功能。Status A(LinkedList L)( /

8、L是无表头单链表if (L&L-next)Q=L; L=L-next; P=L;while (P-next) (p=P-next；p-next=Q;Q-next=NULL;return OK;线性表有两种存储结构：一是顺序表，二是链表，试问：(1)如果有n个线性表同时存在，并且在处理过程中各表的长度会 动态地发生变化，线性表的总数也会自动地变化。在此情况下，应选哪种存储结构？为什 么？（2）如线性表的总数基本稳定，且很少进行插入和删除，但要求以 最快的速度存取线性表中的元素，那么应采取哪种存取结构？为什么？链表所表示的兀素是否是有序的？如果有序，则有序性体现在 何处？链表所表示的元素是否一定要

9、在物理上是相邻的？有序表的有序性该如何理解？四、算法设计题给定（已生成）一个带头结点的单链表，设head为头指针，结 点的结构为（data，next），data为整数元素，next为指针。试写出算法：按递增次序输出单链表 中各结点的数据元素并释放结点所占的存储空间。（要求：不允许使 用数组作辅助空间）。已知数组线性表数据类型如下，写一个算法，删除线性表中小 于0的所有元素。有一个单链表，其头指针为head，编写一个函数计算数据域为 x的结点个数。编写算法，实现在无头结点的线性链表L中删除第i个结点的 操作 Delete（L,i）。编写算法，实现在无头结点的线性链表L中第i个结点前插入 数据为e

10、的结点的操作insert（L，i，e）。设计将一个双向循环链表逆置的算法。已知递增有序的单链表A、B分别存储了一个集合，请设计算 法以求出两个集合A和B的差集A-B （即仅在A中出现而不在B中 出现的元素所构成的集合），并以同样的形式存储，同时返回该集合 的元素个数。已知两个整数集合A和B，它们的元素分别依元素值递增有序 存放在两个单链表H和Hb中，编写一个函数求出这两个集合的并集 丁并要求表示集合C的链表H的结点仍依元素值递增有序存放。已知A、B和C为3个递增有序的线性表，现要求对A表做如 下操作：删去那些在B表中出现又在C表中出现的元素。试对单链 表编写实现上述操作（要求释放表A中的无用结

11、点空间）的算法， 并分析算法的时间复杂度（注：题中没有特别指明表中的元素各不相 同）。有两个单链表 A 和 B，A： （a，a，-, a ，（b，b，-, b ，i 2ni 2n编写函数将其合并成一个链表C, C=（a ,b ,a ,b，a ,b .112 2 n n假设有两个按元素递增有序排列的线性表A和B,均以单链表 做存储结构。请编写算法，将表A和表B归并成一个按元素值非递减有序（允许值相同） 排列的线性表6并要求利用原表（即表A和表B）的结点空间存放 表C。12 .设在一个带表头结点的单链表中所有元素结点的数据值按递 增顺序排列，试编写一个函数，删除表中所有大于min小于max的元素（

12、若存在）。13.有两个循环链表，链头指针分别为L1和L2,要求将L2链表 链到L1链表之后，且链接后仍保持循环链表形式，试写出程序并估 计时间复杂度。第二章线性表 第2章线性表一、选择题1.C2.C3.B4.A5.C6.C7.A8.A9.B10.AIl.C12.B13.C14.C15. A,C,D二、填空题相邻位置，链接指针。 2. p-next=NULL。r-next=S. 4.O（1）,O（n）.5.线性表。6.插入和删除首元素时不必进行特殊处理。其直接前驱结点的链域。8. q-prior二p。9.前驱结点，后继结点。10.必定，不一定。三、简答题在单链表和双向链表中，能否从当前结点出发访

13、问到任一结 点？在单链表中，只能由当前结点访问其后继的任一结点，但因其没 有指向前驱的指针而无法访问其前驱结点。在双向链表中，由于当前 结点既有指向后继结点的指针，又有指向前驱结点的指针，所以在双 向链表中可以由当前结点出发访问表中的任何一个结点。不一定。由于链式存储需要额外的空间来存储指针，所以要 比顺序表存储多占用空间。在空间允许的情况下，链存储结构可以克 服顺序存储结构的弱点式，但空间不允许时，链式存储结构会出现新 的问题。不合适。因为一个城市的设计和规划涉及非常多的项目，比 较复杂，经常需要改动、扩充和删除各种信息，以适应不断发展的需 要，所以顺序不能很好地满足其需要。该线性表宜采用链

14、式存储结构。因为采用链式存储结构的线 性表，插入和删除操作只需要改变指针，时间复杂度0(1)；而采用顺 序存储结构的线性表插入和删除涉及到数据的大量移动，时间复杂度 为 0(n)。如果L的长度大于或等于2,则将首结点移到表尾。6.链式存储结构可以用任意的空间来存储线性表中的各数据元 素，其存储空间可以是连续的，也可以不连续;此外，这种存储结构 对元素进行插入和删除操作时都无需移动元素，而仅修改指针即可， 所以很适用于线性表容量变化的情况。由于顺序存储结构一旦确定了起始位置，线性表中的任何一 个元素都可以进行随机存取，即存取速度较高；并且，由于线性表的 总数基本稳定，且很少进行插入和删除，故这一

15、特点恰好避开了顺序 存储结构的缺点。因此，应选用顺序存储结构。链表所表示的元素是有序的，其有序性体现在逻辑上有序， 即按指针指向的顺序有序。链表所表示的元素在物理上不一定相邻， 当然也可能会相邻。有序表的有序性不仅体现在逻辑结构上有序，而 且在物理结构上也有序。四、算法设计题(对于有些题目只给出一种参考的解题思路)1. void increase (LkList*head) LkList *p, *q, *r; int min;p=head-next;while(p!=NULL) q=NULL;min=p-data;r=p;while(r-next! =NULL)if(r-next-data)

16、 next-data;r=r-next;printf( %d，min);if (q=NULL) p=p-next;else q-next=q-next-next;#define maxlen 100 /定义一个具体数字作为最大长度typedef struct int elem maxlen;int last; Listtp;算法如下：typedef struct( int elemmaxlen;int last; listtp;void Delete (listtp A) int i, j, k;k=0;if (A. last=0) printf( Its empty!)；else for (

17、i=l; i=A. last; i+)if (A.elemi 0)for(j =i;j data=x) n+;p=p-next; return n; status insert(LinkList *L,int i, Elentype e) (p=L;j=1;s= (LinkList) malloc (sizeof (Lnode);s-data=e;if(i=1) s-next=L; L=s;)elsewhile(p&jnext;+j;if( !p) return ERROR;s-next=p-next;p-next=s; return OK; 两个表的公共元素指的是既存在单链表A中又存在于单链

18、表 B中的元素，为了操作方便，先让单链表C带有一个头结点c,再后 将其删除。函数实现如下：Linklist Inter_eq(LinkList a,LinkList b) linkList p, q, r, c;c=( Linklist) malloc( sizeof (LNode); / 建立单链表 C的头指针r=C;p=a;q=b;while(p&q)(if (p-datadata) p=p-next; else if (p-dataq-data) q=q-next; else/*找到元素值相同的结点*/s=( LinkList) malloc( sizeof( LNode); s-dat

19、a=p-data; r-next=s;/*把s结点链接到c的末尾*/r=s;/*r始终指向C链表的最后一个结点while (p-data=p- next-data) /*跳过值相同的结点*/ p=p-next; p-p-next ;while(q-data=q- next-data) /*跳过值相同的结点*/ q=q-next;q=q-next;r-next=NUIL;S=c;c=c-next;free (s);return C：)invert (dLkList *head) dLkList p, q;p=head;do q=p-next;p-next=p-pre;p-pre=q;p=q; w

20、hile(p!=head);)void Sunset (LkList*A, LkList*B, LkList*C, int n) C=malloc (sizeof (LkList);r=C; n=0; p=A-next; q=B-next;switch(p!=NULL) & (q!二NULL) case p-dataq-data: q=q-next;case p-data=q-data: p=p-next; q=q- next;case p-datadata: (s=malloc( sizeof (lklist); s-data=p-data;p=p-next;n+;while (p!=NUL

21、L) s=malloc (sizeof (LkList); s-data=p-data;r-next=s ;r=s ;p=p-next;r-next=NULl;void MergeList(LinkList Ha, LinkList Hb, LinkList *Hc) LinkList p, q, r, s;Hc= ( LinkList) malloc ( sizeof) ( LNode) ;/*建立一个头结点，r总是指向Hc链表的最后一个 结点*/r=Hc; p=Ha; q=Hb;while (p&q)s= (LinkList) malloc ( sizof ( LNode) ;r-next

22、=s ; r=s ;if (p-datadata) s-data=p-data; p=p-next; else if (p-dataq-data) s-data=q-data; q=q-data; else s-data=p-data;p=p-next ;q=q-next ;while (q) s= (LinkList) malloc (sizeof (LNode);s-data=q-data;r-next=s ; r=s ;q=q-next;while (p) s= (LinkList) malloc (sizeof ( LNode ;s-data=p-data;r-next=s; r=s;

23、p=p-next;r-next=NULL;s=Hc;Hc=Hc-next：free (s);)void ListSubInter(LinkList *A, LinkList B, LinkList C)( LinkList L,p,pre,q,s;L=Inter_eq (B,C);Pre=A; p=A-next;While (p) q=L;while(q&p-datadata)q=q-next;if (p-data=q-data) s=p; p=p-next;pre-next-p; free(s);pre=p;p=p-next;)假设a,b,c分别为单链表A, B,C的头结点指针，同步遍历两

24、个链表，顺序复制A,B的结点到C中，直到链表遍历完为止。函数实 现如下：LinkList union (Linklist a, linkList b) linklist r, s, p, q, c;c=( LinkList) malloc( sizeof (LNode)/* 生成一个头结点* /r=C;p=a; q=b;while (p)(/*复制一个与A链表中结点相同的结点，把它链到c中*/s= (LinkList) malloc (sizeof (LNode);S - data=p-data;r-next=s; p=p-next;r=S;s=(LinkList) malloc (sizeof( LNode);s-data=q-data;r-next=s ; q=q-next;r=S：r-next=NULL;s=c;c=c-next;free (s);return C;)将A、B两个链表合成一个链表C且新链表必须使用A、B的 原有空间，因此需要一边遍历A、B两个表一边进行归并;在归并过程 中