天津大学《计算机软件技术基础(2)》在线作业二：栈与排序算法详解

本资源是天津大学《计算机软件技术基础(2)》在线作业二的一部分，涉及多个计算机科学的基础概念和算法。主要内容包括： 1. 栈的输出序列理解：题目要求分析一个栈的入栈序列(a, b, c, d, e)不可能的输出序列，其中选项C (dceab)是不可能的，因为栈遵循先进后出(FILO)原则，不可能先出栈d再出栈e。 2. 栈的输出顺序规律：另一个问题涉及到栈的出栈顺序规则，当栈的输入序列是1, 2, 3, ..., n，且已知P1=n，表示出栈顺序是从大到小，所以Pi的值应该是n-i+1。 3. 排序算法效率：对于快速获取序列中第5个最小元素之前的排序，堆排序的时间复杂度为O(n)，是最快的，因为它可以保证在最坏情况下也能快速找到最小元素。 4. 链表查找算法的时间复杂度：给出的链表按序号查找算法的时间复杂度是线性的，但不是简单的O(n)，而是O(n2)，因为每次循环都要检查下一个节点，直到找到目标或遍历完整个链表。 5. 稀疏矩阵的压缩存储：稀疏矩阵通常使用压缩存储方法，如三元组和十字链表，用于节省空间，这两者可以高效地表示非零元素的位置。 6. 树的叶子节点计算：根据树的度数分布，叶子节点的数量等于所有度为1的节点数量加上其他每个节点的度减一，即1 + ni*(1 - m)。 7. 二叉树先根遍历：对于给定的二叉表，按先根遍历的顺序是HIDBEFGAC。 8. 插入排序的最好情况：直接插入排序在最好情况（即输入已排序）下的时间复杂度是线性的，即O(n)。 9. 二叉树中序遍历：中序遍历的顺序反映了节点的左子树、根节点和右子树的访问顺序，给定的选项C符合这个规律。 10. 哈夫曼树的加权路径长度：哈夫曼树的加权路径长度是所有边权的总和，根据权集W={2, 3, 4, 7, 8, 9}，计算得出的和为20。 11. 多道程序设计目的：引入多道程序设计的主要目的是提高CPU的利用率，减少CPU等待时间，通过并发执行多个任务。 这些题目涵盖了数据结构（栈、链表、二叉树）、排序算法、稀疏矩阵存储、树的性质、以及操作系统中的并行计算等知识点，有助于巩固学生的理论基础和实践应用能力。