算法与数据结构题库与答案

2024年2月7日发(作者：)

一、单项选择题

1 某算法的时间复杂度是

A 问题规模是 n2

C 执行时间等于 n2

O(n2 ) ，表明该算法（

）。

B 问题规模与

n2 成正比

D 执行时间与

n2 成正比

）。

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

2n)

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

2n)

C O(n

2)

D O(nlog

2n)

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

归并排序

30、为了增加内存空间的利用率和减少溢出的可能，

应将两个栈的栈顶分别设在这片存储空间的两端，当（

A 两个栈的栈顶同时到达栈空间的中心点

B 其中一个栈的栈顶到达栈空间的中心点

C 两个栈的栈顶在栈空间的某一位置相遇

D 两个栈的栈顶相加超过了栈空间的最大容量

31、设一棵二叉树的中序序列为

（

）。

A adbec

A

权值

A 2n-1

B decab

B

顶点

B 2n

C debac

C

边

Huffman 树共有（

C 2n+1

在两个栈共享一片连续的存储空间时，

）时才产生上溢。

badce，后序遍历为

bdeca ，则该二叉树前序遍历的顺序是

D abcde

32、图的简单路径是指（

33、用 n 个权值构造出来的

）不重复的路径。

D

边与顶点均不重复

）个结点。

D n+1

）。

34、在如图（ 2）所示的 AVL树中插入关键码

A 13,48

B 24,48

48，得到了一棵新的 AVL 树，在这棵新的

AVL

C 24,53

D 24,90

树中，关键码 37 所在结点的左右子女结点中保存的关键码分别是（

图（ 1） 14 小题的邻接表

图（ 2） 15 小题的 AVL树

二、填空题

1、算法效率的度量分为

2、算法是一个有穷的指令集，

入、输出、确定性、

3、一个抽象数据类型

4、队列的插入操作是在

5、栈又称为

先进后出

6、对称矩阵的行数和列数

角部分或者下三角部分即可。

7、利用三元组表存放稀疏矩阵中的非零元素，

零元的行号、列号和非零元素的

8、广义表 A((a,b,c),(d,e,f))

9、广义表 A((a,b,c),(d,e,f))

值

的表头是

的表尾是

则在三元组表中每个三元组中应记录相应非

事后测量

有穷性

ADT包括

队尾

相等

和

可行性等特性。

事前估

两种。

它应当具有输

它为解决某一特定任务规定了一个运算序列。

数据操作

和

对象

队头

先进先出

两个部分。

进行。

线性表。

进行，删除操作是在

的线性表，队列又称为

且以主对角线为对称轴，

因此只要存储它的上三

。

(a,b,c)

((d,e,f))

。

。

n2，度为 1 的结点数为

，其叶节点数为

n2+1

n1，度为

10、在一棵有 n 个结点的二叉树中，

若度为 2 的结点数为

0 的结点数为 n0，则树的最小高度为

log2 n

1

。

n1，度为

11、在一棵有 n 个结点的二叉树中，

若度为 2 的结点数为

n2，度为 1 的结点数为

0 的结点数为 n0，则树的最大高度为

n

，其叶节点数为

1

。

12、已知有序顺序表 (13,18,24,35,47,50,62,83,90,115,134)

，当用折半搜索法搜索值

18

第3页，共 7页

的元素时，搜索成功的数据比较次数为

13、采用顺序搜索方式搜索长度为

杂度为

O(n

24

。

(n+1)/2

。

n

2

n 的线性表时，平均搜索长度为

O(n+e)

。

14、对于一个具有 n 个顶点和 e 条边的无向图进行遍历，若采用邻接矩阵表示，则时间复

)

，若采用邻接表表示，则时间复杂度为

2e

。

15、对于一个具有 n 个顶点和 e 条边的无向图， 若采用邻接矩阵表示，

则该矩阵大小是

，矩阵中的非零元个数为

16、每次从无序表中挑选一个最小或者最大元素，把它交换到有序表的一端，此种排序方

法叫做

交换

排序。

17、对 n 个元素的序列进行排序时，如果待排序元素序列的初始排列完全逆序，则起泡排

序过程中需要进行

插入

插入

n(n-1)/2

排序。

次元素值的比较，

n(n-1)/2

次元素值的交换。

18、每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做

19、对 n 个元素的序列进行排序时，如果待排序元素序列的初始排列已经全部有序，则起

泡排序过程中需要进行

三、判断题

1、数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按照使用需要建立的。错

2、数据结构是指相互之间存在一种或多种关系的数据元素的全体。对

3、根据队列的先进先出的特性，最后进队列的元素最后出队列。对

4、在顺序栈中元素是按照其值的大小有序存放的。错

5、栈底元素是不能删除的。错

6、在队列中， n 个元素的进队列顺序和出队列顺序总是一致的。对

7、数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。错

8、广义表是线性表的推广，但它不是一种线性结构。对

9、二维数组可以视为数组元素为一维数组的一维数组。因此，二维数组是线性结构。错

10、有 n 个整数存放在一维数组

有序，其平均搜索长度都相同。错

11、邻接矩阵适用于稠密图（边数接近于顶点数的平方）

于顶点数的平方） 。对

