数据结构考研模糊知识点1.2
1、每种数据结构都具有插入、删除和查找三种基本运算,这种说法并不正确。
一般而言,并不是所有的数据结构都有这三种基本运算。
比如多维数组,就没有插入和删除,可以看看,哪怕是二维数组,如果删除其中某个元素,用行还是列来顶替,顶替后,二维数组不就出现缺口了。
再比如说栈和队列,一般并不需要查找(其实原则上说也不能查找,因为逻辑上其访问点被严格限制在线性表的端点了,即使用顺序存储或者链式存储可以在存储结构中查找)
2、抽象操作是外部怎样使用该数据结构;具体实现是内部的事情,外部不需要关心。先设计抽象操作,再完成具体实现。同一种抽象操作可以有多种具体实现。对于同一种抽象操作,可能某一种具体实现简单而另一种具体实现复杂。所以抽象操作的定义与具体实现没有关系。(数据的操作,运算的定义是针对逻辑结构的,指出运算的功能, 运算的实现是针对存储结构的,指出运算的具体操作)
3、数据结构的基本操作的设置的最重要的准则是,实现应用程序与存储结构的独立。
4、存储结构的定义:是指数据结构在计算机中的表示(又称映像),也称物理结构。它包括数据元素的表示以及关系的表示。
5、数据结构的逻辑结构分类1:
- 集合
- 线性结构
- 树状结构
- 图状结构或网状结构
6、数据结构的逻辑结构分类2:
- 线性结构
- 顺序表
- 栈和队列
- 串
- 非线性结构
- 集合
- 树形结构
- 图形结构
- 广义表
7、逻辑结构:是指数据元素之间的逻辑关系,即从逻辑关系上描述数据。
8、算法的5种重要的texing
- 确定性
- 有穷性
- 可行性
- 有0个或者多个输入
- 有一个或者多个输入
9、算法好的标准
- 正确性
- 可读性
- 健壮性
- 效率与低存储量的需求
10、设m,n均为自然数,m可表示为一些不超过n的自然数之和, f(m,n)为这种表示方式的数目。 例:f(5,3)=5,有五种表示方式: 3+2,3+1+1,2+2+1,2+1+1+1,1+1+1+1+1
int m,n; int f(m,n) { if(m==1)return 1; if(n==1)return 1; if(mreturn f(m,m); if(m==n)return 1+f(m,n-1); return f(m,n-1)+f(m-n,n); } main() { int num; num=f(6,4); printf("f(6,4)=%d/n",num); num=f(111,10); printf("f(111,10)=%d/n",num); }
11、计算时间发杂度的时候常用等差数列的和的公式:二分之项数乘以首项与末项的和