华南师范大学《数据结构》在线作业解析

"这篇资料包含了2014年春季华南师范大学《数据结构》课程的在线作业题目，涉及数据结构的基础概念和操作，如编码、排序算法、链表操作、字符串比较、广义表的关系以及散列表和图的处理。" 在这些题目中，我们可以提取以下几个重要的知识点： 1. **前缀码**：前缀码是一种编码方式，其特点是没有任何编码是其他编码的前缀。题目中A选项{1,01,000,001}满足这一特性，是前缀码。 2. **增长率比较**：题目中比较了不同数量级的增长速度，如n1/2，n!，2^n，n^3/2等，这涉及到算法复杂度分析，通常用于比较不同算法的效率。答案D表明了增长速度从小到大的顺序。 3. **链表操作**：第3题涉及单链表的插入操作。程序段实现了在结点*p之后插入结点*s，而不是在*p之前或交换数据。因此，答案是C。 4. **字符串比较**：strcmp函数用于比较两个字符串，若字符串S在字母顺序上小于T，则返回负数，反之返回正数，相等则返回0。所以strcmp(S, T)返回负数，答案为B。 5. **广义表的关系**：广义表包括线性表、纯表、再入表和递归表四种类型。题目中的答案D表示线性表是最基础的，其次是纯表，然后是再入表，最后是递归表。 6. **散列表冲突处理**：线性探测法是解决哈希冲突的方法之一，当k个关键字互为同义词时，至少需要k(k+1)/2次探测，答案为D。 7. **选择排序**：直接选择排序在最坏的情况下需要交换n(n-1)/2次记录，答案为C。 8. **线索二叉树**：线索二叉树是一种特殊的二叉树，其中非叶子节点的左右线索分别表示其在相应方向上的后继和前驱。题目中D选项表示结点是叶子节点，其左右线索标记都为1。 9. **拓扑排序**：拓扑排序是对有向无环图（DAG）的顶点的一种排序，总计算时间复杂度为O(n+e)，其中n是顶点数，e是边数，答案为D。 10. **排序方法**：题目提到的排序方法可能指的是某种特定的排序算法，但题目不完整，无法确定具体是哪种排序方法。 这些题目涵盖了数据结构课程中的关键概念，包括编码理论、算法复杂度分析、链表操作、字符串处理、广义表、散列表、排序算法和图论。掌握这些知识点对于理解和应用数据结构至关重要。