题目内容
（请给出正确答案）
[主观题]
考查实现如134页代码5.20所示的层次遍历算法，设二叉树共含n个节点。a)试证明，只要辅助队列Q的容量不低于[n/2]，就不致于出现中途溢出的问题;b)在规模为n的所有二叉树中，哪些的确会需要如此大容量的辅助队列？c)在层次遍历过程中，若Q中节点的总数的确会达到这么多，则至多可能达到多少次？
答案
查看答案
重要提示：请勿将账号共享给其他人使用，违者账号将被封禁！
查看《购买须知》>>>
请输入或粘贴题目内容
搜题
拍照、语音搜题，请扫码进入小程序
题目内容
（请给出正确答案）
答案
更多“考查实现如134页代码5.20所示的层次遍历算法，设二叉树共含n个节点。a)试证明，只要辅助队列Q的容量不低于[n/2]，就不致于出现中途溢出的问题;b)在规模为n的所有二叉树中，哪些的确会需要如此大…”相关的问题
第2题
第3题
第4题
序列中元素A[i]和A[j]若满足i＜j且A[i]＞A[j]，则称之为一个逆序对(inversion)。考查如教材80页代码3.19所示的插入排序算法List::insertionSort()，试证明：
a)若所有逆序对的间距均不超过k，则运行时间为o(kn);
b)特别地，当k为常数时，插入排序可在线性时间内完成;
c)若共有I个逆序对，则关键码比较的次数不超过o(I);
d)若共有I个逆序对，则运行时间为o(n+I)。
第5题
基本块的DAG如下图所示，若(1)B在该基本块出口处不活跃，(2)B在该基本块出口处活跃的，请分别给出以下代码经过优化后的代码。
第7题
对于几乎有序的向量，如教材代码2.26(60页)和代码2.27(60页)所示的起泡排序算法，都显得效率不足，比如，即便乱序元素仅限于A[0，√n)区间，最坏情况下仍需调用bubble()做Ω(√n)次调用，共做Ω(n)次交换操作和Ω(n3/2)次比较操作，因此累计运行Ω(n3/2)时间。
a)试改进原算法，使之在上述情况下仅需o(n)时间;
b)继续改进，使之在如下情况下仅需o(n)时间：乱序元素仅限于A[n-√n，n)区间;
c)综合以上改进，使之在如下情况下仅需o(n)时间：乱序元素仅限于任意的A[m，m+√n]区间。
第8题
如图x1.4所示，考查缺失右上角(面积为4n-1)的2n×2n棋盘，n≥1。
a)试证明，使用由三个1x1正方形构成、面积为3的L形积木，可以恰好覆盖此类棋盘;
b)试给出一个算法，对于任意n≥1，给出覆盖方案;
c)该算法的时间复杂度是多少？
第9题
