下载文档原格式
数据结构习题(含答案)数据结构习题(含答案)1. 题目描述：请实现一个栈，要求支持以下操作：push(x)将元素x 入栈；pop()弹出栈顶元素；top()返回栈顶元素；empty()判断栈是否为空。
解答：我们可以使用数组来实现栈的功能。
首先定义一个数组stack来存储栈中的元素，同时定义一个整型变量top来表示栈顶的索引位置。
初始时，将top设置为-1，表示栈中没有元素。
1.1 push(x)操作：当要将元素x入栈时，我们先将top的值加1，然后将x赋值给stack[top]，即将x放入栈顶位置。
1.2 pop()操作：当调用pop()操作时，我们首先判断栈是否为空，即判断top的值是否为-1。
如果top等于-1，说明栈为空，无法进行pop()操作。
如果不为空，则将top的值减1，同时返回stack[top]，即弹出栈顶元素。
1.3 top()操作：top()操作与pop()操作类似，只需在操作完成后不弹出栈顶元素，而是直接返回stack[top]即可。
1.4 empty()操作：empty()操作用来判断栈是否为空，只需判断top的值是否为-1即可。
如果top等于-1，则返回true，表示栈为空；否则返回false，表示栈不为空。
综上所述，我们可以用数组实现一个栈，满足push、pop、top和empty等操作。
2. 题目描述：请实现一个队列，要求支持以下操作：push(x)将元素x入队；pop()将队首元素出队；peek()返回队首元素；empty()判断队列是否为空。
解答：我们可以使用两个栈来实现一个队列的功能。
首先定义两个栈stack1和stack2，其中stack1用来存储新加入队列的元素，stack2用来存储队列中已经处理过的元素。
定义两个整型变量top1和top2，分别表示stack1和stack2的栈顶索引位置。
初始时，top1和top2均设置为-1，表示两个栈均为空。
2.1 push(x)操作：当要将元素x入队时，我们直接将x加入到stack1中，同时将top1的值加1。
一、单选题（每题 2 分，共20分）1.对一个算法的评价，不包括如下（B ）方面的内容。
A．健壮性和可读性B．并行性C．正确性D．时空复杂度2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。
A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3.对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35.AOV网是一种（）。
A．有向图B．无向图C．无向无环图D．有向无环图6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。
A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。
A．值B．函数C．指针D．引用8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。
A．行号B．列号C．元素值D．非零元素个数9.快速排序在最坏情况下的时间复杂度为（）。
A．O(log2n) B．O(nlog2n)C．0(n) D．0(n2)10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A. O(n)B. O(1)C. O(log2n)D. O(n2)二、运算题（每题 6 分，共24分）1.数据结构是指数据及其相互之间的______________。
当结点之间存在M对N （M：N）的联系时，称这种结构为_____________________。
数据结构例题（及答案）项目一习题(答案)一选择题1. 算法的计算量的大小称为计算的(B )。
A( 效率 B. 复杂性 C. 现实性 D. 难度2.算法的时间复杂度取决于(C )A(问题的规模 B. 待处理数据的初态 C. A和B3(从逻辑上可以把数据结构分为(C )两大类。
A(动态结构、静态结构 B(顺序结构、链式结构C(线性结构、非线性结构 D(初等结构、构造型结构4(连续存储设计时，存储单元的地址(A )。
A(一定连续 B(一定不连续 C(不一定连续 D(部分连续，部分不连续5. 以下属于逻辑结构的是(C )。
A(顺序表 B. 哈希表 C.有序表 D. 单链表二、判断题1. 数据元素是数据的最小单位。
(×)2. 记录是数据处理的最小单位。
(×)3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系;(×)4(程序一定是算法。
(×)5. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。
(×)6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
(×)7. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。
(?)8. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. (×)三、填空1(数据的物理结构包括数据元素的表示和数据元素间关系的表示。
2. 对于给定的n个元素,可以构造出的逻辑结构有集合，线性结构，树形结构，图状结构或网状结构四种。
3(数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。
而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。
4(一个数据结构在计算机中表示(又称映像) 称为存储结构。
5(抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。
6(数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。
数据结构试题及答案(10套)数据结构试题及答案(10套)根据您的需求，我为您准备了10套数据结构试题及答案。
每套试题包含以下几个部分：选择题、填空题、编程题及答案解析。
下面是试题的具体内容：第一套试题：选择题：1. 在数据结构中，什么是栈？A. 先进先出（FIFO）的数据结构B. 后进先出（LIFO）的数据结构C. 随机访问的数据结构D. 无序排列的数据结构2. 以下哪种操作与队列的特性不相符？A. 入队操作B. 出队操作C. 查找操作D. 获取队首元素填空题：1. ______ 是一种动态集合，支持插入、删除和查找等操作。
2. 在二叉搜索树中，中序遍历的结果是________。
编程题：实现一个栈的数据结构，并包含以下操作：- push(x)：将元素 x 压入栈中- pop()：删除栈顶的元素并返回该元素- top()：获取栈顶元素的值- empty()：检查栈是否为空答案解析：选择题：B、C填空题：1. 集合 2. 升序序列编程题：略第二套试题：选择题：1. 以下哪个数据结构是一种广度优先搜索的应用？A. 栈B. 队列C. 堆D. 链表2. 在链表中，如果要删除一个节点，只给出该节点的指针，那么需要通过什么方式完成删除操作？A. 直接删除该节点B. 指向该节点的前一个节点的指针C. 指向该节点的后一个节点的指针D. 无法完成删除操作填空题：1. 树是一种________的数据结构。
2. 二叉树每个节点最多有______个子节点。
编程题：实现一个队列的数据结构，并包含以下操作：- enqueue(x)：将元素 x 入队- dequeue()：删除队首的元素并返回该元素- peek()：获取队首元素的值- is_empty()：检查队列是否为空答案解析：选择题：B、B填空题：1. 分层组织 2. 2编程题：略（以下部分省略）通过以上的题目，您可以对数据结构的知识点进行综合练习和复习。
每套试题包含了不同难度和类型的题目，能够帮助您全面了解和掌握数据结构的概念和操作。
一．《树》应用题1. 已知一棵树边的集合为{<i，m>，<i，n>，<e，i>，<b，e>，<b，d>，<a，b>，<g，j>，<g，k>，<c，g>，<c，f>，<h，l>，<c，h>，<a，c>}，请画出这棵树，并回答下列问题：（1）哪个是根结点？（2）哪些是叶子结点？（3）哪个是结点g的双亲？（4）哪些是结点g的祖先？（5）哪些是结点g的孩子？（6）哪些是结点e的孩子？（7）哪些是结点e的兄弟？哪些是结点f的兄弟？（8）结点b和n的层次号分别是什么？（9）树的深度是多少？（10）以结点c为根的子树深度是多少？2. 一棵度为2的树与一棵二叉树有何区别。
3. 试分别画出具有3个结点的树和二叉树的所有不同形态？4. 已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序列。
5. 一棵深度为H的满m叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有m棵非空子树，如果按层次自上至下，从左到右顺序从1开始对全部结点编号，回答下列问题：（1）各层的结点数目是多少？（2）编号为n的结点的父结点如果存在，编号是多少？（3）编号为n的结点的第i个孩子结点如果存在，编号是多少？（4）编号为n的结点有右兄弟的条件是什么？其右兄弟的编号是多少？6. 找出所有满足下列条件的二叉树：（1）它们在先序遍历和中序遍历时，得到的遍历序列相同；（2）它们在后序遍历和中序遍历时，得到的遍历序列相同；（3）它们在先序遍历和后序遍历时，得到的遍历序列相同；7. 假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请写出该二叉树的后序遍历序列。
8. 假设一棵二叉树的后序序列为DCEGBFHKJIA，中序序列为DCBGEAHFIJK，请写出该二叉树的后序遍历序列。
数据结构经典例题数据结构经典例题1.设计⼀个算法将L拆分成两个带头节点的单链表L1和L2。
void split(LinkList *&L,LinkList *&L1,LinkList *&L2){ LinkList *p=L->next,*q,*r1; //p指向第1个数据节点L1=L; //L1利⽤原来L的头节点r1=L1; //r1始终指向L1的尾节点L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点L2->next=NULL; //置L2的指针域为NULLwhile (p!=NULL){ r1->next=p; //采⽤尾插法将*p(data值为ai)插⼊L1中r1=p;p=p->next; //p移向下⼀个节点(data值为bi)q=p->next; //由于头插法修改p的next域,故⽤q保存*p的后继节点p->next=L2->next; //采⽤头插法将*p插⼊L2中L2->next=p;p=q; //p重新指向ai+1的节点}r1->next=NULL; //尾节点next置空}2.查找链表中倒数第k个位置上的节点（k为正整数）。
若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。
typedef struct LNode{int data;struct LNode *link;} *LinkList;int Searchk(LinkList list,int k){ LinkList p,q;int count=0;p=q=list->link;while (p!=NULL){ if (countcount++;elseq=q->link;p=p->link;}if (countelse{ printf("%d",q->data);return(1);}}3.假定采⽤带头节点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。
1、在二叉搜索树（BST）中，以下哪个遍历顺序会按从小到大的顺序访问所有节点？A. 前序遍历B. 中序遍历C. 后序遍历D. 层次遍历（答案：B）2、对于一个给定的无向图，以下哪种算法最适合找到从起点到终点的最短路径（假设所有边的权重都相等）？A. Dijkstra算法B. Bellman-Ford算法C. Floyd-Warshall算法D. 广度优先搜索（BFS）（答案：D）3、在哈希表中处理冲突的一种方法是链地址法（也称为拉链法），以下关于链地址法的说法错误的是：A. 每个哈希表槽位连接一个链表B. 当发生冲突时，新元素添加到对应槽位的链表末尾C. 链地址法不需要处理哈希函数的设计，因为冲突总是通过链表解决D. 查找、插入和删除操作的时间复杂度与链表的长度有关（答案：C）4、以下哪种数据结构最适合实现优先队列，且支持高效的插入和删除最小（或最大）元素操作？A. 数组B. 链表C. 二叉堆D. 平衡二叉搜索树（如AVL树）（答案：C）5、在快速排序算法中，选择哪个元素作为基准（pivot）对算法的效率有重要影响，以下哪种策略通常不是一个好的选择？A. 数组的第一个元素B. 数组的最后一个元素C. 数组中间的元素D. 随机选择一个元素（答案：视具体情况而定，但通常A、B在特定情况下可能不是最佳，如当数组已近排序时；然而，此题要求选一个“通常不是好选择”的，若必须选一个，可以认为A或B在未知数据分布时风险较高，答案可倾向A或B，这里选A作为示例）6、以下哪个不是图的遍历算法？A. 深度优先搜索（DFS）B. 广度优先搜索（BFS）C. A*搜索算法D. 拓扑排序（答案：D）7、在平衡二叉搜索树（如红黑树）中，以下哪个操作的时间复杂度不是O(log n)？A. 查找B. 插入C. 删除D. 计算树中所有节点的和（答案：D，因为计算所有节点和需要遍历整个树，时间复杂度为O(n)）8、以下哪种情况最适合使用动态规划算法来解决？A. 查找无序数组中的最大值B. 对一组数进行排序C. 计算斐波那契数列的第n项D. 在已排序的数组中查找特定元素（答案：C）。
基本概念典型例题一、单项选择题[例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。
其中，D是( ①)的有穷集合，R是D上( ②)的有限集合。
①A.算法B. 数据元素C. 数据操作D. 逻辑结构②A. 操作B. 映像C. 存储D．关系解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。
[例6-2]数据的常用存储结构中不包括( )。
A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储方法和散列存储方法。
由此可知，本题答案为：B。
[例6-3] 算法指的是( ①)，它必须具备( ②)这三个特性。
①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性C．确定性、有穷性、稳定性D．易读性、稳定性、安全性解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。
它必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。
由此可知，本题答案为：①㈠②B。
[例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。
for(i=0；i<n；i++)for(j=0；j<n；j++)x=x+l：A．O(2n) B．O(n) C．O(n2) D．O(1bn)解析：语句的执行频度即语句重复执行的次数，属于算法的时间复杂度类题目。
本题中对x的赋值语句为一个二重循环的循环体，外层循环循环n次，内层循环也循环n次，显然此语句的执行次数为n×n＝n2次。
由此可知，本题答案为：C。
二、填空题[例6-5]是数据的基本单位，通常由若干个组成，是数据的最小单位。
解析：本题是基本概念题，知识点为数据结构的相关概念。
本题答案为：数据元素；数据项；数据项。
三、应用题[例6-6] 简述数据结构的定义。
解析：数据结构是指数据元素之间的相互关系，即数据的组织形式。
数据结构练习题第一部分绪论一、单选题1. 一个数组元素a[i]与________的表示等价。
A、 *(a+i)B、 a+iC、 *a+iD、 &a+i2. 对于两个函数，若函数名相同，但只是____________不同则不是重载函数。
A、参数类型B、参数个数C、函数类型3. 若需要利用形参直接访问实参，则应把形参变量说明为________参数A、指针B、引用C、值4. 下面程序段的时间复杂度为____________。
for(int i=0; i<m; i++)for(int j=0; j<n; j++)a[i][j]=i*j;A、 O(m2)B、 O(n2)C、 O(m*n)D、 O(m+n)5. 执行下面程序段时，执行S语句的次数为____________。
for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)S;A、 n2B、 n2/2C、 n(n+1)D、 n(n+1)/26. 下面算法的时间复杂度为____________。
int f( unsigned int n ) {if ( n==0 || n==1 ) return 1; else return n*f(n-1);}A、 O(1)B、 O(n)C、 O(n2)D、 O(n!)二、填空题1. 数据的逻辑结构被分为__________、_________、__________和__________四种。
2. 数据的存储结构被分为__________、_________、__________和__________四种。
3. 在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着________、________和________的联系。
4. 一种抽象数据类型包括__________和__________两个部分。
5. 当一个形参类型的长度较大时，应最好说明为_________，以节省参数值的传输时间和存储参数的空间。
基本概念典型例题一、单项选择题[例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。
其中，D是( ①)的有穷集合，R是D上( ②)的有限集合。
①A.算法B. 数据元素C. 数据操作D. 逻辑结构②A. 操作B. 映像C. 存储D．关系解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。
[例6-2]数据的常用存储结构中不包括( )。
A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储方法和散列存储方法。
由此可知，本题答案为：B。
[例6-3] 算法指的是( ①)，它必须具备( ②)这三个特性。
①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性C．确定性、有穷性、稳定性D．易读性、稳定性、安全性解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。
它必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。
由此可知，本题答案为：①㈠②B。
[例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。
for(i=0；i<n；i++)for(j=0；j<n；j++)x=x+l：A．O(2n) B．O(n) C．O(n2) D．O(1bn)解析：语句的执行频度即语句重复执行的次数，属于算法的时间复杂度类题目。
本题中对x的赋值语句为一个二重循环的循环体，外层循环循环n次，内层循环也循环n次，显然此语句的执行次数为n×n＝n2次。
由此可知，本题答案为：C。
二、填空题[例6-5]是数据的基本单位，通常由若干个组成，是数据的最小单位。
解析：本题是基本概念题，知识点为数据结构的相关概念。
本题答案为：数据元素；数据项；数据项。
三、应用题[例6-6] 简述数据结构的定义。
解析：数据结构是指数据元素之间的相互关系，即数据的组织形式。
数据结构通常包括三个方面的内容，分别是数据的逻辑结构、数据的存储结构(物理结构)和在这些数据上定义的运算。
用集合的观点可以把数据结构表示为一个二元组DS＝(D，R)。
其中，D是数据元素的有穷集合，R是D上关系的有限集合。
[例6-7]分析以下程序段的时间复杂度。
for(i=0；i<n；i++) //语句①{x=x+1；//语句②for(j=0；j<2*n；j++) //语句③y++；//语句④}解析：语句的执行频度指的是语句重复执行的次数。
一个算法中所有语句的执行频度之和构成了该算法的运行时间。
在本例算法中，语句①的执行频度是n+l，语句②的执行频度是n，语句③的执行频度是n(2n+2)＝2n2-2n，语句④的执行频度是n(2n+1)＝2n2+n。
该程序段的时间复杂度T(n)＝(n+1)+n+(2n2+2n)+(2n2+n)＝4n2+5n+1＝O(n2)。
实际上，可以用算法中基本操作重复执行的频度作为度量标准，而被视为基本操作的一般是最深层循环内的语句。
在上例中，语句④为基本操作，其执行频度为2n2+n，因此，该算法的时间复杂度T(n)＝2n2+n＝O(n2)。
[例6-8] 分析以下程序段的时间复杂度。
i=1；while(i<=m)i=i*2；解析：上述算法的基本操作语句是i＝i*2，设其执行频度为T(n)，则有：2T(n)≤n，即T(n)≤lbn＝O(lbn)。
因此，该程序段的时间复杂度为O(lbn)。
线性结构典型例题一、单项选择题[例7-1]在数据结构中，与所使用计算机无关的数据叫( ①)结构；链表是一种采用( ②)存储结构存储的线性表；链表适用于( ③)查找；在链表中进行( ④)操作的效率比在线性表中进行该操作的效率高。
①A．存储B．物理C．逻辑D．物理和逻辑②A．顺序B．网状C．星式D．链式③A．顺序B．二分法C．顺序及二分法D．随机④A．二分法查找B．快速查找C．顺序查找D．插入解析：本题考查的是基本概念。
本题答案为：①C；②D；③A；④D。
[例7-2] 链表不具备的特点是( )。
A．插入和删除不需要移动元素B．可随机访问任一结点C．不必预分配空间D．所需空间与其长度成正比解析：线性表可随机访问任一结点，而链表必须从第一个数据结点出发逐一查找每个结点。
本题答案为：B。
[例7-3] 不带头结点的单链表head为空的判定条件是( )。
A．head＝＝NULL B．head_>next＝＝NULLC．head_>next＝＝head D．head!＝NULL解析：在不带头结点的单链表head中，head指向第一个数据结点。
空表即该表没有结点，head＝＝NULL表示该单链表为空。
本题答案为：A。
[例7-4] 带头结点的单链表head为空的判定条件是( )。
A．head＝＝NULL B．head—>next＝＝NULLC．head—> next＝＝head D．head!＝NULL解析：在带头结点的单链表head中，head指向头结点。
空表即该表只有头结点，head—>next＝＝NULL 表示该单链表为空。
本题答案为：B。
[例7-5] 带头结点的循环单链表head中，head为空的判定条件是( )。
A．head＝＝NULL B．head—>next＝＝NULLC．head—> next＝＝head D．head!＝NULL解析：在带头结点的循环单链表head中，head指向头结点。
空表即该表只有头结点，head—>next＝＝head表示该单链表为空。
本题答案为：C。
[例7-6] 线性表采用链式存储时其存储地址( )。
A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续不连续都可以解析：链式存储采用动态存储，地址一般不连续。
本题答案为：D。
[例7-7] 在双向链表的* p结点前插入新结点*s的操作为( )。
A．p—>prior=s；s—>next=p；p—>prior—>next=s；s—>prior=p—>prior；B．p—>prior=s；p—>prior—>next=s；s—>next=p；s—>prior=p—>prior；C．s—>next=p；s—>prior=p—>prior；p—prior=s；p—>prior—>next=s；D．s—>next=p；s—>prior=p—>prior；p—prior—>next=s；p—>prior=s；解析：在双向链表的* p结点前插入新结点* s的操作如图7.12所示，图中虚线为所作的操作，序号为操作顺序。
本题答案为：D。
图7.12 双向链表插入结点的过程示意图(例7-8)若某表最常用的操作是在最后一个结点后插入一个结点和删除第一个结点，则采用( )存储方式最节省运算时间。
A．单链表B．双向链表C．给出表头指针的循环单链表D．给出尾指针的循环单链表解析：在链表中插入或删除一个结点，需修改相邻结点的指针域。
上述四个选项中，只有选项D才能从尾指针经过最少的结点来进行题目要求的插入或删除操作。
本题答案为：D。
[例7-9] 若线性表中有2n个元素，算法( )在单链表上实现要比在顺序表上实现效率更高。
A．删除所有值为x的元素B．在最后一个元素的后面插入一个新元素C．顺序输出前k个元素D．交换其中某两个元素的值解析：对于选项A，在单链表上和顺序表上实现的时间复杂度都为O(n)，但后者要移动大量的元素，因此在单链表上实现效率更高。
本题答案为：A。
(例7-10) 在长度为n的( )上，删除第一个元素，其算法复杂度为O(n)。
A．只有表头指针的不带头结点的循环单链表B．只有尾指针的不带表头结点的循环单链表C．只有表尾指针的带头结点的循环单链表D．只有尾指针的带表头结点的循环单链表解析：本题答案为：A。
具体算法如下：linklist * delfirst(linklist * h){Linklist * p＝h；while(p—> next!＝h) //找到表尾结点p＝p—>next；p—>next=h—> next；free(h)；returnp一>next；//返回头指针}二、填空题[例7-11] 在单链表中结点* p后插入结点* s的指令序列为；。
解析：在单链表中结点* p后插入结点* s，即将* p 的后继结点变为* s 的后继结点，* s 则成为* p的后继结点。
操作指令序列为：s—>next＝p—>next；p—>next＝s。
[例7-12]在线性表的链式存储结构中，根据每个结点所含指针的个数，链表可分为和；而根据指针的链接方式，链表又可分为和。
解析：本题答案为：单链表；多重链表；循环链表；普通链表(非循环链表)。
[例7-13] 在单链表中，要删除某一个指定的结点，必须找到该结点的结点。
解析：由单链表的特点可知，删除某一个结点的操作是将其前驱结点的next指针域指向该结点的后继结点。
本题答案为：前驱。
[例7-14] 在一个长度为n 的顺序表中删除第i(0≤i ≤n 一1)个元素，需向前移动 个元素。
解析：需将第i 个元素后的元素依次前移一个位置，总共移动(n-1)-(i+1)+1个元素。
本题答案为：n-i-1。
[例7-15] 在一个具有n 个结点的单链表，在 * p 结点后插入一个新结点的时间复杂度是 ；在给定值为x 的结点后插入一个新结点的时间复杂度是 。
解析：在 * p 结点后插入一个新结点 * s 的操作是：s —> next ＝p —> next ；p —>next ＝s ；其时间复杂度为0(1)。
在给定值为x 的结点后插入一个结点，首先要找到该结点，然后再进行插入。
找到该结点的时间复杂度为O(n)，插入的时间复杂度为O(1)。
本题答案为：O(1)；O(n)。
三、应用题(例7-16) 设A 是一个线性表(a 0，a 1，…，a i ，…，a n-1)，采用顺序存储结构，则在等概率情况下平均每插入一个元素需要移动的元素个数是多少?若元素插在a i 和a i+1之间(0≤i ≤n-1)的概率为1(1)/2n n n -+，则平均每插入一个元素所需要移动的元素个数是多少?解析：在等概率情况下，平均每插入一个元素需要移动的元素个数为：(012)12n n n ++++=+ 若元素插在a i 和a i+l 之间(0≤i ≤n-1)的概率为(1)/2n i n n -+，则平均每插入一个元素所需 要移动的元素个数为：10n i -=∑2222()221(1)1(1)/2(1)3n i n n n n n n n -+⎡⎤=+-++=⎣⎦++ (例7-17) 简述线性表采用顺序存储方式和链式存储方式的优缺点。
