2025年(完整)数据结构考试题9 .pdfVIP

海纳百川，有容乃大；壁立千仞，无欲则刚。——林则徐

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写

上姓名和学号。

22040

一、单项选择题（每小题分，共小题，共计分）

1、设n是描述问题规模的非负整数，下面程序片段的时间复杂度为（）。

x=1;

while(x=n)

x=5*x;

5

A.O(logn)B.O(n)C.O(nlogn)D.O(n)

55

2、顺序表和链表相比存储密度较大，这是因为（）。

A.顺序表的存储空间是预先分配的

B.顺序表不需要增加指针来表示元素之间的逻辑关系

C.链表中所有节点的地址是连续的

D.顺序表中所有元素的存储地址是不连续的

3、在长度为n（n≥1）的循环双链表L中，在尾节点之后插入一个新节点的时间复杂

度为（）。

2

A.O(n)B.O(n)C.O(1)D.O(nlogn)

2

4、设栈的输入序列是1、2、3、4，则（）不可能是其出栈序列。

A.1，2，4，3B.2，1，3，4C.1，4，3，2D.4，3，1，2

5、当用一个数组data[0..n-1]存放栈中元素时，栈底最好（）。

A.设置在data[0]或data[n-1]处B.设置在data[n-1]处

C.设置在data[0]处D.设置在data数组的任何位置

6、在数据处理过程中常需要保存一些中间数据，如果先保存的数据先处理，则使用（）

来保存这些数据。

A.线性表B.队列C.栈D.单链表

7、在环形队列中，元素的排列顺序（）。

A.与队头和队尾指针的取值有关B.与元素值的大小有关

C.由元素进队的先后顺序确定D.与存放队中元素的数组大小有关

8、将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。

A.100B.40C.80D.55

9、设目标串为s，模式串为是t，在KMP模式匹配中，next[4]=2的含义是（）。

A.表示t字符前面最多有2个字符和开头的2个字符相同

4

B.表示s字符前面最多有2个字符和开头的2个字符相同

4

C.表示目标串匹配失败的位置是i=4

D.表示模式串匹配失败的位置是j=2

10、由权值分别为9、2、7、5的四个叶子节点构造一棵哈夫曼树，该树的带权路径长

穷则独善其身，达则兼善天下。——《孟子》

度为（）。

A.23B.44C.37D.27

11、对于无向图的邻接矩阵来说，（）。

A.第i行上、第i列上非零元素总数等于顶点i的度数

B.矩阵中的非零元素个数等于图中的边数

C.第i行上的非零元素个数和第i列的