数据结构期末考试复习：排序算法与基本数据结构

本资源是一份数据结构期末考试A卷及参考答案，涵盖了数据结构课程中的各种概念和算法。其中包括了多项选择题，测试了考生对于基础数据结构的理解和应用能力。 1. 在单项选择题中，第一个问题是关于栈和队列的特性。题目问当元素e1至e6依次进入栈S，然后出栈并进入队列Q，最终队列出队顺序为e2、e4、e3、e6、e5和e1时，栈S的最小容量。根据操作过程，e2和e4在队列中出现前必须出栈，所以它们在栈中至少需要一个额外的空间，即栈S的容量至少为4（选项B）。 2. 银行业务叫号系统的数据结构选择题中，银行的操作流程通常遵循先进先出（FIFO）原则，因此这里应选择队列（选项D），因为它符合这种特性。 3. 二叉树的形态问题，题目询问具有3个节点的不同形状的二叉树种类。由于最少的二叉树形态是只有一个根节点的树，再加一个只有一个孩子的左或右孩子，可以形成2种形态；另一种是两个孩子都存在，但其中一个没有右孩子，这样又有两种形态。因此，共有4种不同的形状（选项B）。 4. 数据结构的分类题中，从逻辑上划分，数据结构主要分为线性结构（如数组、链表）和非线性结构（如树、图）（选项B）。 5. 非空循环单链表的尾结点判断，因为是循环链表，尾节点的next指针会指向头节点，即p->next==head（选项C）。 6. 栈和队列的共同点在于它们都允许在其端点处进行插入和删除操作（选项C），而并非同时具备先进先出（FILO）和先进后出（LIFO）的特性。 7. 队列的输出顺序问题，如果入队序列是1,2,3,4，队列遵循先进先出规则，所以输出序列将是1,2,3,4（选项B）。 8. 串的长度定义为串中所含字符的个数，不区分重复字符（选项A）。 9. 对于具有10个叶子节点的二叉树，每个非叶子节点至少有一个孩子，所以叶子节点数量减去1等于度为2的节点数量。因此，有9个度为2的节点（选项B）。 10. 结合中序和后序遍历的特性，已知中序为ABCDEFG，后序为BDCAFGE，可以推断左子树包含B、C和D，共3个结点（选项C）。 11. 对于二叉树的问题，森林F的结点数与对应二叉树B的关系可以通过观察二叉树的性质得知。如果B的右子树结点个数为n，那么B本身至少有n+1个结点，而森林F的第一棵树即为B，所以第一棵树的结点个数也是n+1（选项C）。 12. 最后一道题目考察排序算法的时间复杂度。快速排序在平均情况下的时间复杂度为O(nlogn)，但在最坏情况下会退化到O(n^2)，堆排序虽然也有O(nlogn)的平均时间复杂度，但总是保持在O(nlogn)级别，不会退化到O(n^2)，因此正确答案是堆排序（选项B）。 整个试卷涉及了栈、队列、二叉树、数据结构的分类、链表特性、排序算法等基础知识，旨在测试学生对这些核心概念的掌握程度。