哈尔滨工程大学考研-数据结构-9.doc

一、 选择题1 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) 。A（N+1）/2 B. N/2 C. N D. （1+N）*N /22. 对线性表进行二分查找时，要求线性表必须（ ）A. 以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序3. 具有12个关键字的有序表，折半查找的平均查找长度（ ）。 A. 3.1 B. 4 C. 2.5 D. 54如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性5. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。A. LL B. LR C. RL D. 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. 顺序查找 FUNC seq(a,n,k):integer; BEGIN I:=1; An+1= _(1)_;WHILE aI<>k DO I:=I+1;IF _(2)_ THEN return(I) ELSE return(0); END; 6. 已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。(C语言，PASCAL语言的考生不填） #define N /*学生人数*/int uprx(int aN,int x ) /*函数返回大于等于X分的学生人数*/ int head=1,mid,rear=N; do mid=(head+rear)/2;if(x<=amid) _(1)_ else _(2)_;while(_(3)_);if (ahead<x) return head-1;return head; 四、应用题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, 9083 依次顺序表示在内存中，现用二分法的方法查找字典中是否有元素612，问需要进行多少次比较才能得到结论? 每次选择的比较对象是什么元素?4 设有以下字典wxw, wxz, wzw, wzy, wzz, yyw, yyx, zww, zwx, zwy, zyw, zyx, zyy, zyz试画出等权情况下的最佳二叉排序树。5 画出包含六个成员K1, K2, K3, K4, K5, K6(K1<K2<<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。试画出分别用拉链法和线性探查法解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和失败时的平均查找长度。请问装填因子的值是什么？