计算机软件技术基础所有题目答案自学

1、241518222628第一节概论第二节线性表第三节栈和队列第五节树第七节查找第八节排序操作系统练习题参考答案数据结构习题答案第一节概论一、选择题1 .要求同一逻辑结构的所有数据元素具有相同的特性，这意味着（）。A.数据元素具有同一的特点B.不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 C .每个数据元素都一样D .数据元素所包含的数据项的个数要相等2 .数据结构是一门研究非数值计算的程序设计问题中计算机的（1）以及它们之间的（2）和运算的学科。（1） A.操作对象 B .计算方法 C .逻辑存储 D .数据映像A .结构 B.关系 C .运算 D .算法3 .数据结构被形

2、式地定义为（D, R）,其中D是（1）的有限集合，R是D上（2）的有限集 合。A .算法B.数据元素 C .数据操作 D .逻辑结构（2）A .操作 B .映像 C .存储D.关系4 .在数据结构中，从逻辑上可以把数据结构分为 （）。A.动态结构和静态结构 B .紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构 和外部结构5 .线性表的顺序存储结构是一种（）的存储结构。A.随机存取 B .顺序存取 C .索引存取D . Hash存取6 .算法分析的目的是（）。A,找出数据结构的合理性B .研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性7 .计算

3、机算法指的是（1）,它必须具备输入、输出和（2）等五个特征。A .计算方法 B .排序方法C.解决某一问题的有限运算序列D .调度方法A .可行性、可移植性和可扩充性B.可行性、确定性和有穷性 C .确定性，有穷性和稳定性D .易读性、稳定性和安全性8 .线性表若采用链表存储结构，要求内存中可用存储单元的地址（）。A.必须是连续的 B .部分必须是连续的 C . 一定是不连续的D.连续不连续都可以9 .在以下的叙述中，正确的是（）。A,线性表的线性存储结构优于链式存储结构B.二维数组是它的每个数据元素为一个线性表的线性表C .栈的操作方式是先进先出D .队列的操作方式是先进后出10 .根据数据

4、元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形 式，其中解释错误的是（）。A.集合中任何两个结点之间都有逻辑关系但组织形式松散B .线性结构中结点按逻辑关系依次排列形成一条“锁链”C .树形结构具有分支、层次特性，其形态有点像自然界中的树D.图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接11 .以下说法正确的是（）。A.数据元素是数据的最小单位B .数据项是数据的基本单位C .数据结构是带有结构的各数据项的集合D.数据结构是带有结构的数据元素的集合二、判断题X1.数据元素是数据的最小单位。V 2.数据结构是带有结构的数据元素的集合。V 3.数据结构、数

5、据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。X4.数据项是数据的基本单位。V 5.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。V 6.数据的物理结构是数据在计算机中实际的存储形式。X7.算法和程序没有区别，所以在数据结构中二者是通用的。X8.顺序存储结构属于静态结构，链式存储结构属于动态结构。三、填空题1.所谓数据的逻辑结构指的是数据元素之间的逻辑关系 02,数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容_数据的逻辑结构、数据的存储2构、对数据施加的操作。3 .数据的逻辑结构包括 集合结构、线性结构、树型结构 和 图状结构

6、 四种类型。4 .在线性结构中，开始结点没有前驱结点，其余每个结点有且只有一个个前驱结点。5 .在树形结构中，根结点只有 一个，其余每个结点有且只有 一个_前驱结点；叶结点 没有 后继结点，其余每个结点的后继结点可以有任意个 6 .在图形结构中,每个结点的前驱结点和后继结点可以有任意个 。7 .算法的五个重要特性是可行性、 确定性、 有穷性、 输入、 输出o8 .下列程序段的时间复杂度是_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&

7、lt;=n ； j+) s=s+Bi,j ；sum=s ;10 .存储结构是逻辑结构的物理 实现。11 .从数据结构的观点看，通常所说的“数据”应分成三个不同的层次，即 数据、 数据元 素和数据项 。12 .根据需要，数据元素又被称为结点、 记录、 元素 或 顶点。13 .通常，存储结点之间可以有顺序存储 、链式存储、索引存储 、 散列存储四种关联方式，称为四种基本存储方式。14 .通常从_确定性、可读性_、健壮性_、高效性等几方面评价算法(包括程序)的 质量。15 . 一个算法的时空性能是指该算法的时间复杂度和 空间复杂度，前者是算法包含的计算量，后者是算法需要的存储量。16 .在一般情况下

