数据结构面试刷题

时间:2024-04-12 12:22:33

树的计算题技巧:

1.在二叉树的第i层至多有2^i - 1 个节点

2.深度为k的二叉树至多有2^k-1 个节点

3. 设度为0,1,2节点为n0,n1,n2,总结点是n,则n0=n2+1;(根据4.5条推出)

4.n0 + n1 + n2 = n

5.n = 分支线数 + 1 = 2*n2 + 1*n1 + 0*n0分支数就是两点的连线的数目,n个点两两连线有n-1条线)

满二叉树:最后一层节点有2^i - 1个节点,就是满了

完全二叉树:对满二叉树进行编号与对完全二叉树进行编号顺序位置完全一样,唯一不同就是完全二叉树最后一层叶子节点比满少

1.节点计算题


一个4叉树,度为4的结点个数为6,度为3的节点个数是10,度为2的节点个数是5,叶子节点个数为()

虽然不是二叉树,但是延伸的道理都是一样的。

设度为1的节点个数为x,度为0的节点为y。该树的分叉数为4*6+3*10+2*5+x*1
又因为节点数=分叉数+1;
节点数:6+10+5+x+y= 4*6+3*10+2*5+x*1+1
解得:y=44

某棵完全二叉树上有699个节点,则该二叉树的叶子节点数为()

完全二叉树,n1的个数在1和0之前选择我们用分支数的公式

2*n2 + n1 + 1 = 699,1移过去后698是复数,很明显如果n1是1,那么n2肯定不是整数,所以n1只能是0,然后算出n2是349;然后根据公式2,n2 = n0 - 1算出n0 = 350

一个包含 n 个节点的四叉树,每个节点都有四个指向孩子节点的指针,这 4n 个指针中有多少个空指针?

答案:n个节点不管多少叉树,肯定有n-1条连线(边),意味着有n-1个非空指针

所以空指针就是4n-(n-1) = 3n+1

2.哈弗曼树

官方定义:给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树,则其带权路径长度是()。

构造方法是每次取最小的两个数, 合并成一个数, 然后循环这种做法, 直到只剩一个点为止。构造的树是 
30 
17 13 
8 9 6 7 
4 5

3.森林与树

树转二叉树

数据结构面试刷题

数据结构面试刷题

森林转二叉树
设森林F中有三棵树,第一,第二,第三棵树的结点个数分别为M1,M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是(     )

答案:M2+M3

数据结构面试刷题

 


图的计算技巧

1.n个顶点的无向完全图有n*(n-1)/2条边

2.n个顶点的有向完全图有n*(n-1)条边

3.无向图边数是各顶点度数和一半

完全图:任意两个顶点都存在边

1.图与边

设某强连通图中有 n 个顶点,则该强连通图中 至少有()条边。

答案:n条

1)强连通图的定义:

在有向图G中,如果对于每一对vi、vj,vi≠vj,从vi到vj和从vj到vi都存在路径,则称G是强连通图。

2)分析:

可知当n个节点的图构成一个环,任意两点之间存在着回路,于是最小的边数为n;最大边数为n(n-1);

2.拓扑

在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出现的是()。
A.G中有弧<Vi,Vj>
B.G中有一条从Vi到Vj的路径
C.G中没有弧<Vi,Vj>
D.G中有一条从Vj到Vi的路径

答案:D

拓扑排序定义:将有向图中的顶点以线性方式进行排序。即对于任何连接自顶点u到顶点v的有向边u->v,在最后的排序结果中,顶点u总是在顶点v的前面

比如下面的图的拓扑结构是V1,V3,V4,V6,V2,V5,V7

数据结构面试刷题

不是所有图都能被拓扑,拓扑排序的充要条件就是它是一个有向无环图

https://blog.csdn.net/jinzhao1993/article/details/51778468