1、数据结构习题精编查找数据结构习题精编：查找一、选择题1对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为 A(n-1)/2 Bn/2 C(n+1)/2 Dn2若有序表的关键字序列为（b，c，d，e，f，g，q，r，s，t），则在折半查找关键字b的过程中，先后进行比较的关键字依次为 Af、c、b Bf、d、b Cg、c、b Dg、d、b3在关键字序列（12，23，34，45，56，67，78，89，91）中折半查找关键字为45、89和12的元素时，所需进行的比较次数分别为 A3，3，4 B3，4，4 C4，3，3 D4，4，34已知一个长度为16 的顺序表L，其元素
2、按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多的是 A4 B5 C6 D75对具有12个关键字的有序表进行折半查找，在查找概率相等的情况下，查找成功的平均查找长度为 A2.5 B3.1 C4 D56某索引顺序表共有元素395个，平均分成5块。若先对索引表采用顺序查找，再对块中元素进行顺序查找，则在等概率情况下，分块查找成功的平均查找长度是 A43 B79 C86 D1987下列关于静态查找表的说法中，正确的是 A用数组和单链表表示的有序表均可使用折半查找方法来提高查找速度。 B就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。 C在索引顺序表中，实现分块查找
3、，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。 D有n个数存放在一维数组A1.n中，采用顺序查找，在等概率查找的情况下，这n个数的排列有序或无序时，其平均查找长度相同。8若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过 An/2 B(n+1)/2 Cn Dn+19当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为 A左子树的叶子结点 B左子树的分支结点 C右子树的叶子结点 D右子树的分支结点10已知8个元素（34，76，45，18，26，54，92，65），按照依
4、次插入结点的方法生成一棵二叉排序树，则该树的深度为 A4 B5 C6 D711由同一关键字集合构造的各棵二叉排序树 A其形态均相同，平均查找长度也都相同 B其形态均相同，但平均查找长度不一定相同 C其形态不一定相同，但平均查找长度相同 D其形态不一定相同，平均查找长度也不一定相同12已知二叉排序树T，要输出其结点的有序序列，则采用的遍历方法是 A先序遍历 B中序遍历 C后序遍历 D层次遍历13已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于 A1.0 B2.9 C3.4 D5.514分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不
5、同的是 A（100，60，80，90，120，110，130） B（100，80，60，90，120，130，110） C（100，80，90，60，120，110，130） D（100，120，110，130，80，60，90）15对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是 A12、25、71、68、33、34 B21、89、77、29、36、38 C92、20、91、34、88、35 D95、22、91、24、94、7116下列关于二叉排序树的说法中，正确的是 A二叉排序树删除一个叶子结点后，仍是二叉排序树。 B在二叉排序树中插入一个新结点，总是插入到叶结点的下面。
6、C在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同。 D某二叉树中除叶结点外，任一结点X，其左子树根结点的值小于该结点的值；其右子树根结点的值大于该结点的值，则此二叉树一定是二叉排序树。17在一棵平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，为使其平衡应做 ALL型调整 BLR型调整 CRL型调整 DRR型调整18在下图1所示的平衡二叉树中插入关键字48 后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37 所在结点的左、右子结点中保存的关键字分别是图1 平衡二叉树 A13，48 B2
7、4，48 C24，53 D24，9019若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为 A10 B20 C32 D3320下列叙述中，不符合m 阶B 树定义要求的是 A根结点最多有m 棵子树 B所有叶结点都在同一层上 C叶结点之间通过指针链接 D各结点内关键字均升序或降序排列21既希望较快的查找又便于线性表动态变化的查找方法是 A顺序查找 B折半查找 C索引顺序查找 D哈希法查找22下列关于哈希查找的说法中，正确的是 A哈希函数的选取以除留余数法最好。 BHash表的平均查找长度与处理冲突的方法无关。 C若哈希表的装填因子1，则可避免冲突的产生。 D在哈希查
8、找中，“比较”操作一般也是不可避免的。23对于哈希函数H(key)=key%13，被称为同义词的关键字是 A15和44 B23和39 C25和51 D35和4124设有一组关键字（19，14，23，1，6，20，4，27，5，11，10，9），用哈希函数H(key)=key%13构造哈希表，用拉链法解决冲突，哈希地址为1的链中记录个数为 A1 B2 C3 D425假定有k个关键字互为同义词，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行的探测次数为 Ak-1 Bk Ck+1 Dk*(k+1)/2二、填空题1顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最少为_次，最多
9、为_次；当使用监视哨时，若查找失败，则比较关键字的次数为_。2己知有序表为（8，11，12，18，24，35，42，47，50，62，83，90，115，134），当用折半查找法查找90时，需_次查找成功，所比较的元素依次为_。查60时，需_次才能确定不成功，所比较的元素依次为_。3在有序表A1.20中，按折半查找方法进行查找，查找长度为5的元素个数是_。4有一个包含2000个元素的表，欲采用索引顺序查找方法进行分块查找，则每块的理想长度是_，分成_块最为理想，平均查找长度是_。5用分块查找法对一个有2000个元素的表进行查找，若每块长度为25，用顺序查找确定块时，平均查找长度为_；用折半查找
10、确定块时，平均查找长度为_。6如果按关键字值递增的顺序依次将关键字插入到二叉排序树中，则对这样的二叉排序树查找时，平均比较次数为_。7如果关键字按值有序排列，而后用折半查找法依次查找这些关键字，并把查找中遇到的在二叉树中没有出现的关键字依次插入到二叉排序树中，则对这样的二叉排序树查找时，平均比较次数为_。8已知一棵二叉排序树（结点值大小按字母顺序）的先序遍历序列为EBACDFHG，则此二叉排序树的后序遍历序列为_。9深度为8的平衡二叉树的结点数至少有_个。设以Nm表示深度为m的平衡二叉树中含有的最少结点数，则有N0=0，N1 =1，N2 =_，N3=_，N4=_，Nm = Nm-1 +_（m2
11、）。10深度为4的3阶B-树中，至少有_个关键字，最多有_个关键字。11含9个叶子结点的3阶B-树中至少有_个非终端结点，此时，树的深度为_，树中每个非终端结点均含_棵子树；含10个叶子结点的3阶B-树中至多有_个非终端结点，此时树的深度为_，除叶子结点所在层外，其它各层非终端结点数依次为_。12在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_。13127阶B-树中每个结点最多有_个关键字；除根结点外所有非终端结点至少有_棵子树。14动态查找表和静态查找表的重要区别在于
12、前者包含有_和_运算，而后者不包含这两种运算。15某哈希表的地址区间为017，哈希函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到哈希表中。元素59存放在哈希表中的地址是_，存放元素59需要探测的次数是_。三、解答题1用折半查找法对一个长度为10的有序表进行查找，填写查找每一元素需要的比较次数。元素下标12345678910比较次数2图2中二叉排序树的各结点的值为19，标出各结点的值。图2 二叉排序树3从空树起，依次插入关键字（37，50，42，18，48，12，56，30，23），构造一棵二叉排序树。（1）画出该二叉排序
13、树。（2）对该二叉排序树作中序遍历，写出遍历序列。（3）求在等概率情况下，查找成功的平均查找长度。（4）画出从（1）所得树中删除关键字为37的结点之后的二叉排序树。4由于元素的插入先后次序不同，所构成的二叉排序树可能有多种形态。请画出4棵含1、2、3、4、5、6六个元素且以元素1为根、深度为4的二叉排序树。5给定关键字序列（15，11，8，20，14，13，24，22，23），试画出从一棵初始时为空的二叉排序树开始，依次插入该序列中的关键字所构成的平衡二叉树，并为每一次的平衡处理指明旋转类型。6深度为h的m阶B树至少有多少个结点？ 7设有一棵空的阶B-树，依次插入关键字30、20、10、40、
14、80、58、47、50、29、22、56、98、99，请画出该B-树。8对如图3所示的3阶B-树，依次执行下列操作，画出各步操作的结果。（1）插入90 ，（2）插入25，（3）插入45，（4）删除60，（5）删除80。图3 3阶B-树9将关键字序列（7、8、30、11、18、9、14）散列存储到哈希表中，哈希表的存储空间是一个下标从0 开始的一个一维数组，哈希函数为：H（key）=（key * 3） MOD T（T为表长），处理冲突采用线性探测再散列法，要求装填因子为0.7。（1）请画出所构造的哈希表。（2）分别计算等概率情况下，查找成功和查找不成功的平均查找长度。10设一组关键字序列为1，1
15、0，11，14，20，23，27，29，55，68 ，采用的哈希函数是H（key）= key MOD 13，冲突用链地址法解决。（1）试画出插入上述关键字序列后的哈希表。（2）求出在等概率情况下查找成功时的平均查找长度。四、分析题1阅读下列函数，并回答问题。void Fun741_1(int H) int k,m,p; cout请输入一个正整数序列，输入 0 表示结束：k; while (k!=0) m=13; p=k % m; while(Hp!=0 & k!=Hp) p=(p+1) % m; if (p=k % m ) break; if (Hp=0) Hp=k; cink; void F
16、un741_2(int H,int m) int cnt1=0,cnt2=0,i; for (i=0;im;i+) if (Hi!=0) cnt2+; cnt1=cnt1+(i-Hi%m+m)%m +1; coutcnt1/cnt2keykeyk) _; / （3） else break; if (p!=NULL) return _; / （4） else return _; / （5）3已知不带头结点的单链表中的关键字为正整数，为提高查找效率，将它改建为采用拉链法处理冲突的哈希表。设哈希表的长度为m，哈希函数为Hash(key)=key%m。链表的类型定义如下：typedef int Key
17、Type;struct LNode KeyType key; LNode *next;typedef LNode* LinkList;请在下面函数中的空缺处填入适当的内容，将程序补充完整。void ReCreate(LinkList &L, LinkList H, int m)/ 由不带头结点的单链表L生成哈希表H，哈希表生成之后原链表不再存在 int i; LinkList p,q,f,r; for (i=0;inext; i=p-key % m ; f=NULL; r=Hi; while(r!=NULL & r-keykey) f=r ; r=r-next; / 查找插入位置 if (r!
18、=NULL & r-key=p-key) delete p; / 当前p所指结点在Hash表中已存在，直接释放其存储空间 else if (f!=NULL) p-next= _; / （3） _; / （4） else p-next=_; / （5） _; / （6） _ ; / （7） L=_; / （8）4阅读下列函数，并回答问题。void CreateHashList(LinkList H, int m, int a,int n)/ 用链地址法解决冲突，将数组a中的n个整数作为关键字构造哈希表，/ 哈希函数用H（key）=key % m int i,j; LinkList p; for
19、(i=0; im; i+) Hi =NULL; / 初始化 for (i=0; ikey=ai; p-next=Hj; Hj=p; （1）设有数据定义：LinkList H7; int a12=19,14,23,1,68,20,84,27,55,11,10,79; 试给出执行函数调用CreateHashList(H,7,a,12);后，数组H的情况。（2）对上问所构造的哈希表进行查找，查找成功时的平均查找长度是多少？（3）上面给出的函数不是很严谨，没有考虑数组a中的n个元素可能重复，而哈希表中不应该存在重复的元素。你觉得应怎样解决这个问题？请给出修改后的程序。5设二叉排序树采用二叉链表存储。下
20、面的函数DeleteAllX(bst,x)的功能是在二叉排序树bst中，删除所有关键字值小于等于x的结点。其基本思想是：利用二叉排序树的性质，从根结点开始查找，若根结点的值小于等于x，则根结点及其左子树均应删除，然后以右子树的根结点为树根，重新开始查找。若根结点的值大于x，则沿着左子树向下查找，直到某结点的值小于等于x，则该结点及其左子树均应删除。请在空缺处填入合适的内容，将程序补充完整。void DelTree (BiTree &root) / 非递归删除以root为根的二叉排序树 BiTree p,S100; / S是栈，假定容量足够大，栈中元素是二叉排序树结点的指针 int top=0;
21、 while (root!=NULL | top0) while (root!=NULL) / 沿左分枝向下 S_=root; / （1） _ ; / （2） if (top0) / 退栈，沿栈顶结点的右子树向下删除，释放被删除结点空间 p=_; / （3）root=_ ; / （4） delete p; void DeleteAllX(BiTree &bst, KeyType x)/ 在二叉排序树bst中，删除所有关键字值小于等于x的结点 BiTree p, q; while (bst & bst-key lchild; / q记p的双亲 while (p) while (p & p-key
22、x) / 沿根结点左分枝向下，查小于等于x的结点 q=p; _ ; / （7） if (p) / p结点的值小于等于x q-lchild =_; / （8） _; / （9） DelTree(p); _; / （10） 五、设计题1设数组A中存储有300个元素，下面的程序段可以求出这300个元素中的最大值和最小值。 max=min=a0; for (i=1;i300;i+) if (maxai) min=ai; 这段程序中，比较次数为598（2n-1）次。能否用448（3n/2-2）次的比较次数找出这300个元素中的最大值和最小值呢？若能，请说明所采取的方法并写出程序代码段。若不能，给出你的理
23、由。2编写一个函数，判别一棵采用二叉链表存储的二叉树是否为二叉排序树。3设二叉排序树采用二叉链表存储，类型定义为：typedef int KeyType;struct BiTNode KeyType key; BiTNode* lchild; BiTNode* rchild; ;typedef BiTNode* BiTree;编写一个函数，删除结点关键字值是key的结点。要求删除该结点后，此树仍然是一棵二叉排序树。4设平衡二叉树的结点定义为struct BiTNode KeyType key; int bf; / 结点的平衡因子 BiTNode* lchild; BiTNode* rchild
24、; ;其中，bf域标明了每个结点的平衡因子。编写一个函数，采用非递归的方法求平衡二叉树的深度。5编写从哈希表中删除关键字为K的一个记录的算法，设哈希函数为：H（key）=key MOD T（T为表长），处理冲突采用线性探测再散列法。哈希表定义及建立的哈希表同本章的实例7-8。删除时，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不致于断裂。参考答案一、选择题1C2A3C4B5B6A7C8C9A10B11D12B13B14A15D16A17C18C19B20C21C22D23C24C25D二、填空题11 n n+124 42、83、115、90 4 42、83、50、6235 445 45 46（块内顺序查找）553.5 19 6(n+1)/2 7 8ADCBGHFE954 2 4 7 Nm-2 +1 107