8、，一个算法的时间复杂度是问题规模 的函数。17 .常见时间复杂度的量级有：常数阶 。(_1_)、对数阶O(_log2n)、线性阶O(_n_)、平方 阶O(_n2_)和指数阶O(_2_)。通常认为，具有指数阶量级的算法是 不可行的。18 .数据结构的基本任务是数据结构的设计 和 实现。19 .数据对象是性质相同的数据元素 的集合。20 .抽象数据类型是指一个数学模型 以及定义在该模型上的一组操作。四、应用题1.分析下列程序段的时间复杂度。i=1 ；WHILE (i<=n) i=i2;答：O(log2n)2,叙述算法的定义及其重要特性。答：算法是对特定问题求解步骤的一种描述，是指令的有限序列

9、。其中每一条指令表示一个或多个操作。算法应该具有下列特性：可行性、确定性、有穷性、输入和输出。3 .简述下列术语：数据，数据元素，数据结构，数据对象。答：数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程 序识别和处理的符号的集合。数据元素是数据的基本单位。在不同的条件下，数据元素又可称为 元素、结点、顶点、记录等。数据结构是指相互之间存在着一种或多种关系的数据元素的集合。 数据对象是性质相同的数据元素的集合。4 .逻辑结构与存储结构是什么关系？答：在数据结构中，逻辑结构与存储结构是密切相关的，存储结构不仅将数据元素存储到计算机 中，而且还要表示各数据元素之间的逻

10、辑关系。逻辑结构与计算机无关，存储结构是数据元素之 间的关系在计算机中的表示。5 .将数量级 210, n, n2, n3, nlog2n, log 2n, 2n, n! , (2/3)n, n2 3按增长率进行排列。答:(2/3)n, 210, 10g2n , n2/3, n, nlog2n , n2, n3, 2n, n!6 .设有数据逻辑结构为： D=k1 , k2, k3,，k9 , R=<k1, k3>, <k1 , k8>, <k2, k3>, <k2, k4>, <k2, k5>, <k3, k9>, <

11、;k5, k6>, <k8, k9>, <k9, k7>, <k4, k6>,画出这个逻辑结构的 图示，并确定相对于关系 R,哪些结点是开始结点，哪些结点是终端结点？答：图略。开始结点k1、k2,终端结点k6、k707 .设有如图1.1所示的逻辑结构图，给出它的逻辑结构，并说出它是什么类型的逻辑结构。答：数据逻辑结构为：D=k1 , k2, k3,，k8, R=<k1, k2>, <k1, k3>, <k3, k5>, <k3, k4>, <k4, k7>, <k4, k6>, &

12、lt;k5, k8>,其逻辑结构类型为树型结构。8 .分析下列程序的时间复杂度(设n为正整数)。(1)int rec(int n)if(n=1)return(1) ； else return(nrec(n-1) ； x=91; y=100;While (y>0) if(x>10) y-；i=1； j=0 ；while(i+j<=n)if(i>j)j+ ； else i+;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为正数。试确定下列各程序段中前面

13、加记号 1语句的频度：i=1； k=0；while(i<=n-1) k+=10 i ；i+;)(2) k=0；for(i=1 ; i<=n ； i+)for(j=i ; j<=n : j+) k+ ；答：(1)n-1 (2)n+(n-1)+1=n(n+1)/2第二节线性表一、选择题1 .线性结构中的一个结点代表一个()。A.数据元素B .数据项 C .数据D .数据结构2 .线性表L=(a1 , a2,，ai ,，an),下列说法正确的是()。A.每个元素都有一个直接前驱和直接后继B .线性表中至少要有一个元素C .表中诸元素的排列顺序必须是由小到大或由大到小的D .除第一个

14、元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继3 .顺序表是线性表的（）。A .链式存储结构B.顺序存储结构C .索引存储结构D .散列存储结构4 .对于顺序表，以下说法错误的是（）。A .顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B .顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C .顺序表的特点是：逻辑结构中相邻的结点在存储结构中仍相邻D .顺序表的特点是：逻辑上相邻的元素，存储在物理位置也相邻的单元中5 .对顺序表上的插入、删除算法的时间复杂度分析来说，通常以 （）为标准操作。A .条件判断B.结点移动C .算术表达式D

