数据结构题库.pdf

第一章绪论

1.一个算法应该是(B)。

A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A和C

C是特性不是定义

2

2.某算法的时间复杂度为O(n)，表明该算法(C)。

A.问题规模是n2B.执行时间等于n2C.执行时间与n2成正比D.问题规模与n2成正比

3.设n表示问题规模，下面程序片段的时间复杂度是()。

x=2;while(xn/2)x=2*x;

设x＝2×2语句的执行次数为t

2^（t+1）＝n/2

f（n）＝log2（n/2）-2

O（log2（n/2））时间复杂度不要常数

4.下面程序段的时间复杂度是().

count=0;

for(k=1;k=n;k*=2)

for(j=1;j=nj;++)

count++;

T1（n）＝O（log2（n））

T2（n）＝O（n）

T＝T1×T2＝O（nlog2（n））

第二章线性表

1.设线性表有n个元素，严格来说，以下操作中，哪些操作在顺序表上实现要比在链表上

实现的效率高。AB

A.输出第i个数据元素的值B.交换第两个指定位置的数据元素C.输出这n个数据元素

ii

2.在一个长度为n的顺序表中删除第(1==n)个元素时，需要向前移动n-i个元

素。

3.设计算法从顺序表中删除具有最小值的元素（假设最小值唯一）并由函数返回被删除的

元素值，空出的位置由最后一个元素填补，若顺序表为空则显示错误信息并退出运行。

要求：(1)给出算法的设计思想；(2)根据设计思想，采用C语言描述算法，关键之处给出

注释；(3)说明你设计的算法时间复杂度。

4.给定一个带头结点的单链表L，设head为头指针，结点的结构为（data,next）,data为

整型元素，next为指针。设计算法，将L逆置，要求算法的空间复杂度为O(1)。

要求：(1)给出算法的设计思想；(2)根据设计思想，采用C语言描述算法，关键之处给出

注释；(3)说明你设计的算法时间复杂度。

第三章栈和队列

1.假定利用数组a[n]顺序存储一个栈，用top表示栈顶指针，top==-1表示栈空，并且已知

栈未满，则元素x入栈需要执行的的操作为a[++top]=x。

2.向一个栈顶指针为top的链栈中插入一个结点x，则执行的操作x-next=top;top=x;。

3.设元素abcdefg依次进入栈S,得到的出栈序列为bdcfeag，则栈的容量至少是3。

4.有5个元素，依次按照A,B,C,D,E的次序入栈，则第一次出栈为C第二次出栈为D的出

栈序列有3种，它们分别是CDBAECDEBACDBEA。

5.循环队列存储在数组A[0…n]中，rear表示队尾，front表示队首，则入队列的操作为rear

=(rear+1)mode(n+1)。

6.在一个链队列中，头指针为front,尾指针为rear,将结点x插入队列的操作是

rear-next=x;rear=x;。

第四章数组和广义表

1.设有n*n的对称矩阵A,将其下三角部分按行优先存放在一维数组B中，A[0][0]存放在

B[0]中，那么A[i][j]在B中的存放位置是B