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

1、数据结构习题答案第一节 概 论一、选择题1 要求同一逻辑结构的所有数据元素具有相同的特性，这意味着 ( ) 。A.数据元素具有同一的特点*B .不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 C 每个数据元素都一样D 数据元素所包含的数据项的个数要相等2数据结构是一门研究非数值计算的程序设计问题中计算机的 ( (1) ) 以及它们之间的 ( (2) ) 和运算的学科。(1) A 操作对象B 计算方法*C 物理存储D.数据映像(2) A 结构 *B 关系 C 运算 D 算法(3) 据结构被形式地定义为(D, R),其中口是(1) 的有限集合，R是D上(2)的有限集合。(1) A

2、 算法 *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计算机算法指的是( (1) ) ，它必须具备输入、输出和 ( (2) ) 等五个特征。(1) A 计

3、算方法B 排序方法*C 解决某一问题的有限运算序列 D 调度方法(2) 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.数据元素是数据的最小单位。V2.数据结构是带有结构的数据元素的集合。，3.数据结构、数据元素、数据项

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

6、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 ；

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

8、间复杂度_，前者是算法包含的_计算量_，后者是算法需要的_存储量_。16 在一般情况下，一个算法的时间复杂度是_ 问题规模 _的函数。17 常见时间复杂度的量级有：常数阶O(_1_) 、对数阶 O(_log 2n_) 、线性阶O(_n_)、平方阶O(_n2_)和指数阶O(_2n_) 。通常认为，具有指数阶量级的算法是 _不可行_ 的。18 数据结构的基本任务是数据结构的_ 设计 _ 和 _实现 _。19 数据对象是性质相同的_数据元素_的集合。20 抽象数据类型是指一个_数学模型_以及定义在该模型上的一组操作。四、应用题1分析下列程序段的时间复杂度。i=1 ；WHILE (i<=n) i

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

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

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

