福师11秋《数据结构概论》在线作业一标准答案.doc

数据结构是计算机科学中的核心概念，它涉及到如何高效地组织和管理数据，以便进行各种操作。在福师11秋《数据结构概论》在线作业一中，涉及的知识点广泛，涵盖了一些基本的数据结构和算法。 1. 循环队列的队空条件：在循环队列中，队空的判断条件是队头指针`front`等于队尾指针`rear`，所以正确答案是B。循环队列是一种特殊的线性表，它在物理存储上形成一个环形结构，避免了“假溢出”的问题。 2. 有向树构造：一个有向树是由若干个结点和有向边构成的，3个结点可以构造出2种不同的有向树，因为一个结点可以作为根，其他两个结点指向这个根，形成两种不同的情况，所以正确答案是A。 3. 栈和队列的特性：栈和队列都是线性结构，但它们的存取规则不同。栈遵循“后进先出”（LIFO）原则，而队列遵循“先进先出”（FIFO）原则。题目中给出的选项B是正确的。 4. 算法的基本性质：算法的空间复杂度表示算法运行过程中临时占用存储空间大小的量度，而时间复杂度则是算法执行时间与输入数据量的关系。有穷性是指算法必须在有限步骤后结束。因此，C选项是正确的描述。 5. 快速排序：快速排序是一种高效的排序算法，通过选取一个基准元素并将数组分为两部分来实现。题目中没有给出具体的划分策略，但根据快速排序的通常行为，B选项可能是正确的，因为较小的元素被放在基准元素的左侧，较大的在右侧。 6. 括号匹配：检测表达式中括号是否配对通常使用栈这种数据结构，因为它支持“后进先出”的操作，便于检查括号的匹配情况。所以正确答案是D。 7. 串的子串数目：一个字符串的子串数目包括空串和自身，因此对于S=’software’，子串总数为2^9 - 1 = 511，但题目中只有四个选项，所以最接近的是C，36。 8. 冒泡排序的比较次数：冒泡排序在最坏的情况下需要进行n*(n-1)/2次比较。对于序列{10,14,26,29,41,52}，它已经是部分有序的，但题目没有提供足够的信息来精确计算比较次数，所以只能根据一般规律推断，C选项15次可能是正确答案。 9. 稳定排序的选择：稳定排序是指相同元素的相对顺序在排序后不会改变。对于稳定性和速度的综合考虑，归并排序是最优选择，因为它始终是稳定的，并且在平均和最坏情况下都有良好的时间复杂度。 10. 动态查找法：如果线性表需要快速查找并且适应动态变化，顺序查找是合适的方法，因为插入和删除操作简单，但查找效率相对较低。 以上是部分题目涉及的知识点，这些知识点涵盖了数据结构的基础概念，如栈、队列、树、图、排序算法、存储结构以及算法分析等。理解和掌握这些知识点是学习数据结构的关键。