题目内容
(请给出正确答案)
[主观题]
设a[0:n-1]是有n个元素的数组,k(0≤k≤n-1)是一个非负整数.试设计一个算法将子数组a[0:k-1]与a[k:n-1]换位.要求:算法在最坏情况下耗时O(n),且只用到O(1)的辅助空间.
查看答案
如果结果不匹配,请 联系老师 获取答案
设α=(a1,a2,...,an)T,a1≠0,A=ααT。
(1)证明λ=0是A的n-1重特征值;
(2)求A的非零特征值及n个线性无关的特征向量。
A.A的n个特征向量两两正交
B.A的n个特征向量构成单位正交向量组
C.对A的k重特征值λ0,有r(λ0E-A)=n-k
D.对A的k重特征值λ0,有r(λ0E-A)=k
a)试按照以上思路,实现一个排序算法:
b)你的这一算法,时间和空间复杂度各是多少?
c)改进你的算法,使之能够在O(n+M)时间内对来自[0,M)范围内的n个整数进行排序,且使用的辅助空间不超过O(M)。
考查任何一棵高度为h的二叉树T,设其中深度为k的叶节点有nk个,0≤k≤h。
a)试证明:
b)以上不等式取等号的充要条件是什么?