![设A的n个元素都不相同,证明下述算法产生的排列A[1],A[2],...,A[n]服从均匀分布:请帮](https://img2.soutiyun.com/ask/2021-02-26/983183777989804.png)
![设A的n个元素都不相同,证明下述算法产生的排列A[1],A[2],...,A[n]服从均匀分布:请帮](https://img2.soutiyun.com/ask/2021-02-26/983183817313053.png)
如果结果不匹配，请 
更多“设A的n个元素都不相同,证明下述算法产生的排列A[1],A[…”相关的问题
第1题
假定序列中n个元素的数值为独立均匀地随机分布，试证明：a)列表的插入排序算法平均需做约n2/4=o（n2)次元素比较操作;b)向量的插入排序算法平均需做约n2/4=o（n2)次元素移动操作;c)序列的插入排序算法过程中平均有expected-o（logn)个元素无需移动。
第2题
设A和B都是有限集合，假定A有m个元素，B有n个元素，说明使下述断为真，m和n之间必须成立的关系。 （a)存在从A到B的单射函数。 （b)存在从A到B的满射函数。 （c)存在A到B的双射函数。
第3题
二叉搜索树可用来对n个元素进行排序。试编写一个排序算法，首先将n个元素a[1..n]插人到一个空的
二叉搜索树中，然后对树进行中序遍历，并将元素按序放人数组a中，为简单起见，假设a中的数据互不相同。试编写一个函数，从一棵二叉搜索树中删除最大元素。要求函数的时间复杂性必须是O(h)，其中h是二叉搜索树的高度。
第4题
（1)设V=＜Z，+，·＞，其中+和·分别表示普通加法和乘法，则V有个不同的子代数，且这些子代数。（2)令T1
(1)设V=＜Z，+，·＞，其中+和·分别表示普通加法和乘法，则V有
个不同的子代数，且这些子代数
。
(2)令T1={2n|n∈Z}，则T1是V的
。
(3)令T2={2n+1|n∈Z}，则T2不是V的子代数，其原因是T2
。
(4)令T3={-1，0，1}，则T3不是V的子代数，其原因是T3
。
供选择的答案
A：①有限;②无限。
B：③含有有限个元素;④含有无限个元素;⑤有的含有有限个元素，有的含有无限个元素。
C：⑥平凡的子代数;⑦非平凡的子代数。
D，E：⑧对加法不封闭;⑨对乘法不封闭;⑩对加法和乘法都不封闭。
第6题
设A为n阶矩阵，下述结论正确的是（)。
A.矩阵A有n个不同的特征根
点击查看答案
B.矩阵A与AT有相同的特征值和特征向量
C.矩阵A的特征向量α1，α2的线性组合c1α1+c2α2仍是A的特征向量
D.矩阵A对应于互不相同特征值的特征向量线性无关
第7题
设 A是n个不相等的正整数构成的集合,其中，n=2k,k为正整数.考虑下述在A中找最大和最小的算法
MaxMin.先将A划分成相等的两个子集A1与A2.用算法.MaxMin递归地在A1与A2中找最大数与最小数.令a1，a2分别表示A1与A2中的最大数,b1与b2分别表示A1与A2中的最小数,那么max(a1，a2)与min(b1，b2)就是所需要的结果.计算对于规模为n的输入，算法Maxmin最坏情况下所做的比较次数.
点击查看答案
第8题
考查实现如134页代码5.20所示的层次遍历算法，设二叉树共含n个节点。a)试证明，只要辅助队列Q的容量不低于[n/2]，就不致于出现中途溢出的问题;b)在规模为n的所有二叉树中，哪些的确会需要如此大容量的辅助队列？c)在层次遍历过程中，若Q中节点的总数的确会达到这么多，则至多可能达到多少次？
第10题
关于典型算法说法错误的是（)。
A.分治法的基本思想是把一个规模为n的问题划分为若干个规模较小、且与原问题相似的子问题,因此和通归问题相同
B.递归法是利用函数直接或间接地调自身来完成某个计算过程
C.迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题
D.回溯法先选择某一种可能情况向前探索,当发现所选用的试探性操作不是最佳选择,需回一步(回溯),重新选择继续进行试探,直到找到问题的解或证明问题无解
