根据给定的西南交通大学数据结构半期试卷及答案,我们可以从中提炼出多个重要的知识点:
### 一、基础知识
1. **图(网)**: 图是一种非线性数据结构,由顶点集和边集组成。在计算机科学中,图被广泛应用于解决各种问题,如路径查找、网络分析等。
2. **操作**: 这里的“操作”通常指的是对数据结构进行的各种处理,例如插入、删除、查找等基本操作。
3. **空间**: 在计算机科学中,“空间”一般指内存空间或存储空间,用来存放数据结构中的元素。合理地管理和利用空间对于提高程序性能至关重要。
4. **“先进后出”**: 这是指栈(Stack)的基本特性。栈是一种特殊的线性表,只允许在一端(称为栈顶)进行插入和删除操作,遵循先进后出的原则。
5. **(r+1)%m==f**: 此表达式出现在环形队列的判断条件中,用于检测队列为满状态。其中,`r` 代表队尾指针,`f` 代表队头指针,`m` 为队列的最大长度。当队列为空时,`r == f`;队列为满时,`(r+1)%m == f`。
6. **50**: 此处的数字可能是特定场景下的数值或者示例值,在没有上下文的情况下难以确定具体含义。
7. **()**: 一般表示空的集合或者序列。
8. **((a))**: 表示包含一个元素 `a` 的集合或列表。
9. **9** 和 **7**: 这两个数字可能是在某个特定情境下的数值,如数组中的元素值等。
10. **p1&&p2 或 p1!=NULL&&p2!=NULL**: 这种表达方式用于检查两个指针是否都指向有效的内存地址。若两个指针都不为空,则表达式返回真。
11. **<**: 这个符号在程序设计中通常表示小于关系运算符,用于比较两个数值的大小。
12. **last->next**: 在链表中,`last->next` 通常指向链表的最后一个节点的下一个节点,如果链表正常结束,则该值应为 `NULL`。
13. **p2**: 这里 `p2` 可能是一个指针变量,其具体的含义取决于上下文环境。
14. **!root->right&&!root->left**: 这个表达式用于判断根节点 `root` 是否为叶子节点,即该节点没有左右子节点。
15. **root**: 在树结构中,`root` 指的是树的根节点。
16. **root 或 p->right**: 这个表达式可能是用于确定访问顺序的逻辑,如遍历二叉树时选择先访问右子树还是根节点。
17. **136**: 这个数字可能是特定算法运行的结果,或者是某种特定场景下的数值。
18. **/-*a+bcde**: 这是一个表达式,其中包含加法和乘法运算,可能用于说明表达式的优先级或求解过程。
19. **-1, -1, -1, 2, -1, -1**: 这组数字可能是某个数据结构或算法中特定位置的索引值。
20. **3log n**: 这个公式通常出现在算法的时间复杂度分析中,表示某种算法的运行时间与输入规模 `n` 的对数成正比。
### 二、单项选择题知识点解析
1. **(1) B**、**(2) A**、**(3) ACD**、**(4) C**、**(5) A**、**(6) D**、**(7) B**、**(8) A**、**(9) C**、**(10) B**: 这些选项涵盖了数据结构中的不同知识点,包括但不限于数组、链表、栈、队列、树、图等数据结构的特点和应用。
### 三、简答题知识点解析
1. **ABC ACB BAC BCA CBA**: 这些排列可能是对字符串或数组进行排序的不同结果,涉及到了排序算法的概念。
2. **1321**:这个数字序列可能是经过某种特定操作后的结果,如逆序排列等。
3. **⌊\log_{2}{n}⌋+2**:这个公式表示了某种算法的时间复杂度,常见于二分查找等算法的分析中。
4. **森林** 和 **二叉树**: 森林是由若干棵不相交的树组成的集合。将森林转换为二叉树是数据结构中的一个重要概念,涉及到树形结构的转换和遍历方法。
5. **哈夫曼二叉树**: 哈夫曼树是一种特殊的二叉树,广泛应用于数据压缩领域。哈夫曼编码是根据哈夫曼树构造的一种最优前缀码。
### 四、算法设计题知识点解析
1. **void erase(LNode *h)**: 这段代码展示了如何删除链表中负数节点的过程。通过设置两个指针 `pr` 和 `p` 来遍历链表,并检查每个节点的数据是否小于零,若是则将其从链表中移除。这段代码体现了链表的基本操作及其应用场景。
以上知识点涵盖了数据结构课程中的许多重要内容,包括但不限于基本数据结构的理解与应用、典型算法的设计与实现等。通过学习这些知识点,可以帮助学生更深入地理解数据结构与算法的核心概念和技术要点。
1