《计算机软件技术基础》课后题答案

数据结构习题答案第一节概论一\选择题.要求同一逻辑结构的所有数据元素具有相同的特性,这意味着（）〇A,数据元素具有同一的特点・B.不仅数据元素包含的数据项的个数要相同,而且对应数据项的类型要一致C,每个数据元素都一样D.数据元素所包含的数据项的个数要相等.数据结构是ー门研究非数值计算的程序设计问题中计算机的（（1））以及它们之间的（（2））和运算的学科。（1）A,操作对象 B.计算方法・C.物理存储D,数据映像⑵A.结构・B.关系 C.运算 D,算法3.数据结构被形式地定义为（D,R）,其中D是（（1））的有限集合,R是D上（（2））的有限集合。（1）A,算法・B.数据元素C,数据操作D.逻辑结构（2）A,操作B,映像C,存储・D.关系4.在数据结构中,从逻辑上可以把数据结构分为（）〇A.动态结构和静态结构B.紧凑结构和非紧凑结构*C.线性结构和非线性结构D,内部结构和外部结构5.线性表的顺序存储结构是一种（）的存储结构。*A.随机存取 B.顺序存取C.索引存取D.Hash存取.算法分析的目的是（）〇A.找出数据结构的合理性B,研究算法中的输入和输出的关系・C.分析算法的效率以求改进D,分析算法的易懂性和文档性.计算机算法指的是（（1））,它必须具备输入、输出和（（2））等五个特征。A.计算方法 B,排序方法 ・C.解决某ー问题的有限运算序列 D.调度方法A.可行性、可移植性和可扩充性・B.可行性、确定性和有穷性C,确定性,有穷性和稳定性D.易读性、稳定性和安全性.线性表若采用链表存储结构,要求内存中可用存储单元的地址（）〇A,必须是连续的 B,部分必须是连续的 C.—定是不连续的 ・D.连续不连续都可以.在以下的叙述中,正确的是（）〇A.线性表的线性存储结构优于链式存储结构*B.二维数组是它的每个数据元素为ー个线性表的线性表C.栈的操作方式是先进先出D•队列的操作方式是先进后出10.根据数据元素之间关系的不同特性,以下四类基本的逻辑结构反映了四类基本的数据组织形式,其中解释错误的是（）〇*A.集合中任何两个结点之间都有逻辑关系但组织形式松散B.线性结构中结点按逻辑关系依次排列形成一条“锁链”C,树形结构具有分支、层次特性,其形态有点像自然界中的树D.图状结构中的各个结点按逻辑关系互相缠绕,任何两个结点都可以邻接11.以下说法正确的是（）〇A,数据元素是数据的最小单位B,数据项是数据的基本单位C,数据结构是带有结构的各数据项的集合・D.数据结构是带有结构的数据元素的集合二、判断题X1.数据元素是数据的最小单位。丿2.数据结构是带有结构的数据元素的集合。V3,数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。X4.数据项是数据的基本单位。V5,数据的逻辑结构是指各数据元素之间的逻辑关系,是用户按使用需要建立的。V6.数据的物理结构是数据在计算机中实际的存储形式。X7.算法和程序没有区别,所以在数据结构中二者是通用的。V8.顺序存储结构属于静态结构,链式存储结构属于动态结构。三、填空题1.所谓数据的逻辑结构指的是数据元素之间的 逻辑关系〇2,数据结构是相互之间存在ー种或多种特定关系的数据元素的集合,它包括三方面的内容一数据的逻辑结构、数据的存储结构、对数据施加的操作ー〇.数据的逻辑结构包括集合结构ー、线性结构ー、ー树型结构和一图状结构四种类型。.在线性结构中,开始结点ー没有一前驱结点,其余每个结点有且只有——个ー个前驱结点。.在树形结构中,根结点只有一ー个ー,其余每个结点有且只有一ー个一前驱结点;叶结点没有一后继结点,其余每个结点的后继结点可以有—任意个.在图形结构中,每个结点的前驱结点和后继结点可以有一任意个ー〇.算法的五个重要特性是一可行性一、ー确定性ー、一有穷性一、ー输入—、ー输出—。.下列程序段的时间复杂度是ー。（n）ー〇for（i=l；i<=n；i++）A[i,i]=0；.下列程序段的时间复杂度是ー0（n2）ー〇S=0；for（i=l；i〈=n；i++）for（j=l；j<=n；j++） s=s+B[i,j]；sum=s；.存储结构是逻辑结构的一物理—实现。11.从数据结构的观点看,通常所说的“数据”应分成三个不同的层次,即—数据—、—数据元素一和—数据项ー〇12,根据需要,数据元素又被称为—结点—、—记录、元素_或ー顶点ー。13,通常,存储结点之间可以有一顺序存储_、链式存储—、索引存储—、一散列存储.四种关联方式,称为四种基本存储方式。.通常从ー确定性一、一可读性一、ー健壮性一、一高效性一等几方面评价算法(包括程序)的质量。.ー个算法的时空性能是指该算法的ー时间复杂度一和一空间复杂度ー,前者是算法包含的ー计算量—,后者是算法需要的ーーー存储量—。.在一般情况下,ー个算法的时间复杂度是ー问题规模—的函数。.常见时间复杂度的量级有:常数阶0(_1一)、对数阶0(ーーlog2n)、线性阶0(—n—)、平方阶0(_n2_)和指数阶0(_21)。通常认为,具有指数阶量级的算法是ー不可行一的。.数据结构的基本任务是数据结构的—设计—和—实现ー。.数据对象是性质相同的ー数据元素一的集合。.抽象数据类型是指ー个ー数学模型一以及定义在该模型上的ー组操作。四、应用题1.分析下列程序段的时间复杂度。1=1;WHILE(i<=n) i=i*2；答:0(log2n)2,叙述算法的定义及其重要特性。答:算法是对特定问题求解步骤的ー种描述,是指令的有限序列。其中每一条指令表示一个或多个操作。算法应该具有下列特性:可行性、确定性、有穷性、输入和输出。.简述下列术语:数据,数据元素,数据结构,数据对象。答：数据是信息的载体,是描述客观事物的数、字符,以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位。在不同的条件下,数据元素又可称为元素、结点、顶点、记录等。数据结构是指相互之间存在着ー种或多种关系的数据元素的集合。数据对象是性质相同的数据元素的集合。.逻辑结构与存储结构是什么关系?答:在数据结构中,逻辑结构与存储结构是密切相关的,存储结构不仅将数据元素存储到计算机中,而且还要表示各数据元素之间的逻辑关系。逻辑结构与计算机无关,存储结构是数据元素之间的关系在计算机中的表示。.将数量级ク°,n,n2,n\nlog2n,log2n,2'\n!,(2/3)、帯/3按增长率进行排列。答:(2/3)n,210,log2n,n,n,nlog2n,n2,n3,2'\n!.设有数据逻辑结构为:D={kl,k2,k3,…，k9},R={<kl,k3>,<kl,k8>,<k2,k3>,<k2,k4>,<k2,k5>,<k3,k9>,<k5,k6>,<k8,k9>,<k9,k7>,<k4,k6>},画出这个逻辑结构的图示,并确定相对于关系R,哪些结点是开始结点,哪些结点是终端结点?答:图略。开始结点kl、k2,终端结点k6、k7o.设有如图1.1所示的逻辑结构图,给出它的逻辑结构,并说出它是什么类型的逻辑结构。答:数据逻辑结构为:D={kl,k2,k3,…，k8},R={<kl,k2>,<kl,k3>,<k3,k5>,<k3,k4>,<k4,k7>,<k4,k6>,<k5,k8>},其逻辑结构类型为树型结构。.分析下列程序的时间复杂度(设n为正整数)。(1)intrec(intn){if(n=l)return(1) ； elsereturn(n*rec(n-l))； }(2)x=91；y=100；While(y>0)if(x>10)y--；⑶i=1；j=0；while(i+j〈=n)if(i〉j)j++;elsei++;(4)x=n；yニ〇;while(x>=(y+1)*(y+1)) y++；答:⑴O(n)(2)0(1) (3)0(n) (4)0(n1/2).设n为正数。试确定下列各程序段中前面加记号@的语句的频度:(l)i=l；kニ〇;while(i<=n-l) {@k+=10*i； i++； )k=0；for(i=l；i<=n；i++)for(j=i；j<=n：j++) @k++；答:(l)n-l(2)n+(n-l)+……+l=n(n+l)/2第二节线性表ー、选择题.线性结构中的ー个结点代表一个()〇*A.数据元素 B.数据项C.数据D.数据结构.线性表L=(al,a2,•••,ai,••,an),下列说法正确的是()〇A,每个元素都有一个直接前驱和直接后继 B.线性表中至少要有一个元素C,表中诸元素的排列顺序必须是由小到大或由大到小的D.・除第一个元素和最后ー个元素外其余每个元素都有一个且仅有ー个直接前驱和直接后继.顺序表是线性表的（）〇A・链式存储结构・B.顺序存储结构C.索引存储结构D,散列存储结构.对于顺序表,以下说法错误的是（）〇*A.顺序表是用ー维数组实现的线性表,数组的下标可以看成是元素的绝对地址B.顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C.顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻D.顺序表的特点是:逻辑上相邻的元素,存储在物理位置也相邻的单元中.对顺序表上的插入、删除算法的时间复杂度分析来说,通常以（）为标准操作。A,条件判断*B.结点移动C,算术表达式D.赋值语句.对于顺序表的优缺点,以下说法错误的是（）〇A.无需为表示结点间的逻辑关系而增加额外的存储空间B.可以方便地随机存取表中的任一结点*C.插入和删除操作较方便D.由于顺序表要求占用连续的空间,存储分配只能预先进行（静态分配）.在含有n个结点的顺序存储的线性表中,在任ー结点前插入ー个结点所需移动结点的平均次数为（）〇A.n*B.n/2C.(n-l)/2D.(n+l)/28,在含有n个结点的顺序存储的线性表中,删除ー个结点所需移动结点的平均次数为()〇A.nB.n/2 *C.(n'l)/2D.(n+l)/29.带头结点的单链表为空的条件是()〇A.head=NULL*B. headー〉next二NULLC.headー〉next二headD.head!=NULL10.非空单循环链表head的尾结点・p满足()〇A. p一〉next二NULL B.p=NULL*C.p-〉next二head D.p二head11.在双循环链表的・P结点之后插入・s结点的操作是()〇p-〉next=s；s-〉prior=p；p-〉next-〉prior二s；sー〉next=p-〉next； B. pー〉next二s；pー〉next-〉prior二s；s-〉prior=p：sー〉next=p-〉next；C.s->prior=p；sー〉next=p-〉next；pー〉next二s；pー〉nextー〉prior二s； *D. s-〉prior二p；sー〉next=p-〉next；pー〉next-〉pror=s；p-〉next二s；12,在ー个单链表中,已知・q结点是・p结点的前驱结点,若在・q和・p之间插入结点・s,则执行()〇A. s-〉next=p-〉next ； pー〉next二s ；p-〉next=s-〉next；sー〉next二p；*C・q-〉next二s;sー〉next=p； D.p-〉next二s;sー〉next二q；13,在ー个单链表中,若・p结点不是最后结点。在*p之后插入结点・s,则执行()〇A.s->next=p；p->next=s;*B.s->next=p->next；pー〉next二s；sー〉next=p-〉next； p=s；D.p->next二s；sー〉next二p;14.若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱元素,则采用()存储方式最节省时间。*A.顺序表B.单链表C.双链表D.单循环链表15.设rear是指向非空带头结点的单循环链表的尾指针,则删除表头结点的操作可表示为()〇A.p二rear；rear=rearー〉next；free(p)B. rear=rearー〉next ；free(rear)；C.rear二rearー〉next-〉next； free(rear)；*D . p=rear-〉next-〉next ；rear-〉next-〉next=p-〉next；free(p)；16.在ー个单链表中,若删除・p结点的后继结点,则执行()〇*A.q=p-〉next；p-〉next二qー〉next；free(q)；B.p=p-〉next；pー〉next=p-〉next-〉next；free(p)；C.p-〉next二pー〉next；free(p->next)；D.p=p-〉next-〉next；free(p->next)；17.设指针p指向双链表的某ー结点,则双链表结构的对称性可用()式来刻画。A. p-〉prior-〉nextー〉ニニpー〉next-〉nextB ・ pー〉prior-〉priorニニpー〉nextー〉prior*C ・ pー〉priorー〉next-〉ニニpー〉next->priorD.p-〉next-〉nextニニp-〉prior-〉prior18,在循环链表中,将头指针改设为尾指针rear后,其头结点和尾结点的存储位置分别是（）〇A.rearネロrear-〉nextー〉next*B.rear-〉next外口rearC.rearー〉nextー〉nextネロrearD.rearネロrear->next.循环链表的主要优点是（）〇A.不再需要头指针了B.已知某个结点的位置后,容易找到它的直接前驱C.在进行插入、删除操作时,能更好地保证链表不断开・D.从表中任一结点出发都能扫描到整个链表.在线性表的下列存储结构中,读取元素花费时间最少的是（）〇A.单链表B.双链表C.循环链表・D.顺序表二、判断题VI.顺序存储的线性表可以随机存取。X2.顺序存储的线性表的插入和删除操作不需要付出很大的代价,因为平均每次操作只有近一半的元素需要移动。V3.线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的特性,因此是属于同一数据对象。X4.在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上不一定相邻。V5.在线性表的链式存储结构中,逻辑上相邻的元素在物理位置上不一定相邻。V6.在单链表中,可以从头结点开始查找任何ー个元素。X7.线性表的链式存储结构优于顺序存储结构。V8,在线性表的顺序存储结构中,插入和删除元素时,移动元素的个数与该元素的位置有关。X9.在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存取的存储结构。X10.顺序存储方式只能用于存储线性结构。三、填空题.为了便于讨论,有时将含n(n>0)个结点的线性结构表示成(al,a2,an),其中每个ai代表ー个ー结点ー。al称为ー第一个ー结点,an称为—最后ー个ー结点,i称为ai在线性表中的一位置ー。对任意ー对相邻结点ai、ai+1(l^i<n),ai称为ai+1的直接一前驱_,ai+1称为ai的直接ー后继 。.线性结构的基本特征是:若至少含有一个结点,则除起始结点没有直接一前驱一外,其他结点有且仅有一个直接一前驱」除终端结点没有直接ー后继一外,其他结点有且仅有一个直接一后继_。.所有结点按ー对ー的邻接关系构成的整体就是ー线性一结构。.线性表的逻辑结构是ー线性，吉构,其所含结点的个数称为线性表的ー长度ー。.在单链表中,删除p所指结点的直接后继的操作是q=p-〉next；pー〉next=q->next；free(q)；•.非空的单循环链表head的尾结点(由指针p所指)满足_pー〉next二head〇.rear是指向非空带头结点的单循环链表的尾指针,则删除起始结点的操作可表示为ーーp二rear-〉next；q=p-〉next；p-〉next=q-〉next；free(q)；〇.对于ー个具有n个结点的单链表,在p所指结点后插入一个结点的时间复杂度为在给定值为x的结点后插入新结点的时间复杂度为_0(n)_o.单链表表示法的基本思想是用一指针ー一表示结点间的逻辑关系。.在顺序表中插入或删除ー个元素,平均需要移动一一半一元素,具体移动的元素个数与一元素的位置一有.在ー个长度为n的向量的第i(lくiWn+1)个元素之前插入ー个元素时,需向后移动n-i+1ー个元素。12,在一个长度为n的向量中删除第i(lWiくn)个元素时,需向前移动ーn-iー个元素。.在双链表中,每个结点有两个指针域,ー个指向一前驱—,另ー个指向ー后继ー一〇.在ー个带头结点的单循环链表中,p指向尾结点的直接前驱,则指向头结点的指针head可用p表示为head=_pー〉next-〉next；〇.设head指向单链表的表头,p指向单链表的表尾结点,则执行pー〉next二head后,该单链表构成一单循环链表ー〇16,在单链表中,若p和s是两个指针,且满足p->next与s相同,则语句p-〉next二sー〉next的作用是ー删除—s指向的结点。.设r指向单循环链表的最后ー个结点,要在最后ー个结点之后插入s所指的结点,需执行的三条语句是s-〉next=r-〉next—；r-〉next=s；r=s；.在单链表中,指针p所指结点为最后一个结点的条件是—pー〉next二NULL〇.在双循环链表中,若要在指p所指结点前插入s所指的结点,则需执行下列语句:sー〉next二p；sー〉prior=p-〉prior；p-〉prior-〉next二s；pー〉prior二s；.在单链表中,若要在p所指结点之前插入s所指的结点,可进行下列操作:sー〉next=pー〉next； pー〉next二s；temp=p-〉data；pー〉data=一s->data； s-〉data=temp四、应用题.描述以下三个概念的区别：头指针,头结点,首元结点（第一个元素结点）。答:首元结点是指链表中存储的线性表中的第一个数据元素的结点。为了操作方便,通常在链表的首元结点之前附设ー个结点,称为头结点。头指针是指向链表中的第一个结点的指针。.何时选用顺序表,何时选用链表作为线性表的存储结构为宜?答:从空间上来看,当线性表的长度变化较大、难以估计其规模时,选用动态的链表作为存储结构比较合适,但链表除了需要设置数据域外,还要额外设置指针域,因此当线性表长度变化不大、易于事先确定规模时,为了节约存储空间,宜采用顺序存储结构。从时间上来看,若线性表的操作主要是查找,很少进行插入和删除操作时,应选用顺序表。对于频繁进行插入和删除操作的线性表,宜采用链表作为存储结构。.在顺序表中插入和删除ー个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?答：平均移动表中大约一半的结点,插入操作平均移动n/2个结点,删除操作平均移动(nT)/2个结点。具体移动的次数取决于表长和插入、删除的结点的位置。.为什么在单循环链表中设置尾指针比设置头指针更好?答:单循环链表中无论设置尾指针还是头指针都可以遍历表中任一个结点,但设置尾指针时,若在表尾进行插入或删除操作可在。(1)时间内完成,同样在表头进行插入或删除操作也可在0(1)时间內完成。但若设置的是头指针,表尾进行插入或删除操作,需要遍历整个链表,时间复杂度为o(n)。.双链表和单循环链表中,若仅知道指针P指向某个结点,不知道头指针,能否将结点・P从相应的链表中删除?若可以,其时间复杂度各为多少?答:能删除。双链表上删除P所指向的结点的时间复杂度为0(1),单循环链表上删除P所指向的结点的时间复杂度为0(n)。.下列算法的功能是什么?LinkList*testl(LinkList*L){//L是无头结点的单链表LinkList*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；}returnL；}答:如果长度大于1,则将首元结点删除并插入到表尾。7.如果有n个线性表同时共存,并且在处理过程中各表的长度会发生动态变化,线性表的总长度也会自动地改变。在此情况下,应选择哪ー种存储结构?为什么?答:应选用链式存储结构。因为顺序表是静态存储结构,只能预先分配,不能随着线性表长度的改变而变化。而链表则可根据需要动态地申请空间,因此适用于动态变化表长的线性表。8.若线性表的总数基本稳定,且很少进行插入、删除操作,但要求以最快的方式存取线性表的元素,应该用哪种存储结构?为什么?答:应选用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为0(1)。五、算法设计题假设算法中用到的顺序表和链表结构如下:#definemaxsize100;Typedefstructnodel{datatypedata[maxsize];intlength)SeqList;Typedefstructnode2{datatypedata;structnode2*next}LinkedList;.试用顺序表作为存储结构,实现将线性表(a0,al,a2,…an-1)就地逆置的操作,所谓“就地”是指辅助空间为0(1)。答：(1)顺序表的就地逆置分析:分别用两个整型变量指向顺序表的两端,同时向中间移动,移动的同时互换两个下标指示的元素的值。voidSeqreverse(SeqList*L){/Z顺序表的就地逆置for(i=0；j=L->length-l；i<j；i++,j--){t=Lー〉data[i]; Lー〉data[i]=L.data[j];Lー〉data]j]=t;} }(2)链表的就地逆置分析:本算法的思想是逐个地把L的当前元素r插入到新的链表头部。voidLinkedreverse(LinkedList*L){/Z链表的就地逆置p=L->next；L->next=NULL；while(p!=NULL){r=p,p=p->next；//r指向当前待逆置的结点,P记下下ー个结点r-〉next二L一>next；L-〉next二r； //放到表头}}.设顺序表L是ー个递增(允许有相同的值)有序表,试写ー算法将x插入L中,并使L仍为ー个有序表。答:分析:先找到x的正确插入位置,然后将大于x的元素从后向前依次向下移动,最后将x插入到其位置上,同时顺序表长度增1。voidSeqListinsert(SeqList*L,intx){//x插入到递增有序的顺序表L中i二〇;while((i〈=L-〉length-1)&&(x>=L->data[i]))i++; //找正确的插入位置for(k=L->length-l;k>=i；k—) //元素从后往前依次后移L->data[k+1]=L->data[k]；Lー〉data[i]=x； //x插入到正确位置L->length++；)3.设单链表L是ー个递减有序表,试写ー个算法将x插入其中后仍保持L的有序性。答:分析:此问题的关键是在链表中找到x的插入位置,因此需要两个指针一前ー后地依次向后移动。voidLinkListinsert(LinkedList*L,intx){//x插入有序链表L中q=L；p=q->next；while(p!=NULL&&P—>data>x) //找到插入的位置{q=p；p=p—>next；}s二(LinkedList*)malloc(sizeof(LinkedList))；/Z生成新结点S->data=x；S一>next=p；qー〉next二s；)4.试写出在不带头结点的单链表的第i个元素之前插入ー个元素的算法。答:分析:对不带头结点的链表操作时,要注意对第ー个结点和其他结点操作的不同。voidLinkedListlnsert(LinkedList*L,intx,inti){//不带头结点的单链表的第i个元素之前插入ー个元素P=L：j=1;while(p!=NULL&&j<i-l)/Z找到第iT个元素{p=P—>next；j++；}if(i<=0||p==NULL)printf(v插入位置不正确、n”)；else{q=(LinkedList*)malloc(sizeof(LinkedList))；q一>data=x；if(i=l){q一〉next=L；L=q；} //在第一个元素之前插入else{q一>next=p一>next；p->next=q；} //在其他位置插入})5.设A、B是两个线性表,其表中元素递增有序,长度分别为m和no试写ー算法分别以顺序存储和链式存储将A和B归并成一个仍按元素值递增有序的线性表Co答:(1)分析:用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置,将A、B表中较小的元素写入C中,直到有一个表先结束。最后将没结束的表的剩余元素写入C表中。SeqList*Seqmerge(SeqListA,SeqListB,SeqList*C){/Z有序顺序表A和B归并成有序顺序表Ci=0；j=0；k=0； //i,i,k分别为顺序表A,B,C的下标while(i<m&&j<n){if(A.data[i]<B.data[j]) //A中当前元素较小{C->data[k]=A.data[il；i++；]TOC\o"1-5"\h\zelse{C->data[k]=B.data[j];j++；} //B中当前元素较小k++； }if(i==m)for(t=j；t<n； t++){C~>data[k]=B.data[t];k++；} //B表长度大于Aelsefor(t=i；t<m；t++){C-〉data[k]=A.data[t]；k++；} //A表长度大于B表Cー〉length=m+n； returnC;}(2)VOidLinkmerge(LinkedList*A,LinkedList*B,LinkedList*C){//有序链表A和B归并成有序链表Cpa=A一>next；pb=B—>next;〇A；pc=C；while(pa&&pb)//A和B都不为空时{if(pa->data<pb一>data) //A当前结点值较小{qa=pa-〉next ； pC-〉next二pa；pc=pc-〉next； pa=qa；}else{qb=pb-〉next；pc-〉next二pb：pc=pc-〉next；pb=qb；}//B当前结点值较小}if(pa)pc一>next=pa； //A没有结束,将A表剩余元素链接到C表if(pb)pc—>next=pb； //B没有结束,将B表剩余元素链接到C表free(B)； //释放B表的头结点}本算法需要遍历两个线性表,因此时间复杂度为0(m+n)〇.设指针!a和1b分别指向两个不带头结点的单链表的首结点,设计从表la中删除第i个元素起共len个元素,并将这些元素插入到1b中第j个结点之前的算法。答:分析:先在la中找到第i个结点,分别用两个指针pre和p指向第iT和第i个结点,然后用指针q从第i个结点起向后走len个元素,使q指向此位置。然后在1b中找到第j个结点,将p所指向的la表中的第i个及q所指向的最后ー个共len个结点插入到1b中。voidDeletelnsert(LinkedList*la,LinkedList*lb,inti,intj,intlen){//删除不带头结点的单链表la中第i个元素起共len个元素,并将这峰元素插入到单链表1b中第j个结点之前if(i<0|Ij<0||len<0)exit(O)；p=1a；k=l；pre=NULL；while(p&&k<i) //在la表中查找第i个结点{pre=p； p=p-〉next;k++；)if(!p)exit(0)；q=P;k=l；//P指向la表中第i个结点while(q&&k<len){q=q—>next； k++；} //查找la表中第i+len-1个结点if(!q)exit(0)；if(preニニla)la=q——>next； //i=l的キ青况elsepre一〉next二q—>next； /Z完成删除//将从la中删除的结点插入到1b中if(j=l) {q->next=lb； lb=p；} //j=l时else{r=lb;k二1； //J>!时while(r&&k<j-1){r二r一>next； k++；}//查找Lb表中第i—1个元素if(!r)exit(0)；qー〉next二r一>next；rー〉next二p； //元成插入}).单链表L是ー个递减有序表,试写一高效算法,删除表中值大于min且小于max的结点(若表中有这样的结点),同时释放被删结点空间,这里min和max是两个给定的参数。答:LinkedListdelete(LinkedList*L,intmin,intmax){/Z删除递减有序单链表L中值大于min且小于max的结点q二L；if(min>max){printf(nmin>max'n")；exit(0)；}elsep=L一>next； //q始终指向p的前驱while(p-〉data〉=max) /Z当前元素大于或等于max,则p、q依次向后移动{q=p；p=p->next；}while((p!二NULL)&&(p->data>min)){//当前元素的值比min大同时比max小,删除P指向的结点q->next=p一>next,free(p)；p=q一>next； }returnL；}..编写ー个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B,其头结点指针分别为pa和pb,使得A链表中含有原链表A中序号为奇数的元素,而B链表中含有原链表A中序号为偶数的元素,且保持原来的相对顺序。答:分析:用两个工作指针P和q分别指示序号为奇数和序号为偶数的结点,将q所指向的结点从A表删除,并链接到B表。voiddecompose(LinkedList*A,LinkedList*B){//单链表A分解成元素序号为奇数的单链表A和元素序号为偶数的单链表Bp=A->next ；B二(LinkedList*)malloc(sizeof(LinkedList))；r=B；while(p!=NULL&&Pー〉next!=NULL){q二P—>next； //q指向偶数序号的结点P->next=q一>next； //将q从A表中删除rー〉next二q； //将q结点链接到B链表的末尾r=q；//r总是指向B链表的最后一•个结点P二P—>next；//p指向原链表A中的奇数序号的结点)rー〉next二NULL； //将生成B链表中的最后一个结点的next域置为空).假设以两个元素值递增有序排列的线性表A、B分别表示两个集合,要求另辟空间构造一个线性表C,其元素为两集合的交集,且表C中的元素值也递增有序排列。用顺序表实现并写出C的算法。答:分析:用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置,若A、B表中当前元素值相同,则写入C中,并使i、j、k值增!;若A表元素值较小,则使i增1;若B表元素值较小,则使j增1,直到有ー个表先结束。SeqLiSt*intersection(SeqListA,SeqListB,SeqList*C){/Z求元素依值递增有序排列的顺序表A、B的交集Ci=0； j=0；k=0；while((i<=A.length-1)&&(j<=B.length-1)){if(A.data[i]=B.data[j]) //找到值相同的元素{C->data[k]=A.data[i]； //相同元素写入C表中k++；i++；j++； }elseif(A.data[i]<B.data[j])i++；//A、B表当前元素不等,值较小的下标增1elsej++； }C->length二k； returnC；}.假设在长度大于1的单循环链表中,既无头结点也无头指针。s为指向链表中某个结点的指针,试编写算法删除结点・s的直接前驱结点。答:分析:因为既不知道此单循环链表的头指针,也不知道其尾指针,所以找S的前驱就只能从S开始,顺次向后寻找。voidDeletePre(Linkedlist*s){/Z删除单循环链表中结点s的直接前驱P=S；while(p->next->next!=s)p=p—>next； //找到s的前驱的前驱pq=p->next； //q是p的后继,即s的前驱p->next=s； //将q删除free(q)； ).计算带头结点的循环链表的结点个数。答:intnumber(Linkedlist*head){//计算单循环链表中结点的个数p=head—>next； i二〇;while(p!=head){i++；p=p-〉next；}returni；}.已知由单链表表示的线性表中,含有三类字符的数据元素(如:字母字符、数字字符和其他字符),试编写算法构造三个以循环链表表示的线性表,使得每个表中只含有同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间。答:分析:P指向待处理的单链表的首元结点,构造三个空的单循环链表,分别存储三类字符,其中一个表可使用原来的单链表。q指向P的下ー个结点,根据・P的数据域的值将其插入到不同的链表上。再把q的值给P,处理下ー个结点。voidchange(LinkedList*L,LinkedList*pa,LinkedList*pb,LinkedList*pc){//分解含有三类字符的单链表为三个以循环链表表示的线性表,使其分别含有三