数据结构考试重点：线性与非线性结构解析及算法复杂度

"大学数据结构考试题和答案.pdf" 这篇资料涵盖了数据结构的基础知识，主要集中在数据结构的分类、存储结构、以及特定数据结构的操作。以下是相关知识点的详细说明： 1. 数据结构类型：数据结构主要包括线性结构、树形结构和图形结构。线性结构如数组和链表，其中数据元素呈线性排列；树形结构如二叉树、堆等，数据元素之间存在一对一的关系；图形结构则表现为一对多的关系，如图和网。 2. 存储结构：存储结构分为顺序存储和链式存储。顺序存储通常指数组，数据元素在内存中连续存放，访问速度快，但插入和删除操作可能涉及大量元素的移动；链式存储则通过指针连接数据元素，插入和删除灵活，但访问速度相对较慢。 3. 数据元素与数据结构：数据的基本单位是数据元素，又称结点，它是数据的最小处理单元。数据结构中的结构指的是数据元素之间的逻辑关系，分为线性结构（如线性表、栈、队列）和非线性结构（如树、图）。 4. 算法复杂度分析：题目中的两个应用题考察了时间复杂度。第一个算法`fun`的时间复杂度是O(n)，因为循环内部的操作对n的依赖是线性的。第二个算法`fun2`的时间复杂度是O(logn)，因为每次循环i乘以10，相当于以10为底的对数操作，每次循环使n的大小减少一个数量级。 5. 线性表：线性表的两种实现方式是顺序表和链表。顺序表支持随机访问，即可以快速访问任何位置的元素；链表则需要遍历来访问特定位置的元素。对于链表操作，插入新节点需要修改前后节点的链接关系，删除节点通常需要找到前趋节点。 6. 线性表操作的时间复杂度：在顺序存储的线性表中，插入和删除操作平均时间复杂度为O(n)，因为在最坏的情况下，可能需要移动n/2个元素。 7. 选择题解答： - 将两个有序表归并成一个有序表，最少的比较次数是n，当两个表已排序且元素不重复时。 - 在单链表中，在节点p后插入新节点s的操作应该是`s->next=p->next; p->next=s;` - 在长度为n的线性表顺序存储结构中，在第i个位置删除元素的平均时间复杂度是O(n)。 这些知识点是数据结构课程的基础，涵盖了基本概念、数据结构操作和算法复杂度分析，对于理解和解决数据结构相关问题至关重要。