数据结构-考研复习题第9章查找

第九章n一个记录，其平均查找长度ASL为()【航空航天大学2000一、8（2分】(n-1)/2B.n/2C.(n+1)/2D.N【理工大学1998一、7（2分A（N+1）/2B.N/2C.ND.[（1+N）*N（1）,21997四、3(4A.N+1B.2log2NC.logND.N/2E.Nlog2N下面关于二分查找的叙述正确的是 )【理工大学1996一、3（2分表必须有序，表可以顺序方式，也可以链表方式C.表必须有序，而且只 D.表必须有序，且表只能以顺序方式 【燕山大学2001一、5（2分A.以顺序方式B.以顺序方式,且数据元素有序C.以方式D.以方式,且数据元素有序适用于折半查找的表的方式及元素排列要求为 )【理工大学1997一、（2A．方式，元素无 B．方式，元素有C．顺序方式，元素无 D．顺序方式，元素有 )【理工大学1998一、（2必然 B.必然 C.相 D.不能确当在一个有序的顺序表上查找一个数据时，即可用折半查找，也可用顺序查找，但 必定 C.在大部分情况下要 D.取决于表递增还是递【理工大学1997一、7（2分 【中山大学1998二、（2A. B. C. D. 【中山大学1999一、15A. B. C. 当采用分快查找时数据的组织方式为 )【理工大学1996一7（2分19962(4 A.B.C.D. A.B.C.D.（1（2（3（41999一、2（4】（1（2A.储，也可以链式方式；D.必须以顺序方式，且数据已按递增或递减顺序排好E.必须以链式方式，且数据已按递增或递减的次序排好（3（4：A.nB.n/2C.n*nD.n*n/2E.log2nF.nlog2nG.(n+1)/2ASL（1）找的ASL为(（2）),对静态树表,在情况下,ASL为(（3）),而当它是一棵平衡树时,ASL为(（4）),在平衡树上删除一个结点后可以通过旋转使其平衡,在情况下需(（5）)次旋转。供选择的答案【海运学院1999二、3（5分】（1（2（3（4（5:E. n失败,它们的平均查找长度是((1)),对于查找成功,他们的平均查找长度是((2))供选择的答案:【海运学院1997二、4（3分】相同 B.不同如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用()查A.分快查找B.顺序查找C.折半查找D.20018（2既希望较快的查找又便于线性表动态变化的查找方法是()【北方交通大学2000二、4（2顺序查找B.折半查找C.索引顺序查找D.20004（2】A（10080，C.（100，60，80，90，120，110，130）D.(100，80，60，90，01业大学2001一、4（2】 B.LRC.RLD.下列关于m阶B-树的说法错误的是 【理工大学1997一、9（2分 C.m/2(mm/2+1（m）棵子树D.下面关于m阶B树说法正确的是 )【理工大学1999一、5（2分 B. C. D.下面关于B和B+树的叙述中，不正确的是( )【北方交通大学2001一、17（2B树和B+树都是平衡的多叉树。 B.B树和B+树都可用于文件的索引结 B树和B+树都能有效地支持顺序检索。D. B树和B+树都能有效地支持随机检m阶B-树是一棵 【邮电大学2000二、2（20/8分A.m叉排序树 B.m叉平衡排序树 C.m-1叉平衡排序树 D.m+1叉平衡排序在一棵含有n个关键字的m阶B-树中进行查找，至多读盘 2000一、6（2mn nm 22A.log 1+log2 1+log222mB+树是一棵(（1）)(（2）)个，最少(（3）院计算机1999一、5】A.m路平衡查找 B.m路平衡索引 C.m路Ptrie D.m路键 E.m-F. G.mH.2-

m2

mJ.226在一棵m阶的B+树中,每个非叶结点的儿子数S应满足 ).【交通科技大19963(4m

m

mm

C.1≤S≤

D.H（key）=keyMOD13,1（）个记录【理工大学1997一、4（2分】B. C. D. )【理工大学1998一10（2H（key）=keyMOD17，则需(（1）)个链表。这些链的链首指针构成一个指针数组，数组的下标范围为(（2）)【理大学1999（4（1）B.D.（2）A．0B.10D.1 【理工大学2000一、16（1.5分采用链地址法解决时，查找一个元素的时间是相同采用链地址法解决时，若插入规定总是在链首，则插入任一个元素的时间是用链地址法解决易引起现A. B. C. D.84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决， )【理工大学2001一、15（1.5分】 )B.kC.k+1D.k（k+1）/2【中国科技大学1998二、3（2分【计算所1998二、3（2分 )次探测【西安电子科技大学1998一8（2分】 B. C. )取其值域的每个值A.最大概 B.最小概 C.平均概 D.同等概散列表的地址区间为0-17,散列函数为H(K)=Kmod17。采用线性探测法处理，并将关键字序列26，25，72，38，8，18，59依次到散列表中。（1920（4 C. C. ）产生【邮电大2001一、4（2一定 B.一定不 C.仍可能采用线性探测法处理散列时的，当从哈希表删除一个记录时，不应将这个记录的所1998一、3(120014（1散列函数越复杂越好，因为这样随机性好，概率小.【理工大学1997二、（2哈希函数的选取平方取中法最好。20007（1Hash表的平均查找长度与处理的方法无关。【航空航天大学1997一、9（1负载因子(装填因子)是散列表的一个重要参数，它反映散列表的装满程度【软1999六（1-3（2】19948(22001 (1若散列表的负载因子α<1，则可避免碰撞的产生。【1994查找相同结点的效率折半查找总比顺序查找高。【邮电大学2002一8（1分用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。【软件所1997一、6（1】素个数有关，而且与每块中元素个数有关【交通大学1998一、17】顺序查找法适用于结构为顺序或的线性表。【山东大学2001一、 折半查找法的查找速度一定比顺序查找法快【山东大学2001一、 (1分)19963(320028（1n【海运学院1995一、11（1分）1998一、12（1分【海运学院1997一、10（1分最佳二叉树是AVL树（平衡二叉树【1994在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。【海运学院1999一、8（1】完全二叉树肯定是平衡二叉树。【航空航天大学1996六、5（1分对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。【航空航天大学1995五、4（1】X，其左子树根结点的值小于该结点（X）的值；其右子树根结点的值≥该结点（X）的值,则此二叉树一定是二叉排序树【邮电大学1998一、4（2】nA[1..nn【邮电大学1998一、6（2分N个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。【交通大学1998一、9】【软件所1997设TnT1T【交通大学1998一、11为log2n量级（n为线形表中的结点数目。【中山大学1994一、9 (2分)】B2001（1，17）(1m在m阶B-树中每个结点上至少有2个关键字最多有m个关键字。【 学4(2虽然信息项序列的顺序不一样，但依次生成的二叉排序树却是一样的【长沙铁道学院1998一、 9B592001二、9（1B-树的插入算法中通过结点的向“代替了专门的平衡调整【华南理工大学2001一3（1分【理工大学1997二、3（2分2000四、4（1B+200210（1顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多

20008需做的关键码比较次数为.【北方交通大学2001二、2 【大学2001一、2（2分） 19999（2高度为4的3阶b-树中，最多有 个关键字【合肥工业大学2000三、9（2 【合肥工业大学200010（2 权路径长度WPL的值为 【理工大学1997三、4（2分在一棵m阶B-树中,若在某结点中插入一个新关键字而引起该结点,则此结点中原有的关键字的个数是;若在某结点中删除一个关键字而导致结点合并,则该结 【中国科技大学1998一、5（3分【理工大学2001二、4（3分己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需 次查找成功，47时 成功，查100时，需 成功【理工大学2000二、7（4.5分】哈希表是通过将查找码按选定的(1)和的线性表。哈希方法的关键是_(3)和

(2)(4)尽可能(5)，而且函数运算应尽可能(6)2000六、2（2 （3在哈希函数H（key）=key%p中，p值最好取 【青岛大学2002三、9（2 【青岛大学三、10（2在n个记录的有序顺序表中进行折半查找，最大比较次数是 学1998一、4（3分】有一个2000 分成 块最为理想平均查找长度是(3)【中国矿业大学2000一6（3 20017（2分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成 【工业大学1999一 2执行顺序查找时，方式可以是(1)，二分法查找时，要求线性表(2)，分

(3)，而散列表的查找，要求线性表的方式是(4)【山大学19981(3如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排 。【山东大学1999二、1(４分)】 【山东大学1999二、２(４分)】 【轻工业学院2000一、2（2分查找是非数值程序设计的一个重要技术问题，基本上分成(1)查找，(2)(3)查找。处理哈希的方法有(4)、(5)、(6)和(7)【华北计算机系统工程1999一（5分】 法构造的哈希函数肯定不会发生【重庆大学2000一、3具有N个关键字的B树的查找路径长度不会大 【计算机1999二2在一棵有N个结点的非平衡二叉树中进行查找，平均时间复杂度的上限（即情况 。【西南交通大学2000一、8个关键字散列到大小为n的地址空间中，共计需要做 汉大学2000一、8】 个【大学2000一、6（ 个结点【大学2000一4 2001二、4（3 【燕山大学1998一、7（1 上所有结点的值均大于它的根结点的值【燕山大学1998一、8（2 20013（14%/5） 【北方交通大学2001二、8127阶B-树中每个结点最多有(1)(2)棵子树；65B+树中除根结点外所有结点至少有(3)个关键字；最多有 二、 key：keytype；……；END；ordlisttp=ARRAY[1..n]OFrectype；bisrchr：odlisttp；：keytype：integer； WHILE AND[mid：=(2) IFsuc

(3)

1998二、8(2FUNCBEGINI:=1; A[n+1]=(1) (2) END;19984(4#defineN/*学生人数intuprx(inta[N],intx)/*X{inthead=1,mid,rear=N;do}while((3)

(1)

(2)if(a[head]<x)returnhead-returnhead;【西南交通大学2000一、12success#include<stdio.h> node{ node*left，}node del_leaf(node {node *p,*pf; if(k==p->key)*sn=1;else{_（2）_; (k<p->key)p=p->left;elsep=p->right;}if(*sn&&p->left==NULL&&p->right==null){if(_（3）_if(pf->left==p)pf->left=null;elsepf->right=null; _（4）_; else/*callform:del_leaf(&root,k,&success);*/【大学1999一、2（81.19994（219993（3都经贸大学1997一、2（4】同义词：【山东大学1998二、1 (2分)【山东工业大学2000二、1（2分】叙述B-树定义，主要用途是什么？它和B+树的主要差异是什么？【青岛大学2001五（5B-树【大学1996五、4(3分)1998五、4(4分)2000二、2（2【山东2000三(8平衡二叉树（AVL树）？【大学1996五、3 (3分)1998五、3 门大学1998四、2（5分）】19992(3（ASL1999一、 trie19973（3（1（2（2（4（3（４（4（３（5（２ 1999（15【航空航天大学1996九、2（6分HASH方法的平均查找路长决定于什么？是否与结点个数N有关？处理的方法主【大学2000一、4（4分）20008（52002二、2（5】（1）设计哈希函数；（2）（4）【东学2001六(18分)a、ba[0..9],b[0..9H（key）=key7,处理使用开放定址法，Hi=[H(key)+Di]MOD10,在哈希表a中Di用线性探测再散列bDi{19,24,10,17,15,38,18,40}分别填入哈希表a,b中,并分别计算出它们的平均查找长度ASL【工业大学1998三(8采用哈希函数Ｈ（k）=3*kmod13并用线性探测开放地址法处理，在数列地址空（2）【工业大学2000三(8分)设一组数据为{1,14,27,29,55,68,10,11,23}，现采用的哈希函数是H(key)=key入上述数据后的哈希表【理工大学1996三、3（5分】i14h(x)=2i的序号，若健值的输入顺序为Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec，用拉链法处理，要求（1）构造散列表（2）求出在等概率情况下，查找成功的平均查找长度。【厦门大学2001二、2（24%/3）】MOD13和线性探测再散列处理的方法在地址空间A[0..15]中构造哈希表【燕山大学1999八（14】设哈希函数H（k）=3Kmod11，散列地址空间为0～10（32,13,49,24,38,21,4,12）按下述两种解决的方法构造哈希表（1）线性探测再散ASLunsucc1998（18使用散列函数hashf(x)=xmod11分）（2）（5）（5）【1998五（15分12用线性探测开放定址法处理(散列地址空间为【海运学院1996五（15分设散列函数为H（K）=KMOD13，给定的键值序列为大学1998三、3(6H(k)=Kmod70-6{32,13,49,18,22,38,21}按链地址法处理的办法构造哈希表并查找各关键字要进19995（5】选取哈希函数Ｈ（key）=keymod7,用链地址法解决。试在０-６的散列地址空间2001八(10设散列函数为H(K)=KMOD11,解决的方法为法，试将下列关键字集ASL1997三（10】A[0..11]，H（k）=kmod11，采用线性探测法处20003（5设输入的关键字序列为：22,41,53,33,46,30,13,01,67,Hash：H（key）=key中【航空航天大学1998二（10分】设哈希(Hash)0～17，哈希函数为：H(K)=KMOD16,K线性探测再散列法处理输入关键字序列:(10,24,32,17,31,30,46,47,40,63,49)造出(2)63，1999（10【1996五 a,b,c,d,e五个字符的编码分别为1,2,3,4,5，并设标识符依以下次序出现：（2）再散列法解决。写出上述各关键字在表中位置【大学1998六(10分))，哈希函数为（K）=（关键字中第一个字母在字母表中的序号）MOD7，用线性探测法处理，求构造长度。【西学 (5分)H0(key)=key Hi=(Hi-1+REV(key+1)%11+1)% (1)(8分)试画出插入这8个关键码后的散列表；(2)(5ASL【2000八(13分设一个散列表含hashsize=13个表项，其下标从0到12，采用线性探查法解决。出每一个产生的关键码可能产生多少次。（7分）散列函数采用先将关键码各位数字折叠相加，再用%hashsize表中的办法。请每一个产生的关键字码可能产生多少次【2001五（15】（26,36,41,38,44,15,6,12,06,51,25，a=0.75，H（K）=KMODP，回答下列问题：（3（3计算出等概率情况下查找失败的平均查找长度3分【东学1999一3(9在B-树和B+树中查找关键字时，有什么不同？【东学2002一、 (2分)简要叙述B树(有些中称为B-树)与B+树的区别?【航空航天大学1999六（5分包括nmB【1997五、2（6分（26,25,20,3321,24,45,204,42,38,2931，【1997三（6分已知记录关键字集合为（53,17,19,61,98,75,79,63,46,49）要求散列到地址区间不成功的平均查找长度（设等概率情况【东学1998一、2(10分)】20015（4求从空树开始，每插入一个关键字,画出一个树形【大学1997六(10分)】hmB20006（53B19993（58（1）插入 （2）插入 （3）插入 （4）删除608已知2棵2-3B-树如下（省略外结点【吉林大学1999一、 53533061613（15 828560705BPBDB二、2（20/3）满二叉检索树符合B？B1995（62B+树。19961（6在一棵B+树上一般可进行那两种方式的查找运算【科技大学2001一8（2分【轻工业学院2000八（10分何？为什么？【长沙铁道学院1997三、4(32002八、2（5）【山东大学2001 (7分)概率情况下查找成功的平均查找长度.【邮电大学1999七（10分】2000（10(1)试画出生成之后的二叉排序树 (2)对该二叉排序树作中序遍历，试写出遍历(3)R={11,4,3,2,17,30,191996构造一棵树，并计算出它的带权路径长度WPL（7分ASL（8） (10分)11000363关键字序列哪一个不可能是在二叉排序树中查到的序列？说明原因【东学2002一、 (4找树有几种？（3）AVL？(4)工业大学1997二、3(5(1)A、B、CD，依照不同的输入顺序，共可能组成多少不同的二叉排序6【1995mAVL1995六T1996四、2论的正确性（HT【吉林大1998四1997六(14出每插入一个关键字检索树的形状及调整后的结果1992一、5(3平衡后树中各结点的平衡系数【吉林大学1999AVL2000（10【1994三（10分试画出从一棵空树开始，依上述顺序（从左到右）输入，用高度平衡树的查试画出在上述生成的高度平衡树中，用高度平衡树的删除算法先后删除结点CAN和AQU20005(6调整过程中指针的变化在调整过程中还有两个指针变量p和q可以使用【1997六（10】60--60--·- --·-{Thu,Tue,Wed,Last,Fri,Sat,Mon,Sun,Next}按算法AVL-INSERT构造均，画出构造过程和进行平衡转换的类型1992五（18【西学2000二、4(5分)下，查找成功所需的平均比较次数是多少？【吉林大学20011(3一、8（41997三、3(32551997一、1（4251999三、21996四（10】A[4]外，还有哪几个？2000一、2（1当实现插入排序过程时，可以用折半查找来确定第I个元素I-1个元素中折半查找的平均查找长度是多少？【西安电子科技大学2000计应用 八（10树，并计算其查找成功的平均查找长度【1997七（12分】1999二(101999一、4（2p1=0.2,p2=0.15，p3=0.1，p4=0.03，p5=0.01。而查找它们之间不存在数据的概率q0=0.2,q1=0.15,q2=0.1,q3=0.03,q4=0.02,q5=0.01。dofor repeatq0p1q1 q2 q3p4q4p5分（4）【1999 二（12分检索的时间分别为了高效的检索方法，为什么低效的方法还不放弃？【邮电大学1993一、2(5分)【 三、2（5分试写一个判别给定二叉树是否为二叉排序树的算法1994(12（lc,data,rc叉树是否为二叉排序树的算法【邮电大学1993四（20分】编写判定给定的二叉树是否是二叉排序树的函数【大学2000找和插入时用一个二元组（i,x）来规定一个元素，i，x一种恰当的数据结构来这k个集合的元素，并能高效的实现所要求的查找和插入操4.2,3.6,2.7,5.1,3.9},待插入的元素二元组为(2,11.2)和(1,5.3【工业大学1995七(20分)K1，K2，…，Kn时，用算法建立一棵以LLINK/RLINK表示的二叉查找树BBADCE（A（CE） PASCAL（C）语言将上述算法写为过程形式。【大学1998七(16分)p,fp,pfpp【轻工业学院1998五（12分况【软件所1999七、1（8分】设记录R1,R2,…,Rn按关键字值从小到大顺序在数组r[1..n]中,在r[n+1]处设立k的算法;并画出此查找过程的【交通科技大学1996四、2(16分)t的m-阶Bk,返回记录(pt,i,tag).若tag=0，kptii+1个关键字之间。简化B-树结构如下所示： ofkeytp ptr:array[0..m] ofmblink院