资源描述
38数据结构习题答案2第一节 概 论2第二节 线性表5第三节 栈和队列16第五节 树19第七节 查找25第八节 排序29操作系统练习题参考答案3238数据结构习题答案第一节 概 论一、选择题1要求同一逻辑结构的所有数据元素具有相同的特性，这意味着( )。A数据元素具有同一的特点 B不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 C每个数据元素都一样 D数据元素所包含的数据项的个数要相等2数据结构是一门研究非数值计算的程序设计问题中计算机的( (1) )以及它们之间的( (2) )和运算的学科。(1) A操作对象 B计算方法 C逻辑存储 D数据映像(2) 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索引存取 DHash存取6算法分析的目的是( )。A找出数据结构的合理性 B研究算法中的输入和输出的关系 C分析算法的效率以求改进 D分析算法的易懂性和文档性7计算机算法指的是( (1) )，它必须具备输入、输出和( (2) )等五个特征。 (1) A计算方法 B排序方法 C解决某一问题的有限运算序列 D调度方法 (2) A可行性、可移植性和可扩充性 B可行性、确定性和有穷性 C确定性，有穷性和稳定性 D易读性、稳定性和安全性8线性表若采用链表存储结构，要求内存中可用存储单元的地址( )。A必须是连续的 B部分必须是连续的 C一定是不连续的 D连续不连续都可以9在以下的叙述中，正确的是( )。A线性表的线性存储结构优于链式存储结构 B二维数组是它的每个数据元素为一个线性表的线性表 C栈的操作方式是先进先出 D队列的操作方式是先进后出10根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式，其中解释错误的是( )。A集合中任何两个结点之间都有逻辑关系但组织形式松散 B线性结构中结点按逻辑关系依次排列形成一条“锁链” C树形结构具有分支、层次特性，其形态有点像自然界中的树 D图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接11以下说法正确的是( )。A数据元素是数据的最小单位 B数据项是数据的基本单位 C数据结构是带有结构的各数据项的集合 D数据结构是带有结构的数据元素的集合二、判断题1数据元素是数据的最小单位。2数据结构是带有结构的数据元素的集合。3数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。4数据项是数据的基本单位。5数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。6数据的物理结构是数据在计算机中实际的存储形式。7算法和程序没有区别，所以在数据结构中二者是通用的。8顺序存储结构属于静态结构，链式存储结构属于动态结构。三、填空题1所谓数据的逻辑结构指的是数据元素之间的_逻辑关系_。2，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容_数据的逻辑结构、数据的存储结构、对数据施加的操作_。3数据的逻辑结构包括_集合结构_、_线性结构_、_树型结构_和_图状结构_四种类型。4在线性结构中，开始结点_没有_前驱结点，其余每个结点有且只有_一个_个前驱结点。5在树形结构中，根结点只有_一个_，其余每个结点有且只有_一个_前驱结点；叶结点没有_后继_结点，其余每个结点的后继结点可以有_任意个_6在图形结构中，每个结点的前驱结点和后继结点可以有_任意个_。7算法的五个重要特性是_可行性_、_确定性_、_有穷性_、_输入_、_输出_。8下列程序段的时间复杂度是_O（n）_。 for (i=1；i=n；i+) Ai，i=0；9下列程序段的时间复杂度是_ O（n2）_。 S=0； for(i=1；i=n；i+) for(j=1；j=n；j+) s=s+Bi,j； sum=s；10存储结构是逻辑结构的_物理_实现。11从数据结构的观点看，通常所说的“数据”应分成三个不同的层次，即_数据_、_数据元素_和_数据项_。12根据需要，数据元素又被称为_结点_、_记录_、_元素_或_顶点_。13通常，存储结点之间可以有_顺序存储_、_链式存储_、_索引存储_、_散列存储_四种关联方式，称为四种基本存储方式。14通常从_确定性_、_可读性_、_健壮性_、_高效性_等几方面评价算法(包括程序)的质量。15一个算法的时空性能是指该算法的_时间复杂度和_空间复杂度_，前者是算法包含的_计算量_，后者是算法需要的_存储量_。16在一般情况下，一个算法的时间复杂度是_问题规模_的函数。17常见时间复杂度的量级有：常数阶O(_1_)、对数阶O(_log2n_)、线性阶O(_n_)、平方阶O(_n2_)和指数阶O(_2n_)。通常认为，具有指数阶量级的算法是_不可行_的。18数据结构的基本任务是数据结构的_设计_和_实现_。19数据对象是性质相同的_数据元素_的集合。20抽象数据类型是指一个_数学模型_以及定义在该模型上的一组操作。四、应用题1分析下列程序段的时间复杂度。 i=1； WHILE (i=n) i=i2； 答：O(log2n)2叙述算法的定义及其重要特性。答：算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。算法应该具有下列特性：可行性、确定性、有穷性、输入和输出。3简述下列术语：数据，数据元素，数据结构，数据对象。答：数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。数据结构是指相互之间存在着一种或多种关系的数据元素的集合。数据对象是性质相同的数据元素的集合。4逻辑结构与存储结构是什么关系？答：在数据结构中，逻辑结构与存储结构是密切相关的，存储结构不仅将数据元素存储到计算机中，而且还要表示各数据元素之间的逻辑关系。逻辑结构与计算机无关，存储结构是数据元素之间的关系在计算机中的表示。5将数量级210，n，n2，n3，nlog2n，log2n，2n，n!，(23)n，n23按增长率进行排列。答：(23)n，210，log2n，n23，n，nlog2n，n2，n3，2n，n!6设有数据逻辑结构为：D=k1，k2，k3，k9，R=，画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？答：图略。开始结点k1、k2，终端结点k6、k7。7设有如图1.1所示的逻辑结构图，给出它的逻辑结构，并说出它是什么类型的逻辑结构。答：数据逻辑结构为：D=k1，k2，k3，k8，R=，其逻辑结构类型为树型结构。8分析下列程序的时间复杂度(设n为正整数)。 (1)int rec(int n) if(n=1)return(1)； else return(nrec(n-1)； (2)x=91；y=100； While (y0) if(x10) y-； (3)i=1；j=0； while(i+jj)j+； else i+; (4)x=n；y=0；while(x=(y+1)(y+1) y+；答：(1) O(n) (2) O(1) (3) O(n) (4) O(n1/2)9设n为正数。试确定下列各程序段中前面加记号的语句的频度： (1)i=1；k=0； while(i=n-1) k+=10i； i+； ) (2) k=0； for(i=1；i=n；i+) for(j=i；jnext=NULL Chead-next=head Dhead!=NULL10非空单循环链表head的尾结点p满足( )。 Ap-next=NULL Bp=NULL Cp-next=head Dp=head11在双循环链表的p结点之后插入s结点的操作是( )。 Ap-next=s；s-prior=p；p-next-prior=s；s-next=p-next； Bp-next=s；p-next-prior=s；s-prior=p：s-next=p-next； Cs-prior=p；s-next=p-next；p-next=s；p-next-prior=s； Ds-prior=p；s-next=p-next；p-next-pror=s；p-next=s；12. 在一个单链表中，已知q结点是p结点的前驱结点，若在q和p之间插入结点s，则执行( )。 As-next=p-next；p-next=s； Bp-next=s-next；s-next=p； Cq-next=s; s-next=p； Dp-next=s; s-next=q；13. 在一个单链表中，若p结点不是最后结点。在p之后插入结点s，则执行( )。 As-next=p；p-next=s; Bs-next=p-next；p-next=s； Cs-next=p-next； p=s； Dp-next=s； s-next=p;14. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱元素，则采用( )存储方式最节省时间。 A顺序表 B. 单链表 C双链表 D单循环链表15设rear是指向非空带头结点的单循环链表的尾指针，则删除表头结点的操作可表示为( )。 Ap=rear；rear=rear-next； free(p) Brear=rear-next；free(rear)； Crear=rear-next-next； free(rear)； Dp=rear-next-next；rear-next-next=p-next；free(p)；16在一个单链表中，若删除p结点的后继结点，则执行( )。 Aq=p-next；p-next=q-next；free(q)； Bp=p-next；p-next=p-next-next；free(p)； Cp-next=p-next；free(p-next)； Dp=p-next-next；free(p-next)；17设指针p指向双链表的某一结点，则双链表结构的对称性可用( )式来刻画。 Ap-prior-next-=p-next-next Bp-prior-prior=p-next-prior Cp-prior-next-=p-next-prior Dp-next-next=p-prior-prior18在循环链表中，将头指针改设为尾指针rear后，其头结点和尾结点的存储位置分别是( )。 Arear和rear-next-next Brear-next和rear Crear-next-next和rear Drear和rear-next19循环链表的主要优点是( )。 A不再需要头指针了 B已知某个结点的位置后，容易找到它的直接前驱 C在进行插入、删除操作时，能更好地保证链表不断开 D从表中任一结点出发都能扫描到整个链表20在线性表的下列存储结构中，读取元素花费时间最少的是( )。 A单链表 B双链表 C循环链表 D顺序表二、判断题1顺序存储的线性表可以随机存取。2顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。3线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。4在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。5在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。6在单链表中，可以从头结点开始查找任何一个元素。7线性表的链式存储结构优于顺序存储结构。8在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。9在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。10顺序存储方式只能用于存储线性结构。三、填空题1为了便于讨论，有时将含n(n0)个结点的线性结构表示成(a1，a2，an)，其中每个ai代表一个_结点_。a1称为_第一个_结点，an称为_最后一个_结点，i称为ai在线性表中的_位置_。对任意一对相邻结点ai、ai+1(1inext；p-next=q-next；free(q)；_6非空的单循环链表head的尾结点(由指针p所指)满足_ p-next= head _。7rear是指向非空带头结点的单循环链表的尾指针，则删除起始结点的操作可表示为_ p=rear-next；q=p-next；p-next=q-next；free(q)；_。8对于一个具有n个结点的单链表，在p所指结点后插入一个结点的时间复杂度为_O(1)_，在给定值为x的结点后插入新结点的时间复杂度为_ O(n)_。9单链表表示法的基本思想是用_指针_表示结点间的逻辑关系。10在顺序表中插入或删除一个元素，平均需要移动_一半_元素，具体移动的元素个数与_元素的位置_有关。11在一个长度为n的向量的第i(1in+1)个元素之前插入一个元素时，需向后移动_ n-i+1_个元素。12在一个长度为n的向量中删除第i(1in)个元素时，需向前移动_ n-i _个元素。13在双链表中，每个结点有两个指针域，一个指向_前驱_，另一个指向_后继_。14在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=_ p-next-next ；_。15设head指向单链表的表头，p指向单链表的表尾结点，则执行p-next=head后，该单链表构成_单循环链表_。16在单链表中，若p和s是两个指针，且满足p-next与s相同，则语句p-next=s-next的作用是_删除_s指向的结点。17设r指向单循环链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是_s-next= r-next _；r-next=s；r=s；18在单链表中，指针p所指结点为最后一个结点的条件是_ p-next=NULL_。19在双循环链表中，若要在指p所指结点前插入s所指的结点，则需执行下列语句：s-next=p； s-prior=p-prior；_ p-prior-next _=s；p-prior=s；20在单链表中，若要在p所指结点之前插入s所指的结点，可进行下列操作： s-next=_ p-next _； p-next=s； temp=p-data； p-data=_ s-data _； s-data=_ temp _；四、应用题1描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。答：首元结点是指链表中存储的线性表中的第一个数据元素的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点。头指针是指向链表中的第一个结点的指针。2何时选用顺序表，何时选用链表作为线性表的存储结构为宜？答：从空间上来看，当线性表的长度变化较大、难以估计其规模时，选用动态的链表作为存储结构比较合适，但链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不大、易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。从时间上来看，若线性表的操作主要是查找，很少进行插入和删除操作时，应选用顺序表。对于频繁进行插入和删除操作的线性表，宜采用链表作为存储结构。3在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？答：平均移动表中大约一半的结点，插入操作平均移动n/2 个结点，删除操作平均移动（n-1）/2 个结点。具体移动的次数取决于表长和插入、删除的结点的位置。4为什么在单循环链表中设置尾指针比设置头指针更好？答：单循环链表中无论设置尾指针还是头指针都可以遍历表中任一个结点，但设置尾指针时，若在表尾进行插入或删除操作可在O(1)时间内完成，同样在表头进行插入或删除操作也可在O(1)时间内完成。但若设置的是头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为O(n)。5双链表和单循环链表中，若仅知道指针p指向某个结点，不知道头指针，能否将结点p 从相应的链表中删除？若可以，其时间复杂度各为多少？答：能删除。双链表上删除p所指向的结点的时间复杂度为O(1)，单循环链表上删除p所指向的结点的时间复杂度为O(n)。6下列算法的功能是什么？ LinkList testl(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；答：如果长度大于1，则将首元结点删除并插入到表尾。7如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构？为什么？答：应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配，不能随着线性表长度的改变而变化。而链表则可根据需要动态地申请空间，因此适用于动态变化表长的线性表。8若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构？为什么？答：应选用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为O(1)。五、算法设计题1试用顺序表作为存储结构，实现将线性表(a0，a1，a2，an-1)就地逆置的操作，所谓“就地”是指辅助空间为O(1)。答：(1)顺序表的就地逆置 分析：分别用两个整型变量指向顺序表的两端，同时向中间移动，移动的同时互换两个下标指示的元素的值。 void Seqreverse(SeqList L)顺序表的就地逆置 for(i=0；j=L.1ength-1；inext；L-next=NULL； while(p!=NULL) r=p，p=p-next； r指向当前待逆置的结点，p记下下个结点 r-next=Lnext；L-next=r； 放到表头 2设顺序表L是一个递增(允许有相同的值)有序表，试写一算法将x插入L中，并使L仍为一个有序表。答：分析：先找到x的正确插入位置，然后将大于x的元素从后向前依次向下移动，最后将x插入到其位置上，同时顺序表长度增1。 void SeqListinsert(SeqList L，int x)x插入到递增有序的顺序表L中 i=0; while(i=L.datai) i+； 找正确的插入位置for(k=L.length-1;k=i；k-) 元素从后往前依次后移 L.datak+1：L.datak； L.data(ix； x插入到正确位置 L.1ength+； ) 3.设单链表L是一个非递减有序表，试写一个算法将x插入其中后仍保持L的有序性。答：分析：此问题的关键是在链表中找到x的插入位置，因此需要两个指针一前一后地依次向后移动。 void LinkListinsert(LinkedList L，int x)x插入有序链表L中 q=L；p=qnext； while(p!=NULL&pdatanext； s=(LinkedList)malloc(sizeof(LNode)； 生成新结点 Sdata=x； Snext=p； qnext=s； 4. 试写出在不带头结点的单链表的第i个元素之前插入一个元素的算法。答：分析：对不带头结点的链表操作时，要注意对第一个结点和其他结点操作的不同。 void LinkedListlnsert(LinkedList head，int x，int i) 不带头结点的单链表的第i个元素之前插入一个元素 p=L：j=1; while(p!=NULL&jnext；j+； if(idata=x； if(i=1) qnext=L；L=q； 在第一个元素之前插入 elseqnext=pnext；pnext=q； 在其他位置插入 5设A、B是两个线性表，其表中元素递增有序，长度分别为m和n。试写一算法分别以顺序存储和链式存储将A和B归并成一个仍按元素值递增有序的线性表C。答：(1)分析：用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置，将A、B表中较小的元素写入C中，直到有一个表先结束。最后将没结束的表的剩余元素写入C表中。SeqList Seqmerge(SeqList A，SeqList B)有序顺序表A和B归并成有序顺序表C i=0；j=0；k=0； i，i，k分别为顺序表A，B，C的下标 while(im&jn) if(A.dataiB.dataj) A中当前元素较小 C.datak=A.datail；i+； else C.datak=B.dataj;j+； B中当前元素较小 k+； if (i=m) for(t=j；tn；t+) C.datak=B.datat;k+； B表长度大于A表 else for(t=i；tnext；pb=Bnext；C=A；pc=C； while(pa&pb) A和B都不为空时 if(padatadata) 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)pcnext=pa； A没有结束，将A表剩余元素链接到C表if(pb)pcnext=pb； B没有结束，将B表剩余元素链接到C表free(B)； 释放B表的头结点本算法需要遍历两个线性表，因此时间复杂度为O(m+n)。6设指针la和lb分别指向两个不带头结点的单链表的首结点，设计从表la中删除第i个元素起共len个元素，并将这些元素插入到lb中第j个结点之前的算法。答：分析：先在la中找到第i个结点，分别用两个指针pre和p指向第i-1和第i个结点，然后用指针q从第i个结点起向后走len个元素，使q指向此位置。然后在lb中找到第j个结点，将p所指向的la表中的第i个及q所指向的最后一个共len个结点插入到lb中。void Deletelnsert(LinkedList la，LinkedList lb，int i，int j, int len)删除不带头结点的单链表la中第i个元素起共len个元素,并将这峰元素插入到单链表lb中第j个结点之前 if(i0|j0|len0) exit(0)； p=la；k=1；pre=NULL； while(p&knext; k+； if(!p) exit(0)； q=p；k=l； p指向la表中第i个结点 while(q&knext； k+； 查找la表中第i+len-1个结点 if(!q) exit(0)； if(pre=la) la=qnext； i=1的情况 else prenext=qnext； 完成删除 将从la中删除的结点插入到lb中 if(j=1) q-next=lb； lb=p； j=1时 else r=lb; k=1； j1时 while(r&knext； k+； 查找Lb表中第i1个元素 if(!r) exit(0)； qnext=rnext；rnext=p； 完成插入 7单链表L是一个递减有序表，试写一高效算法，删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删结点空间，这里min和max是两个给定的参数。答：LinkedList delete(LinkedList L，int min，int max) 删除递减有序单链表L中值大于min且小于max的结点 q=L； if(minmax) printf(”minmaxn”)；exit(0)； else p=Lnext； q始终指向p的前驱while(pdata=max) 当前元素大于或等于max，则p、q依次向后移动 q=p；p=pnext； while(p!=NULL)&(p一datamin) 当前元素的值比min大同时比max小，删除p指向的结点 qnext=pnext， free(p)；p=qnext； return L； 8编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和pb，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。答：分析：用两个工作指针p和q分别指示序号为奇数和序号为偶数的结点，将q所指向的结点从A表删除，并链接到B表。void decompose(LinkedList A，LinkedList B)单链表A分解成元素序号为奇数的单链表A和元素序号为偶数的单链表B p=A-next； B=(LinkedList)malloc(sizeof(LNode)； r=B； while(p!=NULL&p-next!=NULL) q=pnext； q指向偶数序号的结点 pnext=qnext； 将q从A表中删除 rnext=q； 将q结点链接到B链表的末尾 r=q； r总是指向B链表的最后个结点 p=pnext； p指向原链表A中的奇数序号的结点 rnext=NULL； 将生成B链表中的最后一个结点的next域置为空 9假设以两个元素依值递增有序排列的线性表A、B分别表示两个集合，要求另辟空间构造一个线性表C，其元素为两集合的交集，且表C中的元素也依值递增有序排列。对顺序表编写求C的算法。答：分析：用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置，若A、B表中当前元素值相同，则写入C中，并使i、j、k值增1；若A表元素值较小，则使i增1；若B表元素值较小，则使j增1，直到有一个表先结束。SeqLiSt intersection(SeqList A，SeqList B，SeqList C)求元素依值递增有序排列的顺序表A、B的交集C i=0； j=0；k=0； while(i=A.length-1)&(j=B.length-1) if(A.datai=B.dataj) 找到值相同的元素 C.datak=A.datai； 相同元素写入C表中 k+；i+；j+； else if(A.datain时），线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表的结点空间。答：分析：使p和q指向A和B表当前元素，并分别使nextp和nextq指向p和q的后继，这样将q所指向的结点链接到p的后面，再把nextp和nextq的值赋给p和q，处理下一个结点。void merge(LinkedList A，LinkedList B，LinkedList C)把链表A和B合并为C，A和B的元素间隔排列，且使用原存储空间 p=Anext；q=Bnext；C=A；while(p&q) nextp=pnext；pnext=q； 将B的元素插入 if(nextp) nextq=q-next；q-next=nextp；如果A非空，将A的元素插入 p=nextp； q=nextq； 11假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点s的直接前驱结点。答：分析：因为既不知道此单循环链表的头指针，也不知道其尾指针，所以找s的前驱就只能从s开始，顺次向后寻找。void DeletePre(LinkedNode s)删除单循环链表中结点s的直接前驱 p=s； while(pnextnext!=s) p=pnext； 找到s的前驱的前驱p q=pnext； q是p的后继，即s的前驱 pnext=s； 将q删除 free(q)； 12计算带头结点的循环链表的结点个数。答：int number(LinkedNode head) 计算单循环链表中结点的个数 p=headnext； i=0； while(p!=head) i+；p=p-next； return i； 13已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其他字符)，试编写算法构造三个以循环链表表示的线性表，使得每个表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。答：分析：p指向待处理的单链表的首元结点，构造三个空的单循环链表，分别存储三类字符，其中一个可使用原来的单链表。q指向p的下一个结点，根据p的数据域的值将其插入到不同的链表上。再把q的值给p，处理下一个结点。void change(LinkedList L，LinkedList pa，LinkedList pb，LinkedList pc)分解含有三类字符的单链表为三个以循环链表表示的线性表，使其分别含有三类字符 p=Lnext； pa=L； panext=pa； 分别构造三个单循环链表 pb=(LinkedList)malloc(sizeof(LNode)； pc=(LinkedList)malloc(sizeof(LNode)； pbnext=pb；pcnext=pc； while(p!=L) q=pnext； q记下L中下一个结点的位置 if(pdatadata=a) 链接到字母链表的头部 pnext=panext；panext=p； else if (pdatadata=0) 链接到数字链表的头部 pnext=pbnext；pbnext=p； elsep-next=pc-next；pc-next=p；链接到其他字母链表的头部 p=q； 14、己知A、B和C为三个递增有序的线性表，现要求对A表进行如下操作：删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法(注：题中未特别指明同一表中的元素值各不相同)。答：分析：先从B和C中找出共有元素，记为same，再在A中从当前位置开始，凡小于same的元素均保留(存到新的位置)，等于same的就跳过，到大于same时就再找下一个SameSeqList IntersectDelete(SeqList A，SeqList B，SeqList C) 对顺序表A删去那些既在B表中出现又在C表中出现的元素 i=0；j=0；k=0；m=0; i指示A中元素原来的位置，m为移动后的位置 while(iA.length&iB.length&kC.length) if(B.datajC.datak) k+; else same=B.dataj； 找到了相同元素same while(B.dataj=same) j+； while(C.datak=same) k+； j、k后移到新的元素 while(iA.length&A.dataisame) A.datam+=A.datai+；需保留的元素移动到新位置 while(iA.1ength&A.datai1=same i+；跳过相同的元素 while(inext； while(p!=L&p-data!=x) p=p-next； 在链表中查找值为x的结点 if(p-data=x) 找到值为x的结点 q=p-prior； q指向值为x的结点的前驱 s=(DLinkedList)malloc(sizeof(DLNode)； s-data=y； s-next=p； s-prior=q； 将y插入到q与p指向的结点之间 p-prior=s；q-next=s； elseprintf(”没有值为x的结点”)；exit(0)； void DLDelete(DLinkedList L，int x)在双循环链表中删除结点 p=L-next； while(p!=L&p-data!=x)p=p-next； if(p-data=x) p-prior-next=p-next；p-next-prior=p-prior；free(p)； elseprintf(”没有值为x的结点”)；exit(0)；16设有一个双循环链表，其中有一结点的指针为p，编写算法将p与其右边的一个结点进行交换。答：void DLchange(DLinkedList p) 将双循环链表中p指向的结点与其右边的一个结点进行交换 q=pnext； q指向p的后继 ppriornext=q；qprior=pprior； 将p的前驱与q相链接 pnext=qnext；pprior=q； 将p插入到q之后 q-nextprior=p；qnext=p； 17设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个可访问颊度域freq，在链表启用之前，其值均初始为0。每当链表进行一次LocateNode(L，x)操作时令元素值为x的结点中freq域的值加l，并调整表中结点的次序，使其按访问频度的递减次序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode操作的算法。答：分析：先在双链表中查找值为x的结点，若找到则使其freq值增1，然后从头至尾扫描链表，将此结点插入到按freq递减顺序排列的正确位置。typedef struct DLNode int data，freq；struct DLNode prior，next；DLNode，DLinkedList；void LocateNode(DLinkedList head，int x)双链表按访问频度域freq递减次序排列 p2=head； p1=p2next； p2在前，p1在后 whue(p1) 查找单链表中值为x的结点 if(pldata=x) plfreq+； break；使值为x的结点的freq加1 else p2=pl；p1=p2next； if(p1=NULL) printf(”Not found.n”)； elseif(p1next=NULL) p2next=p1next；temp=p1； 在链表中找temp所指向的结点，按freq值递减应插入的位置 elsep2next=p1next； 插入链表中间的某一位置 p1next-prior=p2； temp=pl；for(p2=head，p1=p2-next；pl&p1-freqtemp-freq；p2=p1，pl=p2-next)；插入 if(p1=NULL) p2-next=temp；temp-prior=p2；temp-next=NULL；
展开阅读全文