东北大学21年12月考试《数据结构ⅡX》复习题.doc

PAGE

PAGE1/NUMPAGES4

PAGE1/NUMPAGES4

东北大学继续教育学院

数据结构IIX复习题

单选题

1．表达式a*(b+c)-d的后缀表达式是

A．abcd*+-B．abc*+d-

C．abc+*d-D．-+*abcd

2．某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是

A.空或只有一个结点B.高度等于其结点数

C.任一结点无左孩子D.任一结点无右孩子

3．下面的说法中正确的是

(1)任何一棵二叉树的叶子结点在三种遍历中的相对次序不变。

(2)按二叉树定义，具有三个结点的二叉树共有6种。

A．(1)，(2)B．(1)

C．(2)D．(1)，(2)都错

4．树有先序遍历和后序遍历，树可以转化为对应的二叉树。下面的说法正确的是

A．树的后序遍历与其对应的二叉树的先序遍历相同

B．树的后序遍历与其对应的二叉树的中序遍历相同

C．树的先序序遍历与其对应的二叉树的中序遍历相同

D．以上都不对

5．下列说法正确的是

(1)二又树按某种方式线索化后，任一结点均有指向前趋和后继的线索

(2)二叉树的先序遍历序列中，任意一个结点均处于在子孙结点前

(3)二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值

A．(1)(2)(3)B．(1)(2)

C．(1)(3)D．都不对

6.二叉树的第k层的结点数最多为

A．2k-1B.2K+1

C.2K-1D.2k-1

7．以下说法不正确的是

A．无向图中的极大连通子图称为连通分量

B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点

C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点

D．有向图的遍历不可采用广度优先搜索

8．有向图G用邻接矩阵A存储，则顶点i的入度等于A中

A.第i行1的元素之和B.第i列1的元素之和

C.第i行0的元素个数D.第i列非0的元素个数

9.设有6个结点的无向图，该图至少应有多少条边才能确保是一个连通图？

A.5B.6

C.7D.8

10．.下图的邻接表中，从顶点V1出发采用深度优先搜索法遍历该图，则可能的顶点序列是

A.V1V2V3V4V5B.V1V2V3V5V4

C.V1V4V3V5V2D.V1V3V4V5V2

11．抽象数据类型的三个组成部分分别为

A．数据对象、数据关系和基本操作

B．数据元素、逻辑结构和存储结构

C．数据项、数据元素和数据类型

D．数据元素、数据结构和数据类型

12．要求相同逻辑结构的数据元素具有相同的特性，其含义为

A.数据元素具有同一的特点

B.不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致

C.每个数据元素都一样

D.仅需要数据元素包含的数据项的个数相同

13．下列各式中，按增长率由小至大的顺序正确排列的是

A．，n！，2n，n3/2

B．n3/2，2n，nlogn，2100

C．2n，logn，nlogn，n3/2

D．2100，logn,2n,nn

14.在下列哪种情况下，线性表应当采用链表表示为宜

A.经常需要随机地存取元素

B.经常需要进行插入和删除操作

C.表中元素需要占据一片连续的存储空间

D