数据结构考研习题-第九章集合(3)

（1）散列函数采用除留余数法，用%hashsize（取余运算）将各关键码映像到表中，请指出每一个产生冲突的关键码可能产生多少次冲突。 （7分）

（2）散列函数采用先将关键码各位数字折叠相加，再用%hashsize将相加的结果映像到表中的办法。请指出每一个产生冲突的关键字码可能产生多少次冲突。【清华大学 2001 五 （15分）】

28. 已知一组关键字为（26,36,41,38,44,15,68,12,06,51,25），用链地址法解决冲突。假

设装填因子a=0.75，散列函数的形式为H（K）=K MOD P，回答下列问题： （1） 构造出散列函数；（3分） （2） 计算出等概率情况下查找成功的平均查找长度；（3分） （3） 计算出等概率情况下查找失败的平均查找长度；（3分）【东北大学 1999 一、3 (共9分)】

29. 在B-树和B+树中查找关键字时，有什么不同？【东北大学 2002 一 、5 (2分)】

30. 简要叙述B树(有些教材中称为B-树)与B+树的区别?【南京航空航天大学 1999 六 （5分）】31. 包括n个关键码的m阶B-树在一次检索中最多涉及多少个结点？（要求写出推导过程。）【北京大学 1997 五、2 （6分）】

32. 给定关键码序列（26,25,20,33,21,24,45,204,42,38,29,31），要用散列法进行存储，规定负载因子α=0.6。

（1）请给出除余法的散列函数。

（2）用开地址线性探测法解决碰撞，请画出插入所有的关键码后得到的散列表，并指出发生碰撞的次数。

【北京大学 1997 三（6分）】

33. 已知记录关键字集合为（53,17,19,61,98,75,79,63,46,49）要求散列到地址区间（100,101,102,103,104,105,106,107,108,109）内，若产生冲突用开型寻址法的线性探测法解决。要求写出选用的散列函数；形成的散列表；计算出查找成功时平均查找长度与查找不成功的平均查找长度。（设等概率情况）【东北大学1998一、2 (10分)】 34. 设有一棵空的３阶B-树，依次插入关键字30,20,10,40,80,58,47,50,29,22,56,98,99，请画出该树。

【华南理工大学 2001 一、5 （4分）】

35．设依以下次序给出关键字：34,16,19,21,5,49,24,62,3,17,45,8，构造3阶B-树。要求从空树开始，每插入一个关键字,画出一个树形。【南开大学 1997 六 (10分)】 36.高度为h的m阶B树至少有多少个结点？【西安电子科技大学2000软件一、6 （5分）】

37. 对下面的3阶B-树，依次执行下列操作，画出各步操作的结果。【合肥工业大学 1999 四、3 （1）插入90 （2） 插入25 （3） 插入45 （4）删除60 （5）删除80

38. 已知2棵2-3 B-树如下（省略外结点）：【吉林大学 1999 一、4 (4分)】 （1）对树（a）,请分别画出先后插入26，85两个新结点后的树形； （2）对树（b）,请分别画出先后删除53，37两个结点后的树形。

(a)

5分）】 （

（b） 39. 四阶B树中（如图所示），插入关键字87，试画出插入调整后树的形状【东南大学 1999 五 （15分）】

30 60 80

20 25 35 50 60 70 75 82 85 90

40. 下图是5阶B树 ，画出删去P后的B树，再画出删去D后的B树。【厦门大学 2000 二、2 （20/3分）】

41. 满二叉检索树符合B树定义吗？B树的插入和删除算法适用于满二叉检索树吗？为何？【东南大学 1995 五 （6分）】

42. 设有关键码序列10,20,35,40,44,51,65,70,85,91,93,95。试按照最大关键码复写原则绘出相应的2阶 B+ 树。

【山东工业大学 1996 二、1 （6分）】

43. 在一棵B+树上一般可进行那两种方式的查找运算?【北京科技大学 2001 一、8 （2分）】 44. 含9个叶子结点的3阶B-树中至少有多少个非叶子结点？含10个叶子结点的3阶B-树中至多有多少个非叶子结点？

【北京轻工业学院 2000 八 （10分）】

45. 直接在二叉排序树中查找关键字K与在中序遍历输出的有序序列中查找关键字K，其效率是否相同？输入关键字有序序列来构造一棵二叉排序树，然后对此树进行查找，其效率如何？为什么？【长沙铁道学院 1997 三、4 (3分)】

46. 一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。

【厦门大学 2002 八、2 （5分）】

47. 已知长度为11的表（xal,wan,wil,zol,yo,xul,yum,wen，wim,zi,yon），按表中元素顺序依次插入一棵初始为空的平衡二叉排序树，画出插入完成后的平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

