1、计算机专业基础综合数据结构（集合）历年真题试卷汇编 2 及答案与解析一、单项选择题1 对线性表进行二分查找时，要求线性表必须( )。【南京理工大学 2005 一、11(1分)】【 燕山大学 2001 一、5(2 分)】（A）以顺序方式存储（B）以顺序方式存储，且数据元素有序。（C）以链接方式存储（D）以链接方式存储，且数据元素有序2 当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )。【南京理工大学 1997 一、7(2 分)】（A）必定快（B）不一定（C）在大部分情况下要快（D）取决于表递增还是递减3 请指出在顺序有序表(2、5、7、10、
2、14、15、18、23、35、41、52)中，用“折半查找法”查找关键字 14 需做的比较次数为 ( )。【北京工业大学 2005 一、3(2 分)】（A）2（B） 3（C） 4 （D）54 折半查找有序表(5，8，10，22，36，50，53，88)，若查找元素 70，则需依次与表中元素(关键字)( )进行比较，查找结果是 “失败”。【华中科技大学 2006 一、11(2 分 )】（A）36，53（B） 22，50，53，88（C） 36，53，88 （D）22，53，885 具有 12 个关键字的有序表，折半查找的平均查找长度为( )。【中山大学。1998 二、10(2 分) 】【烟台大学
3、 2007 一、17(2 分)】（A）31（B） 4（C） 25 （D）56 对一个长度为 50 的有序表进行折半查找，最多比较( )次就能查找出结果。【北京邮电大学 2005 一、8(2 分)】（A）6（B） 7（C） 8 （D）97 折半查找有序表(2，10，25，35，40，65，70，75，81，82，88，100)，若查找元素 75，需要依次与表中元素( )进行比较。【华中科技大学 2007 一、5(2 分)】（A）65，82，75（B） 70，82，75（C） 65，81，75 （D）65，81，70，758 折半查找的时间复杂性为( )。【中山大学 1999 一、15(2 分)】
4、（A）O(n 2)（B） O(n)（C） O(nlogn)（D）O(logn)9 当采用分块查找时，数据的组织方式为( )。【南京理工大学 1996 一、7(2 分)】（A）数据分成若干块，每块内数据有序（B）数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块（C）数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块（D）数据分成若干块，每块(除最后一块外)中数据个数需相同10 对表长为 n 的有序表进行折半查找，其判定树高度为：( )。【北京交通大学2004 一、8(2 分) 】（A）log 2(n+1)（B） log2(n+1)（C）
5、log2n（D）log 2n11 顺序查找法适合于存储结构为( )的线性表。【北京航空航天大学 2002】（A）顺序存储结构或链式存储结构（B）散列存储结构（C）索引存储结构（D）压缩存储结构12 对大小均为刀的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找失败，它们的平均查找长度是(1)，对于查找成功，它们的平均查找长度是(2)。【上海海事大学 1997 二、4(3 分)】（A）相同的（B）不同的13 在下列查找方法中，平均查找速度最快的是( )。【四川大学 2005】（A）顺序查找（B）折半查找（C）分块查找（D）二叉排序树查找14 如果要求一个线性表既能较快地查找，又能适
6、应动态变化的要求，可以采用下列哪一种查找方法? ( )【北京交通大学 2005 一、3(2 分)】（A）分块（B）顺序（C）折半（D）哈希15 既希望较快地查找又便于线性表动态变化的查找方法是( )。【北方交通大学2000 二、4(2 分)2005 一、3(2 分) 】（A）顺序查找（B）折半查找（C）索引顺序查找（D）哈希法查找16 当 n 足够大时，在按值有序的顺序表中进行折半查找，在查找概率相等的情况下，其查找成功的平均查找长度是( )。【北京航空航天大学 20021（A）(n+1) 2（B） n2（C） log2(n+1)一 1 （D）log 2(n+1)17 在下述几种树中，( )
7、可以表示静态查找表。【中国科学技术大学 1995 十四、10(2 分 )】（A）次优查找树（B）二叉排序树（C） B 一树（D）平衡二又树18 以下说法正确的是( )。【北京交通大学 2006 一、4(2 分)】（A）先序遍历二叉排序树的结点就可以得到排好序的结点序列（B）任一二叉排序树的平均查找时间都小于顺序查找法查找同样结点的线性表的平均查找时间（C）对具有相同关键字集合的任一插入序列，得到的二叉排序树的形态都是相同的（D）采用分块查找方法，既能实现较快地查找线性表，又能适应动态变化的要求19 折半查找过程所对应的判定树是一棵( )。【北京交通大学 2007】（A）最小生成树（B）平衡二叉
8、树（C）完全二叉树（D）哈夫曼树20 对于二叉排序树，下面的说法( )是正确的。【华南理工大学 2006 一、5(2 分)】（A）二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合（B）对二叉排序树进行层序遍历可得到有序序列（C）用逐点插入法构造二叉排序树时，若先后插入的关键字有序，二叉排序树的深度最大（D）在二叉排序树中进行查找，关键字的比较次数不超过结点数的 1221 对动态查找有高效率的查找表组织结构是( )。【哈尔滨工程大学 2005】（A）有序表（B）分块有序表（C）循环链表（D）B 一树二、填空题22 在 n 个记录的有序顺序表中进行折半查找，最大比较次数是_
9、。【中国科技大学 1998 一、4(3 分)】23 在有序表 A112 中，采用二分查找算法查等于 A12的元素，所比较的元素下标依次为_。【中国人民大学 2001 一、2(2 分)】24 在有序表 A120 中，按二分查找方法进行查找，查找长度为 5 的元素个数是_。【合肥工业大学 1 999 三、9(2 分)】25 假定查找有序表 A112】中每个元素的概率相等，则进行二分查找时的平均查找长度为_。【东南大学 2005 数据结构部分二、10(1 分)】【燕山大学 200l 二、4(3 分) 】26 长度为 10 的按关键字有序的查找表采用顺序存储。若使用折半查找法，则在等概率情况下，查找失
10、败时的 ASL 值是_ 。【北京交通大学 2006 二、7(2分)】三、判断题27 二叉树中除叶结点外，任一结点 X，其左子树根结点的值小于该结点 (X)的值；其右子树根结点的值该结点(X)的值，则此二叉树一定是二叉排序树。 ( )【北京邮电大学 1998 一、4(2 分)】【烟台大学 2007 二、16(1 分)】（A）正确（B）错误28 在二叉排序树中插入一个新结点，总是插入到叶结点下面。( )【中国海洋大学 2003 一、5(2 分) 】（A）正确（B）错误29 N 个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。 ( )【上海交通大学 1998 一、9】【烟台大学 2007
11、 二、15(1 分)】（A）正确（B）错误30 如果完全二叉树从根结点开始按层次遍历的输入序列为1，2，3，4，5，6，7，则该完全二叉树是二叉排序树。( )【中南大学 2003 一、13(1 分 )】（A）正确（B）错误31 设有关键字 n=2n1，构成二叉排序树，每个关键字查找的概率相等，查找成功的 ASL 最大是 n。( )【北京交通大学 2005 三、6(2 分)】（A）正确（B）错误32 若把堆看成是一棵完全二叉树，则该树一定是一棵二叉排序树。( )【北京邮电大学 2005 二、9(1 分) 】（A）正确（B）错误33 中根遍历二元查找树所得序列一定是有序序列。( )【哈尔滨工业大学
12、 2002 三、8(1 分)】【中国海洋大学 2005 二、8(1 分) 】（A）正确（B）错误34 中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。( )【中科院软件所 1999 六、1-1(2 分)】（A）正确（B）错误35 对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。( )【南京理工大学 2004 二、4(1 分)】【中国海洋大学 2006 二、12(1 分) 】【江苏大学 2005 二、5(1 分)】（A）正确（B）错误36 对给定的关键字集合，以不同的次序插入初始为空的二元树中，不可能得到同一棵二元排序树。( ) 【哈尔滨工业大学
13、 2005 三、2(1 分)】（A）正确（B）错误计算机专业基础综合数据结构（集合）历年真题试卷汇编 2 答案与解析一、单项选择题1 【正确答案】 B2 【正确答案】 C3 【正确答案】 C4 【正确答案】 B5 【正确答案】 A6 【正确答案】 A【试题解析】 长度 50(315063)的有序表的判定树高度是 6，所以，最多比较 6次。7 【正确答案】 D8 【正确答案】 D9 【正确答案】 B10 【正确答案】 A【试题解析】 判定树不是完全二又树，但是 n 个结点的判定树的高度和 n 个结点的完全二叉树的高度相同。11 【正确答案】 A12 【正确答案】 B13 【正确答案】 A14 【
14、正确答案】 A15 【正确答案】 C16 【正确答案】 C17 【正确答案】 A18 【正确答案】 D19 【正确答案】 B【试题解析】 判定树和最小生成树以及哈夫曼树是不同的概念，查找长度最小，叶子结点只在最下面两层上，但不一定是完全二叉树，仅从结点的平衡因子角度看是平衡二叉树。20 【正确答案】 C21 【正确答案】 D二、填空题22 【正确答案】 log 2n+123 【正确答案】 6,9，11，1224 【正确答案】 525 【正确答案】 十二月-3726 【正确答案】 ASL 失败 =(53+64)11=3911。折半查找失败结点是判定树的外部结点，该结点不存在。计算查找次数时，和外
15、部结点对应的内部结点在查找成功时相同。例如，本题长度为 3 的外部结点有 5 个，长度为 4 的外部结点有 6 个，故得以上计算公式。三、判断题27 【正确答案】 B【试题解析】 二叉排序树除空树外，还必须具备三条：一是如有左子树，则左子树上所有结点的值要小于根结点的值；二是如有右子树，则右子树上所有结点的值要大于根结点的值；三是左右子树也是如上定义的二叉排序树。28 【正确答案】 B【试题解析】 插入结点成为叶子结点，并非都在叶子结点下面插入。29 【正确答案】 A30 【正确答案】 B31 【正确答案】 B【试题解析】 最坏是单支树的情况。最大查找长度是，2，ASL 是平均查找长度，ASL=(n+1) 2。32 【正确答案】 B33 【正确答案】 A34 【正确答案】 A35 【正确答案】 A36 【正确答案】 B【试题解析】 反例：设关键字集合是 l，2 和 3，输入 2，1，3 和输入 2，3，1 得同样的二叉排序树。