15、.赋值语句6 .对于顺序表的优缺点，以下说法错误的是（）。A .无需为表示结点间的逻辑关系而增加额外的存储空间B .可以方便地随机存取表中的任一结点C.插入和删除操作较方便 D .由于顺序表要求占用连续的空间，存储分配只能预先进行（静态分配）7 .在含有n个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动结点的平均次数 为（）。A . nB. n/2 C . （n-1）/2 D . （n+1）/28 .在含有n个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数为（）。A . n B . n/2C. （n-1）/2 D . （n+1）/29 .带头结点的单链表head为空的

16、条件是（）。A. head=NULL B. head->next=NULL C , head->next=head D . head!=NULL10 .非空单循环链表head的尾结点-p满足（）。A . p->next=NULL B . p=NULL C. p->next=head D . p=head11 .在双循环链表的p结点之后插入s结点的操作是（）。A . p->next=s ； s->prior=p ； p->next->prior=s ； s->next=p->next ； B . p->next=s ； p- &g

17、t;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=s12 .在一个单链表中，已知q结点是p结点的前驱结点，若在q和-p之间插入结点s,则执行 （）。A . s->next=p->next ； p->next

18、=s ； B . 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 ；C . s->next=p->next ； p=s ； D . p->next=s ； s->next=p;14 .若某线性表中最

19、常用的操作是取第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->

20、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->pri

21、or->next->=p->next->next B . p->prior->prior=p->next->prior -C. p->prior->next->=p->next->prior D . p->next->next=p->prior->prior18 .在循环链表中，将头指针改设为尾指针rear后，其头结点和尾结点的存储位置分别是（）。A . rear 和 rear->next->nextB. rear->next 和 rear C . rear->next

22、->next 和 rearD. rear 和 rear->next19 .循环链表的主要优点是()。A .不再需要头指针了B ,已知某个结点的位置后，容易找到它的直接前驱C .在进行插入、删除操作时，能更好地保证链表不断开D.从表中任一结点出发都能扫描到整个链表20 .在线性表的下列存储结构中，读取元素花费时间最少的是()。A .单链表 B .双链表 C .循环链表D.顺序表二、判断题，1 .顺序存储的线性表可以随机存取。X2 .顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半 的元素需要移动。V3.线性表中的元素可以是各种各样的，但同一线性表中的数

23、据元素具有相同的特性，因此是属 于同一数据对象。X4.在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。，5.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。V6.在单链表中，可以从头结点开始查找任何一个元素。X7.线性表的链式存储结构优于顺序存储结构。V8.在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。X9.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存 储结构。X10.顺序存储方式只能用于存储线性结构。三、填空题1 .为了便于讨论，有时将含n(n>0)个结点的线性结构表示成(a1

24、, a2,，an),其中每个ai代 表一个结点_。a1称为第一个结点，an称为_最后一个结点，i称为ai R线性表中的一位置 _0对任意一又t相邻结点ai、ai+1(1 < i<n) , ai称为ai+1的直接_前驱_, ai+1称为ai的直接_ 后继。2 .线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接前驱外，其他结点有且仅有一个直接 前驱；除终端结点没有直接 后继 外，其他结点有且仅有一个直接 后继o3 .所有结点按一对一的邻接关系构成的整体就是线性结构。4 .线性表的逻辑结构是线性 结构，其所含结点的个数称为线性表的长度。5 .在单链表中，删除p所指结点的直接

25、后继的操作是 q=p->next ; p->next=q->next ; free(q) ; 6 .非空的单循环链表head的尾结点(由指针p所指)满足p->next= head 。7 . rear是指向非空带头结点的单循环链表的尾指针，则删除起始结点的操作可表示为p=rear->next; q=p->next ; p->next=q->next ; free(q) ; 。8 .对于一个具有n个结点的单链表，在p所指结点后插入一个结点的时间复杂度为 _O(1)_,在 给定值为x的结点后插入新结点的时间复杂度为_O(n)_。9 .单链表表示法的基本

26、思想是用 指针_表示结点间的逻辑关系。10 .在顺序表中插入或删除一个元素，平均需要移动 一半 元素，具体移动的元素个数与元素的位置有关。11 .在一个长度为n的向量的第i(1 &i&n+1)个元素之前插入一个元素时，需向后移动 n- i+1个元素。12 .在一个长度为n的向量中删除第i(1 &i&n)个元素时，需向前移动 _ n-i 一个元素。13 .在双链表中，每个结点有两个指针域，一个指向 前驱，另一个指向 后继 。14 .在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针 head可用 p 表示为 head=_ p->next

