数据结构1800.pdf

在学习数据结构和算法时，首先需要掌握的概念是对算法基本特性的理解。算法的计算量大小通常被称为算法的时间复杂度，它衡量的是算法执行时间的增长趋势。一个算法的效率是指算法执行速度的快慢。算法的复杂性涉及算法处理问题时所需要的时间和空间资源。算法的难度通常与问题的难易程度有关，与计算量的大小不是一个直接的概念。 问题的规模对算法的时间复杂度有很大影响。此外，算法必须具备可执行性、确定性和有穷性这三个特性。可执行性意味着算法中的每条指令都能被机器所执行；确定性指的是算法中的每条指令都是清晰无二义的；有穷性是指算法在有限的操作步骤内能够完成任务并得出结果。一个算法还应该满足稳定性、易读性和安全性等特性，以便于算法的实现、维护和验证。 数据结构通常可以分为线性结构和非线性结构两大类。线性结构中包含的数据元素之间是有序的一对一关系，如栈、队列、数组、链表和广义表等。非线性结构中包含的数据元素之间则是复杂的关系，如树、图、堆等。数据结构的逻辑结构指的是数据之间的逻辑关系，不考虑数据在计算机中的具体表示。而物理结构是指数据在计算机内的存储方式，包括连续存储和非连续存储。 选择题中涉及了数据结构和算法相关的知识点。例如，算法是否最终必须由计算机程序实现，以及算法和程序的区别。算法的原地工作是指不需要额外的辅助空间。在相同的规模n下，复杂度O(n)的算法在时间上并不一定总是优于复杂度O(2n)的算法，因为算法的时间复杂度要考虑到最坏情况下的执行时间。数据结构的存储结构与栈、链表、哈希表等术语相关，其中哈希表与数据的存储结构无关。数据结构中线性结构的实例包括栈、队列和串，而非线性结构包括树、图等。 在判断题中，数据元素和记录的定义被提出。数据元素是指数据的最小单位，是数据结构中独立的个体；记录是指数据处理的最小单位，是具有相同性质的数据元素的集合。数据的逻辑结构和物理结构的区别也是重要知识点，逻辑结构是数据元素间关系的抽象表示，物理结构是逻辑结构在计算机存储器中的实现方式。 对于具体算法问题，例如在循环嵌套中的赋值语句频度，就需要理解循环的执行次数以及循环内部语句的执行情况。最坏情况下，算法的时间复杂度是指在问题规模增长时，算法执行时间的增长上界，通常用来评价算法的效率。 通过以上内容，我们可以看到数据结构和算法的考研题目不仅仅考察对单一知识点的记忆，更多的是考察对知识点之间联系的理解，以及解决问题的综合能力。在复习时，应注意归纳和总结，将所学知识形成体系，才能在面对不同类型的问题时做出正确的判断和解答。