12、对 n 个顶点的连通图

一定是 G的生成树。错

13、希尔排序、简单选择排序都是不稳定的排序方法。错

14、如果一个二叉树的结点，或者两棵子树都空，或者两棵子树都非空，则此二叉树称为

完全二叉树。错

15、在二叉搜索树中，任一结点所具有的关键码值都大于它的左子女（如果存在）的关键

码值，同时小于其右子女（如果存在）的关键码值。对

16、具有 n 个顶点的无向图最多有

四、简答与计算题

1、什么是数据结构？有关数据结构的讨论涉及哪三个方面？

2、什么是算法，算法的

5 个特性是什么？

Kruskal

算法求出最小生成树。

3、已知如图（ 3）所示的有向图，请利用

n(n-1) 条边，最少有 n-1 条边。错

17、最小生成树是指边数最少的生成树。错

G来说，如果其中的某个子图有

n 个顶点， n-1 条边，则该子图

，邻接表适用于稀疏图（边数远小

n-1

次元素值的比较，

0

次元素值的交换。

A[n] 中，在进行顺序搜索时，无论这

n 个整数的排列是否

第4页，共 7页

图（ 3）

4、如图（ 3）所示的有向图，请给出该图的邻接矩阵和邻接表。

A

B

C

D

E

F

图（ 3）

5、已知一棵二叉树的前序遍历结果是

棵二叉树。

ABECDFGHIJ，中序遍历结果是

EBCDAFHIGJ，试画出这

6、给定权值集合 {15,03,14,02,06,09,16,17}

外部路径长度。

，构造相应的

huffman 树，并计算它的带权

第5页，共 7页

7、设串 s 为“ abcabaa”，试计算其 next 数组的值。

j

r

next[j]

0

a

-1

1

b

0

2

c

0

3

a

0

4

b

1

5

a

2

6

a

1

banana 从广义表

8、利用广义表的

head 和 tail

操作写出函数表达式，

把以下各题中单元素

中分离出来。

(1)L1(apple,pear,banana,orange)

(2)L2((apple,pear),(banana,orange))

(3)L3(((apple),(pear),(banana),(orange)))

(4)L4((((apple),pear),banana),orange)

(5)L5(apple,(pear,(banana),orange))

(1)Head(Tail(Tail(L1)))(1

(2)Head(Head(Tail(L2))) (1

(4)Head(Tail(Head(L4))) (1

分 )

分 )

分 )

(3)Head(Head(Tail(Tail(Head(L3))))) (1

分 )

(5)Head(Head(Tail(Head(Tail(L6))))) (1

9 、 设 有 序 顺 序 表 中 的 元 素 依 次 为

成功的平均搜索长度。

分)

17,154,170,275,503,509,512,553,612,677,765,

897,908 。试画出对其进行折半搜索时的判定树，并计算搜索成功的平均搜索长度和搜索不

搜索成功的平均搜索长度为

搜索不成功的平均搜索长度为

45/14 （ 1 分）

59/14 （ 1 分）

10、已知一个待排序的关键字序列为 {56 ， 36，22，86，72，10， 28，48} ，请写出快速排序每

一趟排序的结果（写出过程） 。（ 5 分）

第 1 趟排序结果： 48,36,22,28,10,

第 2 趟排序结果： 10,36,22,28,

56,72,86

48,56,72,86

第6页，共 7页

第 3 趟排序结果： 10,36,22,28,48,56,72,86

第 4 趟排序结果： 10,22,28, 36,48,56,72,86

第 5 趟排序结果： 10, 22,28,36,48,56,72,86

11、已知一个有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 )

于一维数组 a[12] 中，根据折半搜索过程填写成功搜索下表中所给元素

50 时的比较次数。

元素值

比较次数

顺序存储

34, 56, 58, 63, 94，

34

2

56

1

58

3

63

4

94

4

50

4

12、已知一组关键字（ 1，13，12，34，38， 33， 27， 22）请按哈希函数

H（ key） =key MOD

11，处理冲突的方法是线性探测再散列法，哈希表长度为

找概率相等的情况下的平均查找长度。

33

0

1

2

1

3

13

4

5

12

6

34

7

8

9

38

10

11，请画出该哈希表并求其在查

27

22

平均查找长度为：

1/8(1*4+2*1+3*1+4*1+8*1)=21/8

13. 判断以下序列是否是最小堆？如果不是, 将它调整为最小堆。

(1) { 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 }

(2) { 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }

答：（ 1）调整为最小堆后为 { 21, 35, 39, 57, 86, 48, 42, 73, 66, 100 }

（ 2）调整为最小堆后为 { 12, 24, 33, 65, 33, 56, 48, 92, 86, 70 }

14.在一棵空的二叉排序树中依次插入关键字序列为

请画出所得到的二叉排序树。

20、30、 8、12、34、5、 60、 3、1，29，

五、算法设计题

1、编写程序实现起泡排序算法（从小到大排列）

i>1&&change 、 change = FALSE

L.r[j]=L.r[j+1]

、 change = TRUE

a,an(n>=3) 的单链表的所有节点逆

：

、 L.r[j+1].key

2、设计一个算法，将一个头节点的数据域依次为

置。

第7页，共 7页