考研系列-数据结构第一章、绪论（基本术语、时间复杂度）
目录
一、数据结构的基本概念
1.基本概念和术语
2.习题易错题-选择题
3.习题易错题-简答题
二、算法和算法评价指标
1.算法基本概念
2.时间复杂度计算
3.空间复杂度
4.易错题总结
三、章节归纳总结
四、参考
一、数据结构的基本概念
1.基本概念和术语
数据： 数据是信息的载体 ， 是描述客观事物属性的数 、 字符及所有能输入到计算机中并被计算机程 序识别和处理的符号的集合 。数据对象： 数据对象是具有相同性质的数据元素的集合 ， 是数据的一个子集 。 例如 ， 整数数据对象是集 合 N= {0,±1,±2, … } 。数据元素： 数据元素是数据的基本单位 ， 通常作为一个整体进行考虑和处理， 一个数据元素可由若干数 据项组成。数据项： 数据项是构成数据元素的不可分割的最小单位 。 例如 ， 学生记录就是一个数据元素 ， 它由学号 、 姓名 、 性别等数据项组成。
这里要区分一下逻辑结构和物理结构，直白一点的理解就是：逻辑结构是上层设计，物理结构是底层存储实现。逻辑结构如果是线性结构，底层的物理结构也可以是链式存储，这一点理解好就可以了。
2.习题易错题-选择题
题目：
01.可以用（ ）定义一个完整的数据结构
A.数据元素 B.数据对象 C.数据关系 D.抽象数据类型解答：
01.D
抽象数据类型（ADT）描述了数据的逻辑结构和抽象运算，通常用（数据对象，数据关系，基本操作集）这样的三元组来表示，从而构成一个完整的数据结构定义。
题目：
03.以下属于逻辑结构的是（）。
A.顺序表 B.哈希表 C.有序表 D.单链表解答：
03. C
顺序表、哈希表和单链表是三种不同的数据结构，既描述逻辑结构，又描述存储结构和数据运算。而有序表是指关键字有序的线性表，仅描述元素之间的逻辑关系，它既可以链式存储，又可以顺序存储，故属于逻辑结构。
题目：
解答：
04.D
数据的存储结构有顺序存储、链式存储、索引存储和散列存储。循环队列（易错点）是用顺序表表示的队列，是一种数据结构。栈是一种抽象数据类型，可采用顺序存储或链式存储，只表示逻辑结构。
题目：
解答：
05.A
数据的逻辑结构是从面向实际问题的角度出发的，只采用抽象表达方式，独立于存储结构，数据的存储方式有多种不同的选择；而数据的存储结构是逻辑结构在计算机上的映射，它不能独立于逻辑结构而存在。数据结构包括三个要素，缺一不可。
题目：
07.链式存储设计时，结点内的存储单元地址（ ）
A. 一定连续 B. 一定不连续 C.不一定连续 D.部分连续，部分不连续
解答：
07.A
链式存储设计时，各个不同结点的存储空间可以不连续，但结点内的存储单元地址必须连续。
3.习题易错题-简答题
题目：
01.对于两种不同的数据结构，逻辑结构或物理结构一定不相同吗？
解答：
应该注意到，数据的运算也是数据结构的一个重要方面。对于两种不同的数据结构，它们的逻辑结构和物理结构完全有可能相同。比如二叉树和二叉排序树，二叉排序树可以采用二叉树的逻辑表示和存储方式，前者通常用于表示层次关系，而后者通常用于排序和查找。虽然它们的运算都有建立树、插入结点、删除结点和查找结点等功能，但对于二叉树和二叉排序树，这些运算的定义是不同的，以查找结点为例，二叉树的时间复杂度为O(n)，而二叉排序树的时间复杂度为O(log2n)。
二、算法和算法评价指标
1.算法基本概念
2.时间复杂度计算
3.空间复杂度
4.易错题总结
(1)选择题
题目：
01.一个算法应该是()。
A.程序 B.问题求解步骤的描述 C.要满足五个基本特性 D. A 和 C
解答：
01. B
本题是中山大学考研真题，题目本身没有问题，考查的是算法的定义。程序不一定满足有穷性,如死循环、操作系统等，而算法必须有穷。算法代表对问题求解步骤的描述，而程序则是算法在计算机上的特定实现。不少读者认为C也对，它只是算法的必要条件，不能成为算法的定义。
题目：
解答：
(2)简答题
题目：
解答：
题目：
解答：
主要是写递推公式 f(n)-f(n-1)=O(n2)
f(n)=O(n3)
三、章节归纳总结
递归算法：每一次要计算2次，2*2*2….=2n时间复杂度是O(2n)
非递归算法：时间复杂度O(n)，可以从第一次往外去计算，计算n次复杂度即可算出
四、参考
📚课件来源：王道考研
📚课本及题目：《2024数据结构考研复习指导-王道论坛》
下一章：线性表
考研系列-数据结构第二章、线性表-CSDN博客文章浏览阅读1.2k次，点赞46次，收藏9次。本文是408考研付费专栏系列-数据结构线性表章节，本文章详细地总结了线性表的相关知识，其中包括：顺序表、链表（单链表、双链表、循环链表、静态链表等）的细节和重要知识点汇总。考研听课、复习的好帮手。https://blog.csdn.net/hehe_soft_engineer/article/details/139548564
