前端之家收集整理的这篇文章主要介绍了
《数据结构》必看知识点,
前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
知识点1:
数组A[N][M],A[0][0]是数组中地址最小的元素。如果A[0][0]存放地址为n,那么A[i][j]存放的地址就是:
n+i*M*sizeof(T)+j*sizeof(T),sizeof(T)是每个元素所占的存储单元。
另一种表述:已知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是Loc(A[0][0]),则A[i][j]的地址是 LOC (A[0][0])+(n*i+j)*k
1.已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是( )。
解答:1000+((18-10)*10+9-5)*2=1168
2.二维数组A[10..20][5..10]采用行序为主方式存储,每个元素占4个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的地址是1208。
解答:行序存储,A[18][9]=A[10][5]+(8*6+4)*4=1000+208=1208;
知识点2:
1.设某棵二叉树中度数为0的结点数为N0,度数为1的结点数为N1,则该二叉树中共有 2 N0+ N1 个空指针域。
2.
设一棵完全二叉树中有500个结点,则该二叉树的深度为 9 ;若用二叉链表作为该完全二叉树的存储结构,则共有 501 个空指针域。
3.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至 少为()。
2*(h-1)+1
4.假定在一棵二叉树中,双分支结点数为15,单分支结点数为30,则叶子结点数为(C) 个。
A. 45 B.15 C.16 D.31
5.按照二叉树的定义,具有3个结点的二叉树有(D)种。
A.2 B.3 C.4 D.5
n个节点的二叉树种数:C(2n,n)/(n+1)
n个节点的二叉树种数=前序序列均为12..n的二叉树所能得到的中序序列的数目=数列12...n按不同顺序进栈和出栈所得到的排列数目:
C(2n,n)-C(2n,n-1)=C(2n,n)/(n+1)
知识点3:字符串
知识点4:赫夫曼树:n个叶子节点,共有2n-1个节点,存储在大小为2n-1的数组中
一般方法:使用归纳方法,节点个数n=1,2,3时进行归纳
知识点5:树<----->二叉树的转换
节点数n=3^0+3^1+3^2+3^3=40
通用公式:3^0+3^1+...+3^(h-1)=(1-3^h)/(1-3)
等比数列:
求和公式:Sn=n×a1 (q=1) Sn=a1(1-q^n)/(1-q) (q为公比,n为项数)
知识点6:后缀表达式
中缀表达式(A+B)*D+E/(F+A*D)+C的后缀形式是( A )。
A.AB+D*EFAD*+/C+ B.ABD*+EFAD*+/C+ C.ABDEFADC+#+/+*+ D.AB+D*E/FA+*DC+