当前位置：文档之家 › 数据结构第二章习题(1)

数据结构第二章习题(1)

  • 格式：pdf
  • 大小：166.42 KB
  • 文档页数：8

下载文档原格式

  / 8

合集下载

数据结构课后习题及解析第二章

数据结构课后习题及解析第二章
利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。
例如m的初值为20；n=7，7个人的密码依次是：3，1，7，2，4，8，4，出列的顺序为6，1，4，7，2，3，5。
第二章答案
约瑟夫环问题
约瑟夫问题的一种描述为：编号1,2,…,n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。
9.假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。
10.已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
r=p;
}
}
r->next=L->next;
printf("请输入第一个报数上限值m(m>0):");
scanf("%d",&m);
printf("*****************************************\n");
printf("出列的顺序为:\n");
q=L;
p=L->next;
7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。

数据结构第二章习题课

数据结构第二章习题课

数据结构第二章习题课1、试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。

答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。

链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。

头结点是我们人为地在链表的开始结点之前附加的一个结点。

有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。

而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。

2、何时选用顺序表、何时选用链表作为线性表的存储结构为宜?答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：1) 基于空间的考虑。

当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。

2) 基于时间的考虑。

若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等操作时，宜采用链表做存储结构。

并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。

3、在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点，删除一个结点需平均移动(n-1)/2个结点。

具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。

i越接近n 则所需移动的结点数越少。

4、为什么在单循环链表中设置尾指针比设置头指针更好?答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和rear, 查找时间都是O(1)。

数据结构习题及答案 (2)

数据结构习题及答案 (2)

第二章线性表一、选择题1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )（A）110 （B）108（C）100 （D）120参考答案：B2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。

（A）64（B）63 （C）63.5 （D）7参考答案：C3.线性表采用链式存储结构时，其地址（）。

(A) 必须是连续的 (B) 部分地址必须是连续的(C) 一定是不连续的 (D) 连续与否均可以参考答案：D4. 在一个单链表中，若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;参考答案：B5.在一个单链表中，若删除p所指结点的后续结点，则执行（）（A）p->next=p->next->next; （B）p=p->next; p->next=p->next->next;（C）p->next=p->next; （D）p =p->next->next;参考答案：A6.下列有关线性表的叙述中，正确的是（）（A）线性表中的元素之间隔是线性关系（B）线性表中至少有一个元素（C）线性表中任何一个元素有且仅有一个直接前趋（D）线性表中任何一个元素有且仅有一个直接后继参考答案：A7.线性表是具有n个（）的有限序列（n≠0)（A）表元素（B）字符（C）数据元素（D）数据项参考答案：C二、判断题1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。

（）2.如果没有提供指针类型的语言，就无法构造链式结构。

（）3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。

《数据结构》习题及答案：第2章 线性表(第1次更新2012-3)

《数据结构》习题及答案：第2章 线性表(第1次更新2012-3)

第2章线性表一、选择题1.表长为N 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（），删除一个元素需要移动的元素个数为（）。

【＊＊，★】A. (N-1)/2B. NC. N+1D. N-1E. N/2F. (N+1)/2G. (N-2)/22.线性表是具有N 个（）的有限序列。

【＊】A、表元素B、字符C、数据元素D、数据项E、信息3.“线性表的逻辑顺序和物理顺序总是一致的。

”这个结论是（）。

【＊】A、正确的B、错误的C、不一定，与具体结构有关。

4.线性表采用链式存储结构时，要求内存中可用存储单元的地址（）。

【＊，★】A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以。

5.带头结点的单链表为空的判定条件是（）。

【＊】A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL6.不带头结点的单链表head 为空的判定条件是（）。

【＊】A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL7.非空的循环单链表head 的尾结点P 满足（）。

（注:带头结点）【＊】A、P->NEXT=NULLB、p=NULLC、p->next==headD、p==head8.在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。

【＊，★】A、O(1)B、O(n)C、O(n2)D、O(nlog2n)9.在一个单链表中，若删除P 所指结点的后继结点，则执行（）。

【＊，★】A、p->next=p->next->nextB、p=p->next;p->next=p->next->nextC、p->next=p->next;D、p=p->next->next;10.在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（）。

数据结构课后习题与解析第二章

