[考研类试卷]计算机专业基础综合(查找)模拟试卷2.doc

[考研类试卷]计算机专业基础综合（查找）模拟试卷2

一、单项选择题

1-40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

1 若查找每个记录的概率均等，则在具有凡个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。

（A）(n一1)／2

（B）n／2

（C）(n+1)／2

（D）n

2 顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( (1) )，二分法查找只适用于查找顺序存储的有序表，平均比较次数为( (2) )。在此假定N为线性表中结点数，且每次查找都是成功的。

（A）N+1 N2

（B）2log2N Nlog2N

（C）N／2 log2N

（D）N Nlog2

3 适用于折半查找的表的存储方式及元素排列要求为( )。

（A）链接方式存储，元素无序

（B）链接方式存储，元素有序

（C）顺序方式存储，元素无序

答案见麦多课文库

（D）顺序方式存储，元素有序

4 具有12个关键字的有序表，折半查找的平均查找长度为( )。

（A）3．1

（B）4

（C）2．5

（D）5

5 折半查找的时间复杂性为( )。

（A）O(n2)

（B）O(n)

（C）O(nlog2n)

（D）O(log2n)

6 当采用分块查找时，数据的组织方式为( )。

（A）数据分成若干块，每块内数据有序

（B）数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块

（C）数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块

（D）数据分成若干块，每块(除最后一块外)中数据个数需相同

7 下面函数的功能是实现分块查找，空白处应该添加的内容是( )。 int BlkSearch(int*nz，int key，int block，int BLK，int len) {

答案见麦多课文库

int i；

block=block-1； if(len<=0) {

puts(“表为空！”)； return 0：

}

if(BLK>len)BLK=len；

for(i=block*BLK；i<(block+1)*BLK&&nz[i]！=0；i++) {

if(___________) {

printf(“找到第％d个数是％d＼n”，i，key)； return 0： } }

printf(“＼n”)；

printf(“查找结束＼n”)； return 0； }

（A）nz[i]==key

（B）nz[i]==BLK

（C）nz[i]==block

（D）nz[i]==0

8 二叉查找树的查找效率与二叉树的( (1) )有关，在( (2) )时其查找效率最低。

（A）高度 结点太多

（B）树形 呈单枝树

答案见麦多课文库

（C）结点的多少 完全二叉树

（D）结点的位置 结点太复杂

9 在一棵高度为h的理想平衡二叉树中，最少含有( )个结点，最多含有( )个结点。

（A）2h 2h-1

（B）2h一1 2h

（C）2h+1 2h一1

（D）2h-1 2h一1

10 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是( )。

（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)

11 关于B-树，下列说法中不正确的是( )。

（A）B-树是一种查找树

（B）所有的叶结点具有相同的高度

（C）2-3树中，所有非叶子结点有1或者3个孩子结点

（D）通常情况下，B一树不是二叉树

答案见麦多课文库