2024年4月30日发(作者：)

一、单项选择题

1 某算法的时间复杂度是

A 问题规模是 n

2

C 执行时间等于 n

2

O(n

2

) ，表明该算法（

）。

B 问题规模与

n

2

成正比

D 执行时间与

n

2

成正比

）。

2、关于数据结构的描述，不正确的是（

A 数据结构相同，对应的存储结构也相同。

B 数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。

C 数据结构操作的实现与存储结构有关。

D 定义逻辑结构时可不考虑存储结构。

3、按排序策略分来，起泡排序属于（

A

插入排序

B

选择排序

）。

C

交换排序

D

归并排序

）。

4、利用双向链表作线性表的存储结构的优点是（

A

便于进行插入和删除的操作

C

节省空间

5、一个队列的进队顺序为

A 1,2,3,4

6、 Dijkstra

算法是按（

D

B 1,3,2,4

B 提高按关系查找数据元素的速度

便于销毁结构释放空间

）。

1,2,3,4

，则该队列可能的输出序列是（

C 1,4,2,3

D 4,3,2,1

）方法求出图中从某顶点到其余顶点最短路径的。

A 按长度递减的顺序求出图的某顶点到其余顶点的最短路径

B 按长度递增的顺序求出图的某顶点到其余顶点的最短路径

C 通过深度优先遍历求出图中从某顶点到其余顶点的所有路径

D 通过广度优先遍历求出图的某顶点到其余顶点的最短路径

7、字符串可定义为 n（ n≥ 0）个字符的有限（

中字符的个数。

A

集合

B

数列

C

序列

D聚合

SA 开始按行连续

）。其中， n 是字符串的长度，表明字符串

8、在二维数组 A[9][10]

中，每个数组元素占用

3 个存储单元，从首地址

存放。在这种情况下，元素

A[8][5]

的起始地址为（

）。

A SA+141

B SA+144

C SA+222

D SA+255

9、已知广义表为

L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))

的长度是（

）。

A2

B3

C4

D5

_____。

，则它

10.

对于具有 n(n>1) 个顶点的强连通图，其有向边条数至少有

A. n+1

B. n

C. n-1 D. n-2

11. 一个递归算法必须包括 __________ 。

A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分

12. 从逻辑上看可以把数据结构分为__________两大类。

A．动态结构、静态结构B

．顺序结构、链式结构

C．线性结构、非线性结构

A O(n)

B O(1)

D

．初等结构、构造型结构

）。

13、若在长度为 n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（

C O(n

2

)

D O(log

2

n)

14. 采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜索

长度为 __________。

A. n

B. n/2

first

C . (n+1)/2

B P==NULL;

第1页，共 7页

D. (n-1)/2

）。

15、非空的循环单链表

A p->link==NULL;

的链尾结点（由

p 所指向）满足（

C p->link==first;

16、用 S 表示进栈操作，用

的出栈顺序，相应的

A SXSXSSXX

C SXSSXXSX

A 254

B 255

D p==first;

X 表示出栈操作，若元素的进栈顺序是

）。

1234，为了得到

1342

S 和 X 的操作序列为（

B SSSXXSXX

D SXSSXSXX

17、含有 129 个叶结点的完全二叉树，最少有（

C 257

）个结点。

D 258

A 出发执行

18、一个有向图 G的邻接表存储如图

（ 1）所示，现按深度优先搜索方式从顶点

一次遍历，所得的顶点序列是（

A 1,2,3,4,5

19、树最合适用来表示（

A 有序数据元素

）。

）。

C 1,2,4,5,3

B 1,2,3,5,4

D 1,2,5,3,4

B 元素之间具有分支层次关系的数据

C 无序数据元素

D 元素之间无联系的数据

20、一棵有 124 个叶结点的完全二叉树最少有（

）个结点。

A 247

B 248

C 249

D 250

21、图（ 1）给出的一棵二叉搜索树，对应的二叉判定树如图（

均长度是（

）。

A 21/7

B 28/7

C 15/6

D 16/6

2）所示，它的搜索成功的平

图（ 1）二叉搜索树

A8

B10

图（ 2）二叉判定树

）次比较。

23、对 5 个不同的数据元素进行直接插入排序，最大需要进行（

C15

D25

24、将一个 n×n 的对称矩阵 A 的下三角部分按行存放在一个一维数组

B[0] 中，那么第 i 行的对角元素 A[i][i]

A (i+3)*i/2

25、已知广义表为

它的深度是（

A2

）。

B3

C 4

）的线性表。

B 中，A[0][0]

存放在

）。

在 B 中的存放位置是（

C (2n-i+1)*i/2

B (i+1)*i/2

D (2n-i-1)*i/2

，则

L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))

D5

26、顺序搜索法适合于存储结构为（

A 散列存储

B

顺序存储或链式存储

C 压缩存储 D 索引存储

）。

27、采用折半搜索方式搜索一个长度为

n 的有序顺序表时，其平均搜索长度为（

A O(n)

B O(log

2

n)

C O(n

2

)

D O(nlog

2

n)

28、 n 个结点的线索二叉树中，线索的数目是（

A n-1

B n+1

C 2n

）。

C

交换排序

第2页，共 7页

）。

D 2n-1

是采用下列排序方法之一得到的第二趟排序

29、若数据元素序列 {11,12,13,7,8,9,23,4,5}

后的结果，则该排序方法只能是（

A

插入排序

B

选择排序

D

归并排序