数据结构与算法基础

2023-12-25 13:42:34

数组

image-20230810191230348

稀疏矩阵

image-20230811093747789

题目

image-20230811094321366

代入法选A

数据结构的定义

image-20230811094533131

线性表

image-20230811101135160

image-20230811101222098

image-20230811101303911

顺序存储和链式存储的对比

image-20230811103552891

队列与栈

image-20230811105423817

题目

image-20230811105453824

答案选:D

广义表

image-20230811105551183

树与二叉树

image-20230811111502896

image-20230814085856034

二叉树遍历

image-20230814094850100

图中前序遍历结果是?

1,2,4,5,7,8,3,6

图中中序遍历结果是?

4,7,8,5,2,1,3,6

图中后序遍历结果是?

4,8,7,5,2,6,3,1

图中层次遍历结果是?

1,2,3,4,5,6,7,8

反向构造二叉树

image-20230814100253967

需要中序搭配前序和后序遍历才能反向的构造出二叉树

树转二叉树

image-20230814100929656

  • 孩子结点变为左子树结点

  • 兄弟结点变为右孩子结点

查找二叉树

image-20230814102336883

最优二叉树(哈夫曼树)

image-20230814102718525

线索二叉树

image-20230814104035782

平衡二叉树

图的基本概念级存储

image-20230814104619566

  • 在无向图中,若每对顶点之间都有一条边相连,则称该图为完全图( completegraph )。

  • 在有向图中若每对顶点之间都有二条有向边相互连接,则称该图为完全图。

邻接矩阵

image-20230814105144424

邻接表

image-20230814105219947

树的遍历

image-20230814112637855

拓扑排序

image-20230814112719651

最小生成树

image-20230814135549856

算法

算法的特性

  • 有穷性:执行有穷步之后结束
  • 确定性:算法中每一条指令都必须有确切的含义,不能含糊不清。
  • 一个算法有零个或多个输入,以刻画运算对象的初始情况,所谓零个输入是指算法本身给定了初始条件。
  • 一个算法有一个或多个输出。没有输出的算法毫无意义。
  • 有效性:算法的每个步骤都能有效执行并能得到确定的结果。例如 a =0, b / a 就无效

算法的复杂度

image-20230814151718340

查找

顺序查找

image-20230814152245944

二分查找

image-20230814152306575

image-20230814153921036

折半查找在查找成功时关键字的比较次数最多为 log ? 2 n \log_2 n log2?n + 1 次。折半查找的时间复杂度为伏O( log ? 2 n \log_2 n log2?n) 。

散列表

image-20230814154816073

排序

image-20230814155427733

插入排序

image-20230814155818476

希尔排序

image-20230814160416070

直接选择排序

image-20230814170746130

堆排序

image-20230815092353022

image-20230815092733663

image-20230815094443957

image-20230815094518209

冒泡排序

image-20230815102626272

快速排序法

image-20230815103925893

归并排序法

image-20230815104017820

基数排序

image-20230815104632372

复杂度

image-20230815104926710

来源于软件设计师学习视频(仅供学习参考,附历年真题及详解)_哔哩哔哩_bilibili的网课记

文章来源:https://blog.csdn.net/iloveyouwh/article/details/135197089
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。