27、->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 .

28、在双循环链表中，若要在指 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 .描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。答：首元

29、结点是指链表中存储的线性表中的第一个数据元素的结点。为了操作方便，通常在链表 的首元结点之前附设一个结点，称为头结点。头指针是指向链表中的第一个结点的指针。2 .何时选用顺序表，何时选用链表作为线性表的存储结构为宜？答：从空间上来看，当线性表的长度变化较大、难以估计其规模时，选用动态的链表作为存储结 构比较合适，但链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不 大、易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。从时间上来看，若线性表 的操作主要是查找，很少进行插入和删除操作时，应选用顺序表。对于频繁进行插入和删除操作 的线性表，宜采用链表作为存储结构。3 .在

30、顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？答：平均移动表中大约一半的结点，插入操作平均移动n/2个结点，删除操作平均移动(n-1) /2个结点。具体移动的次数取决于表长和插入、删除的结点的位置。4 .为什么在单循环链表中设置尾指针比设置头指针更好？答：单循环链表中无论设置尾指针还是头指针都可以遍历表中任一个结点，但设置尾指针时，若在表尾进行插入或删除操作可在 O(1)时间内完成，同样在表头进行插入或删除操作也可在O(1)时间内完成。但若设置的是头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为 O(n)。5 .双链表和单循环链表中，若仅知道指针

31、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 答：如

32、果长度大于1,则将首元结点删除并插入到表尾。7 .如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度 也会自动地改变。在此情况下，应选择哪一种存储结构？为什么？答：应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配，不能随着线性表长度的 改变而变化。而链表则可根据需要动态地申请空间，因此适用于动态变化表长的线性表。8 .若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的方式存取线性表的元 素，应该用哪种存储结构？为什么？答：应选用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为O(1)。五、算法设计题1 .试用顺序表作为存储结构，实

33、现将线性表(a0, al, a2,)就地逆置的操作，所谓“就地”是指辅助空间为0(1)。答：(1)顺序表的就地逆置分析：分别用两个整型变量指向顺序表的两端，同时向中间移动，移动的同时互换两个下标指示 的元素的值。void Seqreverse(SeqList L)/顺序表的就地逆置for(i=0 ； j=L.1ength-1 ； i<j ； i+ , j-)t=L.datai; L.datai=L.dataj; L.dataj=t; (2)链表的就地逆置分析：本算法的思想是逐个地把L的当前元素r插入到新的链表头部。void Linkedreverse(LinkedList L)/链表的就

34、地逆置p=L->next ; L->next=NULL;while(p!=NULL)r=p , p=p->next ; /r指向当前待逆置的结点，p记下下一个结点r->next=L >next; L->next=r ；/放至U表头 2 .设顺序表L是一个递增(允许有相同的值)有序表，试写一算法将x插入L中，并使L仍为一个 有序表。答：分析：先找到x的正确插入位置，然后将大于x的元素从后向前依次向下移动，最后将 x插入到其位置上，同时顺序表长度增1。void SeqListinsert(SeqList L , int x) /x 插入到递增有序的顺序表 L 中

