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

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

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

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

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

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

6、结构包括 集合结构_、 线性结构_、 树型结构和_图状结构四种类型。4. 在线性结构中，开始结点 _没有_前驱结点，其余每个结点有且只有 _一个_个前驱结点。5. 在树形结构中，根结点只有 _一个_，其余每个结点有且只有 _一个_前驱结点；叶结点 没有后继结点，其余每个结点的后继结点可以有 任意个_6. 在图形结构中，每个结点的前驱结点和后继结点可以有_任意个_。7. 算法的五个重要特性是 _可行性_、 _确定性 _、 _有穷性 _、 _输入 _、 _输出 _。8. 下列程序段的时间复杂度是 _O（n）_。for （i=1；i<=n ；i+） Ai ， i=0 ；9. 下列程序段的时间复

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

8、算法 （包括程序）的 质量。15. 一个算法的时空性能是指该算法的 _时间复杂度和 _空间复杂度 _，前者是算法包含的 _计算 量_，后者是算法需要的 _存储量 _。16. 在一般情况下，一个算法的时间复杂度是 _问题规模 _的函数。17. 常见时间复杂度的量级有：常数阶 O（_1_）、对数阶 O（_log2n_）、线性阶 O（_n_）、平方 阶0（_n2_）和指数阶0（_2_）。通常认为，具有指数阶量级的算法是 不可行的。18. 数据结构的基本任务是数据结构的 _设计_和_实现_。19. 数据对象是性质相同的 _数据元素 _的集合。20. 抽象数据类型是指一个 _数学模型 _以及定义在该模型

9、上的一组操作。四、应用题1. 分析下列程序段的时间复杂度。i=1 ；WHILE (i<=n) i=i2； 答： 0(log2n) 2叙述算法的定义及其重要特性。 答：算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多 个操作。算法应该具有下列特性：可行性、确定性、有穷性、输入和输出。3简述下列术语：数据，数据元素，数据结构，数据对象。 答：数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程 序识别和处理的符号的集合。数据元素是数据的基本单位。在不同的条件下，数据元素又可称为 元素、结点、顶点、记录等。数据结构是指相互之间存在着一

10、种或多种关系的数据元素的集合。 数据对象是性质相同的数据元素的集合。4逻辑结构与存储结构是什么关系？ 答：在数据结构中，逻辑结构与存储结构是密切相关的，存储结构不仅将数据元素存储到计算机 中，而且还要表示各数据元素之间的逻辑关系。逻辑结构与计算机无关，存储结构是数据元素之 间的关系在计算机中的表示。5 将数量级 210, n, n2, n3, nlog2 n, log? n, 2n, n! , (2 / 3)n, n"按增长率进行排列。 答：(2/3)n , 210, log2n , n2/3, n, nlog2n , n2, n3, 2n, n!6设有数据逻辑结构为：D=k1, k

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

12、 R=<k1 , k2> , <k1 , k3> , <k3 , k5> , <k3 , k4> <k4 k7> <k4 k6> <k5 k8> 其逻辑结构类型为树型结构。8 分析下列程序的时间复杂度(设n为正整数)。(1) int rec(int n)if(n=1)return(1)； else 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+；

13、 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；j<=n ： j+) k+ ；答： (1)n-1 (2)n+(n-1)+ +1=n(n+1)/2第二节 线性表一、选择题 1线性结构中的一个结点代表一个 ( ) 。A数据元素B 数据项C 数据D 数据

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

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

16、28在含有 n 个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数为( )。A n B n/2C(n-1)/2 D(n+1)/29 带头结点的单链表head为空的条件是()。Ahead=NULL Bhead->next=NULL C head->next=head D head!=NULL 10非空单循环链表 head 的尾结点 p 满足( ) 。A p->next=NULL B p=NULLCp->next=head D p=head11在双循环链表的 p 结点之后插入 s 结点的操作是 ( ) 。A p->next=s ； s->prior=

17、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. 在一个

18、单链表中，已知q结点是p结点的前驱结点，若在q和p之间插入结点s，则执行 ( ) 。A s->next=p->next ；p->next=s ； B p->next=s->next ；s->next=p ； Cq->next=s; s->next=p ； D p->next=s; s->next=q ；13. 在一个单链表中，若p结点不是最后结点。在p之后插入结点s，则执行()。A s->next=p ；p->next=s;Bs->next=p->next ；p->next=s ；C s->next

19、=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) Brear=rear->next ；free(rear) ；Crear=rear->next->next； free(rear) ； Dp=