【山东大学 2001 七 ( 7分)】

48. 用序列(46,88,45,39,70,58,101,10,66,34)建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度.【北京邮电大学 1999 七 （10分）】

49. 依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树

【华中理工大学 2000 五 （10分）】

(1) 试画出生成之后的二叉排序树; (2) 对该二叉排序树作中序遍历，试写出遍历序列;

(3) 假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。 50. 已知关键字序列R={11,4,3,2,17,30,19}，请按算法步骤：【北方交通大学 1996 四】 （1）构造一棵哈夫曼树，并计算出它的带权路径长度WPL（7分）

（2）构造一棵二叉排序树，如果对每个关键字的查找概率相同，求查找成功时的平均查找长度ASL。（8分）

51. 输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题。

（1） 按次序构造一棵二叉排序树BS。(2) 依此二叉排序树，如何得到一个从大到小

的有序序列？

（2） 画出在此二叉排序树中删除“66”后的树结构。【同济大学 2001 一 (10分)】 52. 设二叉排序树中关键字由1到1000的整数组成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树中查到的序列？说明原因。【东北大学 2002 一 、3 (4分)】

（1）51，250，501，390，320，340，382，363 （2）24，877，125，342，501，623，421，363

53. 用关键字1,2,3,4的四个结点（1）能构造出几种不同的二叉排序树？其中（2）最优查找树有几种？（3）AVL树有几种？(4)完全二叉树有几种？试画出这些二叉排序树。【北京工业大学 1997 二、 3 ( 5分)】 类似本题的另外叙述有：

(1)设有关键字A、B、C和D，依照不同的输入顺序，共可能组成多少不同的二叉排序树。请画出其中高度较小的6种。 【北京大学 1995 】

54. 一棵具有m层的AVL树至少有多少个结点，最多有多少个结点？【浙江大学 1995 六 (8

分)】

55. 设T是一棵高度平衡树(又称平衡树)，给定关键词K，如果在T中查找K失败，且查找路径上的任一结点的平衡系数皆为零，试回答用高度平衡树插入算法在T中插入关键词为K的新结点后，树T的高度是否一定增加?并回答为什么。

【吉林大学 1996 四、2】

56．设二叉树HT是一棵高度平衡树，当使用二叉查找与插入算法插入一个新的结点时，该操作可能会破坏HT的平衡性。试列举出可能破坏HT的平衡性的所有情况，并论证你的结论的正确性（即要证明你所列举的情况恰好是可能破坏HT的平衡性的所有情况）【吉林大学1998 四 1997 六 (14分)】 57. 按下述次序输入关键字：e,i,p,k,,m,l,b,试画出AVL树的构造与调整过程。（要求画出每插入一个关键字检索树的形状及调整后的结果）。【山东大学 1992 一 、5 (3分)】 58. 已知一棵高度平衡树如下，其中各结点间大小关系（中根次序）按字典序排列，请画出

插入结点JUN后，该二叉树经平衡过程而形成的树形，并说明采用何种转动方式，标出平衡后树中各结点的平衡系数。【吉林大学 1999 一 、1 (4分)】

59. 已知长度为l2的表{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}

（1） 试按表中元素的次序依次插入一棵初始为空的二叉排序树，请画出插入之后的二叉排序树，并求在等概率情况下查找成功的平均查找长度。 （2） 若对表中元素先进行排序构成有序表，求在等概率的情况下对此表进行折半查找成功的平均查找长度。 （3） 按表中元素顺序构造一棵AVL树，并求其在等概率情况下查找成功的平均查找长度。

【中国矿业大学 2000 七（10分）】

60. 试画出从空树开始，由字符序列(t,d,e,s,u,g,b,j,a,k,r,i)构成的二叉平衡树，并为每一次的平衡处理指明旋转类型。

【清华大学 1994 三（10分）】

61. 给定关键词输入序列{CAP,AQU,PIS,ARI,TAU,GEM,CAN,LIB,VIR,LEO,SCO}，假定关键词

比较按英文字典序，

（1）试画出从一棵空树开始，依上述顺序（从左到右）输入关键词，用高度平衡树的查找和插入算法生成一棵高度平衡树的过程，并说明生成过程中采用了何种转动方式进行平衡调整，标出树中各结点的平衡系数。

（2）试画出在上述生成的高度平衡树中，用高度平衡树的删除算法先后删除结点CAN和AQU后的树形，要求删除后的树形仍为一棵高度平衡树，并说明删除过程中采用了何种转动方式进行平衡调整，标出树中各结点的平衡系数。 【吉林大学 2000 一 、5 (6分)】