35、i=0;while(i<=L.length-1)&&(x>=L.datai) i+;/找正确的插入位置for(k=L.length-1;k>=i ； k-)/元素从后往前依次后移L.datak+1 : L.datak;L.data(i ' x；/x插入到正确位置L.1ength+ ；)3 .设单链表L是一个非递减有序表，试写一个算法将x插入其中后仍保持L的有序性。答：分析：此问题的关键是在链表中找到x的插入位置，因此需要两个指针一前一后地依次向后移动。void LinkListinsert(LinkedList L, int x) /x 插入有序链表

36、L 中q=L ; p=q>next;while(p!=NULL&&p >data<x) /找到插入的位置q=p ; p=p>next; s=(LinkedList)malloc(sizeof(LNode) ;/生成新结点S >data=x ； S >next=p; q >next=s ; 4 .试写出在不带头结点的单链表的第i个元素之前插入一个元素的算法。答：分析：对不带头结点的链表操作时，要注意对第一个结点和其他结点操作的不同。void LinkedListlnsert(LinkedList head, int x , int i)/

37、不带头结点的单链表的第i个元素之前插入一个元素p=L : j=1;while(p!=NULL&&j<i-1)/找到第 i-1 个元素p=p >next; j+ ; if(i<=0|p=NULL) printf("插入位置不正确、n”)；else q=(LinkedList)malloc(sizeof(LNode); q>data=x ；if(i=1) q >next=L ； L=q； /在第一个元素之前插入elseq >next=p >next; p>next=q ; /在其他位置插入 )5 .设A、B是两个线性表，其表

38、中元素递增有序，长度分别为m和n。试写一算法分别以顺序存储和链式存储将A和B归并成一个仍按元素值递增有序的线性表Co答：(1)分析：用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置，将 A B表中较小 的元素写入C中，直到有一个表先结束。最后将没结束的表的剩余元素写入C表中。SeqList Seqmerge(SeqList A , SeqList B) /有序顺序表 A和B归并成有序顺序表 Ci=0 ; j=0; k=0；/i , i , k分别为顺序表A, B, C的下标while(i<m&&j<n)if(A.datai<B.dataj)/ / A

39、 中当前元素较小C.datak=A.datail； i+ ；else C.datak=B.dataj;j+; /B 中当前元素较小k+ ； if (i=m) for(t=j ; t<n ； t+) C.datak=B.datat;k+ ； /B表长度大于 A表 else for(t=i ; t<m； t+) C.datak=A.datat ; k+； /A表长度大于 B表 C.length=m+n ； return C;VOid Linkmerge(LinkedList A , LinkedList B , LinkedList C)/有序链表A和B归并成有序链表Cpa=A>

40、next; pb=B >next; C=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没有结

41、束，将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 ,

42、LinkedList lb , int i , int j, int len)/删除不带头结点的单链表la中第i个元素起共len个元素，并将这峰元素插入到单链表lb 中第j个结点之前if(i<0|j<0|len<0) exit(0)；p=la ； k=1； pre=NULLwhile(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+ ； /查找

43、la 表中第 i+len-1 个结点if(!q) exit(0) ;if(pre=la) la=q >next;/ i=1 的情况else pre >next=q >next;/完成删除/将从la中删除的结点插入到lb中if(j=1) q->next=lb ; lb=p ; /j=1 时else r=lb; k=1；/j>1 时while(r&&k<j-1) r=r >next; k+ ； /查找 Lb 表中第 i 1 个元素if(!r) exit(0);q >next=r >next; r >next=p ;/完成插

44、入 7 .单链表L是一个递减有序表，试写一高效算法，删除表中值大于 min且小于max的2点(若表 中有这样的结点),同时释放被删结点空间，这里 min和max是两个给定的参数。答：LinkedList delete(LinkedList L , int min , int max) /删除递减有序单链表L中值大于min且小于max的结点q=L ;if(min>max) printf( " min>max n" ) ； exit(0) ; else p=L >next;/q始终指向p的前驱while(p >data>=max)/当前元素大于或等

45、于 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;return L ；8 .编写一个算法将一个头结点指针为 pa的单链表A分解成两个单链表A和B,其头结点指针分别 为pa和pb,使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为 偶数的元素，且保持原来的相对顺序。答：分析：用两个工作指针p和q分别指示序号为奇数和序号为

46、偶数的结点，将 q所指向的结点 从A表删除，并链接到B表。void decompose(LinkedList A , LinkedList B)/单链表A分解成元素序号为奇数的单链表 A和元素序号为偶数的单链表Bp=A->next ; B=(LinkedList)malloc(sizeof(LNode) ;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链

47、表的最后一个结点p=p >next;/p指向原链表A中的奇数序号的结点r >next=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(S

48、eqList A , SeqList B , SeqList C)/求元素依值递增有序排列的顺序表 A、B的交集Ci=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+ ;elseif(A.datai<B.dataj) i+； /A、B表当前元素不等，值较小的下标增 1else j+；C.length=k；return C ;10 .设有线性表 A=(a1, a2,，am)和B=

49、(b1, b2,，bn)。试编写合并 A、B为线性表C的算 法，使得：C=(a1 , b1,，am bm bm+1,bn)(当 m< n 时)或(a1 , b1,，an, bn, an+1, am)(当m>n时)，线性表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)/把链

50、表A和B合并为C, A和B的元素间隔排列，且使用原存储空间p=A >next; q=B >next ; C=A while(p&&q)nextp=p >next; p>next=q ;/将 B 的元素插入if(nextp) nextq=q->next ; q->next=nextp ; /如果 A非空，将 A的元素插入 p=nextp ; q=nextq ; 11 .假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点s的直接前驱结点。答：分析：因为既不知道此单循环链表的头指针，也不知道其尾指

51、针，所以找s的前驱就只能从s开始，顺次向后寻找。void DeletePre(LinkedNode s)/删除单循环链表中结点s的直接前驱 p=s ;while(p >next>next!=s) p=p >next; /找至U s 的前驱的前驱 pq=p >next;/q是p的后继，即s的前驱p >next=s；/将 q 删除free(q) ;12 .计算带头结点的循环链表的结点个数。答：int number(LinkedNode head) /计算单循环链表中结点的个数p=head >next; i=0 ;while(p!=head) i+; p=p-&g

52、t;next ; return i ；13 .已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其他字符)，试编写算法构造三个以循环链表表示的线性表，使得每个表中只含有同一类的字符，且利用 原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。答：分析：p指向待处理的单链表的首元结点，构造三个空的单循环链表，分别存储三类字符，其 中一个可使用原来的单链表。q指向p的下一个结点，根据p的数据域的值将其插入到不同的链 表上。再把q的值给p,处理下一个结点。void change(LinkedList L , LinkedList pa , LinkedList pb

53、, LinkedList pc)/分解含有三类字符的单链表为三个以循环链表表示的线性表，使其分别含有三类字符p=L >next; pa=L ；pa >next=pa；/分别构造三个单循环链表pb=(LinkedList)malloc(sizeof(LNode);pc=(LinkedList)malloc(sizeof(LNode);pb >next=pb; pc>next=pc ;while(p!=L)q=p >next ; /q记下L中下一个结点的位置if(p >data<=' z' &&p- >data>

54、=' a' )/链接到字母链表的头部p >next=pa>next ； pa >next=p ； else if (p >data<=' 9' &&(p ->data>=' 0' ) /链接到数字链表的头部 p >next=pb>next ; pb>next=p; elsep->next=pc->next ； pc->next=p ； /链接到其他字母链表的头部 p=q ; 14、己知A、B和C为三个递增有序的线性表，现要求对A表进行如下操作：删去那些既

55、在 B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法(注：题中未特别指明同一表中的元素值各不相同)0 答：分析：先从B和C中找出共有元素，记为same再在A中从当前位置开始，凡小于 same的元 素均保留(存到新的位置)，等于same的就跳过，至U大于same时就再找下一个Same SeqList IntersectDelete(SeqList A , SeqList B , SeqList C) /对顺序表A删去那些既在B表中出现又在C表中出现的元素 i=0 ; j=0 ; k=0; m=0; /i指示A中元素原来的位置，m为移动后的位置 while(i<A.lengt

56、h&&i<B.length&&k<C.length) if(B.dataj<C.datak) j+；else if(B.dataj>C.datak) k+; else same=B.dataj ；/找至U了相同元素 samewhile(B.dataj=same) j+;while(C.datak=same) k+； /j、k 后移到新的元素while(i<A.length&&A.datai<same) A.datam+=A.datai+; /需保留的元素移动到新位置while(i<A.1ength&

57、;&A.datai1=same i+; /跳过相同的元素 while(i<A.length) A.datam+=A.datai+ ;/A的剩余元素重新存储A.1ength=m ；15 .双循环链表中，设计满足下列条件的算法。 (1)在值为x的结点之前插入值为y的结点。(2)在值为x的结点之后插入值为y的结点。(3)删 除值为x的结点。 答：分析：在双循环链表中插入和删除结点要注意修改双向的指针。 typedef struct DLNode DataType data ; struct DLNodeprior, next; DLNode,DLinkedList ;void DLin

58、sertl(DLinkedList L , int x , int y) /在双循环链表中插入结点 p=L->next ; 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 插入至U q与 p指向的结点之间p->prior=s ; q->next=s ; elseprintf( " 没有值为 x 的结点”)；exit(0) ； void DLDelete(DLinkedList L , int x) /在双循环链表中删除结点 p=L->next ; while(p!=L&am