计算机专业基础综合（查）-试卷1
(总分：94.00，做题时间：90分钟)
一、 单项选择题(总题数：25，分数：50.00)
1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。
__________________________________________________________________________________________
2.若查每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查法查一个记录，其平均查长度ASL为( )。
 A.(n—1)／2
 B.n／2
 C.(n+1)／2 √
 D.n
此题考查的知识点是顺序查长度ASL的计算。假设表长度为n，那么查第i个数据元素需进行n一i+1次比较，即C i =n一i+l。又假设查每个数据元素的概率相等，即P i =1／n，则顺序查算法的平均查长度为： 所以应选C。
3.顺序查法适用于查顺序存储或链式存储的线性表二分法查只适用于查顺序存储的有序表，平均比较次数为( )。在此假定N为线性表中结点数，且每次查拔都是成功的。
 A.N+1
 B.2log 2 N
 C.log 2 N √
 D.N／2
此题考查的知识点是各类查算法的比较次数计算。顺序查法用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败，其ASL=(n+1)／2，即查成功时的平均比较次数约为表长的一半。应选C。
4.顺序查法适用于查顺序存储或链式存储的线性表，平均比较次数为( )在此假定N为线性表中结点数，且每次查拔都是成功的。
 A.N+1
 B.2log 2 N
 C.log 2 N
 D.N／2 √
二分法查过程可用一个称为判定树的二叉树描述，由于判定树的叶子结点所在层次之差最多为1，故n个结点的判定树的深度与n个结点的完全二叉树的深度相等，均为[log 2 n]+1。这样，折半查成功时，关键字比较次数最多不超过[log 2 n]+1。所以，应选择D。
5.适用于折半查的表的存储方式及元素排列要求为( )。
 A.链接方式存储，元素无序
 B.链接方式存储，元素有序
 C.顺序方式存储，元素无序
 D.顺序方式存储，元素有序 √
此题考查的知识点是折半查的特点。折半查要求顺序存储且元素有序，所以应选D。
6.具有12个关键字的有序表，折半查的平均查长度为( )。
 A.3．1 √
 B.4
 C.2．5
 D.5
此题考查的知识点是折半查的思想。把关键字按完全二叉树的形式画出查树，按结点高度计算比较次数。12个结点可以画出高度为4的完全二又树，1层1个结点比较1次，2层2个结点比较2次，3层4个结点比较3次，4层5个结点比较4次，37／12≈3．1，应选A。
7.折半查的时间复杂性为( )。
 A.O(n 2 )
 B.O(n)
 C.O(nlog 2 n)
 D.O(log 2 n) √
此题考查的知识点是折半查的效率。其查效率与比较次数有关，折半查成功时，关键字比较次数最多不超过[log 2 n]+1，所以其效率为O(log 2 n)，应选D。
8.当采用分块查时，数据的组织方式为( )。
 A.数据分成若干块，每块内数据有序
 B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块 √
 C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块
 D.数据分成若干块，每块(除最后一块外)中数据个数需相同
