计算机专业基础综合数据结构集合历年真题试卷汇编2_真题(含答案与解析)-交互
- 格式：docx
- 大小：135.49 KB
- 文档页数：8
计算机专业基础综合数据结构（集合）历年真题试卷汇编2
(总分64, 做题时间90分钟)
2. 填空题
1.
对于具有144个记录的文件，若采用分块查找法，且每块长度为8，则平均查找长度为__________。【北方交通大学2001二、8】
SSS_TEXT_QUSTI
分值: 2
答案:
正确答案：14计算过程如下：144／8=18块，索引表顺序查找，故(18+1)／2+(8+1)／2=14。
2.
有一个2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是 (1)，分成 (2) 块最为理想，平均查找长度是 (3) 。【中国矿业大学2000一、6(3分)】
SSS_TEXT_QUSTI
分值: 2
答案:
正确答案：(1)45 (2)45 (3)46(索引表顺序查找)
3.
分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成__________块最好；若分成25块，其平均查找长度为__________。【北京工业大学1999一、5(2分)】
SSS_TEXT_QUSTI
分值: 2
答案:
正确答案：30，31．5(索引表顺序查找)
4.
执行顺序查找时，储存方式可以是(1)，二分法查找时，要求线性表(2)，分块查找时要求线性表(3)，而散列表的查找，要求线性表的存储方式是(4)。【山东大学1998一、1(3分)】
SSS_TEXT_QUSTI
分值: 2
答案:
正确答案：(1)顺序存储或链式存储 (2)顺序存储且有序(3)块内顺序存储，块间有序 (4)散列存储
5.
查找是非数值程序设计的一个重要技术问题，基本上分成(1)查找，(2)查找和(3)查找。处理哈希冲突的方法有(4)、(5)、(6)和(7)。【华北计算机系统工程研究所1999一(5分)】
SSS_TEXT_QUSTI
分值: 2
答案:
正确答案：(1)静态查找表 (2)动态查找表 (3)哈希表 (4)开放定址方法(5)链地址方法 (6)再哈希 (7)建立公共溢出区
6.
如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。【山东大学1999二、1(4分)】
SSS_TEXT_QUSTI
分值: 2
答案:
正确答案：（n+1)／2
7.
在含有n个结点的二叉排序树中查找一个关键字，进行关键字比较次数的最大值是__________。【北京交通大学2004一、15(2分)】
SSS_TEXT_QUSTI
分值: 2
答案:
正确答案：n
8.
在二叉排序树上成功地找到一个结点，在平均情况下的时间复杂性是：__________，在最坏情况下的时间复杂性是__________。【上海交通大学2004五、1(15／4分)】
SSS_TEXT_QUSTI
分值: 2
答案:
正确答案：O(logn)，O(n)
9.
AVL树__________是完全二叉树；完全二叉树__________是AVL树。【电子科技大学2005二、5(1分)】
SSS_TEXT_QUSTI
分值: 2
答案:
正确答案：不一定，一定。需要说明，AVL是平衡二叉树，各个结点值之间满足确定关系。从树形上看，完全二又树任意结点左右子树的高度差的绝对值不大于1。仅从结点平衡因子角度看，可以说完全二叉树是平衡二叉树。
10.
一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有__________个结点。【同济大学2005一、3(1．5分)】
SSS_TEXT_QUSTI
分值: 2
答案:
正确答案：2 k -1
11.
在一棵m阶B一树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是__________；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是__________。【中国科技大学1998一、5(3分)】【南京理工大学2001二、4(3分)】
SSS_TEXT_QUSTI
分值: 2
答案:
正确答案：m-1，[m／2]一1
12.
高度为4的3阶B一树中，最多有__________个关键字。【合肥工业大学2000三、9(2分)】
SSS_TEXT_QUSTI
分值: 2
答案:
正确答案：26(第4层是叶子，每个结点两个关键字)
13.
高为4(不含叶子层)的4阶B一树最少有__________个关键字。【北京交通大学2006二、9(2分)】
SSS_TEXT_QUSTI
分值: 2
答案:
正确答案：31
14.
高度为5的平衡二叉树，其结点数最多可以有__________个；最少可以是__________个。【中国科学技术大学1997二、5(4分)】
SSS_TEXT_QUSTI
分值: 2
答案:
正确答案：31，12
3.
判断题
1.
若装填因子α为1，则向散列表中散列元素时一定会产生冲突。( )【北京邮电大学2005二、8(1分)】
SSS_JUDGEMENT
正确 错误
分值: 2
答案:正确
解析：若装填因子α为1，再插入元素一定产生冲突。若α<1，也不能避免碰撞的产生。
2.
若散列表的负载因子α<1，则可避免碰撞的产生。( )【中国海洋大学2007二、12(1分)】【烟台大学2007二、18(1分)】
SSS_JUDGEMENT
正确 错误
分值: 2
答案:错误
3.
随着装填因子α的增大，用闭散列法解决冲突，其平均搜索长度比用开散列法解决冲突时的平均搜索长度增长得慢。( )【清华大学2002二、12(1分)】
SSS_JUDGEMENT
正确 错误
分值: 2
答案:错误
4.
在散列检索中，“比较”操作一般也是不可避免的。( )【华南理工大学2001一、4(1分)】
SSS_JUDGEMENT
正确 错误
分值: 2
答案:正确
5.
散列函数越复杂越好，因为这样随机性好，冲突概率小。( )【南京理工大学1997二、5(2分)】
SSS_JUDGEMENT
正确 错误
分值: 2
答案:错误
解析：不能说哪种哈希函数的选取方法最好，各种选取方法都有自己的适用范围。
6.
Hash表的平均查找长度与处理冲突的方法无关。( )【南京航空航天大学1997一、9(1分)】
SSS_JUDGEMENT
正确 错误
分值: 2
答案:错误
7.
负载因子(装填因子)是散列表的一个重要参数，它反映散列表的装满程度。( )【中科院软件所1999六(卜3)(2分)】【中国海洋大学2006二、13(1分)】【上海海事大学2005一、10(2分)】
SSS_JUDGEMENT
正确 错误
分值: 2
答案:正确
8.
散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。( )【中山大学1994一、8(2分)】
SSS_JUDGEMENT
正确 错误
分值: 2
答案:正确
9.
哈希表的结点中只包含数据元素自身的信息，不包含任何指针。( )【山东大学2001一、6(1分)】
SSS_JUDGEMENT
正确 错误
分值: 2
答案:错误
解析：哈希表的结点中可以包括指针，指向其元素。
10.
杂凑表的查找效率主要取决于构造杂凑表时选取的杂凑函数和处理冲突的方法。 ( )【吉林大学2007一、7(1分)】
SSS_JUDGEMENT
正确 错误
分值: 2
答案:正确
6. 综合题
将关键字序列(7，8，30，1 1，18，9，14)散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组，散列函数为：H(key)=(key×3)MOD
7，处理冲突采用线性探测再散列法，要求装填(载)因子为0．7。
SSS_TEXT_QUSTI
1.
请画出所构造的散列表。
分值: 2
答案:
正确答案：因装填(载)因子为0．7，有7个元素，故散列表长m=7／0．7=10。
构造的哈希表如下：
SSS_TEXT_QUSTI
2.
分别计算等概率情况下查找成功和查找不成功的平均查找长度。【2010年全国试题41(10分)】
分值: 2
答案:
正确答案：ASL 成功 =1／7*(1*4+2*1+3*2)==12／7ASL 失败 =1／7*(3+2+1+2+l+5+4)=18／7计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其哈希地址为i(0≤i≤m一1)时的查找次数。一般情况下分母为表长，但本例哈希地址是0～6，所以分母为7。哈希地址为i的失败比较次数是从i开始往右循环数到没有数据的位置(极端情况是表长m)。
3.
在很多查找和排序算法中，经常使用“监视哨”，其目的是什么?以顺序表上的顺序查找为例，说明如何设置“监视哨”?【江苏大学2006三、8(5分)】