20、rear->next->next ； rear->next->next=p->next ；free(p) ；16在一个单链表中，若删除 p 结点的后继结点，则执行 ( ) 。Aq=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) ； 1

21、7设指针 p 指向双链表的某一结点，则双链表结构的对称性可用( ) 式来刻画。A p->prior->next->=p->next->next B p->prior->prior=p->next->priorCp->prior->next->=p->next->prior Dp->next->next=p->prior->prior18在循环链表中，将头指针改设为尾指针rear 后，其头结点和尾结点的存储位置分别是 ( ) 。A . rear 和 rear->next->ne

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

23、作只有近一半 的元素需要移动。V3.线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属 于同一数据对象。X 4.在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。V 5.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。V 6.在单链表中，可以从头结点开始查找任何一个元素。X 7.线性表的链式存储结构优于顺序存储结构。V 8.在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。X 9.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存 储结构。X10.顺序存储方式只能用于存

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

25、4. 线性表的逻辑结构是 _线性_结构，其所含结点的个数称为线性表的 _长度_。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所指

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

27、后继_。14. 在一个带头结点的单循环链表中，p指向尾结点的直接前驱，贝U指向头结点的指针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-&g

28、t;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-&

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

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

31、行插入或删除操作可在 O(1) 时间内完成，同样在表头进行插入或删除操作也可在O(1) 时间内完成。但若设置的是头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为 O(n)。5. 双链表和单循环链表中，若仅知道指针p指向某个结点，不知道头指针，能否将结点 p从相 应的链表中删除？若可以，其时间复杂度各为多少？答：能删除。双链表上删除p所指向的结点的时间复杂度为 0(1)，单循环链表上删除p所指向的 结点的时间复杂度为 O(n)。6. 下列算法的功能是什么？LinkList testl(LinkList L)单链表L是一个非递减有序表，试写一个算法将x插入其中后仍保持L的有序性。答：

32、分析：此问题的关键是在链表中找到x的插入位置，因此需要两个指针一前一后地依次向后移动。void LinkListinsert(LinkedList L， int x) x 插入有序链表 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 个元素之前插入一个元素的算法

33、。 答：分析：对不带头结点的链表操作时，要注意对第一个结点和其他结点操作的不同。 void LinkedListlnsert(LinkedList head， int x ， int i) 不带头结点的单链表的第 i 个元素之前插入一个元素p=L ： j=1;while(p!=NULL&&j<i-1)找到第 i-1 个元素p=p >next ；j+ ；if(iv=O|p=NULL) printf(”插入位置不正确 n”)；else q=(LinkedList)malloc(sizeof(LNode)；q>data=x；if(i=1) q>next=L ；

34、 L=q； 在第一个元素之前插入elseq>next=p>next ； p>next=q ； 在其他位置插入 5设A、B是两个线性表，其表中元素递增有序，长度分别为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，

35、i，k分别为顺序表A，B, C的下标while(i<m&&j<n)ifi<j)/ A中当前元素较小k=il； i+ ； else k=j;j+; / B中当前元素较小k+；if (i=m) for(t=j; t<n ; t+) k=t;k+; / B 表长度大于 A 表else for(t=i ; t<m; t+) k=t; k+; / A 表长度大于 B 表=m+n； return C;(2)VOid Linkmerge(LinkedList A ， LinkedList B ， LinkedList C)/有序链表A和B归并成有序链表Cpa=A

36、>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;/

37、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

38、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=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&

39、lt;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<j-1) r=r >next;k+ ； /查找 Lb 表中第 i 1 个元素if(!r) exit(0)；q >next

40、=r >next； r>next=p； /完成插入 7 单链表L是一个递减有序表，试写一高效算法，删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删结点空间，这里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>

41、;=max)/当前元素大于或等于 max 则P、q依次向后移动q=p ； p=p>next； while(p!=NULL)&&(p >data>mi n) /当前元素的值比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

42、分别指示序号为奇数和序号为偶数的结点，将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=p >next；/q 指向偶数序号的结点p >next=q >next;/将 q 从 A表中删除r >next=q ;/将q结点链接到B链表的末

43、尾r=q ;/ r总是指向B链表的最后一个结点p=p >next;/p指向原链表A中的奇数序号的结点r >next=NULL;/将生成B链表中的最后一个结点的next域置为空9假设以两个元素依值递增有序排列的线性表A、B分别表示两个集合，要求另辟空间构造一个线性表C,其元素为两集合的交集，且表 C中的元素也依值递增有序排列。对顺序表编写求C的算法。答：分析：用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置，若 A、B表中当前元素 值相同，贝U写入C中，并使i、j、k值增1;若A表元素值较小，则使i增1;若B表元素值较 小，则使 j 增 1，直到有一个表先结束。SeqLiS

