1、计算机专业基础综合数据结构（集合）历年真题试卷汇编 2及答案解析(总分：64.00，做题时间：90 分钟)一、填空题(总题数：14，分数：28.00)1.对于具有 144个记录的文件，若采用分块查找法，且每块长度为 8，则平均查找长度为_。【北方交通大学 2001二、8】（分数：2.00）_2.有一个 2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是 (1)，分成 (2) 块最为理想，平均查找长度是 (3) 。【中国矿业大学 2000一、6(3 分)】（分数：2.00）_3.分块检索中，若索引表和各块内均用顺序查找，则有 900个元素的线性表分成_块最好；若分成 25块，
2、其平均查找长度为_。【北京工业大学 1999一、5(2 分)】（分数：2.00）_4.执行顺序查找时，储存方式可以是(1)，二分法查找时，要求线性表(2)，分块查找时要求线性表(3)，而散列表的查找，要求线性表的存储方式是(4)。【山东大学 1998一、1(3 分)】（分数：2.00）_5.查找是非数值程序设计的一个重要技术问题，基本上分成(1)查找，(2)查找和(3)查找。处理哈希冲突的方法有(4)、(5)、(6)和(7)。【华北计算机系统工程研究所 1999一(5 分)】（分数：2.00）_6.如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次
3、数为_。【山东大学 1999二、1(4 分)】（分数：2.00）_7.在含有 n个结点的二叉排序树中查找一个关键字，进行关键字比较次数的最大值是_。【北京交通大学 2004一、15(2 分)】（分数：2.00）_8.在二叉排序树上成功地找到一个结点，在平均情况下的时间复杂性是：_，在最坏情况下的时间复杂性是_。【上海交通大学 2004五、1(154 分)】（分数：2.00）_9.AVL树_是完全二叉树；完全二叉树_是 AVL树。【电子科技大学 2005二、5(1 分)】（分数：2.00）_10.一棵深度为 k的平衡二叉树，其每个非终端结点的平衡因子均为 0，则该树共有_个结点。【同济大学 20
4、05一、3(15 分)】（分数：2.00）_11.在一棵 m阶 B一树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_。【中国科技大学 1998一、5(3 分)】【南京理工大学 2001二、4(3 分)】（分数：2.00）_12.高度为 4的 3阶 B一树中，最多有_个关键字。【合肥工业大学 2000三、9(2 分)】（分数：2.00）_13.高为 4(不含叶子层)的 4阶 B一树最少有_个关键字。【北京交通大学 2006二、9(2 分)】（分数：2.00）_14.高度为 5的平衡二叉
5、树，其结点数最多可以有_个；最少可以是_个。【中国科学技术大学 1997二、5(4 分)】（分数：2.00）_二、判断题(总题数：10，分数：20.00)15.若装填因子 为 1，则向散列表中散列元素时一定会产生冲突。( )【北京邮电大学 2005二、8(1 分)】（分数：2.00）A.正确B.错误16.若散列表的负载因子 A.正确B.错误17.随着装填因子 的增大，用闭散列法解决冲突，其平均搜索长度比用开散列法解决冲突时的平均搜索长度增长得慢。( )【清华大学 2002二、12(1 分)】（分数：2.00）A.正确B.错误18.在散列检索中，“比较”操作一般也是不可避免的。( )【华南理工大
6、学 2001一、4(1 分)】（分数：2.00）A.正确B.错误19.散列函数越复杂越好，因为这样随机性好，冲突概率小。( )【南京理工大学 1997二、5(2 分)】（分数：2.00）A.正确B.错误20.Hash表的平均查找长度与处理冲突的方法无关。( )【南京航空航天大学 1997一、9(1 分)】（分数：2.00）A.正确B.错误21.负载因子(装填因子)是散列表的一个重要参数，它反映散列表的装满程度。( )【中科院软件所 1999六(卜 3)(2分)】【中国海洋大学 2006二、13(1 分)】【上海海事大学 2005一、10(2 分)】（分数：2.00）A.正确B.错误22.散列法
7、的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。( )【中山大学 1994一、8(2 分)】（分数：2.00）A.正确B.错误23.哈希表的结点中只包含数据元素自身的信息，不包含任何指针。( )【山东大学 2001一、6(1 分)】（分数：2.00）A.正确B.错误24.杂凑表的查找效率主要取决于构造杂凑表时选取的杂凑函数和处理冲突的方法。 ( )【吉林大学 2007一、7(1 分)】（分数：2.00）A.正确B.错误三、综合题(总题数：7，分数：16.00)将关键字序列(7，8，30，1 1，18，9，14)散列存储到散列表中，散列表的存储空间是一个下标从 0开始的一
8、维数组，散列函数为：H(key)=(key3)MOD 7，处理冲突采用线性探测再散列法，要求装填(载)因子为 07。（分数：4.00）(1).请画出所构造的散列表。（分数：2.00）_(2).分别计算等概率情况下查找成功和查找不成功的平均查找长度。【2010 年全国试题 41(10分)】（分数：2.00）_25.在很多查找和排序算法中，经常使用“监视哨”，其目的是什么?以顺序表上的顺序查找为例，说明如何设置“监视哨”?【江苏大学 2006三、8(5 分)】（分数：2.00）_26.采用比较的方法，从具有 n个元素集合中找出最大和次最大的元素，需要的最少比较次数为多少?说明理由和实现的方法。【上
9、海交通大学 2003七(10 分)】（分数：2.00）_27.在长度为 n的线性表中进行顺序查找。查找第 i个数据元素的概率为 p i ，且分布如下： （分数：2.00）_28.对于一个有序顺序表来说，折半查找是否任何时候都比顺序查找快?为什么?【上海交通大学 2005三(6分)】（分数：2.00）_29.对长度为 101的表进行分块查找，确定所在的块及块内查找均采用顺序查找，假设查找表中每个记录的概率相等。怎样分块可以使得 ASL最小?并给出理由。【北京交通大学 2006四、3(5 分)】（分数：2.00）_30.用分块查找法，有 2000项的表分成多少块最理想?每块的理想长度是多少?若每块
10、长度为 25，平均查找长度是多少?【厦门大学 1999三、2(5 分)】（分数：2.00）_计算机专业基础综合数据结构（集合）历年真题试卷汇编 2答案解析(总分：64.00，做题时间：90 分钟)一、填空题(总题数：14，分数：28.00)1.对于具有 144个记录的文件，若采用分块查找法，且每块长度为 8，则平均查找长度为_。【北方交通大学 2001二、8】（分数：2.00）_正确答案：(正确答案：14 计算过程如下：1448=18 块，索引表顺序查找，故(18+1)2+(8+1)2=14。)解析：2.有一个 2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是 (1)，分
11、成 (2) 块最为理想，平均查找长度是 (3) 。【中国矿业大学 2000一、6(3 分)】（分数：2.00）_正确答案：(正确答案：(1)45 (2)45 (3)46(索引表顺序查找)解析：3.分块检索中，若索引表和各块内均用顺序查找，则有 900个元素的线性表分成_块最好；若分成 25块，其平均查找长度为_。【北京工业大学 1999一、5(2 分)】（分数：2.00）_正确答案：(正确答案：30，315(索引表顺序查找)解析：4.执行顺序查找时，储存方式可以是(1)，二分法查找时，要求线性表(2)，分块查找时要求线性表(3)，而散列表的查找，要求线性表的存储方式是(4)。【山东大学 199
12、8一、1(3 分)】（分数：2.00）_正确答案：(正确答案：(1)顺序存储或链式存储 (2)顺序存储且有序(3)块内顺序存储，块间有序 (4)散列存储)解析：5.查找是非数值程序设计的一个重要技术问题，基本上分成(1)查找，(2)查找和(3)查找。处理哈希冲突的方法有(4)、(5)、(6)和(7)。【华北计算机系统工程研究所 1999一(5 分)】（分数：2.00）_正确答案：(正确答案：(1)静态查找表 (2)动态查找表 (3)哈希表 (4)开放定址方法(5)链地址方法 (6)再哈希 (7)建立公共溢出区)解析：6.如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排
13、序树检索时，平均比较次数为_。【山东大学 1999二、1(4 分)】（分数：2.00）_正确答案：(正确答案：（n+1)2)解析：7.在含有 n个结点的二叉排序树中查找一个关键字，进行关键字比较次数的最大值是_。【北京交通大学 2004一、15(2 分)】（分数：2.00）_正确答案：(正确答案：n)解析：8.在二叉排序树上成功地找到一个结点，在平均情况下的时间复杂性是：_，在最坏情况下的时间复杂性是_。【上海交通大学 2004五、1(154 分)】（分数：2.00）_正确答案：(正确答案：O(logn)，O(n)解析：9.AVL树_是完全二叉树；完全二叉树_是 AVL树。【电子科技大学 20
14、05二、5(1 分)】（分数：2.00）_正确答案：(正确答案：不一定，一定。需要说明，AVL 是平衡二叉树，各个结点值之间满足确定关系。从树形上看，完全二又树任意结点左右子树的高度差的绝对值不大于 1。仅从结点平衡因子角度看，可以说完全二叉树是平衡二叉树。)解析：10.一棵深度为 k的平衡二叉树，其每个非终端结点的平衡因子均为 0，则该树共有_个结点。【同济大学 2005一、3(15 分)】（分数：2.00）_正确答案：(正确答案：2 k -1)解析：11.在一棵 m阶 B一树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_；若在某结点中删除一个关键字而导致
15、结点合并，则该结点中原有的关键字的个数是_。【中国科技大学 1998一、5(3 分)】【南京理工大学 2001二、4(3 分)】（分数：2.00）_正确答案：(正确答案：m-1，m2一 1)解析：12.高度为 4的 3阶 B一树中，最多有_个关键字。【合肥工业大学 2000三、9(2 分)】（分数：2.00）_正确答案：(正确答案：26(第 4层是叶子，每个结点两个关键字)解析：13.高为 4(不含叶子层)的 4阶 B一树最少有_个关键字。【北京交通大学 2006二、9(2 分)】（分数：2.00）_正确答案：(正确答案：31)解析：14.高度为 5的平衡二叉树，其结点数最多可以有_个；最少可
16、以是_个。【中国科学技术大学 1997二、5(4 分)】（分数：2.00）_正确答案：(正确答案：31，12)解析：二、判断题(总题数：10，分数：20.00)15.若装填因子 为 1，则向散列表中散列元素时一定会产生冲突。( )【北京邮电大学 2005二、8(1 分)】（分数：2.00）A.正确 B.错误解析：解析：若装填因子 为 1，再插入元素一定产生冲突。若 1，也不能避免碰撞的产生。16.若散列表的负载因子 A.正确B.错误 解析：17.随着装填因子 的增大，用闭散列法解决冲突，其平均搜索长度比用开散列法解决冲突时的平均搜索长度增长得慢。( )【清华大学 2002二、12(1 分)】（
17、分数：2.00）A.正确B.错误 解析：18.在散列检索中，“比较”操作一般也是不可避免的。( )【华南理工大学 2001一、4(1 分)】（分数：2.00）A.正确 B.错误解析：19.散列函数越复杂越好，因为这样随机性好，冲突概率小。( )【南京理工大学 1997二、5(2 分)】（分数：2.00）A.正确B.错误 解析：解析：不能说哪种哈希函数的选取方法最好，各种选取方法都有自己的适用范围。20.Hash表的平均查找长度与处理冲突的方法无关。( )【南京航空航天大学 1997一、9(1 分)】（分数：2.00）A.正确B.错误 解析：21.负载因子(装填因子)是散列表的一个重要参数，它反
18、映散列表的装满程度。( )【中科院软件所 1999六(卜 3)(2分)】【中国海洋大学 2006二、13(1 分)】【上海海事大学 2005一、10(2 分)】（分数：2.00）A.正确 B.错误解析：22.散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。( )【中山大学 1994一、8(2 分)】（分数：2.00）A.正确 B.错误解析：23.哈希表的结点中只包含数据元素自身的信息，不包含任何指针。( )【山东大学 2001一、6(1 分)】（分数：2.00）A.正确B.错误 解析：解析：哈希表的结点中可以包括指针，指向其元素。24.杂凑表的查找效率主要取决于构
19、造杂凑表时选取的杂凑函数和处理冲突的方法。 ( )【吉林大学 2007一、7(1 分)】（分数：2.00）A.正确 B.错误解析：三、综合题(总题数：7，分数：16.00)将关键字序列(7，8，30，1 1，18，9，14)散列存储到散列表中，散列表的存储空间是一个下标从 0开始的一维数组，散列函数为：H(key)=(key3)MOD 7，处理冲突采用线性探测再散列法，要求装填(载)因子为 07。（分数：4.00）(1).请画出所构造的散列表。（分数：2.00）_正确答案：(正确答案：因装填(载)因子为 07，有 7个元素，故散列表长 m=707=10。 构造的哈希表如下： )解析：(2).分
20、别计算等概率情况下查找成功和查找不成功的平均查找长度。【2010 年全国试题 41(10分)】（分数：2.00）_正确答案：(正确答案：ASL 成功 =17*(1*4+2*1+3*2)=127ASL 失败 =17*(3+2+1+2+l+5+4)=187 计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其哈希地址为 i(0im 一 1)时的查找次数。一般情况下分母为表长，但本例哈希地址是 06，所以分母为 7。哈希地址为 i的失败比较次数是从 i开始往右循环数到没有数据的位置(极端情况是表长 m)。)解析：25.在很多查找和排序算法中，经常使用“监视哨”，其目的是什么?以顺序表上的顺序
21、查找为例，说明如何设置“监视哨”?【江苏大学 2006三、8(5 分)】（分数：2.00）_正确答案：(正确答案：监视哨的作用是免去查找过程中每次都要检测整个表是否查找完毕，提高了查找效率。顺序表上顺序查找时监视哨可以设在低端(下标 0)或高端(下标 n+1)。)解析：26.采用比较的方法，从具有 n个元素集合中找出最大和次最大的元素，需要的最少比较次数为多少?说明理由和实现的方法。【上海交通大学 2003七(10 分)】（分数：2.00）_正确答案：(正确答案：使用堆，选最大元素最多比较不超过 4n次，再选次大元素用 logn次。)解析：27.在长度为 n的线性表中进行顺序查找。查找第 i个
22、数据元素的概率为 p i ，且分布如下： （分数：2.00）_正确答案：(正确答案： )解析：28.对于一个有序顺序表来说，折半查找是否任何时候都比顺序查找快?为什么?【上海交通大学 2005三(6分)】（分数：2.00）_正确答案：(正确答案：并非在任何情况下折半查找都比顺序查找快。例如，若待查元素是该顺序表的第一个元素，则顺序查找顺序表会更快。对有序顺序表采用顺序查找，若元素存在表中，则在任一位置，查找都可能成功。同样，若元素不在表中，则在任一位置，查找都可能结束。折半查找必须经一系列计算，方知查找成功还是失败。尽管如此，一般说来，在大多数情况下，折半查找还是比顺序查找快。)解析：29.对
23、长度为 101的表进行分块查找，确定所在的块及块内查找均采用顺序查找，假设查找表中每个记录的概率相等。怎样分块可以使得 ASL最小?并给出理由。【北京交通大学 2006四、3(5 分)】（分数：2.00）_正确答案：(正确答案：设有 n个记录，每块内有 s个记录，容易证明；当 s取 时，ASLb。取最小值 )解析：30.用分块查找法，有 2000项的表分成多少块最理想?每块的理想长度是多少?若每块长度为 25，平均查找长度是多少?【厦门大学 1999三、2(5 分)】（分数：2.00）_正确答案：(正确答案：表长 2000，分成 45块，每块的理想长度为 45(最后一块长 20)。若每块长 25，则平均查找长度为 ASL=(80+1)2+(25+1)2=535(顺序查找确定块)，或 ASL=19(折半查找确定块)。)解析：