数据结构课后习题与解析第二章

第二章习题1. 描述以下三个概念的区别：头指针，头结点，首元素结点。

2. 填空：（1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。

（2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。

在单链表中，逻辑上相邻的元素，其物理位置相邻。

（3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。

3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。

按要求从下列语句中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是：。

b. 在P结点前插入S结点的语句序列是：。

c. 在表首插入S结点的语句序列是：。

d. 在表尾插入S结点的语句序列是：。

供选择的语句有：（1）P->next=S;（2）P->next= P->next->next;（3）P->next= S->next;（4）S->next= P->next;（5）S->next= L;（6）S->next= NULL;（7）Q= P;（8）while(P->next!=Q) P=P->next;（9）while(P->next!=NULL) P=P->next;（10）P= Q;（11）P= L;（12）L= S;（13）L= P;4. 设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。

试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。

5. 写一算法，从顺序表中删除自第i个元素开始的k个元素。

6. 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。

试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。

数据结构Java版第二章习题

数据结构Java版第二章习题

（依据自己的状况选作部分习题，不要剽窃）第二章习题次序储存线性表一判断题1．线性表的逻辑次序与储存次序老是一致的。

×2．次序储存的线性表能够按次号随机存取。

√3．次序表的插入和删除操作不需要付出很大的时间代价，由于每次操作均匀只有近一半的元素需要挪动。

×4．线性表中的元素能够是各种各种的，但同一线性表中的数据元素拥有同样的特征，所以是属于同一数据对象。

√5．在线性表的次序储存构造中，逻辑上相邻的两个元素在物理地点上其实不必定紧邻。

×6．在线性表的次序储存构造中，插入和删除时，挪动元素的个数与该元素的地点相关。

√二单项选择题 ( 请从以下 A，B，C，D 选项中选择一项 )1．线性表是 ( A )。

(A)一个有限序列，能够为空；(B)一个有限序列，不可认为空；(C)一个无穷序列，能够为空；(D)一个无序序列，不可认为空。

2．对次序储存的线性表，设其长度为n，在任何地点上插入或删除操作都是等概率的。

插入一个元素时均匀要挪动表中的（ A ）个元素。

(A) n/2(B) n+1/2(C) n -1/2(D) n三填空题1．在次序表中做插入操作时第一检查___表能否满了 ______________。

四算法设计题1．设线性表寄存在向量A[arrsize]的前elenum个重量中，且递加有序。

试写一算法，将x插入到线性表的适合地点上，以保持线性表的有序性。

而且剖析算法的时间复杂度。

2．已知一次序表A，其元素值非递减有序摆列，编写一个函数删除次序表中剩余的值同样的元素。

3．编写一个函数，从一给定的次序表A 中删除值在 x~y(x<=y) 之间的所有元素，要求以较高的效率来实现。

提示：能够先将序表中所有在 x~y 之的元素置成一个特别的，其实不立刻除它，而后从最后向前挨次描，拥有特别的元素后，移后来面的元素将其除去。

4．性表中有 n 个元素，每个元素是一个字符，存于向量R[n] 中，写一算法，使 R 中的字符按字母字符、数字字符和其余字符的序摆列。

数据结构习题(1-2-3章)

第一章绪论一．选择题1．下面关于算法说法正确的是（）A．算法最终必须由计算机程序实现B．为解决某问题的算法同为该问题编写的程序含义是相同的C．算法的可行性是指指令不能有二义性D．以上几个都是错误的2．以下哪一个术语与数据的存储结构无关？（）A．栈 B．哈希表 C．线索树 D．循环队列3．算法复杂度通常是表达算法在最坏情况下所需要的计算量，O(1)的含义是（）A．算法执行一步就完成B．算法执行1秒钟就完成C．算法执行常数步就完成 D．算法执行可变步数就完成4．数据结构研究的内容是（）。

A．数据的逻辑结构 B．数据的存储结构C．建立在相应逻辑结构和存储结构上的算法 D．包括以上三个方面5．一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（）。

A．确定性、可行性、有穷性 B．易读性、确定性、有效性C．有穷性、稳定性、确定性 D．可行性、易读性、有穷性6．以下关于数据的逻辑结构的叙述中正确的是（）。

