西交《数据结构》在线作业答卷

西交《数据结构》在线作业-00002

试卷总分：100得分：100

一、单选题(共30道试题，共60分)

1.用链表表示线性表的优点是()

A.便于随机存取

B.花费的存储空间比顺序表少

C.便于插入与删除

1).数据元素的物理顺序与逻辑顺序相同

答案:C

2.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾

指针，则执行出队操作后其头指针front值为()

A.front=front+l

B.front=(front+1)%(m-1)

C.front=(front-1)%m

D.front=(front+1)%m

答案:D

3.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用()

查找方法。

A.分块

B.顺序

C.二分

1).散列

答案:A

4.设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构，则该哈夫曼树

中总共有()个空指针域。

A.2m-1

B.2m

C.2m+l

D.4m

答案:B

5.求字符串T在字符串S中首次出现的位置的操作称为()。

A.串的模式匹配

B.求子串

C.求串的长度

D.串的连接

答案:A

6.哈希表的平均查找长度是()的函数。

A.哈希表的长度

B.表中元素的多少

C.哈希函数

1).哈希表的装满程度

答案:D

7.设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R,头指针F总是指向

队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中

的元素个数为()

A.R-F

B.F-R

C.(R-F+M)%M

D.(F-R+M)%M

答案:C

8.设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是()。

A.head==O

B.head->next==O

C.head->next==head

D.head!=O

答案:A

9.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为()。

A.n

B.e

C.2n

D.2e

答案：D

10.设某完全无向图中有n个顶点，则该完全无向图中有()条边。

A.n(n-l)/2

B.n(n-l)

C.n

D.n-1

答案:A

11.一个有序表为｛1,3,9,12,32,41,45,62,75,77,82,95,100),当二

分查找值为82的结点时，()次比较后查找成功。

A.2

B.3

C.4

D.5

答案:C

12.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为()。

A.0(n)

B.0(n*2)

C.0(n"3)

D.0(log2n)

答案:A

13.执行一趟快速排序能够得到的序列是()。

A.[41,12,34,45,27]55[72,63]

B.[45,34,12,41]55[72,63,27]

C.[63,12,34,45,27]55[41,72]

D.[12,27,45,41]55[34,63,72

答案:A

14.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选()排序为

宜。

A.直接插入

B.直接选择

C.堆

D.快速

答案:A

15.一个枝的输入序列为123…n,若输出序列的第一个元素是n,输出第i(K=i<=n)

个元素是()。

A.不确定

B.n-i+l

C.i

D.n-i

答案:B

16.设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是

A.空或只有一个结点

B.高度等于其结点数

C.任一结点无左孩子

D.任一结点无右孩子

答案:D

17.一个具有n个顶点的无向图最多有()条边。

A.nX(n-l)/2

B.nX(n-1)

C.nX(n+l)/2

D.n2

答案:A

18.设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历该

二叉树得到序列为()

A.BADC

B.BCDA

C.CDAB

D.CBDA

答案:A

19.设一组初始记录关键字的长度为8,则最多经过()趟插入排序可以得到有序

序列。

A.6

B.7

C.8

D.9

答案:B

20.存放循环队列元素的数组data有10个元素，则data数组的下标范围是()。

A.0-10

B.0~9

C.1〜9

D.1~10

答案:B

21.空串与空格字符组成的串的区别是().

A.没有区别；

B.两串的长度不等；

C.两串的长度相等；

D.两串包含的字符不相同。

答案:B

22.在二叉排序树中插入一个结点的时间复杂度为()。

A.0(1)

B.0(n)

C.0(log2n)

D.0(n)

答案:B

23.在序列(2,5,8,11,15,16,22,24,27,35,50)中采用折半查找(二分

查找)方法查找元素24,需要进行()次元素之间的比较。

A.3

B.4

C.8

D.11

答案:B

24.设某棵三叉树中有40个结点，则该三叉树的最小高度为()。

A.3

B.4

C.5

D.6

答案:B

25.由两个栈共享一个向量空间的好处是：()

A.减少存取时间，降低下溢发生的机率

B.节省存储空间，降低上溢发生的机率

C.减少存取时间，降低上溢发生的机率

D.节省存储空间，降低下溢发生的机率

答案:B

26.时间复杂度不受数据初始状态影响而恒为0(nlog2n)的是()。

A.堆排序

B.冒泡排序

C.希尔排序

D.快速排序

答案:A

27.设用链表作为栈的存储结构则退栈操作()

A.必须判别栈是否为满

B.必须判别栈是否为空

C.判别栈元素的类型

D.对栈不作任何判别

答案:B

28.设顺序表的长度为n,则顺序查找的平均比较次数为()。

A.n

B.n/2

C.(n+l)/2

D.(n-l)/2

答案:C

29.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓

冲区，主机将要输出的数据依次写入该缓冲区，打印机依次从该缓冲区中取出数

据打印，则该缓冲区的结构应该是()。

A.线性表

B.数组

C.堆栈

D.队列

答案:D

30.广度优先遍历类似于二叉树的()o

A.先序遍历

B.中序遍历

C.后序遍历

D.层次遍历

答案:D

二、判断题(共20道试题，共40分)

31.中序遍历一棵二叉排序树可以得到一个有序的序列。

答案:正确

32.子串“ABC”在主串“AABCABCD”中的位置为3。

答案:错误

33.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能

存在的块号，然后再在相应的块内进行顺序查找。

答案:正确

34.为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。

答案:正确

35.在B+树中查找和在B-树中查找的过程完全相同。()

答案:错误

36.栈的特点是“后进先出”。()

答案:正确

37.不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复

杂度均为0(n)«

答案:正确

38.设串S的长度为n,则S的子串个数为n(n+l)/2。

答案:错误

39.设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。

()

答案:正确

40.由树转化成二叉树，该二叉树的右子树不一定为空。()

答案:错误

41.磁带是顺序存取的外存储设备。

答案:正确

42.调用一次深度优先遍历可以访问到图中的所有顶点。

答案:错误

43.希尔排序算法的时间复杂度为0(n2),

答案:错误

44.二维数组和多维数组均不是特殊的线性结构。

答案:错误

45.层次遍历初始堆可以得到一个有序的序列