当前位置：文档库 › 2012计算机本科数据结构与算法单选题题库4

2012计算机本科数据结构与算法单选题题库4

Title AnswerA AnswerB AnswerC AnswerD

1.顺序存储的表中有90000个元素，已按关键字值升序排列，假设对每个元素进行查找的概率相同，且每个元素的关键字值皆不相同，用顺序查找法查找时，需平均比较的次数为( )。A．25000 B. 30000 C. 45000 D. 90000

2.分块查找方法将表分为多块，并要求（）A．块内有

序B.块间有

序

C.链式存

储

D.链式存

储

3.设有一组关键字(19,14,23,1，6，20,

4，27,5，11,10,9)，用散列函数

H(key)=key%13构造散列表，用拉链法解决冲

突，散列地址为1的链中记录个数为（）。

A．1 B.2 C. 3 D. 4

4.一个有序表为(1，3，9，12，32，41，45，

62，75，77，82，95，100)，当采用折半查找

方法查找值32时，查找成功需要的比较次数是

（）。

A．2 B. 3 C. 4 D. 8

5.某索引顺序表共有元素395个，平均分成5块

。若先对索引表采用顺序查找，再对块中元素

进行顺序查找，则在等概率情况下，分块查找

成功的平均查找长度是（）

A．43 B.79 C. 198 D.200

6．在含有10个关键字的3阶B-树中进行查找，

至多访问的结点个数为（）。

A．2B．3C．4D．5

7．设散列表长m=14,散列函数H（K）=K％11，

已知表中已有4个结点：r(15)=4;r(38)=5;

r(61)=6;r(84)=7，其他地址为空，如用二次探

测再散列处理冲突，关键字为49的结点地址是

（）。

A．8 B. 3 C. 5 D. 9

8对于哈希函数H(key)=key MOD13，被称为同

义词的关键字是（）。

A．35和41 B. 23和39 C. 15和44 D. 25和51

9．从二叉排序树中查找一个元素时，其时间复杂度大致为（）A．O(n) B. O(1) C.O(log2n

)

D. O(n2)

10．若在查找的同时对表进行增、删工作，这种查找称为（）。A．内

查B．外查找C．静态查

找

D．动态查

找

11．当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（）。A. 必定快 B. 不一定 C.在大部

分情况下

要快

D.取决于

表递增还

是递减

12．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。A．20，

70，30，

B．30，

88，70，

C．20，50D．30，

88，50

13.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）。A．

（100，

80，90，

60，

120，

110，

130）

B．

（100，

60，80，

90，

120，

110，

130）

C．

（100，

120，

110，

130，80，

60， 90）

D．(100，

80，60，

90，

120，

130，110)

14.下面关于哈希查找的说法，正确的是（）。A．哈希函

数构造的

越复杂越

好，因为

这样随机

性好，冲

突小

B.除留余

数法是所

有哈希函

数中最好

的

C.不存

在特别好

与坏的哈

希函数，

要视情况

而定

D.哈希表

的平均查

找长度有

时也和记

录总数有

关

15．在平衡二叉树中插入一个结点后造成了不

平衡，设最低的不平衡结点为A，并已知A的左

孩子的平衡因子为0右孩子的平衡因子为1，则

应作（）型调整以使其平衡。

A．LL B．LR C．RL D．RR

16.用二分（对半）查找表的元素的速度比用顺序法( )A．必然快 B. 必然慢 C. 相等 D.不能确

定

17.具有12个关键字的有序表，折半查找的平

均查找长度（）.

A．3.1 B. 4 C. 2.5 D. 5

18.哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行( )次探测。A．k B. k+1 C.

k(k+1)/2

D.1+k(k+1

)/2

19.m阶B-树是一棵( )A．m叉排

序树B.m叉平

衡排序树

C.m-1叉

平衡排序

树

D.m+1叉

平衡排序

树

20.下面关于m阶B树说法正确的是()

①每个结点至少有两棵非空子树；②树中每个结点至多有m一1个关键字;

③所有叶子在同一层上;④当插入一个数据项引起B树结点分裂后，树长高一层。A．①②

③

B. ②③

C. ②③④

D. ③

21．从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（）。A．插入排

序

B．归并排

序

C．冒泡排

序

D．选择排

序

22．从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。A.归并排

序

B.冒泡排

序

C.插入排

序

D.选择排

序

23．对n个不同的关键字由小到大进行冒泡排序，在下列（）情况下比较的次数最多。A．从小到

大排列好

的

B．从大到

小排列好

的

C．元素无

序

D．元素基

本有序

24.对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（）。A．n(n-

1)/2

B．n+1C． n D．n-1

25.若一组记录的排序码为（46,79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。A．38，

40，46，

56，79，

B．40，

38，46，

56，79，

C．40，

38，46，

79，56，

D．40，

38，46，

84，56，

26.下列关键字序列中，（）是堆。A．16，

72，31，

23，94，

53B．94，

23，31，

72，16，

C．16，

23，53，

31，94，

D.16，

