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

试卷总分:100 得分:100

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

1.用链表表示线性表的优点是（）

A.便于随机存取

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

C.便于插入与删除

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

2.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）

A.front=front+1

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

C.front=(front-1)%m

D.front=(front+1)%m

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

A.分块

B.顺序

C.二分

D.散列

4.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。

A.2m-1

B.2m

C.2m+1

D.4m

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

A.串的模式匹配

B.求子串

C.求串的长度

D.串的连接

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

A.哈希表的长度

B.表中元素的多少

C.哈希函数

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

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

A.head==0

B.head->next==0

C.head->next==head

D.head!=0

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

A.n

B.e

C.2n

D.2e

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

A.n(n-1)/2

B.n(n-1)

C.n

D.n-1

11.一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，（ ）次比较后查找成功。

A.2

B.3

C.4

D.5

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

A.O(n)

B.O(n^2)

C.O(n^3)

D.O(1og2n)

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

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

A.直接插入

B.直接选择

C.堆

D.快速

15.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。

A.不确定

B.n-i+1

C.i

D.n-i

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

A.空或只有一个结点

B.高度等于其结点数

C.任一结点无左孩子

D.任一结点无右孩子

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

A.n×(n-1)/2

B.n×(n-1)

C.n×(n+1)/2

D.n2

18.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）

A.BADC

B.BCDA

C.CDAB

D.CBDA

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

A.6

B.7

C.8

D.9

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

A.0～10

B.0～9

C.1～9

D.1～10

21.空串与空格字符组成的串的区别是（ ）。

A.没有区别；

B.两串的长度不等；

C.两串的长度相等；

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

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

A.O(1)

B.O(n)

C.O(log2n)

D.O(n)

23.在序列（2，5，8，11，15，16，22，24，27，35，50）中采用折半查找（二分查找）方法查找元素24，需要进行（ ）次元素之间的比较。

A.3

B.4

C.8

D.11

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

A.3

B.4

C.5

D.6

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

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

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

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

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

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

A.堆排序

B.冒泡排序

C.希尔排序

D.快速排序

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

A.必须判别栈是否为满

B.必须判别栈是否为空

C.判别栈元素的类型

D.对栈不作任何判别

28.设顺序表的长度为n，则顺序查找的平均比较次数为（）。

A.n

B.n/2

C.(n+1)/2

D.(n-1)/2

29.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，打印机依次从该缓冲区中取出数据打印，则该缓冲区的结构应该是（ ）。

A.线性表

B.数组

C.堆栈

D.队列

30.广度优先遍历类似于二叉树的（ ）。

A.先序遍历

B.中序遍历

C.后序遍历

D.层次遍历

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

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

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

33.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。

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

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

36.栈的特点是“后进先出”。（ ）

37.不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O（n）。

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

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

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

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

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

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

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

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

46.从本质上看,文件是一种非线性结构。

47.设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。

48.{图}

49.对连通图进行深度优先遍历可以访问到该图中的所有顶点。

50.完全二叉树中的叶子结点只可能在最后两层中出现。（ ）