请输入或粘贴题目内容
搜题
拍照、语音搜题，请扫码下载APP
题目内容
（请给出正确答案）
证明下列关系：
(1)设T是具有n个内结点的扩充二叉树，I是它的内路径长度，E是它的外路径长度。试利用归纳法证明E=1+2n，n≥1.
(2)利用(1)的结果，试说明：成功搜索的平均搜索长度Sn与不成功搜索的平均搜索长度U.之间的关系可用公式Sn=(1+1/n)Un-1，n≥1表示。
答案
更多“证明下列关系：(1)设T是具有n个内结点的扩充二叉树，I是它的内路径长度，E是它的外路径长度。试利”相关的问题
第1题
设二叉树中所有非叶结点的左、右子树都不为空。试证明对此类二叉树满足：
(1)含有n个叶结点的二叉树中共有2n-1个结点。
(2)
，其中，n为叶结点个数，1.表示第i个叶结点所在的层次(设根结点所在的层次为1).
第2题
设G为n个结点的无向简单图,若x(G)≥k,则称G是k-连通图,k为非负整数.证明以下结论:
(1)当
时,正明G连通.
(2)当
时,证明G是k-连通图.
第3题
设α=(a1，a2，...，an)T，a1≠0，A=ααT。
(1)证明λ=0是A的n-1重特征值;
(2)求A的非零特征值及n个线性无关的特征向量。
第4题
设单链表中结点的结构为：
在一个具有n个结点的单链表中插人一个新结点，并可以不保持原有顺序的算法的时间复杂度是().
A、O(1)
B、O(n)
C、O(n2)
D、O(nlog2n)
第6题
设η0是线性方程组的一个解，η1，η2，...，ηt是它的导出方程组的一个基础解系，令
证明：线性方程组的任一个解γ，都可表成
其中u1+u2+...+ut+1=1。
第9题
设A是n个元素的集合。
(a)证明A上有2n个一元关系。
(b)证明A上有
个二元关系。
(c)A上有多少个三元关系呢？
第10题
设单链表中结点的结构为：
从一个具有n个结点的有序单链表中查找其值等于x的结点时，在查找成功的情况下，平均需要比较()个结点。
A、n
B、n/2
C、(n-1)/2
D、(n+1)/2
第11题
A、d<12n/(k-n)
B、d≥12n/(k-n)
C、d<12n/(k+n)
D、d>12n/(k+n)