A．数据的逻辑结构是数据间关系的描述B．数据的逻辑结构反映了数据在计算机中的存储方式C．数据的逻辑结构分为顺序结构和链式结构D．数据的逻辑结构分为静态结构和动态结构7．下列时间复杂度中最坏的是（）A．O(1) B．O(n) C．O(log2n） D．O(n2)8．算法的时间复杂度取决于（）A．待处理数据的初态 B．问题的规模C．程序本身所占的空间 D．问题的规模和待处理数据的初态二．综合应用题1.有下列运行时间函数：（1）f1(n)=1000; （2）f2(n)=n2+1000n; （3）f3(n)=3n3+100n2+n+1;分别写出相应的大O表示的运算时间。

2.下面函数mergesort执行的时间复杂度为多少?假设函数调用为mergesort(1,n)，merge 函数时间复杂度为 O(n)void mergesort(int i,int j){int m;if(i!=j){mergesort(i,m);mergesort(m+1,j);merge(i,j,m);//本函数时间复杂度为 O(n)}}第二章线性表一．选择题1．下述哪一条是顺序存储结构的优点？（）A．存储密度大 B．插入运算方便C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。

数据结构第二章参考答案

数据结构第二章参考答案习题21. 填空题（1）在一个单链表中，已知每个结点包含data和next两个域，q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（___________）和（___________）操作。

答案：q->next = s; s->next = p; 或 s->next=q->next; q->next = s; （2）表长为n的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（___________），删除一个元素需要移动元素的平均个数为（___________）。

答案：n/2 (n-1)/2（3）表长为0的线性表称为（___________）。

答案：空表（4）动态内存管理是操作系统的基本功能之一，其作用是响应用户程序对内存的（___________）和（___________）请求。

答案：申请释放（5）顺序表多采用（___________）实现的，是一种随机存取结构，对表中任意结点存取操作的时间复杂度为（___________）。

而查找链表中的结节，需要从头指针起顺着链扫描才能得到，平均时间复杂度为（___________）。

因此，若线性表的操作主要是进行查找，很少进行插入或删除操作时，采用（___________）表比较合适。

答案：数组 O(1) O(n) 顺序（6）在链表某个位置上进行插入和删除操作，只需要修改（___________）即可，而无须移动大量元素，操作的时间复杂度为（___________）。

而在顺序表中进行插入和删除操作，往往要移动大量元素，平均移动元素的数目为（___________），平均时间复杂度为（___________）。

因此，若对线性表进行频繁的插入和删除操作时，采用（___________）表相对合适。

若插入和删除主要发生在表头和表尾，则采用（___________）表更为合适。

数据结构1-2章习题课答案


14
1-5 试说明数据的逻辑结构、存储结构和算法三者之间的关系。 答：数据的逻辑结构、存储结构和算法是数据结构所讨论的三个 方面。 1个数据逻辑结构可有多种不同的存储结构；存储结构是对 逻辑结构实现；算法是基于逻辑结构对操作的实现；函数是 基于存储结构对算法的实现，是程序；
15
1-6 请给出下列函数的大O和Ω表示：
}
4
16. 一维数组逻辑结构是 对于二维方式.
.
对于一个二维数组A[m][n],若采用行优先顺序存储的
方式, 则任一数组元素A[i][j]相对于A[0][0]的地址为
.
5
补充题: 按增长率由小到大的顺序排列下列各函数： 2100，(3/2)n，(2/3)n，(4/3)n，nn，n2/3， n1/2， n!，n，log2n，n/log2n，log22n，log2(log2n)， nlog2n，nlog2n
2
7. 在顺序表中插入一个元素，需要平均移动
元素，具体移动的元素个数与
8. 在顺序表中逻辑上相邻的元素的物理位置 单链表中逻辑上相邻的元素的物理位置 置由 指示。
有关。
紧邻。 紧邻。
9. 在单链表中，除了首元结点外，任一结点的存储位 10. 在单链表中设置头结点的作用是 。
3
14. 从一维数组A[n]中顺序找出一个最大值元素的时间复杂度
数据结构: 所研究内容的着重点主要体现在三个方面： 第一是数据间的逻辑关系，即数据元素之间的关系。 第二是数据的存储关系，即数据在计算机中的存储结构。 第三是算法，即定义在逻辑关系上的一组操作。 因此，简单说来，数据结构所研究的问题是如何将现实世界中的事 物合理描述为计算机世界中所研究的对象，并根据研究对象的特点， 分析对象之间的关系、存储结构和操作的学科。

数据结构部分习题

数据结构部分习题一、问答题1、简述下列术语：线性表，顺序表，链表。

2、何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么?3、在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个因素?4、链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?二、单选题1、在表长为n的单链表中,算法时间复杂度为O(n)的操作是( )。

A. 查找单链表中第i个结点B. 在p结点之后插入一个结点C. 删除表中第一个结点D. 删除p结点的直接后继结点2、在下列链表中不能从当前结点出发访问到其余各结点的是( )。

A. 单链表B. 单循环链表C. 双向链表D. 双向循环链表3、线性表采用顺序存储时，其地址( )A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续与否均可以4、线性表采用链式存储结构时，其地址( )A．必须是连续的B．部分地址必须是连续的C.一定是不连续的D．连续与否均可以5、在长度为n的顺序表的第i个数据元素(1≤i≤n)之前插入一个数据元素,元素的移动次数为( )。

A. n-i+1B. n-iC. iD. i-16、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )。

A. 顺序表B. 用头指针表示的单循环链表C. 用尾指针表示的单循环链表D. 单链表7、在需要经常查找结点的前驱与后继的场合中，使用( )比较合适。

A．单链表B．双向链表C．单循环链表D．循环链表8、在一个单链表h中，若要删除由指针q所指向结点的直接后继结点，则执行（）。

A．p = q->next ; p->next = q->next;B．p = q->next ; q->next = p;C．p = q->next ; q->next = p->next;D．q->next = q->next->next; q->next = q;9、9、链表不具有的特点是（）。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

B. 单链表
C. 双链表
D. 单循环链表
3.具有线性结构的数据结构是（ ）。
A. 图
B. 树
C. 广义表
D. 栈
4.在一个长度为 n 的顺序表中，在第 i 个元素之前插入一个新元素时，需向后移动（ ）
个元素。
A. n-i
B. n-i+1
C. n-i-1
5.非空的循环单链表 head 的尾结点 p 满足（ ）。
A. n-i
B. n-i+1
C. n-i-1
D. i+1
10.线性表是n个（ ）的有限序列。
A. 表元素
B. 字符 C. 数据元素 D. 数据项
11.从表中任一结点出发，都能扫描整个表的是（ ）。
A. 单链表
B. 顺序表
C. 循环链表
D. 静态链表
12.在具有n个结点的单链表上查找值为x的元素时，其时间复杂度为（ ）。
A. q->next=s->next；s->next=p； B. s->next=p；q->next=s->next；
C. p->next=s->next；s->next=q； D. s->next=q；p->next=s->next； 24.在以下的叙述中，正确的是（ ）。
A. 线性表的顺序存储结构优于链表存储结构 B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
A. p->next=p->next->next;
B. p=p->next;p->next=p->next->next;
C. p =p->next;
D. p=p->next->next; 17.将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（ ）。
A. O(1)
B. O(n)
C. O(m)
第二章 线性表
一、选择题
1.若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素算法的时间复 杂度（ ）。
A. O(log2n)
B.O(1)
C. O(n)
D.O(n2)
2.若一个线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素，则采用（ ）
存储方式最节省时间。
A. 顺序表
D. O(m+n)
18.线性表的顺序存储结构是一种（ ）存储结构。
A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取
19.顺序表中，插入一个元素所需移动的元素平均数是（ ）。
A. (n-1)/2
B. n
C. n+1
20.循环链表的主要优点是（ ）。
A. 不再需要头指针
B. 已知某结点位置后能容易找到其直接前驱
操作是（ ）。
A. p->next=q;q->prior=p;p->next->prior=q;q->next=q;
B. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;
C. q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;
int k;
if(i<1||i>L->length) return ERROR;
for(k=i-1;k<L->length-1;k++)
L->slist[k]= （1）
;
（2）
;
return OK;
}
4、函数实现单链表的删除算法，请在空格处将算法补充完整。
int ListDelete(LinkList L,int i,ElemType *s){
D. q->next=p->next;q->prior=p;p->next=q;p->next=q;
8.线性表采用链式存储时，结点的存储地址（ ）。
A. 必须是连续的
B. 必须是不连续的
C. 连续与否均可
D. 和头结点的存储地址相连续
9.在一个长度为n的顺序表中删除第i个元素，需要向前移动（ ）个元素。
D. i
A. p->next==head
B. p->next==NULL
C. p==NULL
D. p==head
6.链表不具有的特点是（ ）。
A. 可随机访问任一元素
B. 插入删除不需要移动元素
C. 不必事先估计存储空间
D. 所需空间与线性表长度成正比
7.在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的
14.一个顺序表的第一个元素的存储地址是 90，每个元素的长度为 2，则第 6 个元素的存
储地址是（ ）。
A. 98
B. 100
C. 102
D. 106
15.在线性表的下列存储结构中，读取元素花费的时间最少的是（ ）。
A. 单链表
B. 双链表
C. 循环链表
D. 顺序表
16.在一个单链表中，若删除p所指向结点的后续结点，则执行（ ）。
A. p指向头结点
B. p指向尾结点
C. p的直接后继是头结点
D. p的直接后继是尾结点
二、填空题
1、设单链表的结点结构为（data,next）。已知指针p指向单链表中的结点，q指向新结点，
欲将q插入到p结点之后，则需要执行的语句：
；
。
2、线性表的逻辑结构是
，其所含元素的个数称为线性表的
。
3、写出带头结点的双向循环链表 L 为空表的条件
if(p==NULL||j>i-1) return ERROR;
s=(LNode *)malloc(sizeof(LNode));
s->data=e;
(1)
;
(2)
;
return OK;
}/*ListInsert*/
3、函数ListDelete_sq实现顺序表删除算法，请在空格处将算法补充完整。
int ListDelete_sq(Sqlist *L,int i){
。
4、带头结点的单链表 head 为空的条件是
。
5、在一个单链表中删除p所指结点的后继结点时，应执行以下操作：
q = p->next;
p->next=_ ___;
三、判断题
1、单链表不是一种随机存储结构。 2、在具有头结点的单链表中，头指针指向链表的第一个数据结点。 3、用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指针。 4、顺序存储方式只能用于存储线性结构。 5、在线性表的顺序存储结构中，逻辑上相邻的两个元素但是在物理位置上不一定是相邻的。 6、链式存储的线性表可以随机存取。
3. 设一个带头结点的单向链表的头指针为 head，设计算法，将链表的记录，按照 data 域的 值递增排序。
4. 编写算法,将一个头指针为 head 不带头结点的单链表改造为一个单向循环链表，并分析算 法的时间复杂度。
5. 已 知 head 为 带 头 结 点 的 单 循 环 链 表 的 头 指 针 ， 链 表 中 的 数 据 元 素 依 次 为 （ a1 ， a2,a3,a4,…,an）,A为指向空的顺序表的指针。阅读以下程序段，并回答问题： （1）写出执行下列程序段后的顺序表A中的数据元素； （2）简要叙述该程序段的功能。 if(head->next!=head) { p=head->next; A->length=0; while(p->next!=head){ p=p->next; A->data[A->length ++]=p->data; if(p->next!=head)p=p->next; }
C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况 D. 线性表的链表存储结构优于顺序存储结构 25.在表长为 n 的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需
移动的平均个数为（ ）。
A. (n-1)/2
B. n/2
C. (n+1)/2
D. n
26.在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 和 p 之间插入一个
void f2(SeqList *L){ int i,j,k; k=0; for(i=0;i<L->length;i++){ for(j=0;j<k && L->data[i]!=L->data[j];j++); if(j==k){ if(k!=i)L->data[k]=L->data[i]; k++; } } L->length=k;
C. 在进行插入、删除运算时能保证链表不断开
D. 在表中任一结点出发都能扫描整个链表
21.不带头结点的单链表 head 为空的判定条件是（
D. (n+1)/2 ）。
A. head==NULL
B. head->next==NULL
C. head->next==head
D. head!=NULL
22.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（ ）。
LNode *p,*q;
int j;
p=L;j=0;
while((
（1） )&&(j<i-1)) { p=p->next;j++; }