44、t intersection(SeqList A ， SeqList B ， SeqList C) /求元素依值递增有序排列的顺序表A、 B 的交集 Ci=0 ； j=0 ；k=0；while(i<=&&(j<=)ifi=j)/找到值相同的元素k=i；/相同兀素与入 C表中k+； i+ ；j+ ； elseifi<j) i+;/ A、B表当前元素不等，值较小的下标增 1else j+；=k ； return C； 10设有线性表 A=(a1,a2,，am)和B=(b1,b2,，bn)。试编写合并A、B为线性表C的算法，使得：C=(a1 , b1,，am bm

45、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) /把链表A和B合并为C, A和B的元素间隔排列，且使用原存储空间 p=A>next；q=B>nex

46、t；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 的直接前驱结点。答：分析：因为既不知道此单循环链表的头指针，也不知道其尾指针，所以找 s 的前驱就只能从 s 开始，顺次向后寻找。void DeletePre(LinkedNod

47、e 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->next ； return i ；13已知由单链表表示的线性表中，含有三类字符的数据元素

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

49、使其分别含有三类字符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>='a')链接到字母链表的头部p>next=pa>next ; pa

50、>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表中出现的元素。试对顺序表编写实现上述操作的算法(注：题中未特别指明同一表中的元素值各不相同 )。答：

51、分析：先从B和C中找出共有元素，记为same再在A中从当前位置开始，凡小于 same的元 素均保留(存到新的位置)，等于same的就跳过，至U大于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<&&i<&&k<ifj<k) j+；else ifj>k) k+;else same=

52、j； /找到了相同元素 samewhilej=same) j+；whilek=same) k+； /j 、 k 后移到新的元素while(i<&&i<same)m+=i+；/需保留的元素移动到新位置while(i<&&i1=same i+；/跳过相同的元素while(i<m+=i+;/ A的剩余元素重新存储=m ；15双循环链表中，设计满足下列条件的算法。(1) 在值为 x 的结点之前插入值为 y 的结点。 (2) 在值为 x 的结点之后插入值为 y 的结点。 (3) 删 除值为 x 的结点。答：分析：在双循环链表中插入和删除结点要注意修

53、改双向的指针。typedef struct DLNodeDataType data ； struct DLNodeprior ， next ；DLNode， DLinkedList ； void DLinsertl(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=(DLinkedLi

54、st)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->

55、next=p->next； p->next->prior=p->prior；free(p) ； elseprintf( ”没有值为 x 的结点” ) ； exit(0) ； 16设有一个双循环链表，其中有一结点的指针为p,编写算法将p与其右边的一个结点进行交换。答： void DLchange(DLinkedList p) 将双循环链表中 p 指向的结点与其右边的一个结点进行交换q=p >next ；/ q指向p的后继p >prior >next=q ; q>prior=p >prior ； /将 p 的前驱与 q 相链接p>next

56、=q >next; p >prior=q ；/将 p 插入至卩 q 之后q->next>prior=p ； q>next=p； 17设有一个双链表，每个结点中除有prior 、data 和 next 三个域外，还有一个可访问颊度域freq ，在链表启用之前，其值均初始为0。每当链表进行一次 LocateNode(L ， x) 操作时令元素值为 x 的结点中 freq 域的值加 l ，并调整表中结点的次序，使其按访问频度的递减次序排列，以便 使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode操作的算法。答：分析：先在双链表中查找值为 x 的结点，

57、若找至则使其 freq 值增 1，然后从头至尾扫描链 表，将此结点插入至按 freq 递减顺序排列的正确位置。typedef struct DLNodeint data ， freq ； struct DLNode prior ， next； DLNode， DLinkedList ；void LocateNode(DLinkedList head ， int x) /双链表按访问频度域 freq 递减次序排列p2=head ; p仁p2 >next ;/ p2 在前，pl 在后whue(p1) /查找单链表中值为 x 的结点if(pl >data=x) pl >freq+ ； break ； /使值为 x 的结点的 freq 加 1else p2=pl ； p1=p2>next； if(p1=NULL) printf( ” Not found. n”)；elseif(p1>next=NULL) p2 >next=p1 >next； temp=p1； /在链表中找temp所指向的结点，按freq值递减应插入的位置elsep2>next=p1 >next； /插入链表中间的某一位置p