计算机科学入门：数据结构习题详解

《数据结构》（计算机科学与技术本科）是一本经典的教材，主要探讨了计算机科学中数据结构的基础理论和实践应用。该课程的第一部分主要考察了一些基础概念和算法的理解。 1. 时间复杂度分析：第1题考查的是程序执行效率，通过嵌套循环判断，该代码的时间复杂度是O(n^2)，因为两个嵌套循环都是n层，所以答案是D。理解时间复杂度有助于优化算法性能，对于设计高效的数据处理流程至关重要。 2. 数据移动平均问题：第2题涉及顺序表操作，由于元素均匀分布，插入一个元素平均需要将后面的元素向前移动(n-1)/2个位置，以保持顺序，因此答案是B。 3. 栈与输出序列：第3题描述了栈的特性，栈遵循后进先出的原则，当入栈序列是1到n，如果输出序列p1=n，那么前一个元素p2应该是n-1，以此类推，pi = n - (i-1) = n-i+1。 4. 串的子串数量：第4题考查字符串的子串问题，对于字符串"ABCDEFGH"，有8个长度为1的子串，7个长度为2的子串，...，1个长度为8的子串，共计1+2+...+8=36个不同子串，答案是C。 5. 二叉树性质：第5题指出二叉树的度并非固定为2，它可以小于2，这意味着有的节点可能只有一个子节点或没有子节点，正确答案是B。 6. 图遍历与二叉树：第6题，深度优先遍历（DFS）在二叉树中的对应是先访问根节点然后递归地访问左子树和右子树，这与先序遍历相符，答案是A。 7. 散列表：第7题涉及散列表的结构，链地址法处理冲突时，每个地址单元链接的同义词表中的结点具有相同的散列地址，答案是C。 8. 折半查找：第8题，给定有序表中查找95，第一次比较将范围缩小到45到100之间，第二次比较确定在75到95之间，第三次比较找到95，共需要3次比较，答案是B。 9. 稳定排序：第9题问哪种排序方法是稳定的，稳定的排序方法在相等元素的顺序不会改变，直接插入排序是稳定的，答案是D。 10. 堆排序时间复杂度：第10题，堆排序的最坏时间复杂度是O(nlogn)，因为构建堆和调整堆的时间复杂度都是O(n)，答案是B。 11. 数据结构分类：第11题，数据结构根据是否能动态改变其结构分为动态结构（如链表、树等）和静态结构（如数组），题目表述错误。 12. 链表首元结点：第12题，非空单链表的首元结点不一定存储在头指针指示的位置，因为头结点的存在与否取决于链表的具体实现，答案是B。 这些题目涵盖了数据结构的基础概念，包括时间复杂度分析、数据结构类型、链表操作、栈和队列、二叉树遍历、散列表、查找算法以及排序方法的特点，适合用于复习或检验对数据结构的理解程度。