湖北师大2022数据结构期末考卷B：算法与数据结构实践

湖北师范大学2022年11月的《数据结构》期末考试试卷B包含两大部分：选择题和填空题，旨在考察学生对数据结构基础理论和实践应用的理解。以下是各部分知识点的详细解析： 一、单项选择题（共20分） 1. **时间复杂度**：分析给出的程序段`i=1; while(i<=n) i=i*2;`，可以看出这是一个指数增长的过程，每次循环i翻倍，所以时间复杂度为O(log2n)，因为n的每一次对数增长都会使得循环次数减半。答案是A。 2. **算法评价**：评价一个算法应考虑多方面，包括正确性、健壮性和可读性，以及空间和时间复杂度。并行性虽然重要，但在单个程序中通常不作为主要评价指标，因为这是硬件层面的优化问题。因此，选项B不包括在内。 3. **线性表链式存储**：链表的结点存储地址可以是连续也可以是不连续的，取决于具体实现方式，不一定要求连续存储。答案是B。 4. **单链表删除操作**：删除p所指向结点的后续结点，需要更新p的指针使其指向下一个结点，即`p->next = p->next->next;`。答案是A。 5. **队列特性**：队列是一种特殊的线性表，遵循先进先出（FIFO）原则，允许在一端进行插入，在另一端进行删除。答案是C。 6. **字符串操作**：在给定的串S1中查找S2首次出现的位置称为模式匹配或查找子串。答案是C。 7. **图的连通性**：一个无向图至少需要有n-1条边才能确保是连通的，对于6个结点的图，至少需要5条边。答案是A。 8. **二分查找**：在有序表中查找70，由于是递增序列，二分查找首先会比较中间元素，即30，然后根据结果决定在左半部分（小于30）或右半部分继续查找，直到找到目标。所以顺序是30，70。答案是A。 9. **哈夫曼树**：哈夫曼树是带权路径长度最小的二叉树。给定权值，构造哈夫曼树的过程会形成最优的编码，带权路径长度等于所有叶子结点路径之和。计算这个值需要具体步骤，但直接给定的答案是74，所以选A。 10. **快速排序**：快速排序在数据基本有序的情况下效率最低，因为此时分割过程难以达到理想效果，递归深度大，导致额外开销增加。答案是C。 二、填空题（每题2分，共14分） 这部分题目涉及更具体的细节，例如数据的存储结构、特定算法的实现等，填空题可能涉及到数组、链表、栈、队列、树等数据结构的具体概念和操作，以及算法的实现技巧和原理。这部分内容因缺失具体内容而无法详细展开，但答题时需要结合所学知识准确填写。 总结：这份数学试卷主要涵盖了数据结构中的基本概念、算法分析、线性数据结构（如链表、队列）、图论、查找算法（如二分查找）、哈夫曼树以及排序算法（如快速排序）等核心知识点，旨在考核学生对数据结构理论和实践应用的掌握程度。