1、计算机专业基础综合数据结构（集合）历年真题试卷汇编 3及答案解析(总分：60.00，做题时间：90 分钟)一、填空题(总题数：9，分数：18.00)1.一棵含有 15个关键字的 4阶 B树，其非叶结点数最少不能少于_个，最多可以为_个。【中国科学技术大学 1997二、4(4 分)】（分数：2.00）_2.对于 m=4(4阶)的 B一树，如果根的层次为第 1层，则高度为 2的 B一树最少要存储_个关键字，最多可以保存_个关键字。【北京理工大学 2005二、4(2 分)】（分数：2.00）_3.具有 n个关键字的 B树的查找路径长度不会大于_。【中科院计算机 1999二、2(1 分)】（分数：2.
2、00）_4.127阶 B一树中每个结点最多有(1)个关键字；除根结点外所有非终端结点至少有(2)棵子树；65 阶 B+树中除根结点外所有结点至少有(3)个关键字；最多有(4)棵子树；【北方交通大学 1999二、5(4 分)】（分数：2.00）_5.设高为 h的 m阶 B一树上共有 k个关键字，则其叶子结点有_个。【北京交通大学 2006二、8(2分)】（分数：2.00）_6.高度为 h的 2-3树中叶子结点的数目至多为_。【西安电子科技大学 1999软件一、6(2 分)】（分数：2.00）_7.哈希表用_确定记录的存储位置。【北京理工大学 2005二、5(2 分)】（分数：2.00）_8.在哈
3、希造表中，不同的关键字产生同一哈希地址的现象，称为_。【北京理工大学 2006十、6(1分)】（分数：2.00）_9.设已知 n个关键字具有相同的散列函数值，并且采用线性探测再散列方法处理冲突，将这 n个关键字散列到初始为空的地址空间中，一共发生了_次散列冲突。【北京航空航天大学 2006一、9(1 分)】【西安电子科技大学 2001软件一、7(2 分)】（分数：2.00）_二、综合题(总题数：10，分数：26.00)10.设有 n个值不同的元素存于顺序结构中，试问：你能否用比(2n 一 3)少的比较次数选出这 n个元素中的最大值和最小值?若能，请说明是如何实现的；在最坏情况下，至少要进行多少
4、次比较。【西安电子科技大学 1996四(10 分)】（分数：2.00）_假定折半查找表长为 10的有序表。【华中科技大学 2006四、3(10 分)】（分数：4.00）(1).试画出描述折半查找过程的带外部结点的判定树；（分数：2.00）_(2).假定每个元素的查找概率相等，试计算查找成功时的平均查找长度。（分数：2.00）_11.设有序表为(a，b，c，e，f g，i，j，k，p，q)，请分别画出对给定值 b，g 和 n进行折半查找的过程。【吉林大学 2006三、6(206 分)】（分数：2.00）_解答下面的问题：（分数：6.00）(1).画出在递增有序表 A121中进行折半查找的判定树。
5、（分数：2.00）_(2).当实现插入排序过程时，可以用折半查找来确定第 I个元素在前 I-1个元素中的可能插入位置，这样做能否改善插入排序的时间复杂度?为什么?（分数：2.00）_(3).折半查找的平均查找长度是多少?【西安电子科技大学 2000计算机应用八(10 分)】（分数：2.00）_12.画出对长度为 1 8的有序顺序表进行折半查找的判定树，并计算出在等概率时查找成功的平查找长度，以及查找失败时所需的最多的关键字比较次数。【哈尔滨工业大学 2005四、1 (8 分)】（分数：2.00）_13.假定对有序表：(3，4，5，7，24，30，42，54，63，72，87，95)进行折半查找
6、，试回答下列问题：(1)画出描述折半查找过程的判定树。(2)若查找元素 54，需依次与哪些元素比较?(3)若查找元素 90，需依次与哪些元素比较?(4)假定每个元素的查找概率相等，求查找成功时的平均查找长度。【华中理工大学1999二(10 分)】（分数：2.00）_14.在顺序表(5，12，17，19，23，25，30，36，45，49，58)中，用二分法查找关键词 36，进行多少次比较后查找成功?写出查找过程。【吉林大学 2007二、2(4 分)】（分数：2.00）_15.在分析二叉查找树性能时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点 i所在层次为 L i ，那么查找失败
7、到达失败结点时所作的数据比较次数是多少?【清华大学 1999一、4(2 分)】（分数：2.00）_16.顺序检索、二分检索、哈希(散列)检索的时间分别为 O(n)、O(log 2 n)、O(1)。既然有了高效的检素方法，为什么低效的方法还不放弃?【北京邮电大学 1993一、2(5 分)】（分数：2.00）_17.设有一组数据 black，blue，green，purple，red，white，yellow，它们的查找概率分别为010，008，012，005，020，025，020。试以它们的查找概率为权值，构造一棵次优查找树，并计算其查找成功的平均查找长度。【清华大学 1997七(12 分)】
8、（分数：2.00）_三、设计题(总题数：7，分数：16.00)18.已知顺序表中有 m个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到 O(m)。【清华大学 1994八(15 分)】（分数：2.00）_19.假设长度为 n的顺序表 A中每一个数据元素均为整型数据，请写出在该顺序表中采用顺序查找法查找值为 item的数据元素的递归算法。若查找成功，算法返回 item在表中的位置，否则，返回信息为一1(写成非递归算法不得分)。【北京航空航天大学 2006二(10 分)】（分数
9、：2.00）_20.编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。【清华大学 1995七(20 分)】（分数：2.00）_21.某个任务的数据模型可以抽象为给定的 K个集合：S1，S2，SK。其中 Si(1ik)中的元素个数不定。在处理数据过程中将会涉及元素的查找和新元素的插入两种操作，查找和插入时用一个二元组(i，x)来规定一个元素，i 是集合的序号，x 是元素值。设计一种恰当的数据结构来存储这 k个集合的元素，并能高效地实现所要求的查找和插入操作。
10、(1)借助 Pascal的数据类型来构造和描述你所选定的数据结构，并且说明选择的理由；(2)若一组数据模型为 S1=102，17，48，162)，S2=17，84，05，S3=48，42，36，27，51，39)，待插入的元素二元组为(2，112)和(1，53)，按你的设计思想画出插入元素前后的数据结构状态。【北京工业大学 1995七(20分)】（分数：2.00）_22.写一算法找出 n个数的最大值和最小值，要求其最坏条件下的元素比较次数为3n2-2。【西安电子科技大学 2003五(10 分)】（分数：2.00）_23.请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用 llink-r
11、link法存储。【北京大学1998三、2(5 分)】【南京大学 2000】【苏州大学 2004五(15 分)】【中国海洋大学 2005八(15 分)】（分数：2.00）_假设 K1，Kn 是 n个关键词，试解答：（分数：4.00）(1).试甩二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为 K1，K2,，Kn 时，用算法建立一棵以 LLINKRLINK 链接表示的二叉查找树。（分数：2.00）_(2).设计一个算法，打印出该二叉查找树的嵌套括号表示结构。例如，K1=B，K2=A，K3=D，K4=C，K5=E，则用二叉查找树的插入算法建立的二叉查找树为： （分数：2.00）_计算机
12、专业基础综合数据结构（集合）历年真题试卷汇编 3答案解析(总分：60.00，做题时间：90 分钟)一、填空题(总题数：9，分数：18.00)1.一棵含有 15个关键字的 4阶 B树，其非叶结点数最少不能少于_个，最多可以为_个。【中国科学技术大学 1997二、4(4 分)】（分数：2.00）_正确答案：(正确答案：5，15(最多结点数相当于平衡二叉树，每个结点只一个关键字的两棵子树)解析：2.对于 m=4(4阶)的 B一树，如果根的层次为第 1层，则高度为 2的 B一树最少要存储_个关键字，最多可以保存_个关键字。【北京理工大学 2005二、4(2 分)】（分数：2.00）_正确答案：(正确答
13、案：3，15。4 阶 B树的每个结点(除去根结点)至少有 2棵子树，至多有 4棵子树。根结点最低有 2棵子树，结点内关键字个数比子树数少 1。)解析：3.具有 n个关键字的 B树的查找路径长度不会大于_。【中科院计算机 1999二、2(1 分)】（分数：2.00）_正确答案：(正确答案： )解析：4.127阶 B一树中每个结点最多有(1)个关键字；除根结点外所有非终端结点至少有(2)棵子树；65 阶 B+树中除根结点外所有结点至少有(3)个关键字；最多有(4)棵子树；【北方交通大学 1999二、5(4 分)】（分数：2.00）_正确答案：(正确答案：(1)126 (2)64 (3)33 (4)
14、65)解析：5.设高为 h的 m阶 B一树上共有 k个关键字，则其叶子结点有_个。【北京交通大学 2006二、8(2分)】（分数：2.00）_正确答案：(正确答案：k+1)解析：6.高度为 h的 2-3树中叶子结点的数目至多为_。【西安电子科技大学 1999软件一、6(2 分)】（分数：2.00）_正确答案：(正确答案：叶子数至多=3 k-1 。每个结点都是 3棵子树。)解析：7.哈希表用_确定记录的存储位置。【北京理工大学 2005二、5(2 分)】（分数：2.00）_正确答案：(正确答案：关键字)解析：8.在哈希造表中，不同的关键字产生同一哈希地址的现象，称为_。【北京理工大学 2006十
15、、6(1分)】（分数：2.00）_正确答案：(正确答案：冲突)解析：9.设已知 n个关键字具有相同的散列函数值，并且采用线性探测再散列方法处理冲突，将这 n个关键字散列到初始为空的地址空间中，一共发生了_次散列冲突。【北京航空航天大学 2006一、9(1 分)】【西安电子科技大学 2001软件一、7(2 分)】（分数：2.00）_正确答案：(正确答案：n 2 。进行了 n(n+1)次探测，每个关键字在其最后一次探测中无冲突，故发生 n 2 次散列冲突。大概本题原意是问发生了多少次探测。)解析：二、综合题(总题数：10，分数：26.00)10.设有 n个值不同的元素存于顺序结构中，试问：你能否用
16、比(2n 一 3)少的比较次数选出这 n个元素中的最大值和最小值?若能，请说明是如何实现的；在最坏情况下，至少要进行多少次比较。【西安电子科技大学 1996四(10 分)】（分数：2.00）_正确答案：(正确答案：将顺序存储的 n个元素对称比较，即第一个元素与最后一个元素比较，第二个元素与倒数第二个元素比较，比较中的小者放前半部，大者放后半部，用了n2恢比较。再在前后两部分中分别简单选择最小和最大元素，各用 pn2一 1次比较。总共用了 3*n2一 2次比较。)解析：假定折半查找表长为 10的有序表。【华中科技大学 2006四、3(10 分)】（分数：4.00）(1).试画出描述折半查找过程的
17、带外部结点的判定树；（分数：2.00）_正确答案：(正确答案：表长为 10的有序表的判定树： )解析：(2).假定每个元素的查找概率相等，试计算查找成功时的平均查找长度。（分数：2.00）_正确答案：(正确答案：ASL 成功 =(1*1+2*2+4*3+3*4)10=24。)解析：11.设有序表为(a，b，c，e，f g，i，j，k，p，q)，请分别画出对给定值 b，g 和 n进行折半查找的过程。【吉林大学 2006三、6(206 分)】（分数：2.00）_正确答案：(正确答案：折半查找走了一条从根结点到元素(下标)结点的路径。)解析：解答下面的问题：（分数：6.00）(1).画出在递增有序表
18、 A121中进行折半查找的判定树。（分数：2.00）_正确答案：(正确答案：图中，结点中的数字为元素在有序表中的下标。 )解析：(2).当实现插入排序过程时，可以用折半查找来确定第 I个元素在前 I-1个元素中的可能插入位置，这样做能否改善插入排序的时间复杂度?为什么?（分数：2.00）_正确答案：(正确答案：插入排序中，用折半查找确定待插入元素位置，比直接插入排序减少了比较次数，但数据移动次数没有改变，排序的时间复杂度也未改变。)解析：(3).折半查找的平均查找长度是多少?【西安电子科技大学 2000计算机应用八(10 分)】（分数：2.00）_正确答案：(正确答案：折半查找的平均查找长度是
19、(n+1)n)log 2 (n+1)一 1log(n+1)一 1。本例ASL=7921。)解析：12.画出对长度为 1 8的有序顺序表进行折半查找的判定树，并计算出在等概率时查找成功的平查找长度，以及查找失败时所需的最多的关键字比较次数。【哈尔滨工业大学 2005四、1 (8 分)】（分数：2.00）_正确答案：(正确答案：ASL 成功 =(1*1+2*2+4*3+8*4+3*5)18=6418 最多比较次数是 5。平均 ASL 失败 =(13*4+6*5)19=7219。)解析：13.假定对有序表：(3，4，5，7，24，30，42，54，63，72，87，95)进行折半查找，试回答下列问题
20、：(1)画出描述折半查找过程的判定树。(2)若查找元素 54，需依次与哪些元素比较?(3)若查找元素 90，需依次与哪些元素比较?(4)假定每个元素的查找概率相等，求查找成功时的平均查找长度。【华中理工大学1999二(10 分)】（分数：2.00）_正确答案：(正确答案：(1) )解析：14.在顺序表(5，12，17，19，23，25，30，36，45，49，58)中，用二分法查找关键词 36，进行多少次比较后查找成功?写出查找过程。【吉林大学 2007二、2(4 分)】（分数：2.00）_正确答案：(正确答案：进行了 4次比较，先后和 25，45，30 比较后，找到 36。)解析：15.在分
21、析二叉查找树性能时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点 i所在层次为 L i ，那么查找失败到达失败结点时所作的数据比较次数是多少?【清华大学 1999一、4(2 分)】（分数：2.00）_正确答案：(正确答案：失败结点是不存在的结点，在其双亲结点处查找失败，这时的比较次数为 L i 一1。)解析：16.顺序检索、二分检索、哈希(散列)检索的时间分别为 O(n)、O(log 2 n)、O(1)。既然有了高效的检素方法，为什么低效的方法还不放弃?【北京邮电大学 1993一、2(5 分)】（分数：2.00）_正确答案：(正确答案：时间复杂度是判断检索方法的一个重要指标，但不
22、是唯一指标。使用什么检索方法要综合考虑。哈希检索时间复杂度为 O(1)，查找速度最快，但需构建哈希函数，设计解决冲突的方法；二分检索时间复杂度为 O(log 2 n)，需要元素有序且顺序存储，排序操作的时间开销大；顺时检索时间复杂度最差为 O(n)，但对检索表无要求，数据有序无序均可，在数据量较小时使用方便。)解析：17.设有一组数据 black，blue，green，purple，red，white，yellow，它们的查找概率分别为010，008，012，005，020，025，020。试以它们的查找概率为权值，构造一棵次优查找树，并计算其查找成功的平均查找长度。【清华大学 1997七(1
23、2 分)】（分数：2.00）_正确答案：(正确答案：根据次优查找树的定义，首先取第 i个记录(1ih)构造根结点，使 取最小值。 )解析：三、设计题(总题数：7，分数：16.00)18.已知顺序表中有 m个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到 O(m)。【清华大学 1994八(15 分)】（分数：2.00）_正确答案：(正确答案：顺序表无序，索引表有序。由顺序表中的关键字及其下标地址组成索引表中的一项。顺序表有 m个记录，索引表应有 m项。建立索引表宜采用“直接
24、插入排序”，这样才能在顺序表有序时，算法复杂度达到最好 O(m)。)解析：19.假设长度为 n的顺序表 A中每一个数据元素均为整型数据，请写出在该顺序表中采用顺序查找法查找值为 item的数据元素的递归算法。若查找成功，算法返回 item在表中的位置，否则，返回信息为一1(写成非递归算法不得分)。【北京航空航天大学 2006二(10 分)】（分数：2.00）_正确答案：(正确答案：int Search(int A，int item， int i) 在数组 A中查值 item的数据，成功返回其位序，失败返回一 1。初始调用时 i：n 一 1 if(i解析：20.编写对有序表进行顺序查找的算法，并
25、画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。【清华大学 1995七(20 分)】（分数：2.00）_正确答案：(正确答案：核心语句是： while(iK) return (一 1)； i+； while return (一 1)； 在等概率情况下，查找成功的平均查找长度为(n+1)2，查找失败的平均查找长度为 (n+2)2(失败位置除小于每一个，还存在大于最后一个)。若查找成功和不成功的概率也相等，则查找成功时和关键字比较的个数的期望值约为 075(n+1)。)解析：21.某个任务的
26、数据模型可以抽象为给定的 K个集合：S1，S2，SK。其中 Si(1ik)中的元素个数不定。在处理数据过程中将会涉及元素的查找和新元素的插入两种操作，查找和插入时用一个二元组(i，x)来规定一个元素，i 是集合的序号，x 是元素值。设计一种恰当的数据结构来存储这 k个集合的元素，并能高效地实现所要求的查找和插入操作。(1)借助 Pascal的数据类型来构造和描述你所选定的数据结构，并且说明选择的理由；(2)若一组数据模型为 S1=102，17，48，162)，S2=17，84，05，S3=48，42，36，27，51，39)，待插入的元素二元组为(2，112)和(1，53)，按你的设计思想画出
27、插入元素前后的数据结构状态。【北京工业大学 1995七(20分)】（分数：2.00）_正确答案：(正确答案：借助于分块查找思想，在建立数据顺序表的同时，建立一索引表。数据表中按尼个集合分块 (元素个数不一定相等)，素引表中有两个域，一是各集合最后一个元素在数据表中的位置(一维数组中的下标)，二是集合的个数(k)。实现数据运算时，根据给定的二元组(i，x)，首先在索引表中找到集合 i的位置，然后在数据表中查找 x。如查到 x，则查找成功，返回 x在数据表中的位置，否则查找失败。若要插入，则将数据表中的数据后移，插入 x，同时修改索引表。插入算法的核心语句段如下： if(i：=1)first=0；
28、 要求在第 i个集合插入数据 else first=id.ai1+1； first 指向第i个集合在数据表的首址 last=id.ai； last 是第 i个集合在数据表中的末址 for(j=first；Jlast；j+) if(Rj=x)return (j)； 查找成功，返回元素位序 for(j=id.a lid.k；jid.ai；j 一一) 查找失败，将 x插入数据表 Rj+1=Rj； 元素后移 Rj+1=x； 将 x插入原第 i个集合最后一个元素之后 for(J=i；jk；j+)id.aj+； 修改索引表中各集合最后一个元素的下标 由于各集合元素个数不等，各块长度不等且块间无序，索引表中
29、用数组表示，数组中元素值是各集合最后一个元素在数据表中的下标。按本算法插入(2，112)和(1，53)，数据表前后状态如下： )解析：22.写一算法找出 n个数的最大值和最小值，要求其最坏条件下的元素比较次数为3n2-2。【西安电子科技大学 2003五(10 分)】（分数：2.00）_正确答案：(正确答案：设 n个元素存于向量中，元素两两比较，每次比较的大者置于向量的后端，小者置于向量的前端，一趟比较后将元素分成大者端和小者端，比较次数n2。接着对大者端和小者端分别进行简单选择排序，选出最大元素和最小元素，各制n2一 1次比较，总共比较次数不超过 3n2一 2。分成大者端和小者端的核心语句是：
30、 for(i=0，j=n-1 一 i；irjkey)rirj；)解析：23.请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用 llink-rlink法存储。【北京大学1998三、2(5 分)】【南京大学 2000】【苏州大学 2004五(15 分)】【中国海洋大学 2005八(15 分)】（分数：2.00）_正确答案：(正确答案：根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论。为此设全局指针变量 pre(初值为 null)和全局变量 flag，初值为true。若非二叉排序树，则置 flag为 false。算法如下： void Ju
31、dgeBST(BSTree t，int&flag) 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由 flag得出结论 if(t!=nullflag) Judgebst(t一ichild，flag)； 中序遍历左子树 if(pre=null)pre=t； 中序遍历的第一个结点不必判断 else if(pre 一datadata)pre=t； 前驱指针指向当前结点 else flag：false； 不是完全二叉树 Judgebst(t 一rchild，flag)； 中序遍历右子树 JudgeBST 算法结束 本题的另一算法是按定义，二叉排序树的左、右子树都是二叉排序树，根结点的值大于左子树中所有结点的值而小于右子树中所有结点的值，即根结点大于左子树的最大值而小于右子树的最小值。算法如下： int JudgeBST(BSTree t) 判断二叉树 t是否是二叉排序树，若是，返回 true，否则，返回 false (if(t=null)return true； if(Judgebst(t 一Ichild
