证明下列关系:(1)设T是具有n个内结点的扩充二叉树,I是它的内路径长度,E是它的外路径长度。试利
证明下列关系:
(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是它的外路径长度。试利用归纳法证明E=1+2n,n≥1.
(2)利用(1)的结果,试说明:成功搜索的平均搜索长度Sn与不成功搜索的平均搜索长度U.之间的关系可用公式Sn=(1+1/n)Un-1,n≥1表示。
第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)