53，23，

94，31，

27．堆的形状是一棵（）。A．二叉排

序树B．完全二

叉树

C．满二叉

树

D．平衡二

叉树

28.下述几种排序方法中，要求内存最大的是（）。A．归并排

序

B．希尔排

序

C．快速排

序

D．堆排序

29．下述几种排序方法中，（）是稳定的排序方法。A．希尔排

序

B．快速排

序

C．归并排

序

D．堆排序

30．下列排序算法中，（）不能保证每趟排序至少能将一个元素放到其最终的位置上。A.希尔排

序

B.快速排

序

C.冒泡排

序

D.堆排序

31．若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（）。A．79，

46，56，

38，40，

B．84，

79，56，

46，40，

C．84，

56，79，

40，46，

D．84，

79，56，

38，40，

32．某内排序方法的稳定性是指( )。 A.该排序

算法不允

许有相同

的关键字

记录B.该排序

算法允许

有相同的

关键字记

录

C.平均时

间为0（n

log n）的

排序方法

D.前面

三个都不

正确

33．比较次数与排序的初始状态无关的排序方法是( )。A．直接插

入排序

B．起泡排

序

C．快速排

序

D．简单选

择排序

34．数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的()的两趟排序后的结果。A．选择排

序

B．冒泡排

序

C．插入排

序

D．堆排序

35.对一组数据（84，47，25，15，21）排

序，数据的排列次序在排序的过程中的变化为

（1）8447251521（2）15472584

21（3）1521258447（4）152125

47 84

则采用的排序是 ( )。

A．选择B．冒泡C．快速D．插入

36.对序列{15，9，7，8，20，-1，4}进行排

序，进行一趟后数据的排列变为{4，9，-1，

8，20，7，15}；则采用的是（）排序。

A．选择B．快速C．希尔D．冒泡

37.下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。A. 堆排序 B.冒泡排

序

C.快速

排序

D.插入排

序

38.直接插入排序在最好情况下的时间复杂度为（）。A.

O(logn)

B. O(n)

O(n*logn)

D. O(n2)

39.若用冒泡排序方法对序列

{10,14,26,29,41,52}从大到小排序，需进行

（）次比较。

A. 3

B. 10

C. 15

D. 25

40.对序列{15，9，7，8，20，-1，4，}用希

尔排序方法排序，经一趟后序列变为{15，-l，

4，8，20，9，7}则该次采用的增量是()

。

A. 1

B.4

C.3

D.200

41 .稳定的排序方法是（）。 A.直接插

入排序和

快速排序B.折半插

入排序和

起泡排序

C.简单选

择排序和

四路归并

排序

D.树形选

择排序和

shell排序

42.用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（）。A.

94,32,40,

90,80,46,

21,69

32,40,21,

46,69,94,

90,80

21,32,46,

40,80,69,

90,94

90,69,80,

46,21,32,

94,40

43.对下列关键字序列用快速排序法进行排序时，速度最快的情形是（）。A.

{21,25,5,

17,9,23,3

B.{25,23,

30,17,21,

5,9}

C.{21,9,1

7,30,25,2

3,5}

{5,9,17,2

1,23,25,3

44.有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（）A.-1，

4，8，9，

20，7，

15，7

B.-1，7，

15，7，

4，8，

20，9

C.-1，4，

7，8，

20，15，

7，9

D.A，B，C

均不对。

45.就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是　（）.A.堆排序

〈快速

排序〈归

并排序

B.堆排序

〈归并

排序〈快

速排序

C.堆排序

〉归并排

序〉快速

排序

D.堆排序

>快速排

序>归并

排序

46.已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。

#define N /*学生人数*/

int uprx(int a[N],int x)/*函数返回大于等于X分的学生人数*/

{ int head=1,mid,rear=N;

do {mid=(head+rear)/2;

if(x<=a[mid]) __(1)__ else __(2)__;

}while(__(3)__);

if (a[head]

return head; } 第（1）个空填：A.

rear=mid-

B.rear=mi

d+1

head=mid-

D.head=mi

d+1

47.已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。

#define N /*学生人数*/

int uprx(int a[N],int x)/*函数返回大于等于X分的学生人数*/

{ int head=1,mid,rear=N;

do {mid=(head+rear)/2;

if(x<=a[mid]) __(1)__ else __(2)__;

}while(__(3)__);

if (a[head]

return head; } 第（2）个空填：A.

rear=mid-

B.rear=mi

d+1

head=mid-

D.head=mi

d+1

48.已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。

#define N /*学生人数*/

int uprx(int a[N],int x)/*函数返回大于等于X分的学生人数*/

{ int head=1,mid,rear=N;

do {mid=(head+rear)/2;

if(x<=a[mid]) __(1)__ else __(2)__;

}while(__(3)__);

if (a[head]

return head; } 第（3）个空填：A.head>re

B.head>=r

ear

C.head

D.head<=r

ear

Answer C

C C

D A C B B

A D

B A

C B A C A

D D D C A

C D B

B B

C A C A A