下载文档原格式
数据结构c语言版耿国华课后习题答案数据结构是计算机科学中的一个重要领域，它涉及到数据的组织、管理和存储方式，以便可以高效地访问和修改数据。
C语言作为一种高级编程语言，提供了丰富的数据结构实现方法。
耿国华教授编写的《数据结构C语言版》一书，为学习者提供了深入理解和实践数据结构的机会。
以下是该书课后习题的一些参考答案。
# 第一章绪论1. 习题1：数据结构的定义是什么？- 参考答案：数据结构是计算机科学中用于组织、管理和存储数据的方式，以便可以高效地访问和修改数据。
2. 习题2：为什么需要学习数据结构？- 参考答案：学习数据结构有助于提高编程效率，优化算法性能，以及更好地解决实际问题。
# 第二章线性表1. 习题1：线性表的特点是什么？- 参考答案：线性表的特点是数据元素之间存在一对一的线性关系，可以顺序存储或链式存储。
2. 习题3：如何实现线性表的插入操作？- 参考答案：线性表的插入操作通常涉及找到插入位置，然后将新元素插入到该位置，并调整后续元素。
# 第三章栈和队列1. 习题1：栈的后进先出（LIFO）特性是什么？- 参考答案：栈的后进先出特性意味着最后插入的元素将是第一个被删除的元素。
2. 习题2：如何用C语言实现一个队列？- 参考答案：可以用数组或链表来实现队列。
队列的基本操作包括入队（enqueue）和出队（dequeue）。
# 第四章树和二叉树1. 习题1：二叉树的定义是什么？- 参考答案：二叉树是每个节点最多有两个子节点的树结构，通常分为左子节点和右子节点。
2. 习题3：二叉树的遍历方法有哪些？- 参考答案：二叉树的遍历方法包括前序遍历、中序遍历、后序遍历和层序遍历。
# 第五章图1. 习题1：图的基本概念有哪些？- 参考答案：图由顶点（节点）和边组成，可以表示对象之间的关系。
2. 习题2：图的存储方式有哪些？- 参考答案：图的存储方式主要有邻接矩阵和邻接表两种。
# 结语通过学习《数据结构C语言版》一书，读者可以掌握各种数据结构的基本概念、特性以及实现方法。
数据结构C语言版第一二章习题答案Document number：BGCG-0857-BTDO-0089-2022第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
3．简述逻辑结构的四种基本关系并画出它们的关系图。
4．存储结构由哪两种基本的存储方法实现？5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。
A．存储结构 B．存储实现C．逻辑结构 D．运算实现（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。
A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等（4）以下说法正确的是（）。
A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构（5）以下与数据的存储结构无关的术语是（）。
A．顺序队列 B. 链表 C.有序表 D. 链栈（6）以下数据结构中，（）是非线性数据结构A．树 B．字符串 C．队 D．栈6．试分析下面各程序段的时间复杂度。
（1）x=90; y=100;?while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++) s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1)) y++;（1）O（1）（2）O（m*n）（3）O（n2）n）（4）O（log3（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
数据结构与算法课后习题解答数据结构与算法课后习题解答第一章绪论（参考答案）1.3 (1) O(n)(2) (2) O(n)(3) (3) O(n)(4) (4) O(n1/2)(5) (5) 执行程序段的过程中，x,y值变化如下：循环次数x y0（初始）91 1001 92 1002 93 100。
9 100 10010 101 10011 9112。
20 9921 91 98。
30 101 9831 91 97到y=0时，要执行10*100次，可记为O（10*y）=O（n）数据结构与算法课后习题解答1.5 2100 , (2/3)n , log2n , n1/2 , n3/2 , (3/2)n , nlog2n , 2 n , n! , n n第二章线性表(参考答案)在以下习题解答中，假定使用如下类型定义：（1）顺序存储结构：#define ***** 1024typedef int ElemType;// 实际上，ElemTypetypedef struct{ ElemType data[*****];int last; // last}sequenlist;（2*next；}linklist;（3）链式存储结构（双链表）typedef struct node{ElemType data;struct node *prior,*next；数据结构与算法课后习题解答}dlinklist;（4）静态链表typedef struct{ElemType data;int next;}node;node sa[*****];2.1 la，往往简称为“链表la”。
是副产品）2.2 23voidelenum个元素，且递增有序，本算法将x插入到向量A中，并保持向量的{ int i=0,j;while (ielenum A[i]=x) i++; // 查找插入位置for (j= elenum-1;jj--) A[j+1]=A[j];// 向后移动元素A[i]=x; // 插入元素数据结构与算法课后习题解答} // 算法结束24void rightrotate(ElemType A[],int n,k)// 以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。
数据结构(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. 单链表单链表是一种常见的链式存储结构，每个节点包含数据和指向下一个节点的指针。
数据结构(C语言版本)课后练习答案的完整版本第一章引言5。
选择题:CCBDCA 6。
尝试分析以下程序段的时间复杂性。
(1)o(1)(2)o(m * n)(3)o(N2)(4)o(log3n)(5)因为x已执行n-1n-2.1=n (n-1)/2，执行时间为O(n2)(6)O()第2章线性表1。
多项选择babadbcbdcddac 2。
算法设计问题(6)设计一种算法，通过一次遍历来确定单个链表中具有最大值的节点。
元素类型最大值(链表L ){如果(下一个==空)返回空；pmax=1-下一个；//假设第一个节点中的数据具有最大值p=L-下一个-下一个；同时(p！=NULL ){//如果在下一个节点处存在if(p-数据pmax-数据)pmax=p；p=p-下一个；}返回pmax-数据；(7)设计一种算法，通过遍历一次来反转链表中所有节点的链接方向，并且仍然使用原表的存储空间。
空逆(链表L) {//逆单个链表L p=L-头节点的下一个；下一个=空；而(p){ q=p-next；//q指向*p=l-next 的下一个p-next；l-next=p；//*p插入在头节点p=q之后；}}(10)已知长度n的线性表A采用顺序存储结构。
请编写一个时间复杂度为0(n)和空间复杂度为0(1)的算法，删除线性表中所有有值项的数据元素。
[主题分析]删除线性表中按顺序存储的元素通常涉及一系列元素的移动(删除第I个元素，并按顺序向前移动第I到第N个元素)。
本主题要求删除线性表中项目值为的所有数据元素，并且不要求元素之间的相对位置保持不变。
因此，可以考虑设置两个指针(i=1，j=n)从两端移到中间。
当遇到带有值项的数据元素时，右端元素将直接移动到带有值项的数据元素的位置。
虚删除(元素类型A[)，整数n)A是一个有n个元素的一维数组。
此算法删除值为项的中的所有元素。
{ I=1；j=n。
∑设置数组的低端和高端指针(下标)。
同时(不精确；r=p；//让r 作为指针，而(q！=null){ if(q-data data)r=q；q:=q-next。
国家计算机等级考试二级C语言公共基础知识总结第一章数据结构与算法1.1 算法算法：是指解题方案的准确而完整的描述。
算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。
算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。
特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。
算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。
指令系统：一个计算机系统能执行的所有指令的集合。
基本运算包括：算术运算、逻辑运算、关系运算、数据传输。
算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。
算法复杂度：算法时间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。
算法空间复杂度是指执行这个算法所需要的内存空间。
1.2 数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。
数据结构是指相互有关联的数据元素的集合。
数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。
数据的存储结构有顺序、链接、索引等。
线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。
非线性结构：不满足线性结构条件的数据结构。
1．3 线性表及其顺序存储结构线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。
绪论1．将下列复杂度由小到大重新排序：A．2n B．n! C．n5D．10 000 E．n*log2 (n)【答】10 000< n*log2(n)< n5< 2n < n!2．将下列复杂度由小到大重新排序：A．n*log2(n) B．n + n2 + n3C．24D．n0.5【答】24< n0.5< n*log2 (n) < n + n2 + n33．用大“O”表示法描述下列复杂度：A．5n5/2 + n2/5 B．6*log2(n) + 9nC．3n4+ n* log2(n) D．5n2 + n3/2【答】A：O (n5/2) B：O (n) C：O (n4) D：O (n2)4．按照增长率从低到高的顺序排列以下表达式：4n2 , log3n, 3n , 20n , 2000 , log2n , n2/3。
又n！应排在第几位？【答】按照增长率从低到高依次为：2000, log3n, log2n , n2/3 , 20n , 4n2 , 3n。
n！的增长率比它们中的每一个都要大，应排在最后一位。
5. 计算下列程序片断的时间代价：int i=1;while(i<=n){printf(“i=%d\n”,i);i=i+1;}【答】循环控制变量i从1增加到n，循环体执行n次，第一句i的初始化执行次数为1，第二句执行n次，循环体中第一句printf执行n次，第二句i从1循环到n，共执行n次。
所以该程序段总的时间代价为：T(n) = 1 + n + 2n = 3n+ 1 = O(n)6. 计算下列程序片断的时间代价：int i=1;while(i<=n){int j=1;while(j<=n){int k=1;while(k<=n){printf(“i=%d,j=%d,k=%d\n”,I,j,k);k=k+1;}j=j+1;}i=i+1;}【答】循环控制变量i从1增加到n，最外层循环体执行n次，循环控制变量j从1增加到n，中间层循环体执行n次，循环控制变量k从1增加到n，最内层循环体执行n次，所以该程序段总的时间代价为：T(n) = 1 + n + n｛1 + n + n[1 + n + 2n +1] +1 +1｝+ 1= 3n3 + 3n2 +4n +2= O(n3)2. 线性表1.试写一个插入算法int insertPost_seq(palist, p, x )，在palist所指顺序表中，下标为p的元素之后，插入一个值为x的元素，返回插入成功与否的标志。
数据结构c语言版严蔚敏课后习题答案数据结构是计算机科学中的一个重要领域，它涉及到数据的组织、管理和存储方式，以便可以高效地访问和修改数据。
C语言作为一种广泛使用的编程语言，提供了丰富的数据结构实现方法。
严蔚敏教授编写的《数据结构（C语言版）》是许多计算机专业学生的必读教材。
以下是对该书课后习题的一些参考答案，供学习者参考。
第一章：绪论1. 数据结构的定义：数据结构是计算机中存储、组织数据的方式，它不仅包括数据元素的类型和关系，还包括数据操作的函数。
2. 数据结构的重要性：数据结构对于提高程序的效率至关重要。
合理的数据结构可以减少算法的时间复杂度和空间复杂度。
第二章：线性表1. 线性表的定义：线性表是由n个元素组成的有限序列，其中n称为线性表的长度。
2. 线性表的顺序存储结构：使用数组来存储线性表的元素，元素的存储关系是连续的。
3. 线性表的链式存储结构：使用链表来存储线性表的元素，每个元素包含数据部分和指向下一个元素的指针。
第三章：栈和队列1. 栈的定义：栈是一种特殊的线性表，只能在一端（栈顶）进行插入和删除操作。
2. 队列的定义：队列是一种特殊的线性表，允许在一端（队尾）进行插入操作，在另一端（队首）进行删除操作。
第四章：串1. 串的定义：串是由零个或多个字符组成的有限序列。
2. 串的存储结构：串可以采用顺序存储结构或链式存储结构。
第五章：数组和广义表1. 数组的定义：数组是由具有相同类型的多个元素组成的集合，这些元素按照索引顺序排列。
2. 广义表的定义：广义表是线性表的推广，其中的元素可以是数据也可以是子表。
第六章：树和二叉树1. 树的定义：树是由节点组成的，其中有一个特定的节点称为根，其余每个节点有且仅有一个父节点。
2. 二叉树的定义：二叉树是每个节点最多有两个子节点的树。
第七章：图1. 图的定义：图是由顶点和边组成的数据结构，可以表示复杂的关系。
2. 图的存储结构：图可以用邻接矩阵或邻接表来存储。
第一章绪论习题练习答案简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。
●数据：指能够被计算机识别、存储和加工处置的信息载体。
●数据元素：就是数据的大体单位，在某些情况下，数据元素也称为元素、结点、极点、记录。
数据元素有时可以由若干数据项组成。
课后答案网数据类型：是一个值的集合和在这些值上概念的一组操作的总称。
通常数据类型可以看做是程序设计语言中已实现的数据结构。
●数据结构：指的是数据之间的彼此关系，即数据的组织形式。
一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。
●逻辑结构：指数据元素之间的逻辑关系。
●存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构.●线性结构：数据逻辑结构中的一类。
它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，而且所有结点都有且只有一个直接前趋和一个直接后继。
线性表就是一个典型的线性结构。
栈、队列、串等都是线性结构。
●非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。
数组、广义表、树和图等数据结构都是非线性结构。
试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。
答：例如有一张学生体检情况记录表，记录了一个班的学生的身高、体重等各项体检信息。
这张记录表中，每一个学生的各项体检信息排在一行上。
这个表就是一个数据结构。
每一个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来讲，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。
这几个关系就肯定了这个表的逻辑结构是线性结构。
这个表中的数据如何存储到计算机里，而且如何表示数据元素之间的关系呢? 即用一片持续的内存单元来寄存这些记录(如用数组表示)仍是随机寄存各结点数据再用指针进行链接呢? 这就是存储结构的问题。
第1章概论习题参考答案一、基础知识题1.简述下列概念数据，数据元素，数据类型，数据结构，逻辑结构，存储结构，算法。
【解答】数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。
数据元素是数据的基本单位。
在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。
数据类型是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种总体描述。
每一种计算机程序设计语言都定义有自己的数据类型。
“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。
作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。
而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。
数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。
数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则依赖于存储结构。
数据结构在计算机中的表示称为物理结构，又称存储结构。
是逻辑结构在存储器中的映像，包括数据元素的表示和关系的表示。
逻辑结构与计算机无关。
算法是对特定问题求解步骤的一种描述，是指令的有限序列。
其中每一条指令表示一个或多个操作。
一个算法应该具有下列特性：有穷性、确定性、可行性、输入和输出。
2.数据的逻辑结构分哪几种，为什么说逻辑结构是数据组织的主要方面？【解答】数据的逻辑结构分为线性结构和非线性结构。
（也可以分为集合、线性结构、树形结构和图形即网状结构）。
逻辑结构是数据组织的某种“本质性”的东西：（1）逻辑结构与数据元素本身的形式、内容无关。
（2）逻辑结构与数据元素的相对位置无关。
（3）逻辑结构与所含数据元素的个数无关。
3.试举一个数据结构的例子，叙述其逻辑结构、存储结构、运算三方面的内容。
【解答】如学生成绩表，逻辑结构是线性结构，可以顺序存储（也可以链式存储），运算可以有插入、删除、查询、等等。
4.简述算法的五个特性，对算法设计的要求。
【解答】算法的五个特性是：有穷性、确定性、可行性、零至多个输入和一至多个输出。
对算法设计的要求：正确性，易读性，健壮性，和高的时空间效率（运算速度快，存储空间小）。
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)n为偶数时，均为n div 2;你为奇数时，分别为：(n div 2)+1 和n div 2(3)n+1, n(n+1), n2,(n+1)n2, n3(4)100, 10006.有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2n)，A2的时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好?【解答】对算法A1和A2的时间复杂度T1和T2取对数，得nlog2和2logn。
显然，当n<4时，算法A1好于A2；当n=4时，两个算法时间复杂度相同；当n>4时，算法A2好于A1。
7. 选择题：算法分析的目的是（）A、找出数据结构的合理性B、研究算法中的输入和输出的关系C、分析算法的效率以求改进D、分析算法的易懂性和文档特点【解答】C二、算法设计题8. 已知输入x，y，z三个不相等的整数，设计一个“高效”算法，使得这三个数按从小到大输出。
“高效”的含义是用最少的元素比较次数、元素移动次数和输出次数。
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;}//ifprintf(“%d,%d,%d\n”,a,b,c);//最佳2次比较，无移动；最差3次比较，7个赋值}9．在数组A[n]中查找值为k的元素，若找到则输出其位置i(1≤i≤n)，否则输出0作为标志。
设计算法求解此问题，并分析在最坏情况下的时间复杂度【题目分析】从后向前查找，若找到与k值相同的元素则返回其位置，否则返回0。
int Search(ElemType A[n+1], ElemType k){i=n;wile(i>=1)&&(A[i]!=k)) i--;if(i>=1) return i;else return 0;}当查找不成功时，总的比较次数为n+1次，所以最坏情况下时间复杂度为O(n)。
第2章线性表习题参考答案一、基础知识题2.1 试述头指针、头结点、元素结点、首元结点的区别，说明头指针和头结点的作【解答】指向链表第一个结点（或为头结点或为首元结点）的指针称为头指针。
“头指针”具有标识一个链表的作用，所以经常用头指针代表链表的名字，如链表L既是指链表的名字是L，也是指链表的第一个结点的地址存储在指针变量L中，头指针为“NULL”则表示一个空表。
有时，我们在整个线性链表的第一个元素结点之前加入一个结点，称为头结点，它的数据域可以不存储任何信息（也可以做监视哨或存放线性表的长度等附加信息），指针域中存放的是第一个数据结点的地址，空表时为空。
“头结点”的加入，使插入和删除等操作方便统一。
元素结点即是数据结点，至少包括元素自身信息和其后继元素的地址两个域。
首元结点是指链表中第一个数据元素的结点；为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点。
2.2分析顺序存储结构和链式存储结构的优缺点，说明何时应该利用何种结构。
【解答】①从空间上来看，当线性表的长度变化较大，难以估计其规模时，选用动态的链表作为存储结构比较合适，但链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不大，易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。
②从时间上看，顺序表具有按元素序号随机访问的特点，在顺序表中按序号访问数据元素的时间复杂度为O(1)；而链表中按序号访问的时间复杂度为O(n)。
所以如果经常按序号访问数据元素，使用顺序表优于链表。
在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此n较大时顺序表的插入和删除效率低。
在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作。
从这个角度考虑显然链表优于顺序表。
总之，两种存储结构各有长短，选择那一种存储结构，由实际问题中的主要因素决定。
2.3 分析在顺序存储结构下插入和删除结点时平均需要移动多少个结点。
【解答】平均移动表中大约一半的结点，插入操作平均移动个结点，删除操作平均移动个结点。
具体移动的次数取决于表长和插入、删除的结点的位置。
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结点的操作是（）la、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;lc、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 选择题：若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
la．顺序表B．双链表lc．带头结点的双循环链表D．单循环链表【解答】la二、算法设计题2.9 设ha和hb分别是两个带头结点的非递减有序单链表的头指针，试设计算法，将这两个有序链表合并成一个非递增有序的单链表。
要求使用原链表空间，表中无重复数据。
【题目分析】因为两链表已按元素值非递减次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针，若遇值相同的元素，则删除之。
该问题要求结果链表按元素值非递增次序排列，故在合并的同时，将链表结点逆置。
LinkedList Union(LinkedList ha,hb)∥ha,hb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列∥本算法将两链表合并成一个按元素值递减次序排列的单链表,并删除重复元素{ pa=ha->next; ∥pa是链表ha的工作指针pb=hb->next; ∥pb是链表hb的工作指针ha->next=null; ∥ha作结果链表的头指针，先将结果链表初始化为空while(pa!=null && pb!=null) ∥当两链表均不为空时作{while(pa->next && pa->data==pa->next->data){u=pa->next; pa->next=u->next; free(u)}∥删除pa链表中的重复元素while(pb->next && pb->data==pb->next->data){u=pb->next; pb->next=u->next; free(u)}∥删除pb链表中的重复元素if(pa->data<pb->data){r=pa->next; ∥将pa 的后继结点暂存于rpa->next=ha->next; ∥将pa结点链于结果表中，同时逆置ha->next=pa;pa=r; ∥恢复pa为当前待比较结点}else if(pb->data<pa->data){r=pb->next; ∥将pb 的后继结点暂存于rpb->next=ha->next; ∥将pb结点链于结果表中，同时逆置ha->next=pb;pb=r; ∥恢复pb为当前待比较结点}else{u=pb;pb=pb->next;free(u)}∥删除链表pb和pa中的重复元素}// while(pa!=null && pb!=null)if(pa) pb=pa; ∥避免再对pa写下面的while语句while(pb!=null) ∥将尚未到尾的表逆置到结果表中{r=pb->next; pb->next=ha->next; ha->next=pb; pb=r; }return ha}∥算法Union结束2.11 设p指向头指针为la的单链表中某结点，试编写算法，删除结点*p的直接前驱结点。