12、;k3, k4>, <k4, k7>, <k4, k6>, <k5, k8>,其逻辑结构类型为树型结构。8 .分析下列程序的时间复杂度(设n为正整数)(1)int rec(int n)elseif(n=1)return(1) return(n*rec(n-1)(2)x=91； y=100；While (y>0) if(x>10) y-；(3)i=1； j=0 ；while(i+j<=n)if(i>j)j+； else i+;(4)x=n； y=0 ；while(x>=(y+1)*(y+1) y+；答： (1) O(n) (

13、2) O(1) (3) O(n) (4) O(n1/2)9设n 为正数。试确定下列各程序段中前面加记号的语句的频度：(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 每个元素都有一个直接前驱和

14、直接后继 B 线性表中至少要有一个元素 C 表中诸元素的排列顺序必须是由小到大或由大到小的 D * 除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继3顺序表是线性表的 ( ) 。A 链式存储结构 *B 顺序存储结构 C 索引存储结构 D 散列存储结构4对于顺序表，以下说法错误的是( ) 。* A 顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B 顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 C 顺序表的特点是：逻辑结构中相邻的结点在存储结构中仍相邻 D 顺序表的特点是：逻辑上相邻的元素，存储在物理位置也相邻的单元中5对顺序表上

15、的插入、删除算法的时间复杂度分析来说，通常以 ( ) 为标准操作。A 条件判断*B 结点移动 C 算术表达式D.赋值语句6对于顺序表的优缺点，以下说法错误的是( ) 。A 无需为表示结点间的逻辑关系而增加额外的存储空间 B 可以方便地随机存取表中的任一结点*C 插入和删除操作较方便 D 由于顺序表要求占用连续的空间，存储分配只能预先进行( 静态分配 )7在含有 n 个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动结点的平均次数为 ( ) 。A n *B n/2 C (n-1)/2 D (n+1)/28在含有n 个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数为 ( )

16、。A n B n/2 *C (n-1)/2 D (n+1)/29带头结点的单链表为空的条件是( ) 。A head=NULL *B head->next=NULLC head->next=head D head!=NULL10 非空单循环链表head 的尾结点 *p 满足 ( ) 。A p->next=NULLB p=NULL*C p->next=head D p=head11. 在双循环链表的 *p 结点之后插入*s 结点的操作是A p->next=s ； s->next=p->next p->next->prior=s C s->

17、prior=p p->next->prior=s s->next=p->nexts->prior=p ； p->next->prior=s ；p->next=s ；s->prior=p ： s->next=p->nexts->next=p->next*Dp->next->pror=s； p->next=s s->prior=p p->next=s ；12. 在一个单链表中，已知 *q 结点是 *p 结点的前驱结点，若在*q和*p之间插入结点*s ,s->next=p->nex

18、t( ) 。p->next=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->nex

19、t=p;14. 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前驱元素，则采用 ( ) 存储方式最节省时间。*A 顺序表B. 单链表 C 双链表D 单 循环链表15 设rear 是指向非空带头结点的单循环链表的尾指针，则删除表头结点的操作可表示为,则删除表头结点的操作可表示为A B C *Dp=rear ； rear=rear->nextrear=rear->nextrear=rear->next->next ；Ofree(p)free(rear)free(rear)p=rear->next->nextrear->next->ne

20、xt=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 指向双链表的某一结点，则双链表结构的对称性可用 ( ) 式来刻画

21、。A p->prior->next->=p->next->nextBp->prior->prior=p->next->prior*Cp->prior->next->=p->next->priorD p->next->next=p->prior->prior18 在循环链表中，将头指针改设为尾指针rear 后，其头结点和尾结点的存储位置分别是( ) 。A rear 和 rear->next->next *B rear->next 和 rear C rear->nex

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

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

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

25、线性表的_长度 _。5在单链表中，删除p 所指结点的直接后继的操作是_ 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)_ ， 在给定

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

27、前驱，则指向头结点的指针 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->

28、;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->d

29、ata=_ s->data _；s->data=_ temp_四、应用题1描述以下三个概念的区别：头指针，头结点，首元结点 （ 第一个元素结点 ）答：首元结点是指链表中存储的线性表中的第一个数据元素的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点。头指针是指向链表中的第一个结点的指针。2何时选用顺序表，何时选用链表作为线性表的存储结构为宜？答：从空间上来看，当线性表的长度变化较大、难以估计其规模时，选用动态的链表作为存储结构比较合适，但链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不大、易于事先确定规模时，为了节约存储空间，宜采用顺序存储结

30、构。从时间上来看，若线性表的操作主要是查找，很少进行插入和删除操作时，应选用顺序表。对于频繁进行插入和删除操作的线性表，宜采用链表作为存储结构。3在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？答：平均移动表中大约一半的结点，插入操作平均移动 n/2 个结点，删除操作平均移动( n-1 ) /2 个结点。具体移动的次数取决于表长和插入、删除的结点的位曾置。4为什么在单循环链表中设置尾指针比设置头指针更好？答：单循环链表中无论设置尾指针还是头指针都可以遍历表中任一个结点，但设置尾指针时，若在表尾进行插入或删除操作可在 O(1) 时间内完成，同样在表头进行插入或删

31、除操作也可在 O(1) 时间内完成。但若设 置的是头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为 O(n) 。5双链表和单循环链表中，若仅知道指针 p 指向某个结点，不知道头指针，能否将结点 *p 从相应的链表中删除？若可以，其时间复杂度各为多少？答：能删除。双链表上删除 p 所指向的结点的时间复杂度为 O(1) ，单循环链表上删除p 所指向的结点的时间复杂度为 O(n) 。6下列算法的功能是什么？LinkList *testl(LinkList *L)/L 是无头结点的单链表LinkList *q ， *p ；if(L&&L->next) q=L ； L

32、=L->next ； p=L;while(p->next) p=p->next；p->next=q; q->next=NULL ； return L ； 答： 如果长度大于 1， 则将首元结点删除并插入到表尾。7如果有 n 个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构？为什么？ 答：应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配，不能随着线性表长度的改变而变 化。而链表则可根据需要动态地申请空间，因此适用于动态变化表长的线性表。8若线性表的总数基本稳定，且很少进行插入、删除操

33、作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构？为什么？答：应选用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为 O(1) 。五、算法设计题假设算法中用到的顺序表和链表结构如下：#define maxsize 100;Typedef struct node1 datatype datamaxsize;int length SeqList;Typedef struct node2 datatype data; struct node2 *next LinkedList ;1试用顺序表作为存储结构，实现将线性表(a0 ， a1，a2, an-l)就地逆置的操作，所谓“就地”是

34、指辅助空间为 O(1) 。答： (1) 顺序表的就地逆置分析：分别用两个整型变量指向顺序表的两端，同时向中间移动，移动的同时互换两个下标指示的元素的值。void Seqreverse(SeqList *L) 顺序表的就地逆置for(i=0 ； j=L->length-1 ； i<j ； i+ ， j-) t=L->datai;L->datai=L.dataj;L->dataj=t; (2) 链表的就地逆置分析：本算法的思想是逐个地把L 的当前元素r插入到新的链表头部。void Linkedreverse(LinkedList *L) 链表的就地逆置p=L->

35、next ； L->next=NULL ；while(p!=NULL)r=p ， p=p->next ； r 指向当前待逆置的结点， p 记下下个结点r->next=L >next ； L->next=r ；放到表头 2设顺序表L 是一个递增 ( 允许有相同的值) 有序表，试写一算法将x 插入 L 中，并使 L 仍为一个有序表。答：分析：先找到 x 的正确插入位置，然后将大于 xx 插入到其位int x) xvoid SeqListinsert(SeqList *L插入到递增有序的顺序表L 中i=0;while(i<=L->length-1)&

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

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

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

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

40、n) A 中当前元i+ ； ； Bif(A.datai<B.dataj)素较小C->datak=A.datailelse C->datak=B.dataj;j+中当前元素较小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;(2)VOid Linkmerge(LinkedList *A ， LinkedList

41、 *B ， LinkedList *C)/有序链表A和B归并成有序链表Cpa=A >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

42、没有结束，将 A表剩余元素链接到C表if(pb)pc >next=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

43、个结点，将p 所指向的 la 表中的第 i 个及 q 所指向的最后一个共len 个结点插入到lb 中。void Deletelnsert(LinkedList *la ， 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=NULL；while(p&&k<i) 在 la 表中查找第 i 个结点pre=p ； p=p->nex

44、t; 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=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

45、<j-1) r=r >next ； k+ ； 查找 Lb 表中第 i 1 个元素if(!r) exit(0)；q >next=r >next ； r >next=p ；完成插入 7单链表L 是一个递减有序表，试写一高效算法，删除表中值大于 min 且小于max 的结点( 若表中有这样的结点)，同时释放被删结点空间，这里 min和max是两个给定的参数。int min答： LinkedList delete(LinkedList *L int max) 删除递减有序单链表max的结点L 中值大于 min 且小于q=L ；if(min>max) printf(

46、" min>max' n " )；exit(0) ； else p=L >next ； q 始终指向 p 的前驱while(p >data>=max) 当前元素大于或等于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 的

47、单链表 A分解成两个单链表A和B,其头结点指针分别为pa和pb,使得A链表中含有原链表 A中序号为奇数的元素， 而 B 链表中含有原链表A 中序号为偶数的元素，且保持原来的相对顺序。答：分析：用两个工作指针p 和 q 分别指示序号为奇数和序号为偶数的结点，将q 所指向的结点从A 表删除，并链接到 B 表。void decompose(LinkedList *A ， LinkedList *B) 单链表A 分解成元素序号为奇数的单链表A 和元素序号为偶数的单链表Bp=A->next；B=(LinkedList*)malloc(sizeof(LinkedList)；r=B ；while(p!

48、=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 域置为空9假设以两个元素值递增有序排列的线性表A、B 分别表示两个集合， 要求另辟空间构造一个线性表C， 其元素为两集合的交集，且表C 中的元素值也递增有序排列。用顺序表实现

49、并写出 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 的交集Ci=0 ； j=0 ； k=0 ；while(i<=A.length-1)&&(j<=B.length-1)if(A.datai=B.dataj)

50、的元素C->datak=A.datai入 C 表中k+； i+ ； j+ ；elseif(A.datai<B.dataj) i+前元素不等，值较小的下标增else j+；找到值相同相同元素写； A、B 表当C->length=k ； return C 11 假设在长度大于 1 的单循环链表中，既无头结点 也无头指针。 s 为指向链表中某个结点的指针， 试编写算法删除结点 *s 的直接前驱结点。答：分析：因为既不知道此单循环链表的头指针，也不知道其尾指针，所以找 s 的前驱就只能从s 开始，顺次向后寻找。void DeletePre(Linkedlist *s) 删除单循环链表

51、中结点 s 的直接前驱p=s ；while(p >next >next!=s) p=p >next ；找到 s 的前驱的前驱pq=p >next ； q 是 p 的后继， 即 s 的前驱p >next=s ； 将 q 删除free(q) ；12 计算带头结点的循环链表的结点个数。答： int number(Linkedlist *head) 计算单循环链表中结点的个数p=head >next ； i=0 ；while(p!=head) i+； p=p->next ； return i ；13 已知由单链表表示的线性表中，含有三类字符的数据元素 ( 如：

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

53、表表示的线性表，使其分别含有三类字符p=L >next ； pa=L ；pa >next=pa ； 分别构造三个单循环链表pb=(LinkedList*)malloc(sizeof(LinkedList)；pc=(LinkedList*)malloc(sizeof(LinkedList)；pb >next=pb ； pc >next=pc ；while(p!=L)q=p >next ; -/q记下L中下一个结点的位if(p >data<= z &&p >data>= a )链接到字母链表的头部p >next=pa &g

54、t;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表进行如下操作：删去那些既在B表中出现又在C 表中出现的元素。试对顺序表编写实现上述操作的算法( 注：题中未特别指明同一表中的元素值各不相同) 。

55、答：分析：先从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(i<A->length&&i<B.length&&k<C.length)if(B.dataj<C.datak) j+；e