华师大学数据结构在线作业解析

"华师远程数据结构在线作业包含多项选择题，涉及编码、算法复杂度、链表操作、字符串比较、广义表的关系以及排序算法等数据结构和算法相关内容。" 1. 前缀码是一种编码方式，其中没有任何一个编码是另一个编码的前缀。在给出的选项中，只有A项{1,01,000,001}满足这个条件，因为不存在一个编码是其他编码的起始部分。 2. 此题考察了不同增长速率的比较，涉及对数和指数增长。根据增长率由小到大排序，正确的顺序是n的1/2次方，n的3/2次方，n的logn次方，2的n次方。所以答案是A。 3. 题目描述的程序段是用于在已有的链表中插入一个新结点。首先将p指向的结点的下一个结点保存到s->next，然后将s插入到p之后，最后交换p和s的数据域，表明是在结点p之前插入结点s，因此答案是D。 4. strcmp函数是C语言中的字符串比较函数，当比较的两个字符串不相等时，会返回一个整数值，表示第一个不相同字符的ASCII码差值。如果字符串S（"abc"）小于字符串T（"xyz"），strcmp(S, T)将返回一个负数，因此答案是B。 5. 广义表的分类包括线性表、纯表、再入表和递归表。线性表是最基础的形式，纯表允许空表和只有一个元素的表，再入表可以包含自身引用，递归表是包含自身引用的纯表。按照从简单到复杂的顺序，答案是D。 6. 线性探测法是解决哈希冲突的一种方法。如果有k个关键字互为同义词，并且要存入散列表，最坏情况下，每个关键字都需要探测k次，因为它们都可能被放到同一个位置，所以总共需要探测k(k+1)/2次。 7. 直接选择排序算法在最坏的情况下，需要交换n(n+1)/2次记录。在本题中，学生未能正确回答此题，得分为0。 8. 在线索二叉树中，如果一个结点是叶子结点，意味着它既没有左子结点也没有右子结点，所以其左右标志位都应该为0。因此，正确的条件是p->ltag==0 && p->rtag==0。 这些题目涵盖了数据结构的基础知识，包括编码理论、算法复杂度分析、链表操作、字符串处理、数据存储（哈希表）和排序算法。这些都是计算机科学特别是数据结构与算法课程中的核心概念。