type
status
date
slug
summary
tags
category
icon
password
前言：
软件工程专业卢鹏丽老师布置的六次平时作业，该课程考试题99%来源于平时作业，禁止后来者抄袭，只做复习备考用，以下是第一次作业
一、判断题
1. 线性表的逻辑顺序与存储顺序总是一致的
答案：错误
解释 ：线性表有两种存储结构，顺序存储结构和链式存储结构。在顺序存储结构中，线性表的逻辑顺序与存储顺序是一致的，因为元素是连续存储的，逻辑上相邻的元素在物理位置上也相邻。但在链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻，所以整体来说线性表的逻辑顺序与存储顺序并不总是一致。
2. 顺序存储的线性表可以按序号随机存取
答案：正确
解释 ：顺序存储的线性表是把元素顺序存放在一组连续的存储单元中，每个元素的存储位置和它的序号之间存在一个简单的映射关系。因此可以根据序号直接计算出对应元素的存储地址，实现按序号随机存取。
3. 顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动
答案：错误
解释 ：顺序表的插入和删除操作通常需要付出较大的时间代价。因为当在指定位置插入或删除一个元素时，为了保持顺序表的连续性，其后所有元素都需要依次向后或向前移动一个位置，平均来说每次操作大约有近一半的元素需要移动，这使得时间复杂度为 O(n)（n 为顺序表长度），所以需要付出较大的时间代价。
4. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻
答案：错误
解释 ：线性表的顺序存储结构是把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，这样才能保证其顺序性，方便按序号随机存取等操作，所以逻辑上相邻的两个元素在物理位置上一定是紧邻的。
5. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻
答案：正确
解释 ：链式存储结构是用一组任意的存储单元存储线性表的数据元素，这些存储单元可以是连续的，也可以是不连续的。逻辑上相邻的元素在物理位置上不一定相邻，通过指针（或称为链）来体现元素之间的逻辑关系。
6. 线性表的链式存储结构优于顺序存储结构
答案：错误
解释 ：线性表的顺序存储结构和链式存储结构各有优缺点，不能简单地说谁优于谁。顺序存储结构的优点是支持随机访问、存储密度高，但插入和删除操作需要移动大量元素；链式存储结构插入和删除操作相对方便（不需要移动元素，只需改变指针），但只能顺序访问元素，存储密度相对较低（因为需要存储指针等额外信息）。在不同的应用场景下，根据具体需求选择合适的存储结构。
7. 在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关
答案：正确
解释 ：在顺序存储结构的线性表中，插入和删除元素时，其后所有元素都需要依次移动。例如在第 i 个位置插入元素，从表尾开始到第 i 个位置的元素依次向后移动一个位置；删除第 i 个元素时，从第 i+1 个位置到表尾的元素依次向前移动一个位置。所以移动元素的个数与该元素的位置（即 i 的大小）有关，位置越靠前（i 越小），移动的元素个数越多。
<ins/>
二、叙述题
1. 描述以下三个概念的区别：头指针 (head pointer)、头节点(head node)、首元节点（第一个元素节点） (the first node)
头指针 ：是指向链表中第一个节点（即头节点）的指针，它主要用于标识整个链表的起始位置。有了头指针，就可以从链表的开头开始访问链表中的各个节点。例如在一个单链表中，头指针
head 指向头节点，通过 head 就可以顺着链表依次访问后续的各个节点。头节点 ：是链表中的一个特殊节点，通常位于链表的开头。它可以用来简化链表操作，特别是在插入和删除操作时。头节点一般不存储具体的数据元素（当然也可以存储一些辅助信息，比如链表的长度等），其主要作用是作为一个固定的起点，方便对链表进行统一的管理和操作。比如在带头节点的单链表中，不管链表是否为空，头节点都存在，这样在插入和删除第一个元素节点时，操作就和其他位置的操作具有一致性，不需要单独处理特殊情况。
首元节点（第一个元素节点） ：是链表中第一个存储数据元素的节点。在有头节点的链表中，首元节点是头节点的下一个节点；在无头节点的链表中，首元节点就是头指针所指向的那个节点，即链表的第一个节点。它标志着链表中实际存储数据元素的开始位置。
区别 ：头指针是一个指针变量，用于指向链表的开头；头节点是链表中的一个实际节点，位于链表的起始位置，主要用于操作的方便；首元节点是链表中第一个存储数据元素的节点，在有头节点的链表中和无头节点的链表中其位置有所不同。
2. 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于 mink 且小于 maxk 的元素（若表中存在这样的元素），同时释放被删节点空间（注意：mink 和 maxk 是给定的两个参变量，他们的值可以和表中的元素相同，也可以不同）
【关键学习点】
- 双指针护航：q始终作为p的前驱，维护链表连续性
- 有序性利用：递增有序特性使范围判断只需单次遍历
- 内存管理三部曲：标记→摘除→释放，防止野指针
- 边界处理艺术：头节点保护、空链表检测、区间端点处理
- 时间复杂度：O(n)线性遍历，符合链表操作最优效率
3. 已知带头结点的单链表 L，数据域为整型，写算法计算所有数据域为 x 的结点的个数
代码理解：
- 函数定义
SLink *L是带头结点的单链表入口，就像快递站的货架入口；x是要找的特定包裹，i是找到的包裹计数器。函数如同快递扫描仪，逐个检查包裹。
- 指针初始化
p = L->next让探测器跳过"假头"（头结点），直接从真正的第一个储物柜（数据节点）开始搜查，避免误算头结点。
- 遍历技巧
while(p)条件像探照灯，只要前面还有储物柜就继续扫描。每次循环p=p->next像打开当前储物柜的下一扇门，直到遇到空储物柜（NULL）停止。
- 条件判断
p->data == x是精确比对，就像用扫码枪核对包裹条形码。匹配成功时i++如同在统计板上划正字，简单但有效。
- 内存安全 与删除操作不同，此函数只需读取数据不需修改链表结构，因此无需处理节点释放问题，降低了内存泄漏风险。
4. 已知带头结点的单链表 L，数据域为整型，且从小到大排列，写算法插入值为 x 的元素，且仍升序
5. 什么是算法分析？算法分析从哪两个方面进行分析？
算法分析 是估计算法的好坏。
主要从以下两个方面进行：
时间复杂度 ：用于衡量算法在运行过程中所消耗的时间。通常通过计算算法中基本操作（如比较、赋值等）的执行次数来估算，用大 O 符号表示，如 O(1)、O(n)、O(n²) 等。它反映了算法在不同输入规模下的运行时间增长趋势。
空间复杂度 ：用于衡量算法在运行过程中所占用的存储空间。同样用大 O 符号表示，主要考虑算法在执行过程中临时占用的存储空间大小，如 O(1) 表示常数级空间复杂度，即占用的额外空间是一个固定值，与输入规模无关。
6. 设单链表中结点结构为 (data, next)。已知指针 q 所指结点是指针 p 所指结点的直接前驱，若在q 与p 之间插入结点*s，请写出所做操作
7. 设单链表中结点结构为 (data, next)。已知指针 q 所指结点是指针 p 所指结点的直接前驱，写出删除单链表中的节点 p 的操作
8. 给出下面术语的英文表示：数据结构、算法、时间复杂度、空间复杂度
数据结构：Data Structure
算法：Algorithm
时间复杂度：Time Complexity
空间复杂度：Space Complexity
9. 写出算法实现的功能及每步操作的含义
算法功能：在单链表L的第i个位置插入一个新元素e。如果插入成功，返回OK；如果插入位置非法（如超出链表长度范围），返回ERROR。
10. 已知带头节点的单链表H，写一算法，删除其重复结点实现如图的操作，并分析算法复杂度。（a）为删除前，（b）为删除后
11. 课堂补充代码，判断一个字符向量（字符串）是否为回文
<ins/>
- 作者:EageYren
- 链接:https://eageyren.edu.deal/learning/algorithm1
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
