计算机专业基础综合数据结构集合历年真题试卷汇编2

《计算机专业基础综合数据结构集合历年真题试卷汇编2》由会员分享，可在线阅读，更多相关《计算机专业基础综合数据结构集合历年真题试卷汇编2（8页珍藏版）》请在金锄头文库上搜索。

1、2计算机专业基础综合数据结构（集合）历年真题试卷汇编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答案

2、：正确答案：（1）45 （2）45 （3）46（索引表顺序查找） 3.分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成块最好；若分成25块，其平均查找长度为。【北京工业大学1999 一、5（2分）】SSS_TEXT_QUSTI 彳 I分值：2答案：正确答案：30，31. 5（索引表顺序查找） 4.执行顺序查找时，储存方式可以是（1）,二分法查找时，要求线性表（2）,分块 查找时要求线性表（3）,而散列表的查找，要求线性表的存储方式是（4）。【山 东大学1998 、1（3分）】SSS_TEXT_QUSTI = |分值：2答案：正确答案：（1）顺序存储或链式存储（2）顺序存储

3、且有序（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 呻 |分

4、值：2答案：正确答案：（n+1） /27.在含有n个结点的二叉排序树中查找一个关键字，进行关键字比较次数的最大 值是。【北京交通大学2004 、15（2分）】SSS_TEXT_QUSTI=11分值：2答案：正确答案：n8.在二叉排序树上成功地找到一个结点，在平均情况下的时间复杂性是：，在最坏情况下的时间复杂性是。【上海交通大学2004 五、1（15 / 4分）】打1SSS_TEXT_QUSTI分值：2答案：正确答案：O（logn）, 0（n） 9.AVL树是完全二叉树；完全二叉树是AVL树。【电子科技大学2005二、5（1分）】打1rLSSS_TEXT_QUSTI分值：2答案：正确答案：不一定

5、，一定。需要说明，AVL是平衡二叉树，各个结点值之间满 足确定关系。从树形上看，完全二又树任意结点左右子树的高度差的绝对值不 大于1。仅从结点平衡因子角度看，可以说完全二叉树是平衡二叉树。10.一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0,则该树共 有个结点。【同济大学2005 、3（1. 5分）】分值：2答案：正确答案：2 k -111.在一棵m阶B树中，若在某结点中插入一个新关键字而引起该结点分裂，则 此结点中原有的关键字的个数是;若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是。【中国科技大学1998 、5（3分）】【南京理工大学2001二、4（3分

6、）】A.*iin1SSS_TEXT_QUSTI分值：2答案：正确答案：m-1，m/2 112.【合肥工业大学2000rSSS_TEXT_QUSTI钉1高度为4的3阶B树中，最多有个关键字。三、9（2分）】分值：2答案：正确答案：26（第4层是叶子，每个结点两个关键字）13.高为4（不含叶子层）的4阶B 树最少有个关键字。【北京交通大学 2006 二、9（2 分）】*11SSS_TEXT_QUSTI分值：2答案：正确答案：31 14.高度为5的平衡二叉树，其结点数最多可以有个；最少可以是个。【中国科学技术大学1997二、5（4分）】SSS_TEXT_QUSTI 彳 |分值：2答案：正确答案：31

7、，123.判断题1.若装填因子a为1,则向散列表中散列元素时一定会产生冲突。（）【北京 邮电大学2005二、8（1分）】SSS_JUDGEMENT正确错误分值：2答案:正确解析：若装填因子a为1,再插入元素一定产生冲突。若a1，也不能避免碰 撞的产生。2.若散列表的负载因子a1，则可避免碰撞的产生。（）【中国海洋大学2007 二、12（1分）】【烟台大学2007二、18（1分）】SSS_JUDGEMENT正确错误分值：2答案:错误3.随着装填因子a的增大，用闭散列法解决冲突，其平均搜索长度比用开散列法 解决冲突时的平均搜索长度增长得慢。（）【清华大学2002 二. 12（1分）】SSS_JUD

8、GEMENT正确错误分值：2答案:错误4.在散列检索中，“比较”操作一般也是不可避免的。（）【华南理工大学2001 、4（1 分）】SSS_JUDGEMENT正确错误分值：2答案:正确5.散列函数越复杂越好，因为这样随机性好，冲突概率小。（）【南京理工大 学 1997 二、5（2 分）】SSS_JUDGEMENT正确错误分值：2答案:错误解析：不能说哪种哈希函数的选取方法最好，各种选取方法都有自己的适用范 围。6.Hash表的平均查找长度与处理冲突的方法无关。（）【南京航空航天大学 1997 、9（1 分）】SSS_JUDGEMENT正确错误分值：2答案:错误7.负载因子（装填因子）是散列表的

