《数据结构》必看知识点

知识点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+

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!