搜索
一、选择题1．对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为()。A．（N+1）/2B.N/2C.ND.[（1+N）*N]/22.对线性表进行二分查找时，要求线性表必须（）A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序3.具有12个关键字的有序表，折半查找的平均查找长度（）。A.3.1B.4C.2.5D.54．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用()查找法。A.分快查找B.顺序查找C.折半查找D.基于属性5.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作()型调整以使其平衡。A.LLB.LRC.RLD.RR6．下列关于m阶B-树的说法错误的是()。A．根结点至多有m棵子树B．所有叶子都在同一层次上C．非叶结点至少有m/2(m为偶数)或m/2+1（m为奇数）棵子树D．根结点中的数据是有序的7.m阶B-树是一棵()。A.m叉排序树B.m叉平衡排序树C.m-1叉平衡排序树D.m+1叉平衡排序树二、判断题1．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。2．在散列检索中，“比较”操作一般也是不可避免的。3．查找相同结点的效率折半查找总比顺序查找高。4．完全二叉树肯定是平衡二叉树。5.设T为一棵平衡树，在其中插入一个结点n，然后立即删除该结点后得到T1，则T与T1必定相同。6．在9阶B-树中，除叶子以外的任意结点的分支数介于5和9之间。7.二叉排序树删除一个结点后，仍是二叉排序树。三、填空题1.高度为4的3阶b-树中，最多有__________个关键字。2.给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为__________，带权路径长度WPL的值为__________。3.己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需__________次查找成功，47时__________成功，查100时，需__________次才能确定不成功。4．在哈希函数H（key）=key%p中，p值最好取__________。5.顺序查找FUNCseq(a,n,k):integer;BEGINI:=1;A[n+1]=__(1)____;WHILEa[I]kDOI:=I+1;IF__(2)___THENreturn(I)ELSEreturn(0);END;6.已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。(C语言，PASCAL语言的考生不填）#defineN/*学生人数*/intuprx(inta[N],intx)/*函数返回大于等于X分的学生人数*/{inthead=1,mid,rear=N;do{mid=(head+rear)/2;if(x=a[mid])__(1)__else__(2)__;}while(__(3)__);if(a[head]x)returnhead-1;returnhead;}四、应用题1．在包含n个元素的字典里进行顺序查找，若查找第i个元素的概率为pi，pi如下分布∶p1=1/2，p2=1/4，…，pn-1=1/(2n-1)，pn=1/2n求成功的查找的平均比较次数。2．设某字典组成如下∶D={016,087,154,170,275,426,503,509,512,612,653,677,703,765,897,908}3．依次顺序表示在内存中，现用二分法的方法查找字典中是否有元素612，问需要进行多少次比较才能得到结论?每次选择的比较对象是什么元素?4．设有以下字典∶{wxw,wxz,wzw,wzy,wzz,yyw,yyx,zww,zwx,zwy,zyw,zyx,zyy,zyz}试画出等权情况下的最佳二叉排序树。5．画出包含六个成员∶K1,K2,K3,K4,K5,K6(K1K2…K6)，权分别为p1=3,p2=p3=p4=p5=p6=1，q1=q2=q3=q4=q5=q6=1的最佳二叉排序树。6．从一棵空AVL树开始，将关键码xal,wan,wil,zol,yo,xul,yum,wen,wim,zi,yon,xem,xul,zom逐个插入，画出每插入一个新关键码后得到的AVL树。7．已知元素个数为12的字典，其元素集合为∶{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}(1)试按元素的次序依次插入一棵初始时为空的二叉排序树，请画出插入完成之后的二叉排序树，并求其在等概率情况下查找成功的平均查找长度。(2)按元素顺序构造一棵AVL树，并求其在等概率情况下查找成功的平均查找长度。8．将（for，case，while，class，protected，virtual，public，private，do，template，const，if，int）中的关键字依次插入初态为空的二叉排序树中，请画出所得到的树T。然后画出删去for之后的二叉排序树T'，若再将for插入T'中得到的二叉排序树T是否与T相同？最后给出T的前序、中序和后序序列。9．设散列表长度为11，散列函数h(x)=x%11，给定的关键字序列为：1，13，12，34，38，33，27，22。试画出分别用拉链法和线性探查法解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和失败时的平均查找长度。请问装填因子的值是什么？