中学信息学《数据结构》习题及参考答案(2)

第 2 章 线 性 表

基础知识题

2.1① 描述以下三个概念的区别，头指针，头结点，首元结点（第一个元素结点）。 2.2① 填空题。

（1）在顺序表①中插入或删除一个元素，需要平均移动 元素，具体移动的元素与 有关。

（2）顺序表中逻辑上相邻的元素的物理位置 紧邻。单链表中逻辑的元素物理位置 紧邻。

（3）在单链表中，除了首元结点外，任一结点的存储位置由 指示。 （4）在单链表中设置头结点的作用是 。 2.3② 在什么情况下用顺序表比链表好？

2.4① 对以下单链表分别执行下列各程序段，并画出结果意图。

Q=P-> next; L=P->next;

R->data=R->data;

R->data=P->next->data;

P->next->next->next->data=P->data; T=P;

While (T!=NULL){ T->data=T->data * 2;T=T->next;}

(7) T= P

while (T-> next!=NULL) {T->data=T->data * 2;T=T->next;}

2.5① 画出执行下列各行语句后各指针及链表的示意图。 L= (LinKList)malloc(sizeof(L Node));P=L; for (i =1;i<=4;i++){

P->next =( LinKList)malloc(sizeof(LNode)); P=P->next;P->data= i* 2 – 1;

}

P-> next =NULL;

for (i=4;i>=4;i - -;) Ins_LinkList(L,i+1,i * 2); for (i=1;I<=3;i ++;)Del_LinkList(L, i ); 2.6② 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a.在P结点后插入S结点的语句序列是 b.在P结点前插入S结点的语句序列是 c.在表首插入S结点的语句序列是 d.在表首插入S结点的语句序列是

(1) P->next=S;

(2)P->next=P->next->next;

（1） （2） （3） （4） （5） （6）

(3)P->next=S->next; (4)S->next=P->next; (5)S->next=L;

(6)S->next=NULL; (7)Q=P;

(8)while (P->next!=Q)P=P->next;

(9) while (P->next!=NULL)P=P->next; (10) P=Q; (11) P=L; (12) L=S (13) L=P;

2.7② 已知L是带头结点的非空单链表，且P结点既不是首结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列是 a. 删除P结点的直接后继结点的语句序列是

b.删除P结点的直接后继结点的语句序列是 c.删除P结点的语句序列是 d.删除首元结点的语句序列是

e.删除尾元结点的语句序列是 . (1) P=P->mext; (2) P->next= P; (3) P->next=P;

(4) S->next=P->next->next; (5) While(P!=NULL)P=P->next;

(6) While(Q - >next! = NULL) {P=Q;Q=Q->next;} (7) While (P->next!=Q) P=P->next; (8) While(P->next->next!=Q)P=P->next; (9) While( P->next->next!=NULL)P=P->next (10) Q=P; (11) Q=P->next; (12) P=L; (13) L=L->next; (14) free(Q);

2.8② 已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适 的合适语序序列。

a.在P结点后插入S结点的语句序列是 b.在P结点前插入S结点的语句序列是 c.删除P结点的直接后继结点的语句序列是

d.删除P结点的直接前驱结点的语句序列是 e.删除P结点的语句序列是 (1) P->next=P->next->next; (2) P->priou=P->priou->priou; (3) P->next=S; (4) P->priou=S; (5) S->next=P;

(6) S->priou=P;

(7) S->next=P->next; (8) S->priou =P->priou; (9) P->priou->next=P->next; (10) P->priou->next=P; (11) P-> next -> priou =P; (12) P->priou->next=S; (13) P->priou->next=S;

(14) P-> next -> priou =P->priou; (15) Q=P->next; (16) Q=P->priou; (17) Free(p); (18) Free(Q);

2.9② 简述以下算法的功能。

