2025年数据结构考研试卷 (10) .pdfVIP

古之立大事者，不惟有超世之才，亦必有坚忍不拔之志。——苏轼

附录B三份数据结构考研试题及参考

答案

试题一(满分75)

一、单项选择题(2×10分,共20分)

2

1.某算法的时间复杂度为O(n),表明该算法的＿.

A.问题规模是n2B.执行时间等于n2

C.执行时间与n2成正比D.问题规模与n2成正比

2.设线性表有n个元素,以下操作中,＿在顺序表上实现比在链表上实现效率更高.

A.输出第i(1≤i≤n)个元素值

B.交换第1个元素与第2个元素的值

C.顺序输出这n个元素的值

D.输出与给定值x相等的元素在线性表中的序号

3.设n个元素进栈序列是1,2,3,…,n,其输出序列是p,p,…p,若p=3,则p的值＿.

12n12

A.一定是2一定是1B.

C.不可能是1以上都不对D.

4.设循环队列中数组的下标是0～N-1,其头尾指针分别为f(指向队头元素的前一位置)和

r(指向队尾元素的位置),则其元素个数为＿.

A.r-fB.r-f-1

C.(r-f)%N+1D.(r-f+N)%N

5.若串s=’abcefgh’,其子串(含空串和自身)的个数是＿.

A.8B.37

C.36D.9

6.若将n阶上三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中,第一个非零

元素a存放于B[1]中,则应存放到B[k]中的非零元素a(1≤i≤n;1≤j≤i)的下标i，j

11ij

与k的对应关系是k=(。)

A.i(i+1)/2+jB.i(i-1)/2+j-1C.j(j+1)/2+ID.j(j-1)/2+i-1

7.设高度为h（根结点为第1层）的二叉树上只有度为0和度为2的结点，则此类二叉

学而不知道，与不学同；知而不能行，与不知同。——黄睎

树中所包含的结点数至少为().

A.2hB.2h-1C.2h+1D.h+1

8.无向图的邻接矩阵是一个（）。

A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵

9.对线性表进行二分查找时，要求线性表必须（）。

A.以顺序表方式存储

B.以链接方式存储

C.以顺序方式存储，且结点按关键字有序排序

D.以链式方式存储，且结点按关键字有序排序

10.以下排序算法中，（）不能保证每趟排序至少能将一个元素放到

其最