9、一个重要参数，它反映散列表的装满程度。（）【中科院软件所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.

10、杂凑表的查找效率主要取决于构造杂凑表时选取的杂凑函数和处理冲突的方 法。（）【吉林大学2007 、7（1分）】SSS_JUDGEMENT正确错误分值：2答案:正确6. 综合题将关键字序列（7, 8, 30, 1 1, 18, 9, 14）散列存储到散列表中，散列表的存 储空间是一个下标从0开始的一维数组，散列函数为：H（key） = （keyX3）MOD7, 处理冲突采用线性探测再散列法，要求装填（载）因子为0. 7。SSS_TEXT_QUSTI1.请画出所构造的散列表。厶打1分值：2答案：正确答案：因装填（载）因子为0. 7,有7个元素，故散列表长m=7/0. 7=10。SSS_TEXT_Q

11、USTI2.分别计算等概率情况下查找成功和查找不成功的平均查找长度。【2010年全国 试题41（10分）】答案：正确答案：ASL、工=1/7*（1 *4+2*1+3*2）=12/7ASL=1 /7* （3+2+1+2+l+5+4）=18 / 7计算查找失败时的平均查找长度，必须计算不在表 中的关键字，当其哈希地址为i （0WiWm 1）时的查找次数。一般情况下分母 为表长，但本例哈希地址是06,所以分母为7。哈希地址为i的失败比较次 数是从i开始往右循环数到没有数据的位置（极端情况是表长m）。3.在很多查找和排序算法中，经常使用“监视哨”，其目的是什么？以顺序表上的 顺序查找为例，说明如何设置

12、“监视哨”？【江苏大学2006三、8（5分）】答案：正确答案：监视哨的作用是免去查找过程中每次都要检测整个表是否查找完 毕，提高了查找效率。顺序表上顺序查找时监视哨可以设在低端（下标0）或高 端（下标n+1）。4.采用比较的方法，从具有n个元素集合中找出最大和次最大的元素，需要的最 少比较次数为多少?说明理由和实现的方法。【上海交通大学2003 七（10分）】SSS_TEXT_QUSTI 坤 |分值：2答案：正确答案：使用堆，选最大元素最多比较不超过4n次，再选次大元素用logn 次。5.在长度为n的线性表中进行顺序查找。查找第i个数据元素的概率为p i ,且A.打i1SSS_TEXT_QUS

13、TI分布如下n的简单表达式形式）。【北京航空航天大学2007 、4（5分）】分值：2答案：正确答案:6.对于一个有序顺序表来说，折半查找是否任何时候都比顺序查找快?为什么?【上海交通大学2005三（6分）】A*iinSSS_TEXT_QUSTI分值：2答案：正确答案：并非在任何情况下折半查找都比顺序查找快。例如，若待查元素是 该顺序表的第一个元素，则顺序查找顺序表会更快。对有序顺序表采用顺序查 找，若元素存在表中，则在任一位置，查找都可能成功。同样，若元素不在表 中，则在任一位置，查找都可能结束。折半查找必须经一系列计算，方知查找 成功还是失败。尽管如此，一般说来，在大多数情况下，折半查找还是

14、比顺序 查找快。7.对长度为101的表进行分块查找，确定所在的块及块内查找均采用顺序查找， 假设查找表中每个记录的概率相等。怎样分块可以使得ASL最小?并给出理由。【北京交通大学2006四、3（5分）】分值：2答案：正确答案：设有n个记录，每块内有s个记录，容易证明；当s取时，ASLb。取最小值。本题每块长度为10（说明，本题每块长度10或11均可，对索引表和块内均采用顺序查找，平均查找长度相同）。8.用分块查找法，有2000项的表分成多少块最理想?每块的理想长度是多少?若每 块长度为25，平均查找长度是多少？【厦门大学1999三、2（5分）】*iin1SSS_TEXT_QUSTI分值：2答案：正确答案：表长2000，分成45块，每块的理想长度为45（最后一块长20）。若 每块长25,则平均查找长度为ASL=（80+1）/ 2+（25+1）/ 2=53. 5（顺序查找确定 块），或ASL=19（折半查找确定块）。