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