文彦考研
让
梦想
有迹可循
逐勋师兄
以专业课分数近分的成绩考入哈尔滨工业大学计算机学院，连续3年从事哈工大计算机专业课考研辅导工作，精通计算机系统基础（csapp)，计算机网络和数据结构，研究哈工大历年考研真题，有自己独到的解题思路和方法。
本次主要讲解数据结构第一部分内容-绪论，本部分内容主要是要了解逻辑结构和存储结构，另外时间复杂度和空间复杂度是重点，要格外注意。
图-数据结构三要素
数据
数据:是描述客观事物的符号,是计算机中可操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。
数据元素:是组成数据的,有一定意义的基本单位,在计算机里通常作为整体处理,也被称为记录。
数据项:一个数据元素可以由若干个数据项组成,数据项是数据不可分割的最小单位。
数据对象:是性质相同的数据元素的集合,是数据的子集。
数据结构:是相互之间存在的一种或多种特定关系的数据元素的集合。
数据的逻辑结构主要分为线性和非线性，其中线性包括队列，栈等，非线性为一对多包括树，图等结构。
集合结构:数据元素除了同属一个集合外,他们之间没有其他关系。
线性结构:线性结构中的数据元素之间是一对一的关系。
树形结构:树形结构中的数据元素之间是一对多的关系。
图形结构:图形结构中的数据元素是多对多的关系。
数据结构在计算机中的表示（又称映像），也称物理结构，它包括元素的表示和关系表示。
存储
顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里。
优点：是可以实现随机存取，每个元素占用最少的存储单元，缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
链式存储：不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针表示元素之间的逻辑关系。
优点：是不会出现碎片现象，充分利用所有存储单元；缺点是每个元素因存储指针而占用额外的存储空间，并且只能实现顺序存储。
索引存储：在存储元素信息的同事，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字：地址）。
优点：是索引速度快；缺点是增加了附加的索引表，会占用较多的存储空间。另外，在增加和删除数据时要修改索引表，因而会花费较多的时间。
散列存储：根据元素的关键字直接计算出该元素的存储地址，又称hash存储。
优点：是索引、增加和删除结点的操作都很快；缺点是如果散列函数不好可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。
重定位
算法（Algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中，每一条指令表示一个或多个操作。
（1）执行算法所耗费的时间，即时间复杂度，记作T(n)=O(f(n))
（2）执行算法所耗费的存储空间，其中主要考虑辅助存储空间的大小，即空间复杂度。记作S(n)=O(f(n))。其中，n为问题的规模（或大小）。
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作T(n)=O(f(n))
假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则称T(n)为算法的(渐近)时间复杂度。
习题解析：
01
以下数据结构中，（）是非线性数据结构？
A.队列
C.集和
B.栈
D.串
答案
点击下方空白处获得答案
解析：选C，树、图和集和属于非线性结构。
02
已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（）。
A.O(n)
C.O(min(m,n))
B.O(m×n)
D.O(max(m,n))
答案
点击下方空白处获得答案
解析：选择D，两个升序链表合并，两两比较表中元素，没比较一次确定一个元素的链接位置（取较小的元素，头插法）。当一个链表比较结束后，将另一个链表的剩余元素插入即可，最坏的情况是两个链表中的元素依次进行比较，时间复杂度为O(max(m，n))。
推荐阅读：
21哈工大计算机考研
备考重点与参考书目推荐！
21届考研初试辅导班招生进行中...
大家有任何疑问，入群或
加老师