下载文档原格式
第1章4．答案：（1）顺序存储结构顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。
（2）链式存储结构顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。
但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。
所以链式存储结构通常借助于程序设计语言的指针类型来描述。
5. 选择题(1)~(6)：CCBDDA6．（1）O(1) （2）O(m*n) （3）O(n2)（4）O(log3n) （5）O(n2) （6）O(n)第2章1．选择题（1）~（5）：BABAD （6）~（10）：BCABD （11）~（15）：CDDAC 2．算法设计题（1）将两个递增的有序链表合并为一个递增的有序链表。
要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。
表中不允许有重复的数据。
[题目分析]合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，依次摘取其中较小者重新链接在Lc表的最后。
如果两个表中的元素相等，只摘取La表中的元素，删除Lb表中的元素，这样确保合并后表中无重复的元素。
当一个表到达表尾结点，为空时，将非空表的剩余元素直接链接在Lc表的最后。
void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){//合并链表La和Lb，合并后的新表使用头指针Lc指向pa=La->next; pb=Lb->next;//pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点Lc=pc=La; //用La的头结点作为Lc的头结点while(pa && pb){ if(pa->data<pb->data){pc->next=pa; pc=pa; pa=pa->next;}//取较小者La中的元素，将pa链接在pc的后面，pa指针后移else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;}//取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移else //相等时取La中的元素，删除Lb中的元素{pc->next=pa;pc=pa;pa=pa->next;q=pb->next; delete pb ; pb =q;}}pc->next=pa?pa:pb; //插入剩余段delete Lb; //释放Lb的头结点}（5）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A中的元素为非零整数，要求B、C表利用A表的结点）。
数据结构(c语言版)课后习题答案完整版数据结构(C语言版)课后习题答案完整版一、数据结构概述数据结构是计算机科学中一个重要的概念，用来组织和存储数据，使之可以高效地访问和操作。
在C语言中，我们可以使用不同的数据结构来解决各种问题。
本文将提供完整版本的C语言数据结构的课后习题答案。
二、顺序表1. 顺序表的定义和基本操作顺序表是一种线性表，其中的元素在物理内存中连续地存储。
在C 语言中，我们可以通过定义结构体和使用指针来实现顺序表。
以下是顺序表的一些基本操作的答案：（1）初始化顺序表```ctypedef struct{int data[MAX_SIZE];int length;} SeqList;void InitList(SeqList *L){L->length = 0;}```（2）插入元素到顺序表中```cbool Insert(SeqList *L, int pos, int elem){if(L->length == MAX_SIZE){return false; // 顺序表已满}if(pos < 1 || pos > L->length + 1){return false; // 位置不合法}for(int i = L->length; i >= pos; i--){L->data[i] = L->data[i-1]; // 向后移动元素 }L->data[pos-1] = elem;L->length++;return true;}```（3）删除顺序表中的元素```cbool Delete(SeqList *L, int pos){if(pos < 1 || pos > L->length){return false; // 位置不合法}for(int i = pos; i < L->length; i++){L->data[i-1] = L->data[i]; // 向前移动元素 }L->length--;return true;}```（4）查找顺序表中的元素```cint Search(SeqList L, int elem){for(int i = 0; i < L.length; i++){if(L.data[i] == elem){return i + 1; // 找到元素，返回位置 }}return -1; // 未找到元素}```2. 顺序表习题解答（1）逆置顺序表```cvoid Reverse(SeqList *L){for(int i = 0; i < L->length / 2; i++){int temp = L->data[i];L->data[i] = L->data[L->length - 1 - i]; L->data[L->length - 1 - i] = temp;}}```（2）顺序表元素去重```cvoid RemoveDuplicates(SeqList *L){for(int i = 0; i < L->length; i++){for(int j = i + 1; j < L->length; j++){if(L->data[i] == L->data[j]){Delete(L, j + 1);j--;}}}}```三、链表1. 单链表单链表是一种常见的链式存储结构，每个节点包含数据和指向下一个节点的指针。
填空题（10 ＊1’ = 10' ）一、概念题2。
2.当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。
2。
3。
当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。
2。
6。
带头结点的单链表L中只有一个元素结点的条件是L—〉Next->Next==Null。
3。
6。
循环队列的引入,目的是为了克服假溢出.4。
2。
长度为0的字符串称为空串。
4。
5.组成串的数据元素只能是字符。
4。
8.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。
7.2。
为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。
5.7。
广义表的深度是广义表中括号的重数7。
8.有向图G可拓扑排序的判别条件是有无回路。
7.9。
若要求一个稠密图的最小生成树，最好用Prim算法求解。
8。
8.直接定址法法构造的哈希函数肯定不会发生冲突。
9。
2。
排序算法所花费的时间，通常用在数据的比较和交换两大操作。
1。
1。
通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。
1。
2.对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。
1。
3。
存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。
1。
4。
抽象数据类型的定义仅取决于它的一组逻辑特性,而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变,都不影响其外部使用。
1。
5.一个算法具有五大特性:有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。
2.8.在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点,则需执行下列语句:s—〉prior= p—〉prior; s-〉next= p; p-〉prior- next= s；p-〉prior= s；。
2.9。
在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空,并使得对单链表的操作（如插入和删除)在各种情况下统一。
数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论 (1)第2章线性表 (5)第3章栈和队列 (13)第4章串、数组和广义表 (26)第5章树和二叉树 (33)第6章图 (42)第7章查找 (54)第8章排序 (65)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
在有些情况下，数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。
逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构：数据对象在计算机中的存储表示，也称为物理结构。
抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
第1章绪论2 、(1)×(2)×(3) √3 、(1)A(2)C(3)C5、f or计(算i=下1n程;序中 1 得语句频度for(j=1;j<=i; j++)for(k=1;k<=j;k ++)x=x+1;【解答】 x=x+1 得语句频度为：T(n)=1+(1+2)+(1+2+3)+. …+(1+2+……+n)=n(n+1)(n+2)/66 、编写算法，求一元多项式p。
(x)=a。
+a,x+a₂X2+……、+a Xn得值p(x) 并确定算法中每一语句得执行次数与整个算法得时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数.注意：本题中得输入为a,(i=01,…n)、x 与n,输出为P。
(x)。
算法得输入与输出采用下列方法(1)通过参数表中得参数显式传递(2)通过全局变量隐式传递。
讨论两种方法得优缺点，并在算法中以您认为较好得一种实现输入输出.【解答】(1)通过参数表中得参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。
缺点：形参须与实参对应，且返回值数量有限。
(2)通过全局变量隐式传递优点：减少实参预形参得个数，从而减少内存空间以及传递数据时得时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue({ int,in;floatx,a[]p;pri n tf(hn=”);s c anf(“%f,”&n);printf(“x=”;)sca nf(“%f&x);f or(i=0;i<n; i++)s c anf(%f ,&a[i]; /*执行次数：n 次 */p=a[0];for (i=1;i<=n;i++){ p=p+a [i]*x; /*执行次数：n次*/x= x*x;}prin t f(%f” p);}算法得时间复杂度：T(n)=0(n)通过参数表中得参数显式传递f loat PolyVa lue(float a[ ], float x, i nt n)f 1 oat p, s;int;is p a X0];for(=1;i<= n;i++)/执行次数：n 次*/{s=s+a [i]* p;p=p*x;}re turn(p);算法得时间复杂度：T(n)=O(n)第2章线性表习题1、填空：(1)在顺序表中插入或者删除一个元素，需要平均挪移一半元素，具体挪移得元素个数与插入或者删除得位置有关。
大学课程《数据结构》课后习题答案第 1 章绪论课后习题讲解1. 填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
【解答】数据元素⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。
【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。
⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。
【解答】集合，线性结构，树结构，图结构⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。
【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。
【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。
【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺在一般情况下，一个算法的时间复杂度是（）的函数。
【解答】问题规模⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。
【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。
2. 选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。
A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。
⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。
则表示该遗产继承关系的最合适的数据结构应该是（）。
数据结构(C语言版)(第2版)课后习题答案数据结构(C语言版)(第2版)课后习题答案1. 简介数据结构是计算机科学领域中非常重要的一门学科，它研究的是数据的组织、存储和管理方式。
本文将针对《数据结构(C语言版)(第2版)》的课后习题提供答案，帮助读者更好地理解和应用数据结构。
2. 第一章: 绪论在第一章中，主要介绍了数据结构的基本概念、分类和基本操作。
以下是部分习题的答案：2.1 习题1习题描述：什么是数据结构？答案：数据结构是指数据对象中元素之间的关系，以及对这些关系进行操作的方法和技术的集合。
2.2 习题2习题描述：数据结构的分类有哪些？答案：数据结构可以分为线性结构和非线性结构。
线性结构包括线性表、栈、队列等；非线性结构包括树、图等。
3. 第二章: 线性表第二章介绍了线性表的定义、分类和实现。
以下是部分习题的答案：3.1 习题1习题描述：什么是线性表？答案：线性表是由n个数据元素a1, a2, ..., an组成的有限序列，其中元素之间存在着一一对应的关系。
3.2 习题2习题描述：线性表的分类有哪些？答案：线性表可以分为顺序表和链表。
顺序表是用一段地址连续的存储单元一次存储线性表的所有元素，而链表是采用链式存储结构，通过每个元素存储其后继元素的地址来实现元素之间的逻辑关系。
4. 第三章: 栈与队列第三章讲解了栈和队列的定义、特性和实现。
以下是部分习题的答案：4.1 习题1习题描述：栈和队列有什么区别？答案：栈是一种后进先出的线性表，只能在表尾进行插入和删除操作；队列是一种先进先出的线性表，只能在表的一端进行插入和删除操作。
4.2 习题2习题描述：栈的应用有哪些？答案：栈在计算机科学中有广泛的应用，如函数的调用和返回、括号匹配、表达式求值等。
5. 第四章: 串第四章讲解了串的定义、模式匹配和实现。
以下是部分习题的答案：5.1 习题1习题描述：什么是串？答案：串是由零个或多个字符组成的有限序列，串中的字符个数称为串的长度。
数据结构部分课后习题答案第一章1.1数据的逻辑结构是从具体问题中抽象出来的数学模型，体现了事物的组成和事物之间的逻辑关系。
数据的存储结构主要用来解决各种逻辑结构在计算机中物理存储表示的问题。
1.2事前分析和事后统计事前分析：优点，程序不必运行，所得结果只依赖于算法本身缺点，不够精确事后统计：优点，精确缺点，必须运行程序，所得结果依赖于硬件、环境等因素考虑赋值、运算操作执行的次数第3行赋值2次第6行赋值执行n次，加法执行n次所以，总共2n+2次操作，算法复杂度为O(n)1.4y= y + i * j 执行次数：1.5第二章2.9内存中一片连续空间（不妨假设地址从1到m）提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。
答：S1和S2共享内存中一片连续空间（地址1到m），可以将S1和S2的栈底设在两端，两栈顶向共享空间的中心延伸，仅当两栈顶指针相邻（两栈顶指针值之差的绝对值等于1）时，判断为栈满，当一个栈顶指针为0，另一个栈顶指针m+1时为两栈均空。
2.10线性表是数据项组成的一种有限且有序的序列，各元素之间呈线性关系。
从逻辑结构来说，栈和队列与线性表相同，都是典型的线性结构。
与线性表不同的是，栈和队列的操作特殊，受到一定的限制，仅允许在线性表的一端或两端进行。
栈是限定仅在一端进行插入删除的线性表，无论插入、删除还是读取都在一端进行，按后进先出的原则。
队列的元素只能从一端插入，从另一端删除，按先进先出的原则进行数据的存取。
2.11共有132种合法序列。
235641序列可以。
154623序列不可以。
对于每一个数来说，必须进栈一次、出栈一次。
我们把进栈设为状态‘1’，出栈设为状态‘0’。
n个数的所有状态对应n个1和n个0组成的2n位二进制数。
由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b)，因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数，1的累计数不小于0的累计数的方案种数。
第1章绪论一、基础知识题1.1 简述下列概念数据，数据元素，数据类型，数据结构，逻辑结构，存储结构，算法。
【解答】数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。
数据元素是数据的基本单位。
在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。
数据类型是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种总体描述。
每一种计算机程序设计语言都定义有自己的数据类型。
“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。
作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。
而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。
数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。
数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则依赖于存储结构。
数据结构在计算机中的表示称为物理结构，又称存储结构。
是逻辑结构在存储器中的映像，包括数据元素的表示和关系的表示。
逻辑结构与计算机无关。
算法是对特定问题求解步骤的一种描述，是指令的有限序列。
其中每一条指令表示一个或多个操作。
一个算法应该具有下列特性：有穷性、确定性、可行性、输入和输出。
1.2数据的逻辑结构分哪几种，为什么说逻辑结构是数据组织的主要方面？【解答】数据的逻辑结构分为线性结构和非线性结构。
（也可以分为集合、线性结构、树形结构和图形即网状结构）。
逻辑结构是数据组织的某种“本质性”的东西：（1）逻辑结构与数据元素本身的形式、内容无关。
（2）逻辑结构与数据元素的相对位置无关。
（3）逻辑结构与所含数据元素的个数无关。
1.3 试举一个数据结构的例子，叙述其逻辑结构、存储结构、运算三方面的内容。
【解答】学生成绩表，逻辑结构是线性结构，可以顺序存储（也可以链式存储），运算可以有插入、删除、查询，等等。
1.4 简述算法的五个特性，对算法设计的要求。
【解答】算法的五个特性是：有穷性、确定性、可行性、零至多个输入和一至多个输出。
对算法设计的要求：正确性，易读性，健壮性，和高的时空间效率（运算速度快，存储空间小）。
1.5 设n是正整数，求下列程序段中带@记号的语句的执行次数。
(1)i=1;k=0; (2) i=1;j=0;while(i<n) while(i+j<=n) {k=k+50*i; i++; @ {if(i>j)j++; @} else i++; }@(3)x=y=0; (4)x=91;y=100;for(i=0;i<n;i++) @ while(y>0)for(j=0;j<n;j++) @ if(x>100) {x++; @ {x=x-10; y--;@for(k=0;k<n;k++) @ }y++; @ else x++; @}【解答】(1)n-1(2)i= ⎡n/2⎤，j=⎣n/2⎦(3)n+1, n(n+1), n2,(n+1)n2, n3(4)100, 10001.6 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2n)，A2的时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。
【解答】对算法A1和A2的时间复杂度T1和T2取对数，得nlog2和2log n。
显然，当n<4时，算法A1好于A2；当n=4时，两个算法时间复杂度相同；当n>4时，算法A2好于A1。
1.7 选择题：算法分析的目的是（）A、找出数据结构的合理性B、研究算法中的输入和输出的关系C、分析算法的效率以求改进D、分析算法的易懂性和文档特点【解答】C二、算法设计题1.8 已知输入x，y，z三个不相等的整数，设计一个“高效”算法，使得这三个数按从小到大输出。
“高效”的含义是用最少的元素比较次数、元素移动次数和输出次数。
【算法1.8】void Best(){//按序输出三个整数的优化算法int a,b,c,t;scanf(“%d%d%d”,&a,&b,&c);if(a>b){t=a; a=b; b=t:} //a和b已正序if(b>c){t=c; c=b; //c已到位if(a>t) {b=a; a=t;} //a和b已正序else b=t;}printf(“%d,%d,%d\n”,a,b,c);//最佳2次比较，无移动；最差3次比较，7个赋值}1.9 在数组A[n]中查找值为k的元素，若找到则输出其位置i(1≤i≤n)，否则输出0作为标志。
设计算法求解此问题，并分析在最坏情况下的时间复杂度。
【题目分析】从后向前查找，若找到与k值相同的元素则返回其位置，否则返回0。
【算法1.9】int Search(ElemType A[n+1], ElemType k){i=n;while(i>=1)&&(A[i]!=k)) i--;if(i>=1) return i;else return 0;}当查找不成功时，总的比较次数为n+1次，所以最坏情况下时间复杂度为O(n)。
在学过第 9 章“查找”后，可优化以上算法:设“监视哨”。
算法如下：int Search(ElemType A[n+1], ElemType k){i=n; A[0]=k;while(A[i]!=k) i--;return i;}研究表明，当n>=1000时，算法效率提高50%。
第2章线性表一、基础知识题2.1 试述头指针、头结点、元素结点、首元结点的区别，说明头指针和头结点的作【解答】指向链表第一个结点（或为头结点或为首元结点）的指针称为头指针。
“头指针”具有标识一个链表的作用，所以经常用头指针代表链表的名字，如链表L既是指链表的名字是L，也是指链表的第一个结点的地址存储在指针变量L 中，头指针为“NULL”则表示指针变量L没指向任何链表。
有时，我们在整个线性链表的第一个元素结点之前加入一个结点，称为头结点，它的数据域可以不存储任何信息（当然，作为“副产品”，头结点的数据域也可能做监视哨或存放线性表的长度等附加信息），指针域中存放的是第一个数据结点的地址，空表时为空。
“头结点”的加入，使插入和删除等操作方便、统一。
元素结点即是数据结点，至少包括元素自身信息和其后继元素的地址两个域。
首元结点是指链表中第一个数据元素的结点；为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点。
2.2分析顺序存储结构和链式存储结构的优缺点，说明何时应该利用何种结构。
【解答】①从空间上来看，当线性表的长度变化较大，难以估计其规模时，选用动态的链表作为存储结构比较合适。
由于链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不大，易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。
②从时间上看，顺序表具有按元素序号随机访问的特点，在顺序表中按序号访问数据元素的时间复杂度为O(1)；而链表中按序号访问的时间复杂度为O(n)。
所以如果经常按序号访问数据元素，使用顺序表优于链表。
在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此n较大时顺序表的插入和删除效率低。
在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作。
从这个角度考虑显然链表优于顺序表。
总之，两种存储结构各有长短，选择那一种存储结构，由实际问题中的主要因素决定。
2.3 分析在顺序存储结构下插入和删除结点时平均需要移动多少个结点。
【解答】平均移动表中大约一半的结点。
插入操作平均移动2n个结点，删除操作平均移动2n个结点。
具体移动的次数取决于表长和插入、删除的结点的)1(位置。
2.4 为什么在单循环链表中常使用尾指针，若只设头指针，插入元素的时间复杂度如何？【解答】单循环链表中无论设置尾指针还是头指针都可以遍历到表中任一个结点。
设置尾指针时，若在表尾进行插入元素或删除第一元素，操作可在O(1)时间内完成；若只设置头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为O(n)。
2.5 在单链表、双链表、单循环链表中，若知道指针p指向某结点，能否删除该结点，时间复杂度如何？【解答：】以上三种链表中，若知道指针p指向某结点，都能删除该结点。
双链表删除p所指向的结点的时间复杂度为O(1)，而单链表和单循环链表上删除p所指向的结点的时间复杂度均为O(n)。
2.6 下面算法的功能是什么？LinkedList Unknown(LinkedList la){LNode *q，*p;if(la && la->next){q=la; la=la->next; p=la;while(p->next) p=p->next;p->next=q; q->next=null;}return la;}【解答】将首元结点删除并插入到表尾（设链表长度大于1）。
2.7 选择题：在循环双链表的*p结点之后插入*s结点的操作是（）A、p->next=s; s->prior=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->prior =s; p->next=s;【解答】D2.8 选择题：若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表【解答】A二、算法设计题2.9 设ha和hb分别是两个带头结点的非递减有序单链表的头指针，试设计算法，将这两个有序链表合并成一个非递增有序的单链表。
要求使用原链表空间，表中无重复数据。
【题目分析】因为两链表已按元素值非递减次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针，若遇值相同的元素，则删除之。
