考研系列-数据结构第一章、绪论(基本术语、时间复杂度)

本文主要是介绍考研系列-数据结构第一章、绪论(基本术语、时间复杂度),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一、数据结构的基本概念

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


这篇关于考研系列-数据结构第一章、绪论(基本术语、时间复杂度)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1050584

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

SpringBoot整合MybatisPlus的基本应用指南

《SpringBoot整合MybatisPlus的基本应用指南》MyBatis-Plus,简称MP,是一个MyBatis的增强工具,在MyBatis的基础上只做增强不做改变,下面小编就来和大家介绍一下... 目录一、MyBATisPlus简介二、SpringBoot整合MybatisPlus1、创建数据库和

Python如何获取域名的SSL证书信息和到期时间

《Python如何获取域名的SSL证书信息和到期时间》在当今互联网时代,SSL证书的重要性不言而喻,它不仅为用户提供了安全的连接,还能提高网站的搜索引擎排名,那我们怎么才能通过Python获取域名的S... 目录了解SSL证书的基本概念使用python库来抓取SSL证书信息安装必要的库编写获取SSL证书信息

MySQL 日期时间格式化函数 DATE_FORMAT() 的使用示例详解

《MySQL日期时间格式化函数DATE_FORMAT()的使用示例详解》`DATE_FORMAT()`是MySQL中用于格式化日期时间的函数,本文详细介绍了其语法、格式化字符串的含义以及常见日期... 目录一、DATE_FORMAT()语法二、格式化字符串详解三、常见日期时间格式组合四、业务场景五、总结一、

Python中多线程和多进程的基本用法详解

《Python中多线程和多进程的基本用法详解》这篇文章介绍了Python中多线程和多进程的相关知识,包括并发编程的优势,多线程和多进程的概念、适用场景、示例代码,线程池和进程池的使用,以及如何选择合适... 目录引言一、并发编程的主要优势二、python的多线程(Threading)1. 什么是多线程?2.

如何利用Java获取当天的开始和结束时间

《如何利用Java获取当天的开始和结束时间》:本文主要介绍如何使用Java8的LocalDate和LocalDateTime类获取指定日期的开始和结束时间,展示了如何通过这些类进行日期和时间的处... 目录前言1. Java日期时间API概述2. 获取当天的开始和结束时间代码解析运行结果3. 总结前言在J

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

MyBatis-Flex BaseMapper的接口基本用法小结

《MyBatis-FlexBaseMapper的接口基本用法小结》本文主要介绍了MyBatis-FlexBaseMapper的接口基本用法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具... 目录MyBATis-Flex简单介绍特性基础方法INSERT① insert② insertSelec