} }
16、statas change (CirLinkList &L) {
If(L=null)
error(‘nodata’); else
If(p->next==null) error(‘can’t change’) else {
q=p->next; p->prior->next=q; q->prior=p->prior; p->next=q->next; q->next=p; p->prior=q; }
19、void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc)
{ //已知带头结点的单链线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。 LinkList pa, pb, pc; pa = La->next; pb = Lb->next;
Lc = pc = La; // 用La的头结点作为Lc的头结点 while (pa && pb) {
if (pa->data <= pb->data)
{ pc->next = pa; pc = pa; pa = pa->next; } Else
{ pc->next = pb; pc = pb; pb = pb->next; } }
pc->next = pa ? pa : pb; // 插入剩余段
free(Lb); // 释放Lb的头结点 } // MergeList_L
- 26 -
数据结构复习题：线性表 填空题
1、在线性结构中第一结点_____前驱结点，其余每个结点有且只有______个前驱结点；最后一个结点______后继结点。
2、对于顺序存储的线性表，当随机插入或删除一个元素时，约需平均移动表长______的元素。
3、对于长度为n的顺序表，插入或删除元素的时间复杂性为________；对于顺序栈或队列，插入或删除元素的时间复杂性为_________。
4、在线性表的顺序存储中，元素之间的逻辑关系是通过__________决定的；在线性表的链接存储中，元素之间的逻辑关系是通过____________决定的。
5、一个单链表中删除*p结点时，应执行如下操作: (1)q=p->next;
(2)p->data=p->next->data; (3)p->next=__________; (4)free(q);
6、对于线性表的顺序存储，需要预先分配好存储空间，若分配太多则容易造成存储空间的__________，若分配太少又容易在算法中造成__________，因此适应于数据量变化不大的情况；对于线性表的链接存储(假定采用动态结点)，不需要__________存储空间，存储器中的整个__________都可供使用，分配和回收结点都非常方便，能够有效地利用存储空间，在算法中不必考虑__________的发生，因此适应数据量变化较大的情况。
7、从顺序表中删除第i个元素时，首先把第i个元素赋给__________带回，接着从_____________开始向后的所有元素均___________一个位置，最后使线性表的长度_____________。
8、向一个长度为n的顺序表中的第i个元素(0<=i<=n-1)之前插入一个元素时，需向后移动______个元素。 9、在一个长度为n的顺序表删除第i个元素(0<=i<=n-1)时，需向前移动______个元素。 10、在单链表中设置头结点的作用是___________。
11、在单链表中，要删除某一指定的结点，必须找到该结点的_______结点。 12、访问单链表中的结点，必须沿着________依次进行。
13、在双链表中，每个结点有两个指针域，一个指向________，另一个指向_________。 14、在______链表上，删除最后一个结点，其算法的时间复杂度为O(1)。
15、在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作。 (1)s->next=_________。 (2)p->next=s; (3)t=p->data;
(4)p->data=_________。 (5)s-.data=_________。
16、在一个单链表中删除p所指结点时，应执行以下操作： q=p->next;
p_data=p->next->data; p->next=______; free(q);
17、在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=_______和p->next=________的操作。
18、对于一个具有n个结点的单链表，在*p结点后插入一个新结点的时间复杂度是________；在给定值为x的结点后插入一后新结点的时间复杂度是________。
- 27 -
19、在线性表的顺序存储中，元素之间的逻辑关系是通过______决定的；在线性表的链式存储中，元素之间的逻辑关系是通过______决定的。
20、在一个长度为n的顺序表中删除第i个元素(1<=i<=n)时，需向前移动_______个元素。 21、为了设置一个空的顺序表L，采用的操作是______。 22、删除顺序表的______元素，不需要移动任何元素。 23、删除顺序表的______元素，不需要移动的元素最多。
24、在顺序表_____元素后面插入一个元素，不需要移动任何元素。 25、插入顺序表的______元素，需要移动的元素最多。
26、在长度为n的顺序表L中查找指定元素值的元素，其时间复杂度为______。 27、求单链表长度的时间复杂度为_______。
28、删除单链表L中某结点*p之后的一个结点，其时间复杂度为______。 29、删除单链表L中某结点*p之前的一个结点，其时间复杂度为______。
30、在一个单链表(己知每个结点含有数据域data和指针域next)中删除p所指结点时，应执行以下操作： (1)q=p->next;
(2)p->data=q->data; (3)p->next = _____; (4)free(q);
31、在一个单链表中的p所指结点之后插入*s结点时，应执行s->next=_____和p->next______的操作。 32、对于一个具有n个结点的单链表，在*p结点后插入一个新结点的时间复杂度是_______;在给定值为x的结点后插入一个新结点的时间复杂度是_______。
33、删除双链表L中某结点*p之后的一个结点，其时间复杂度为_______。 34、删除双链表L中某结点*p之前的一个结点，其时间复杂度为_______。 35、在非循环的______链表中，可以用表尾指针代替表头指针。
36、对于双链表，在两个结点之间插入一个新结点需要修改的指针共______。 37、在一个双链表中，若要在*p结点之前插入结点*q，则执行的操作是______。 38、循环单链表L为空的条件是______。
39、在单链表中,结点与结点之间的逻辑关系不是通过存储单元的顺序来表示的,而是通过______来实现的. 40、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为____________，在表尾插入元素的时间复杂度为____________。
41、对于一个单链接存储的线性表，在表头插入结点的时间复杂度为____________，在表尾插入元素的时间复杂度为____________。
42、在线性表的顺序存储中，若一个元素的下标为i，则它的前驱元素的下标为____________，后继元素的下标为____________。
43、在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为____________，若p为一个数组a中的下标，则其后继结点的下标的____________。
44、在循环单链表中，最后一个结点的指针域指向____________结点。
45、在双向链表中每个结点包含有两个指针域，一个指向其____________结点，另一个指向其____________结点。
46、在循环双向链表中表头结点的左指针域指向____________结点，最后一个结点的右指针域指向____________结点。
47、在以ＨＬ为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为____________和____________。
50、在由数组a中元素结点构成的单链表中，在下标为i的结点的后面插入一个下标为j的结点时，需要进行的操作为____________和____________语句。
- 28 -
数据结构复习题答案：线性表 填空题
1、无|一|无|一 2、一半
3、O(n)|O(1)
4、相邻位置|链接指针 5、q->next?p->next->next
6、浪费|溢出|预先分配|动态存储区|溢出 7、变参或函数名|链接指针|前移|减1 8、n-i+1 9、n-i-1
10、简化插入、删除算法 11、前驱
12、指针链?next链 13、前驱结点|后续结点 14、循环双
15、p->next|s->data|t 16、p->next->next 17、p->next|s 18、O(0)|O(n)
19、物理存储位置|链域的指针值 20、n-i
21、L->length=0?L.length=0 22、最后一个 23、第一个 24、最后一个 25、第一个 26、O(n) 27、O(n) 28、O(1) 29、O(n)
30、q->next?p->next->next 31、p->next|s 32、O(1)|O(n) 33、O(1) 34、O(1) 35、双 36、4
37、p->prior->next=q;q->next=p;q->prior=p->prior;p->prior=q; 38、L->next==L
39、指向下一个结点的指针 40、O(n)| O(1) 41、O(1)|O(n)
- 29 -
42、i-1| i+1
43、p->next |a[p].next 44、表头
45、前驱|后继 46、表尾|表头
47、HL->next==NULL| HL->next==HL 50、a[j].next=a[i].next; | a[i].next=j;
数据结构复习题：线性表 问答题
1、线性表有两种存储结构：一是顺序表，二是链表。试问： (1)两种存储表示各有哪些主要优缺点?
(2)如果有n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性 表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么?
(3)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么，应采用哪种存储结构?为什么?
2、用线性表的顺序结构来描述一个城市的设计和规划合适吗?为什么? 3、在单链表和双向表中，能否从当前结点出发访问到任一结点? 4、编写下列算法
(1)向类型有list的线性表L的第i个元素（0≤i≤L.len）之后插入一个新元素x。 (2)从类型为list的线性表L中删除其值等于x的所有元素。
(3)将两个有序表A和B合并成一个有序表C，其中A，B，C均为list类型的变参。
5、编写下列算法，假定单链表的表头指针用HL表示，类型为linklist。 (1)将一个单链表中的所有结点按相反次序链接。 (2)删除单链表中第i个（i≥1）结点。 (3)删除单链表中由指针p所指向的结点。
(4)从带有附加表头结点的循环单链表中删除其值等于x的第一个结点。 (5)在单链表中指针p所指结点之前插入一个值为x的新结点。 (6)从循环单链表中查找出最小值。
(7)根据一维数组A(1:n)中顺序存储的具有n个元素的线性表建立一个带有附加表头结 点的单链表。
6、对链表设置头结点的作用是什么?(至少说出两条好处)
7、在单链表、双链表和单循环表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去？若可以，其时间复杂度各为多少？ 8、简述顺序表和链表存储方式的特点。
9、有两个递增有序表，设计一个算法将它们归并成一个有序表(假设每个表中没有重复关键字的元素，归并时重复关键字的元素只归并一次)。
数据结构复习题答案：线性表 问答题
1、解答：(1)顺序存储是按索引（隐含的）直接存取数据元素，方便灵活，效率高，但插入、删除操作时将引起元素移动，因而降低效率；链接存储内存采用动态分配，利用率高，但需增设指示结点之间有序关系的
- 30 -