62. 如图2所示是一棵正在进行插入运算的AVL树，关键码70的插入使它失去平衡，按照AVL树的插入方法，需要对它的结构进行调整以恢复平衡。 (1) 请画出调整后的AVL树。

(2) 假设AVL树用llink-rlink法存储，t是指向根结点的指针，请用Pascal(或C)语句

表示出这个调整过程。 （说明：不必写出完整的程序，只需用几个语句表示出在本题中所给出的具体情况下调整过程中指针的变化。在调整过程中还有两个指针变量p和q可以使用。【北京大学 1997 六）（10分）】

t .

100 -- 60 + 120 · -

40 ·-- 80 -

·- 70

63. 若以序列 {Thu,Tue,Wed,Last,Fri,Sat,Mon,Sun,Next} 作为输入序列

(1) 按算法AVL-INSERT构造均高树，画出构造过程和进行平衡转换的类型。

(2) 若均高树中有n个结点，其高度为h，指出在最坏情况下，对该树的插入、删除和依次输出操作的时间复杂性。 【东南大学 1992 五（18分）】

64. 在数轴上有N个彼此相临不交的区间，每个区间下界上界都是整数。N个区间顺序为

1-N。要查找给定的X落入的区间号，您认为应怎样组织数据结构，选择什么方法最快，简述原因。

【西北大学 2000 二、4 (5分)】

65. 有一个长度为12的有序表，按对半查找法对该表进行查找，在表内各元素等概率情况

下，查找成功所需的平均比较次数是多少？【吉林大学 2001 一、 1 (3分)】

66. 若对一个线性表进行折半查找，该线性表应满足什么条件？【北京航空航天大学 1998 一、8 （4分）】

67. 在查找和排序算法中，监视哨的作用是什么？【长沙铁道学院 1997 三、3 (3分)】 68. 长度为255的有序表采用分块查找，块的大小应取多少？【首都经贸大学 1997 一、1 （4分）】

69. 用分块查找法，有2000项的表分成多少块最理想？每块的理想长度是多少？若每块长度为25 ，平均查找长度是多少？

【厦门大学 1999 三、2】

70. 设有n个值不同的元素存于顺序结构中，试问：你能否用比（2n-3）少的比较次数选出这n个元素中的最大值和最小值？若能，请说明是如何实现的；在最坏情况下，至少要进行多少次比较。【西安电子科技大学 1996 四 （10分）】 71. 对有14个元素的有序表A[1?14]作折半查找，当比较到A[4]时算法结束。被比较元素除A[4]外，还有哪几个？

【燕山大学 2000 一、2 （1分）】 72. 解答下面的问题

（1）画出在递增有序表A[1..21]中进行折半查找的判定树。

（2）当实现插入排序过程时，可以用折半查找来确定第I个元素在前I-1个元素中的可能插入位置，这样做能否改善插入排序的时间复杂度？为什么？ （3）折半查找的平均查找长度是多少？【西安电子科技大学2000计应用 八 （10分）】 73. 设有一组数据black,blue,green,purple,red,white,yellow，它们的查找概率分别为0.10,0.08,0.12,0.05,0.20,0.25,0.20。 试以它们的查找概率为权值，构造一棵次优查找树，并计算其查找成功的平均查找长度。【清华大学 1997 七 （12分）】 74. 假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题：

(1).画出描述折半查找过程的判定树；

(2).若查找元素54，需依次与那些元素比较? (3).若查找元素90，需依次与那些元素比较?

(4).假定每个元素的查找概率相等，求查找成功时的平均查找长度。【华中理工大学 1999 二 (10分)】

75. 在分析二叉查找树性能时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点i所在层次为Li，那么查找失败到达失败结点时所作的数据比较次数是多少？【清华大学 1999 一、4 （2分）】

76. 设有五个数据do，for，if,repeat，while，它们排在一个有序表中，其查找概率分别

为p1 =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。 do for if repeat while

q0 p1 q1 p2 q2 p3 q3 p4 q4 p5 q5

(1) 试画出对该有序表采用顺序查找时的判定树和采用折半查找时的判定树。（6分） (2) 分别计算顺序查找时的查找成功和不成功的平均查找长度，以及折半查找时的查找成功和不成功的平均查找长度。（4分）

(3) 判定是顺序查找好？还是折半查找好？（2分） 【清华大学 1999年 二 （12分）】

77. 顺序检索，二分检索，哈希（散列）检索的时间分别为O(n),O(log2n),O(1)。既然有了高效的检索方法，为什么低效的方法还不放弃？【北京邮电大学 1993 一、2 (5分)】

五、 算法设计题

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构考研习题-第九章集合(3)在线全文阅读。