（1） Status A(Linked List L) { //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; }//A

(2) Void BB(Lnode * s,Lodes * q){

p=s;

while(p->next!=q)q=p-next; p->next=s; }//BB

void AA(Lnode * pa,Lnode * pb){

//pa 和 pb分别是指向单循环链表的类型定义如下： BB(pa,pb); BB(pb,pa); }//AA

算法设计题

本章算法设计题涉及的顺序表和线性表的类型定义如下： # define LIST_INIT_SIZE 100 # define LISTINCREMENT 10 typedef struct{

Elem Type * elem; //存储空间基址 int length; //当前长度

int listsize; //当前分配的存储容量 } SqList; //顺序表类型 typedef struct Lnode{ Elem Type data;

Struct Lnode *next;

} Lnode,* LinkList; //线性链表类型

2.10② 指出以下算法中的错误和低效（既费时）之处，并将它改写成一个既正确

又高效的算法。

Status DeleteK(SqList&a,inti,int k){

//本过程从顺序存储结构的线性表中a中删除第 i个元素起的k个元素 if (i,1||k<0||i+k>a.length)return INFEASIBLE //参数不合法 else {

for (count = 1;count

//删除一个元素

for(j=a.length;j>=i+1;j--)a.elem[j - 1]=a.elem[j]; a.length--; }

return OK; }//DeleteK

2.22 ② 设顺序表中的数据元素递增有序。试写一算法，将插入到顺序表的适当

位置上，以保持该表的有序性。

2.12 ③设A=（a1 , …am）B=( b1 ,…,bm )均为顺序表，A’ 和B’分别为A 和B中

同前缀为（x,y,y,z），在两表中除最大共同前缀后的子表分别为A’=（x,z）和 B’=（y,x,x,z）若A’ =B’=空表，则A=B；若A’ =空表，而B’ ≠空表，或者两者均不为空表，且A’的首元小于B’的首元，则A＜B；否则A ＞B。试写一个比较A，B大小的算法（请注意：在算法中，不要破坏原表A与B，并且也不一定先求得A’和 B’才进行比较）。

2.13②试写一算法在带头结点的单链表结构上的实现线性表操作LOCATE（L，X）。 2.14② 试写一算法在带头结点的单链表结构上的实现线性表操作LENGTH（L）。 2.15②已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长

度分别为m和n。试写一算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点之后），假设指针hc指向连接后的链表 的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。

2.16③已知指针la和lb分别指向两个无头结点单链表的首元结点。下列算法是从

表la中删除自第i个元素起共len个元素后，，将它们插入到表lb中第i个元素之前，试问此算法是否正确？若有错，则请改正之。

Status Dlete AndInsertSub(Linked la,LinkedList lb,int i ,int j ,int len{

If (i <0||j<0||len<0)return INFEASIBLE; p=la;k=1;

while(k< i){p==p->next;k++;} q=p;

while(k<=len){q=q->next;k++;} s=lb;k=1;

while(knext;k++;} s->next=p;q->next=s->next; return OK;

}//Delete AndInsertSub

2.17② 试写一算法，在无头结点的动态单链表上实现线性表操作INSERT（L，i，b），

并和在带头结点的动态单链表上实现相同操作的算法进行比较。

2.18② 同2.17题要求，试写一算法，实现线性表操作DELETE（L，i）。

2.19③ 已知线性表中的元素以值递增有序排列，并以单链表作存储结构，试写出一

高效算法，删除表中所有值大于mink且小于maxk的元素，（若表中存在这样的元素）同时释放被删除结点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）

2.20②同2.19题条件，试写出一高效算法，删除表中所有值相同的多余元素（使得

操作后的线性表中所有元素的值均不相同），同时释放被删除结点空间，并分析你的算法的时间复杂度。

2.21③试写一算法，实现顺序表的就地逆置，即利用原表中的存储空间将线性表（a1 , …an）逆置为（an , …a1）。

2.22③是写一算法，对单链表实现就地逆置。 2.23③设线性表A=（a1 , …am）B=（b1 , …bm），试写一个按下列规则合并A，B为

线性表C的算法，即使得

C=（a1 , b1, …am ，bm , bm+1…bn）当m≤n 时；或者 C=（a1 , b1, …an ，bn , an+1…am） 当m＞n 时。

线性表A，B，C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成，注意：单链表的长度值m和n均未显示存储。

2.24④假设有两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结

构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。

2.25④假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同

一表中的元素各不相同），现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素也依值递增有序排列，试对顺序表编写求C的算法。

2.26④ 对2.25题。试对单链表编写求C的算法

2.27④对2.25题的条件作以下两点修改，对顺序表重新编写求得C的算法。

（1）假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C

中的元素值各不相同；

（2）利用A表空间存放表C。

2.28④对2.25题的条件作以下两点修改，对顺序表重新编写求得C的算法。

（1）假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C

中的元素值各不相同；

（2）利用原表（A表或B表）中的结点构造C，并释放A表中的无用节点空

间。

2.29⑤已知A，B和C为三个递增有序的线性表C，现要求对A表中作如下操作；删

除那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作算法，并分析你的算法的时间复杂度，（注意；题中没有特别指明同一表中的元素各不相同）。

2.30⑤要求同2.29题，试对单链表编写算法，请释放A表中的无用结点空间。

2.31②假设某个单向循环链表的长度大于1，且表中即无头结点也无头指针。已知s

为指向链表中的某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱节点。

2.32②已知有一个单向循环链表，其每一个结点中含三个域：pre，data和next，其中

data为数据域，next为指向后继结点的指针域，pre也为指针域，但它的值为空（NULL），