数据结构与算法分析-题目_which is the realization of a data type as a softw-CSDN博客

本文链接：https://blog.csdn.net/Zephyr_0/article/details/135501685

数据结构题型

概念
应用题
编程题

四川大学数据结构与算法课程重点题型2023

概念

1-2 chapter

data type:a type together with a collection of operations to manipulate the type.
一个类型以及用于操作该类型的操作集合。
ADT(abstract data type):the realization of a data type as a software component.
数据类型作为软件组件的实现。
data structure:the implementation for an ADT.

problems:a function or a mapping of inputs to outputs.
输入到输出的函数或映射。
algorithms:a recipe for solving a problem whose steps are concrete and unambiguous.
解决问题的方法，步骤具体且明确。
programs:an instantiation of an algorithm in a programming language.
编程语言中算法的实例化。

set:a collection of distinguishable members or elements.
集合：可区分的成员或元素的集合。(不能有重复成员)
recursion:it calls itself to do part of its work.
递归

3 algorithm analysis

asymptotic algorithm analysis:estimate the resource consumption of an algorithm.
渐近算法分析：估计算法的资源消耗。
growth rate:the rate at which the cost of the algorithm grows as the size of its input grows.
算法成本随着其输入大小的增长而增长的速率。
不同速率例子：( $T (n)$ ，n为输入数据数量)

n\T(n)	$\log n$	$n$	$n^2$
16	4	$2^4$	$2^8$
256	8	$2^8$	$2^{16}$
1024	10	$2^{10}$	$2^{20}$

best/worst/average case:for different input, running time/space is short/long/average
upper/lower bound
上/下限：算法的最高/最低增长率，即最糟情况和最好情况
big-Oh/big-Omega/Theta notation:describes an upper bound/lower bound/when the upper and lower are the same
上限符号： $O\left(g(n)\right)$
下限符号： $\varOmega \left(g(n) \right)$
上限下限一样时： $\varTheta \left(g(n) \right)$

4 list

list:a finite, ordered sequence of data items
有限、有序的数据项序列
array-based list：顺序表
(singly/doubly)linked list：单/双链表
(array-based, linked)stack：顺序表/链表栈
(array-based, circular, linked) queue：顺序表/循环/链表队列
FIFO ：先进先出
LIFO ：后进先出

5 binary tree

pre-/in-/post-order traversal：前序/中序/后序遍历 NLR/LNR/LRN
level-order(Breadth-First) traversal：层序遍历（也称为广度优先遍历），按照树的层次，从上到下，从左到右的顺序访问每个节点
full/complete binary tree：没有或有两个子代/除最后一层外全满，最后一次从左到右添加子代
height/depth/level of a binary tree：层数（包括根）/深度（根为0，向下一次+1）/层级：从根节点到该节点的唯一路径上的边的数量。（大小与深度相等）
full binary tree theorem：满二叉树定理：叶子结点数 $n_0$ =内部结点数 $n_2$ +1
BST：二叉查找树，满足leftchild $<$ root $\leqslant$ rightchild
Huffman tree：哈夫曼树
heap：堆，是完全二叉树，分为大顶堆（root大于两个子结点）和小顶堆（root小于两个子结点）
priority queue ：优先队列，由堆实现，先取优