分块查是将数据分成若干块，块间有序，块内不必有序。
9.下面函数的功能是实现分块查，空白处应该添加的内容是( )。 int BlkSearch(int*nz，int key，int block，int BLK，int len) { int i； block=block-1； if(1en<=0) { puts(”表为空!")； return 0： } if(BLK>len)BLK=len； for(i=block*BLK；i
&[i]==key √
&[i]==BLK
&[i]==block
&[i]==0
如果当前的值与所查关键字相等，则完成查。
10.二叉查树的查效率与二叉树的( )有关。
 A.高度
 B.结点的多少
 C.树形 √
 D.结点的位置
二叉查树的查效率与树形有关，当结点呈单枝树排列时效率最低。
11.二叉查树的查效率，在( )时其查效率最低。
 A.结点太多
 B.完全二叉树
 C.呈单枝树 √
 D.结点太复杂
12.在一棵高度为h的理想平衡二叉树中，最少含有( )个结点，最多含有( )个结点。
 A.2 h 2 h-1
 B.2 h-1 2 h
 C.2 h +1 2 h 一1
 D.2 h-1 2 h 一1 √
由平衡二叉树的特性可知，一棵高度为h的理想平衡二叉树中，含有结点数最少的情形是：前h一1层为满二叉树，第h层只有一个结点，因而结点总数为(2 h-1 一1)+1=2 h-1 。 含有结点数最多的情形是：该树是一棵高度为^的满二叉树，因而结点总数为2 h-1 。
13.分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是( )。
 A.(100，80，90，60，120，110，130)
 B.(100，120，110，130，80，60，90)
 C.(100，60，80，90，120，110，130) √
 D.(100，80，60，90，120，130，110)
分别根据给出的序列构建平衡二叉树，得出C与其他不同。
14.关于B-树，下列说法中不正确的是( )。
 A.B-树是一种查树
 B.所有的叶结点具有相同的高度
 C.2-3树中，所有非叶子结点有1或者3个孩子结点 √
 D.通常情况下，B-树不是二叉树
B-树定义如下： 一棵m阶B-树，或者是空树，或者是满足以下性质的m叉树： (1)根结点或者是叶子，或者至少有两棵子树，至多有m棵子树。 (2)除根结点外，所有非终端结点至少有[m／2]棵子树，至多有m棵子树。 (3)所有叶子结点都在树的同一层上。 (4)每个结点应包含
如下信 息：(n，A 2 ，K 1 ，A 1 ，K 2 ，A 2 ，…，K n ，A n )。 其中： K i (1≤i≤n)是关键字，且K＜K i+1 (1≤i≤n一1)； A i (i=0，1，…，n)为指向孩子结点的指针，且A i-1 所指向的子树中所有结点的关键字都小于K i ，A i 所指向的子树中所有结点的关键字都大于K i 。 n是结点中关键字的个数，且[m／2]一1≤n≤m一1，n+1为子树的棵数。
15.在含有15个结点的平衡二叉树上，查关键字为28(存在该结点)的结点，则依次比较的关键字有可能是( )。
 A.30，36
 B.38，48，28
 C.48，18，38，28 √
 D.60，30，50，40，38，36
设N i 表示深度为h的平衡二叉树中含有的最少结点数，有： N 0 =0，N 1 =1，N 2 =2； 计算的公式为： N h =N h-1 +N h-2 +1； N 3 =N 2 +N 1 +1=4； N 4 =N 3 +N 2 +1=7； N 5 =
N 4 +N 3 +1=12； N 6 =N 5 +N 4 +1=20＞15。 也就是说，高度为6的平衡二叉树最少有20个结点，因此15个结点的平衡二叉树的高度为5，而最小叶子结点的层数为3，所以选项D错误。 选项A在查30后，指针应该指向左孩子，而不是右孩子；选项B与选项A存在同样的问题，因而选项A、B错误。而选项C的查路径如下图所示：
16.下面关于m阶B树的说法中，正确的是( )。 ①每个结点至少有两棵非空子树。 ②树中每个结点至多有m-1个关键字。 ③所有叶子在同一层上。 ④当插入一个数据项引起B树结点分裂后，树长高一层。
 A.①②③
 B.②③
 C.②③④
 D.③ √
根据B树定义可知只有③正确。
17.下面关于B和B+树的叙述中，不正确的是( )。
 A.B树和B+树都是平衡的多又树
 B.B树和B+树都可用于文件的索引结构
 C.B树和B+树都能有效地支持顺序检索 √
 D.B树和B+树都能有效地支持随机检索
此题考查的知识点是B-树和B+树的定义。B-树定义见第11题，B+树是应文件系统所需而发展出的一种B-树的变形树。一棵m阶的B+树和m阶的B-树的差异在于： (1)有n棵子树的结点中含有n个关键字。 (2)所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。 (3)所有的非终端结点可以看成是索引部分，结点中仅含其子树(根结点)中的最大(或最小)关键字。通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。所以B+树能有效地支持随机检索和顺序检索。显然应选C。
二叉树公式
18.m阶B-树是一棵( )。
 A.m叉排序树
 B.m 叉平衡排序树 √
 C.m-1叉平衡排序树
 D.m+1叉平衡排序树
此题考查的知识点是m阶B-树的定义。B-树是一种平衡的多路排序树，m阶即m叉。应选B。
19.若对有18个元素的有序表做二分查，则查A[3]的比较序列的下标为( )。
 A.1，2，3
 B.9，4，2，3
 C.10，5，3
 D.9，2，3 √
二分查判定树如下图所示，查A[3]的比较序列的下标为9，4，2，3，本题选D。
20.有一个有序表{1，3，9，12，32，41，45，62，75，77，82，95，100}，当用二分查法查值为82的结点时，经( )次比较后查成功。
 A.1
 B.2
 C.4 √
 D.8
n=13，R[11]=82，第1次与R[(1+13)／2=7]=45比较，第2次与R[(8+13)／2=10]=77比较，第3次与R[(11+13)／2=12]=95比较，第4次与R[(10+12)／2=11]=85比较时成功，总共比较4次。
21.采用分块查时，若线性表中共有625个元素，查每个元素的概率相同，假设采用顺序查来确定结点所在的块，则每块分为( )个结点最佳。
 A.9
 B.25 √
 C.6
 D.625
分块查时最佳块数为=25。
22.在有n个结点且为完全二叉树的二叉排序树中查一个键值，其平均比较次数的数量级为( )。
 A.O(n)
 B.O(log 2 n) √
 C.O(nlog 2 n)
 D.O(n 2 )
有n个结点且为完全二叉树的二叉排序树的高度为log 2 n。
23.对包含n个关键码的散列表进行检索，平均检索长度为( )。
 A.O(log 2 n)
 B.O(n)
 C.O(nlog 2 n)
 D.不直接依赖于n √
对散列表进行检索，平均检索长度仅与装填因子α有关，而与关键字个数n无关。
24.在散列表上，每个地址单元所链接的同义词表的( )。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。