将关键码DEC,FEB,NOV,OCT,JLIL,SEP,AUG,APR,MAR,MAY,JUN,JAN依次插人到一棵初始为空的AVL树中
已知如下所示长度为12的表:(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)
①试按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成之后的二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。
②若对表中元素先进行排序构成有序表,求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
③按表中元素顺序构造一棵平衡二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。
利用CEMENT.RAW中的数据。
(i)将水泥价格月增长率(gprc)作为供给数量增长率(gce)函数,写出静态供给函数是
其中,gprcpet(汽油价格上涨率)被假定为外生变量,而feb,···,dec为月度虚拟变量。你预期a1和β1的符号是什么?用OLS估计这个方程。供给函数向上倾斜吗?
(ii)变量gdefs是美国真实国防支出的月增长率。gdefs要作为gcem的一个好的工具变量,你需要对它做什么假定?检验gcem是否与gdefs偏相关。(不用担心约简型中可能的序列相关。)你能用gdefs作为估计供给函数中的一个Ⅳ吗?
(iii)谢伊(Shea,1993)认为建住宅楼的产出增长率(gres)和非住宅楼的产出增长率(gnon)是gcem的有效工具变量。其思想是,存在一些应该与供给误差项u,大致无关的需求移动因子。检验gcem是否与gres和gnon偏相关;同样不用担心约简型中的序列相关。
(iv)利用gres和gnon作为gcem的工具变量估计供给函数。你对水泥的静态供给函数得到什么结论?[动态供给函数显然是向上倾斜的;参见Shea(1993)。]
插入初始为空的二叉搜索树中,请画出所得到的树T。然后画出删除for之后的二叉搜索树T',若再将for插人T'中得到的二叉搜索树T''是否与T'相同?
A.She seldom reads books from cover to cover.
B.She is interested in reading novels.
C.She read unly part ofthe book.
D.Shewaseagertoknowwhatthebookwasabout
A.To look for a part-time job here.
B.To borrow "War and Remembrance."
C.To borrow a novel for some light reading.
D.To learn to use the library as efficiently as possible.
为提高空间利用率,可将内部节点的分支数下限从[m/2]提高至[2m/3]。于是,一旦节点v发生上溢且无法通过旋转完成修复,即可将v与其(已经饱和的某一)兄弟合并,再将合并节点等分为三个节点,采用这一策略之后,即得到了B-树的一个变种,称作B'-树(B'-tree)。
当然,实际上不必真地先合二为一,再一分为三。可通过更为快捷的方式,达到同样的效果:从来自原先两个节点及其父节点的共计m+(m-1)+1=2m个关键码中,取出两个上交给父节点,其余2m-2个则尽可能均衡地分摊给三个新节点。
a)按照上述思路,实现B'-树的关键码插入算法;
b)与B-树相比,B'-树的关键码删除算法又有何不同?
设散列表容量为11且初始为空,采用除余法确定散列地址,采用单向平方试探法排解冲突,采用懒惰策略实现删除操作。
a)若通过put()接口将关键码(2012,10,120,175,190,230)依次插入中,试给出此时各桶单元的内容;
b)若再执行remove(2012),试给出此时各桶单元的内容;
c)若继续执行get(2012),会出现什么问题?为什么?
d)为避免此类问题的出现,可以采取什么措施?试给出至少两种方案。