下载文档原格式
第3章线性表算法题：1、线性表的单链表存储结构如下：Typedef struct LNode{int data；struct LNode *next；}LNode，*linklist；试写算法，计算单循环链表的长度。
函数头定义为：int listlength（linklist ta）{ ...}//listlength2.线性表的单链表存储结构如下：typedef struct LNode{ int data；struct LNode *next；}LNode，*linklist；试写算法，将值为x的结点插到带头结点的单链表的链尾。
函数头定义为：void insert(LNode *h, int x){ ...}// insert第4章栈和队列1、P78 题1（1）出栈序列：1,3，2，4（2）出栈序列1432可以得到，即1入栈后出栈，2，3，4依次入栈后出栈4，3，2；出栈序列1423不可能得到，因为先是1入栈后出栈，接着是4出栈，应是按234入栈后开始出栈，这时2不能先于3出栈。
2、P78 题4（1）将栈S中的数据倒置（2）将栈S1数据复制到栈S2中（3）将栈S中值为m的数据删除（4）将队列Q中数据倒置（5）将队列Q1中数据复制到Q2中3、已知一个后缀算术表达式为3 7 25 5 / * - 8 2 * + #画出在进行后缀表达式求值的过程中数值栈的变化。
答案：数值栈的变化：第6章树试问：⑴哪个结点是根结点？⑵哪个结点是D的双亲结点？⑶C的左右孩子分别是什么？⑷画出这棵二叉树。
答案:根结点为: AD的双亲结点: CC的左右孩子: 空、D2. 假设一棵二叉树的先序序列为ABDEGHJCFI 和中序序列为DBGEHJACIF 。
请画出该树。
答案：3.已知二叉树如图所示，画出二叉树中序的线索二叉树的逻辑结构图。
C(a)CBAC(d)(e)答案：GDJHKBEACFMI4. 设有一组权ＷＧ＝1,4,9,16,25,36,49,64,81,100，试画出其哈夫曼树，并计算加权的路径长度。
第三章习题1.按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。
（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。
2.设队列中有A、B、C、D、E这5个元素，其中队首元素为A。
如果对这个队列重复执行下列4步操作：（1）输出队首元素；（2）把队首元素值插入到队尾；（3）删除队首元素；（4）再次删除队首元素。
直到队列成为空队列为止，得到输出序列：（1）A、C、E、C、C （2） A、C、E（3） A、C、E、C、C、C （4） A、C、E、C3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4.按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ5.试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1& 序列2’模式的字符序列。
其中序列1和序列2中都不含字符’&’，且序列2是序列1的逆序列。
例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。
6.假设表达式由单字母变量和双目四则运算算符构成。
试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。
7.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
8.要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。
9.简述以下算法的功能（其中栈和队列的元素类型均为int）：（1）void proc_1(Stack S){ int i, n, A[255];n=0;while(!EmptyStack(S)){n++; Pop(&S, &A[n]);}for(i=1; i<=n; i++)Push(&S, A[i]);}（2）void proc_2(Stack S, int e) { Stack T; int d;InitStack(&T);while(!EmptyStack(S)){ Pop(&S, &d);if (d!=e) Push( &T, d);}while(!EmptyStack(T)){ Pop(&T, &d);Push( &S, d);}}（3）void proc_3(Queue *Q){ Stack S; int d;InitStack(&S);while(!EmptyQueue(*Q)){DeleteQueue(Q, &d);Push( &S, d);}while(!EmptyStack(S)){ Pop(&S, &d);EnterQueue(Q，d)}}实习题1．回文判断。
第三章习题1.按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。
（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。
2.设队列中有A、B、C、D、E这5个元素，其中队首元素为A。
如果对这个队列重复执行下列4步操作：（1）输出队首元素；（2）把队首元素值插入到队尾；（3）删除队首元素；（4）再次删除队首元素。
直到队列成为空队列为止，得到输出序列：（1）A、C、E、C、C （2） A、C、E（3） A、C、E、C、C、C （4） A、C、E、C3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4.按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ5.试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1& 序列2’模式的字符序列。
其中序列1和序列2中都不含字符’&’，且序列2是序列1的逆序列。
例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。
6.假设表达式由单字母变量和双目四则运算算符构成。
试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。
7.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
8.要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。
9.简述以下算法的功能（其中栈和队列的元素类型均为int）：（1）void proc_1(Stack S){ int i, n, A[255];n=0;while(!EmptyStack(S)){n++; Pop(&S, &A[n]);}for(i=1; i<=n; i++)Push(&S, A[i]);}（2）void proc_2(Stack S, int e){ Stack T; int d;InitStack(&T);while(!EmptyStack(S)){ Pop(&S, &d);if (d!=e) Push( &T, d);}while(!EmptyStack(T)){ Pop(&T, &d);Push( &S, d);}}（3）void proc_3(Queue *Q){ Stack S; int d;InitStack(&S);while(!EmptyQueue(*Q)){DeleteQueue(Q, &d);Push( &S, d);}while(!EmptyStack(S)){ Pop(&S, &d);EnterQueue(Q，d)}}实习题1．回文判断。
大数据（单选）第三章1. 1.设某顺序表中第一个元素的地址是se(下标从1开始),每个结点占m个单元,则第i个结点的地址为( )。
[单选题]A、 se+(i-1)×m(正确答案)B、 se+(i+1)×mC、 se+i×mD、 se-i×m2. 2.（）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。
但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。
[单选题]A、回溯法(正确答案)B、递归法C、分而治之法D、演绎法3. 3.在常用的问题解决方法中，一一列举出问题所有可能的解，并逐一检验每个可能解，采纳问题的真正解，抛弃非真正解的方法，我们称之为( )。
[单选题]A、算法B、解析算法C、归纳法D、枚举法(正确答案)4. 4.算法是对解题过程的精确描述，目前表示算法的工具主要有自然语言、流程图、伪代码和（）等。
[单选题]A、程序设计语言(正确答案)B、汇编语言C、机器语言D、人工智能语言5. 5.以下叙述中，错误的是（）。
[单选题]A、算法就是求解问题的方法和步骤B、算法可以用中文来描述C、算法必须在有限步内完成D、一个算法可以没有输出(正确答案)6. 6.造成下面三段论推理错误的原因是（）。
所有的鸟都会飞 ,鸵鸟是鸟 ,所以鸵鸟会飞 [单选题]A、大前提(正确答案)B、小前提C、结论D、都不是7. 7.有A、，B两个充满水的杯子和一个空杯C，假设A、B、C三个杯的容量是相等的，现要求将A，B两个杯中的水互换，下面算法中正确的是（）。
（B←A 表示将A中的水到入B中，其它类似） [单选题]A、B←A，A←B，C←AB、B←A，C←B，A←CC、C←A，A←B，B←C(正确答案)D、B←A，C←B，A←C8. 8.问题解决的过程大致可以划分为若干个阶段，其中首先要做的是（）。
[单选题]A、总结评价B、分析问题C、提出假设D、发现问题(正确答案)9. 9.问题虽然有简单或复杂、具体或抽象之分，但每个问题都包含三个基本成分（）。
第3章栈和队列一选择题1. 对于栈操作数据的原则是（）。
【青岛大学2001 五、2（2分）】A. 先进先出B. 后进先出C. 后进后出D. 不分顺序2. 在作进栈运算时,应先判别栈是否( ①),在作退栈运算时应先判别栈是否( ②)。
当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③)。
为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的( ④)分别设在这片内存空间的两端,这样,当( ⑤)时，才产生上溢。
①, ②: A. 空 B. 满 C. 上溢 D. 下溢③: A. n-1 B. n C. n+1 D. n/2④: A. 长度 B. 深度 C. 栈顶 D. 栈底⑤: A. 两个栈的栈顶同时到达栈空间的中心点.B. 其中一个栈的栈顶到达栈空间的中心点.C. 两个栈的栈顶在栈空间的某一位置相遇.D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.【上海海运学院1997 二、1（5分）】【上海海运学院1999 二、1（5分）】3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。
A. 不确定B. n-i+1C. iD. n-i【中山大学1999 一、9(1分)】4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。
A. i-j-1B. i-jC. j-i+1D. 不确定的【武汉大学2000 二、3】5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( )。
A. iB. n-iC. n-i+1D. 不确定【南京理工大学2001 一、1（1.5分）】6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 34 15 6【北方交通大学2001 一、3（2分）】7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。
下面哪种选项描述了链表的特点？A) 可以随机访问元素B) 拥有固定大小的内存空间C) 元素之间通过指针连接D) 可以自动调整大小答案: C在链表中，头节点的作用是什么？A) 存储链表的长度B) 存储链表的最后一个节点C) 存储链表的第一个节点D) 存储链表的中间节点答案: C下面哪种选项描述了双向链表的特点？A) 每个节点只有一个指针指向下一个节点B) 每个节点只有一个指针指向上一个节点C) 每个节点同时拥有指向前一个节点和后一个节点的指针D) 只能从链表的一端进行操作答案: C在链表中，删除一个节点的操作涉及修改哪些指针？A) 只需要修改被删除节点的前一个节点的指针B) 只需要修改被删除节点的后一个节点的指针C) 需要修改被删除节点的前一个节点和后一个节点的指针D) 不需要修改任何指针答案: C在链表的尾部添加一个新节点的操作复杂度是多少？A) O(1)B) O(n)C) O(log n)D) O(n^2)答案: A如何遍历链表的所有节点？A) 使用for循环B) 使用while循环C) 使用递归函数D) 使用if语句答案: B在链表中，如何找到特定值的节点？A) 使用线性搜索B) 使用二分搜索C) 使用递归搜索D) 使用栈搜索答案: A链表和数组相比，哪个更适合频繁插入和删除操作？A) 链表B) 数组C) 二叉树D) 堆栈答案: A在链表中，如何在指定位置插入一个新节点？A) 修改前一个节点的指针B) 修改后一个节点的指针C) 修改当前节点的指针D) 不需要修改任何指针答案: A链表的头指针指向什么？A) 链表的第一个节点B) 链表的最后一个节点C) 链表的中间节点D) 链表的空节点答案: A链表中节点的个数称为什么？A) 链表的长度B) 链表的高度C) 链表的宽度D) 链表的容量答案: A在链表中，如何删除指定值的节点？A) 修改前一个节点的指针B) 修改后一个节点的指针C) 修改当前节点的指针D) 不需要修改任何指针答案: A单链表的最后一个节点指向什么？A) 链表的第一个节点B) 链表的最后一个节点C) NULLD) 链表的中间节点答案: C双向链表相比于单向链表的优势是什么？A) 占用更少的内存空间B) 遍历速度更快C) 可以从任意方向遍历D) 插入和删除操作更快答案: C在链表中，如何找到倒数第n个节点？A) 遍历整个链表B) 使用递归函数C) 使用栈数据结构D) 使用双指针技巧答案: D链表的删除操作和数组的删除操作的时间复杂度分别是什么？A) 链表的删除操作为O(1)，数组的删除操作为O(n)B) 链表的删除操作为O(n)，数组的删除操作为O(1)C) 链表的删除操作为O(n)，数组的删除操作为O(n)D) 链表的删除操作为O(1)，数组的删除操作为O(1)答案: A在链表中，如何判断链表是否为空？A) 检查头指针是否为NULLB) 检查尾指针是否为NULLC) 检查链表的长度是否为0D) 检查链表的第一个节点是否为NULL答案: A链表的逆序操作是指什么？A) 删除链表中的节点B) 反转链表中节点的顺序C) 插入节点到链表的尾部D) 在链表中查找指定值的节点答案: B在链表中，如何查找指定值的节点？A) 使用线性搜索B) 使用二分搜索C) 使用递归搜索D) 使用栈搜索答案: A在双向链表中，如何删除指定值的节点？A) 修改前一个节点的指针B) 修改后一个节点的指针C) 修改当前节点的指针D) 不需要修改任何指针答案: A链表的插入操作和数组的插入操作的时间复杂度分别是什么？A) 链表的插入操作为O(1)，数组的插入操作为O(n)B) 链表的插入操作为O(n)，数组的插入操作为O(1)C) 链表的插入操作为O(n)，数组的插入操作为O(n)D) 链表的插入操作为O(1)，数组的插入操作为O(1)答案: A如何删除单向链表中的重复节点？A) 使用递归算法B) 使用双指针技巧C) 使用栈数据结构D) 不需要额外操作，链表会自动去重答案: B链表的优势之一是什么？A) 随机访问速度快B) 占用内存空间少C) 插入和删除操作高效D) 支持高级操作如排序和搜索答案: C在链表中，如何找到中间节点？A) 遍历整个链表B) 使用递归函数C) 使用栈数据结构D) 使用快慢指针技巧答案: D在链表中，如何在尾部添加一个新节点？A) 修改前一个节点的指针B) 修改后一个节点的指针C) 修改当前节点的指针D) 创建一个新节点并更新尾指针答案: D链表的查找操作的时间复杂度是多少？A) O(1)B) O(log n)C) O(n)D) O(n^2)答案: C在双向链表中，如何找到倒数第n个节点？A) 从头节点开始遍历B) 从尾节点开始遍历C) 使用递归函数D) 使用双指针技巧答案: B链表的删除操作的时间复杂度是多少？A) O(1)B) O(log n)C) O(n)D) O(n^2)答案: A链表和数组相比，哪个更适合频繁插入和删除操作？A) 链表B) 数组C) 哈希表D) 栈答案: A如何判断链表是否有环？A) 使用线性搜索B) 使用递归算法C) 使用快慢指针技巧D) 使用栈数据结构答案: C在链表中，如何反转链表的顺序？A) 使用递归算法B) 使用栈数据结构C) 使用双指针技巧D) 使用循环迭代答案: D在链表中，如何删除所有节点？A) 依次删除每个节点B) 修改头指针为NULLC) 修改尾指针为NULLD) 不需要额外操作，链表会自动清空答案: A链表的头节点是什么？A) 链表的第一个节点B) 链表的最后一个节点C) 链表的中间节点D) 链表的空节点答案: A在链表中，如何插入一个新节点到指定位置之前？A) 修改前一个节点的指针B) 修改后一个节点的指针C) 修改当前节点的指针D) 不需要修改任何指针答案: A在链表中，如何删除指定位置的节点？A) 修改前一个节点的指针B) 修改后一个节点的指针C) 修改当前节点的指针D) 不需要修改任何指针答案: A单向链表和双向链表的区别是什么？A) 单向链表只有一个指针指向下一个节点，双向链表有两个指针分别指向前一个节点和后一个节点B) 单向链表只能从头到尾遍历，双向链表可以从头到尾或者从尾到头遍历C) 单向链表只能在尾部添加节点，双向链表可以在头部和尾部都添加节点D) 单向链表只能包含整型数据，双向链表可以包含任意类型的数据答案: A链表的删除操作和数组的删除操作的时间复杂度分别是什么？A) 链表的删除操作为O(1)，数组的删除操作为O(n)B) 链表的删除操作为O(n)，数组的删除操作为O(1)C) 链表的删除操作为O(n)，数组的删除操作为O(n)D) 链表的删除操作为O(1)，数组的删除操作为O(1)答案: A如何判断两个链表是否相交？A) 比较链表的长度是否相等B) 比较链表的头节点是否相等C) 比较链表的尾节点是否相等D) 比较链表中的所有节点是否相等答案: B链表和数组的主要区别是什么？A) 链表是一种线性数据结构，数组是一种非线性数据结构B) 链表的长度可变，数组的长度固定C) 链表支持随机访问，数组只能顺序访问D) 链表的插入和删除操作效率高，数组的访问效率高答案: B在链表中，如何找到倒数第k个节点？A) 从头节点开始遍历，直到倒数第k个节点B) 从尾节点开始遍历，直到倒数第k个节点C) 使用递归函数查找倒数第k个节点D) 使用双指针技巧，一个指针先移动k步，然后两个指针同时移动直到第一个指针到达链表末尾答案: D在链表中，如何判断是否存在环？A) 使用线性搜索，检查是否有重复的节点B) 使用递归算法，判断节点是否已经访问过C) 使用栈数据结构，检查节点是否已经入栈D) 使用快慢指针技巧，如果两个指针相遇，则存在环答案: D如何将两个有序链表合并成一个有序链表？A) 创建一个新链表，依次比较两个链表的节点并插入新链表中B) 将第一个链表的尾节点指向第二个链表的头节点C) 将第二个链表的尾节点指向第一个链表的头节点D) 使用递归算法，依次比较两个链表的节点并合并答案: A在链表中，如何删除重复的节点？A) 使用递归算法，遍历链表并删除重复的节点B) 使用双指针技巧，依次比较相邻节点并删除重复的节点C) 使用栈数据结构，检查节点是否已经入栈并删除重复的节点D) 不需要额外操作，链表会自动去重答案: B链表的优点是什么？A) 占用内存空间少B) 插入和删除操作高效C) 支持高级操作如排序和搜索D) 可以随机访问任意位置的元素答案: B。
选择题第3章线性表的链式存储（1）两个有序线性表分别具有n个元素与m个元素且n≤m，现将其归并成一个有序表，其最少的比较次数是（ A ）。
A．n B．m C．n− 1D．m + n（2）非空的循环单链表 head 的尾结点（由 p 所指向）满足（ C ）。
A．p->next==NULL B．p==NULL C．p->next==head D．p==head（3）在带头结点的单链表中查找x应选择的程序体是（ C ）。
A．node *p=head->next; while (p && p->info!=x) p=p->next;if (p->info==x) return p else return NULL;B．node *p=head; while (p&& p->info!=x) p=p->next; return p;C．node *p=head->next; while (p&&p->info!=x) p=p->next; return p;D．node *p=head; while (p->info!=x) p=p->next ; return p;（4）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。
A．必须是连续的C．一定是不连续的B．部分地址必须是连续的D．连续不连续都可以（5）在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（ B ）。
A．O(1) B．O(n)C．O(n2)D．O(n log2n)（6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（D ）。
A．仅修改队头指针C．队头、队尾指针都要修改B．仅修改队尾指针D．队头,队尾指针都可能要修改（7）若从键盘输入n个元素，则建立一个有序单向链表的时间复杂度为（ B ）。
单链表、双链表、循环链表和静态链表的习题一、单项选择题1.关于线性表的顺序存储结构和链式存储结构的描述中，正确的是（）。
Ⅰ.线性表的顺序存储结构优于其链式存储结构Ⅱ.链式存储结构比顺序存储结构能更方便地表示各种逻辑结构Ⅲ.如频繁使用插入和删除结点操作，顺序存储结构更优于链式存储结构Ⅳ.顺序存储结构和链式存储结构都可以进行顺序存取A. Ⅰ、Ⅱ、ⅢB. Ⅱ、ⅣC. Ⅱ、ⅢD. Ⅲ、Ⅳ2.对于一个线性表既要求能够进行较快速地插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（）。
A.顺序存储方式B.链式存储方式C.散列存储方式D.以上均可以3.对于顺序存储的线性表，其算法的时间复杂度为O(1)的运算应该是（）。
A.将n个元素从小到大排序B.删除第i个元素（1<i<n）C.改变第i个元素的值（1<=i<=n）D.在第i个元素后插入一个新元素（1<=i<=n）4.下列关于线性表说法正确的是（）。
Ⅰ.顺序存储方式只能用于存储线性结构Ⅱ.取线性表的第i个元素的时间同i的大小有关Ⅲ.静态链表需要分配较大的连续空间，插入和删除不需要移动元素Ⅳ.在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度为O(n) Ⅴ.若用单链表来表示队列，则应该选用带尾指针的循环链表A. Ⅰ、ⅡB.Ⅰ、Ⅲ、Ⅳ、ⅤC. Ⅳ、ⅤD. Ⅲ、Ⅳ、Ⅴ5.设线性表中有2n个元素，（）在单链表上实现要比在顺序表上实现效率更高。
A.删除所有值为x的元素B.在最后一个元素的后面插入一个新元素C.顺序输出前k个元素D.交换第i个元素和第2n-i-l个元素的值(i=0,…, n-1)6.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入结点s，则执行（）。
A .s->next=p->next;p->next=s; B.p->next=s->next; s->next=p;C. q->next=s;s->next=p;D. p->next=s;s->next=q;7.给定有n个元素的一维数组，建立一个有序单链表的最低时间复杂度是（）。
单向链表练习题单向链表练习题链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。
在计算机科学中，链表常用于实现其他数据结构，如栈和队列。
掌握链表的基本操作对于编程人员来说是至关重要的。
在本篇文章中，我们将通过一些练习题来加深对单向链表的理解。
1. 反转链表题目：给定一个单向链表，将其反转。
示例：输入：1 -> 2 -> 3 -> 4 -> 5输出：5 -> 4 -> 3 -> 2 -> 1解析：反转链表是一个常见的链表操作。
我们可以使用三个指针prev、curr和next来完成反转。
初始时，prev指向null，curr指向头节点。
我们需要将curr的next指针指向prev，然后移动prev、curr和next指针，直到遍历完整个链表。
2. 链表中倒数第k个节点题目：给定一个单向链表，找到链表中倒数第k个节点。
示例：输入：1 -> 2 -> 3 -> 4 -> 5，k = 2输出：4解析：要找到链表中倒数第k个节点，我们可以使用双指针法。
首先，我们让一个指针p1指向链表的头节点，然后让另一个指针p2指向链表的第k个节点。
接下来，同时移动p1和p2指针，直到p2指向链表的末尾。
此时，p1指向的节点就是倒数第k个节点。
3. 合并两个有序链表题目：给定两个有序链表，将它们合并为一个有序链表。
示例：输入：1 -> 2 -> 4, 1 -> 3 -> 4输出：1 -> 1 -> 2 -> 3 -> 4 -> 4解析：合并两个有序链表是一个常见的链表操作。
我们可以使用递归或迭代的方式来实现。
递归的思路是比较两个链表的头节点，将较小的节点作为合并后的链表的头节点，并递归地合并剩余的节点。
迭代的思路是使用一个额外的指针来指向合并后的链表的末尾，然后比较两个链表的头节点，将较小的节点接在末尾，并更新指针和链表头。
第三章单链表题⽬和答案第2章⾃测卷答案⼀、填空1.顺序表中逻辑上相邻的元素的物理位置相互相邻。
单链表中逻辑上相邻的元素的物理位置不相邻。
2.在单链表中，除了⾸元结点外，任⼀结点的存储位置由其直接前驱结点值域指⽰。
3．在n个结点的单链表中要删除已知结点*p，需找到它的地址。
⼆、判断正误（在正确的说法后⾯打勾，反之打叉）1. 链表的每个结点中都恰好包含⼀个指针。
X2. 链表的物理存储结构具有同链表⼀样的顺序。
X3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会⾃动地将后续的各个单元向前移动。
X4. 线性表的每个结点只能是⼀个简单类型，⽽链表的每个结点可以是⼀个复杂类型。
Y5. 顺序表结构适宜于进⾏顺序存取，⽽链表适宜于进⾏随机存取。
Y6. 顺序存储⽅式的优点是存储密度⼤，且插⼊、删除运算效率⾼。
X7. 线性表在物理存储空间中也⼀定是连续的。
X8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
X9. 顺序存储⽅式只能⽤于存储线性结构。
X10. 线性表的逻辑顺序与存储顺序总是⼀致的。
X三、单项选择题（A）1. 链接存储的存储结构所占存储空间：（A）分两部分，⼀部分存放结点值，另⼀部分存放表⽰结点间关系的指针（B）只有⼀部分，存放结点值（C）只有⼀部分，存储表⽰结点间关系的指针（D）分两部分，⼀部分存放结点值，另⼀部分存放结点所占单元数（B）2. 链表是⼀种采⽤存储结构存储的线性表；（A）顺序（B）链式（C）星式（D）⽹状（D）3. 线性表若采⽤链式存储结构时，要求内存中可⽤存储单元的地址:（A）必须是连续的（B）部分地址必须是连续的（C）⼀定是不连续的（D）连续或不连续都可以（B）4．线性表Ｌ在情况下适⽤于使⽤链式结构实现。
（Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进⾏删除插⼊（Ｃ）Ｌ中含有⼤量的结点（Ｄ）Ｌ中结点结构复杂（C）5．单链表的存储密度（Ａ）⼤于1；（Ｂ）等于1；（Ｃ）⼩于1；（Ｄ）不能确定（A）6、在单链表的⼀个结点中有个指针。
第三章链表基本题3.2.1单项选择题1.不带头结点的单链表head为空的判定条件是A.head=NULLB.head->next=NULLC.head->next=headD.head!=NULL2.带头接待点的单链表head为空的判定条件是A.head=NULLB.head->next=NULLC.head->next=headD.head!=NULL3.非空的循环单链表head的尾结点(由p所指向)满足A.p->head=NULLB.p=NULLC.p->next=headD.p=head4.在循环双链表p的所指结点之后插入s所指结点的操作是A.p->right=s; s->left=p; p->right->lefe=s; s->right=p->right;B.p->right=s; p->right->left=s; s->lefe=p; s->right=p->right;C.s->lefe=p; s->right=p->right; p->right=s; p->right->left=s;D.s->left=p; s->right=p->right; p->right->left=s; p->right=s;5.在一个单链表中，已知q所指结点是所指结点p的前驱结点，若在q和p之间插入结点S，则执行A.s->next=p->next; p->next=s;B.p->next=s->next; s->next=p;C.q->next=s; s->next=p;D.p->next=s; s->next=q;6.在一个单链表中，若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;7.在一个单链表中，若删除p所指结点的后续结点，则执行A.p->next=p->next->next;B.p=p->next; p->next=p->next->next;C.p->next=p->nextD.p=p->next->next8.假设双链表结点的类型如下：typedef struct linknode{int data; /*数据域*/Struct linknode *llink; /*llink是指向前驱结点的指针域*/Struct linknode *rlink; /*rlink是指向后续结点的指针域*/}bnode下面给出的算法段是要把一个所指新结点作为非空双向链表中的所指结点的前驱结点插入到该双链表中，能正确完成要求的算法段是A.q->rling=p; q->llink=p->llink; p->llink=q;p->llink->rlink=q;B.p->llink=q; q->rlink=p; p->llink->rlink=q; q->llink=p->llink;C.q->llink=p->llink; q->rlink=p; p->llink->rlink=q; p->llink=q;D.以上都不对9.从一个具有n个结点的有序单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个结点。
第一章绪论一、选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。
1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。
1 A.算法 B.数据元素 C.数据操作 D.逻辑结构2 A.操作 B.映像 C.存储 D.关系3.在数据结构中，从逻辑上可以把数据结构分成。
A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。
A.随机存取 B.顺序存取 C.索引存取 D.散列存取5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。
1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系C.可读性和文档性D.数据复杂性和程序复杂性k6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。
1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。
A.正确 B.不正确8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。
A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是。
A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。
单链表算法题以下是单链表算法题：1. 判断单链表是否有环题目描述：给定一个链表的头节点 head，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
示例：输入：head = [1,2,3,4], pos = -1输出：false解释：链表中没有环。
解题思路：使用快慢指针法，快指针每次移动两个节点，慢指针每次移动一个节点。
如果存在环，快指针最终会追上慢指针并相遇；如果不存在环，快指针会先到达链表尾部。
2. 单链表插入元素题目描述：给定一个链表的头节点 head 和要插入的位置 pos，以及要插入的元素 value。
在链表中插入新元素后，返回插入后的链表。
示例：输入：head = [1,2,3], pos = 2, value = 4输出：[1,2,4,3]解释：在位置 2 处插入元素 4，得到新的链表 [1,2,4,3]。
解题思路：在链表中插入元素需要先找到要插入的位置的前驱节点，然后将新节点插入到前驱节点和后继节点之间。
如果插入位置为链表第一个位置，则需要创建新节点并将其指向头节点；如果插入位置超过了链表的长度，则无法插入元素。
3. 单链表删除元素题目描述：给定一个链表的头节点 head 和要删除的位置 pos，删除链表中第 pos 个节点（从 1 开始计数），并返回删除后的链表。
示例：输入：head = [1,2,3,4], pos = 2输出：[1,3,4]解释：删除位置 2 上的节点 2，得到新的链表 [1,3,4]。
解题思路：在链表中删除元素需要先找到要删除位置的前驱节点，然后将前驱节点的 next 指针指向要删除节点的后继节点，最后释放要删除节点的内存空间。
如果删除位置为链表第一个位置，则需要修改头节点；如果删除位置超过了链表的长度，则无法删除元素。
链表练习题及答案1、已知L是带表头的单链表，其P结点既不是首元结点，也不是尾元结点，a.删除p结点的直接后继的语句是11，3，14b.删除p结点的直接前驱的语句是10，12，8，11，3，14c.删除p结点的语句序列是10，7，3，14d.删除首元结点的语句序列是12，10，13，14e.删除尾元结点的语句序列是9，11，3，14（1）p=p->next;(2) p->next=p;(3)p->next=p->next->next;(4)p=p->next->next;(5)while(p)p=p->next;(6)whlie(Q->next){p=Q;Q=Q->next;}(7)while(p->next!=Q)p=p->next;(8)while(p->next->next!=Q)p=p->next;(9)while(p->next->next)p=p->next;(10)Q=p;(11)Q=p->next;(12)p=L;(13)L=L->next;(14)free(Q);2、已知L是带表头的单链表，其P结点既不是首元结点，也不是尾元结点，a.在p结点后插入s结点的语句序列是4，1b.在p结点前插入s结点的语句序列是7，11，8，4，1c.在表首插入s结点的语句序列是5，12d.在表尾插入s结点的语句序列是7，9，4，1或11，9，1，61.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;3、已知P结点是某双向链表的中间结点，从下列提供的答案中选择合适的语句序列a.在P结点后插入S结点的语句序列是12，7，3，6b.在P结点前插入S结点的语句序列是13，8，5，4c.删除p结点的直接后继结点的语句序列是15，1，11，18d.删除p结点的直接前驱结点的语句序列是16，2，10，18e.删除p结点的语句序列是9，14，171.P->next=P->next->next;2.P->priou=P->priou->priou;3.P->next=S;4.P->priou=S;5.S->next=P;6.S->priou=P;7.S->next=P->next;8.S->priou=P->priou;9.P->priou->next=P->next;10.P->priou->next=P;11.P->next->priou=P;12.P->next->priou=S;13.P->priou->next=S;14.P->next->priou=P->priou;15.Q=p->next;16.Q=P->priou;17.free(P);18.free(Q);。
数据结构第三章习题3．1 单项选择题2.一个栈的入栈序列a, b, c, d, e, 则栈的不可能的输出序列是。
A. edcbaB. DecbaC. DceabD. abcde3. 若已知一个栈的入栈序列是1，2，3，………..n, 其输出序列为p1, p2, p3,……,pn, 若p1=n, 则pi为。
A.i.B. n=IC. n- i+1D.不确定4．栈结构通常采用的两种存储结构是。
A. 顺序存储结构和链表存储结构B. 散链方式和索引方式C.链表存储结构和数组D. 线性存储结构和非线性存储结构5．判定一个栈ST（最多元素为m0）为空的条件是。
A. ST->top<>0B. ST->top=0C.ST->top<>m0D.ST->top=m06．判定一个栈ST（最多元素为m0）为栈满的条件是。
A. ST->top!=0B.ST->top==0C.ST->top!=m0D.ST->top==m07.栈的特点是，队列的特点是。
A先进先出 B. 先进后出8. 一个队列的入栈序列是1，2，3，4，则队列的输出序列是。
A. 4,3,2,1B. 1,2,3,4C. 1,4,3,2D. 3,2,4,19. 判定一个队列QU(最多元素为m0)为空的条件是。
A.QU->rear- QU->front==m0B.QU->rear- QU->front-1==m0C.QU->front== QU->rearD. QU->front== QU->rear+110.判定一个队列QU（最多元素为m0）为满队列的条件是。
A.QU->rear- QU->front==m0B.QU->rear- QU->front-1==m0C.QU->front== QU->rearD.QU->front== QU->rear+111. 判定一个循环队列QU(最多元素为m0)为空的条件是。
数据结构课后习题答案-完整版下面是《数据结构课后习题答案-完整版》的内容：---第一章：数组1. 题目：给定一个整数数组，判断是否存在两个元素之和等于目标值。
答案：使用双指针法，首先将数组排序，然后设置左指针指向数组头部，右指针指向数组尾部。
如果左指针和右指针指向的元素之和小于目标值，则左指针右移；如果大于目标值，则右指针左移；如果等于目标值，则找到了两个元素之和等于目标值的情况。
2. 题目：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数的下标。
答案：使用哈希表，在遍历数组的过程中，将每个元素的值和下标存储在哈希表中。
遍历到当前元素时，检查目标值与当前元素的差值是否在哈希表中，如果存在，则找到了两个数的下标。
---第二章：链表1. 题目：给定一个链表，判断链表中是否存在环。
答案：使用快慢指针法，定义两个指针，一个指针每次向前移动一个节点，另一个指针每次向前移动两个节点。
如果存在环，则两个指针必定会相遇。
2. 题目：给定一个链表，删除链表的倒数第N个节点。
答案：使用双指针法，定义两个指针，一个指针先移动N个节点，然后两个指针同时向前移动，直到第一个指针到达链表尾部。
此时第二个指针指向的节点即为要删除的节点。
---第三章：栈和队列1. 题目：设计一个栈，使得可以在常数时间内获取栈中的最小元素。
答案：使用辅助栈来保存当前栈中的最小元素。
每次压栈操作时，将当前元素与辅助栈的栈顶元素比较，只有当前元素较小才将其压入辅助栈。
2. 题目：设计一个队列，使得可以在常数时间内获取队列中的最大元素。
答案：使用双端队列来保存当前队列中的最大值。
每次入队操作时，将当前元素与双端队列的末尾元素比较，只有当前元素较大才将其压入双端队列。
---第四章：树和二叉树1. 题目：给定一个二叉树，判断它是否是平衡二叉树。
答案：通过递归遍历二叉树的每个节点，计算每个节点的左子树高度和右子树高度的差值。
如果任意节点的差值大于1，则该二叉树不是平衡二叉树。
3.5习题一、名词解释（1）栈栈是限制在表的一端进行插入和删除操作的线性表。
允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。
栈的顺序结构：利用顺序存储方式实现的栈称为顺序栈。
栈的链式结构：用链式存储结构实现的栈称为链栈。
（2）队队是一种“先进先出” (FIFO---First In First Out)的数据结构，即插入操作在表一端进行，而删除操作在表的另一端进行，这种数据结构称为队列。
把允许插入的一端称为队尾(rear)，把允许删除的一端称为队头(front)。
队的顺序结构：顺序存储的队称为顺序队。
队的链式结构：采用链式存储结构的队称为链队。
二、判断题（1）栈和队列都是特殊的线性表。
( √ )（2）栈和队列都将插入和删除操作限制在表的端点处进行。
(√ )（3）只允许在表的一端进行插入和删除操作的线性表称为栈。
(√)（4）没有元素的栈称为空栈，空栈用不着栈顶指针。
( × )（5）只要栈不空，就能任意删除栈的元素。
(× )（6）栈允许删除的一端称为栈顶，而栈底元素是不能删除的。
(× )（7）对采用链式存储结构的栈进行操作不必判断溢出。
(√ )（8）元素进出队列一定满足“先进先出”的规律。
(√ )（9）链队列不存在溢出问题。
(√ )（10）在链队列中删除一个元素是在链表的最前端进行的。
(√ )三、单项选择题（1）栈和队列的共同之处在于它们具有相同的( A )。
A．逻辑特性 B．物理特性 C．运算方法 D．元素类型（2）栈和队列都是特殊的线性表，其特殊性在于( C )。
A．它们具有一般线性表所没有的逻辑特性B．它们的存储结构比较特殊C．对它们的使用方法做了限制D．它们比一般线性表更简单（3）若5个元素的出栈序列为1，2，3，4，5，则进栈序列可能是( )。
A．2，4，3，1，5 B．2，3，1，5，4C．3，1，4，2，5 D．3，1，2，5，4（4）某队列初始为空，若它的输入序列为a，b，c，d，它的输出序列应为( )。
数据结构第三章习题及解答Chap3一选择题1. 对于栈操作数据的原则是（B）。
A. 先进先出B. 后进先出C. 后进后出D. 不分顺序2. 在作进栈运算时,应先判别栈是否( B ),在作退栈运算时应先判别栈是否( A )。
当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( B )。
A. 空B. 满C. 上溢D. 下溢③: A. n-1 B. n C. n+1 D. n/23. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（B）。
A. 不确定B. n-i+1C. iD. n-i4. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（C）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 34 15 65. 设栈的输入序列是1，2，3，4,则（D）不可能是其出栈序列。
A. 1，2，4，3，B. 2，1，3，4，C. 1，4，3，2，D. 4，3，1，2，6. 设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（D）。
A. 5 1 2 3 4B. 4 5 1 3 2C. 4 3 1 2 5D.3 2 1 5 47. 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( C)。
A．XYZ B. YZX C. ZXYD. ZYX8. 执行完下列语句段后，i值为：（B）int f(int x){ return ((x>0) ? x* f(x-1):2);}int i ;i =f(f(1));A．2 B. 4 C. 8 D. 无限递归9. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( D )。
A．仅修改队头指针 B. 仅修改队尾指针C. 队头、队尾指针都要修改D. 队头,队尾指针都可能要修改10. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ C ）的数据结构。
第2章自测卷答案一、填空1.顺序表中逻辑上相邻的元素的物理位置相互相邻。
单链表中逻辑上相邻的元素的物理位置不相邻。
2.在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点值域指示。
3．在n个结点的单链表中要删除已知结点*p，需找到它的地址。
二、判断正误（在正确的说法后面打勾，反之打叉）1. 链表的每个结点中都恰好包含一个指针。
X2. 链表的物理存储结构具有同链表一样的顺序。
X3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
X4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
Y5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
Y6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
X7. 线性表在物理存储空间中也一定是连续的。
X8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
X9. 顺序存储方式只能用于存储线性结构。
X10. 线性表的逻辑顺序与存储顺序总是一致的。
X三、单项选择题（A）1. 链接存储的存储结构所占存储空间：（A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针（B）只有一部分，存放结点值（C）只有一部分，存储表示结点间关系的指针（D）分两部分，一部分存放结点值，另一部分存放结点所占单元数（B）2. 链表是一种采用存储结构存储的线性表；（A）顺序（B）链式（C）星式（D）网状（D）3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续或不连续都可以（B）4．线性表Ｌ在情况下适用于使用链式结构实现。
（Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入（Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂（C）5．单链表的存储密度（Ａ）大于1；（Ｂ）等于1；（Ｃ）小于1；（Ｄ）不能确定（A）6、在单链表的一个结点中有个指针。
A、1B、2C、3D、4（D）7、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用最节省时间。
A、单链表B、单循环链表C、带尾指针的单循环链表D、带头结点的双循环链表（B ）8、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是。
A、p->next=s;s->next=p->next;B、s->next=p->next;p->next=s;C、p->next=s;p->next=s->next;D、p->next=s->next;p->next=s;（C ）9、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是。
A、head==NULLB、head→next==NULLC、head→next==headD、head!=NULL （head指向谁的)（c）10、在双向链表指针p的结点前插入一个指针q的结点操作是。
A、p->prior=q;q->next=p;p->prior->next=q;q->prior=q;B、p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior;C、q->next=p;q->prior=p->prior;p->Prior->next=q;p->prior=q;D、q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;（A ）11、在一个单链表中，若删除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;（A）12、不带头结点的单链表head为空的判定条件是。
A、head=NULLB、head->next=NULLC、head->next=headD、head!=NULL（B）13、链表不具有的特点是。
A、插入、删除不需要移动元素B、可随机访问任一元素C、不必事先估计存储空间D、所需空间与线性长度成正比× ）1. 链表的每个结点中都恰好包含一个指针。
答：错误。
链表中的结点可含多个指针域，分别存放多个指针。
例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。
（ × ）2. 链表的物理存储结构具有同链表一样的顺序。
错，链表的存储结构特点是无序，而链表的示意图有序。
（ × ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
错，链表的结点不会移动，只是指针内容改变。
（ × ）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。
（ × ）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
错，正好说反了。
顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”（ × ）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
错，前一半正确，但后一半说法错误，那是链式存储的优点。
顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。
（ × ）7. 线性表在物理存储空间中也一定是连续的。
错，线性表有两种存储方式，顺序存储和链式存储。
后者不要求连续存放。
（ × ）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
错误。
线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。
（ × ）9. 顺序存储方式只能用于存储线性结构。
错误。
顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。
（后一节介绍）（ × ）10. 线性表的逻辑顺序与存储顺序总是一致的。
错，理由同7。
链式存储就无需一致。
三、填空题1、在带头结点的单链表L中，若要删除第一个元素，则需要执行下列三条语句：_______________；L→next＝U→next；free（U）。
2、在单链表L中，若要在指针P所指结点之后插入由指针S所指的结点，则需执行下列语句：S->next=P->next；______________；3、在带有头结点的单链表L中，第一个元素结点的指针是_____________。
4、双循环链表L中由指针P所指向的某结点为尾结点的条件是_______________。
1. 【严题集2.2①】在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。
2.线性表中结点的集合是有限的，结点间的关系是一对一的。
3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 n-i+1 个元素。
4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动 n-i 个元素。
5. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为随机存取的数据结构。
6. 【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置必定相邻。
单链表中逻辑上相邻的元素的物理位置不一定相邻。
7. 【严题集2.2①】在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。
8．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。
data next四、算法设计题1、设有两个单链表L和L1，各结点结构如下：试画出该链表的结构图，并编写算法，判断单链表L1是否与单链表L相同，相同返回1，不同返回0。
五、简答题1. 【严题集2.3②】试比较顺序存储结构和链式存储结构的优缺点。
在什么情况下用顺序表比链表好？答：①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。
优点：存储密度大（＝1？），存储空间利用率高。
缺点：插入或删除元素时不方便。
②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。
缺点：存储密度小（<1），存储空间利用率低。
顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
2 .【严题集2.1①】描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。
在单链表中设置头结点的作用是什么？答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。
为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。
头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。
若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。
否则表示空表的链表的头指针为空。
这三个概念对单链表、双向链表和循环链表均适用。
是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。
头结点headàdata link头指针首元结点简而言之，头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针）首元素结点是指链表中存储线性表中第一个数据元素a1的结点。
