题1

1、下列程序段的时间复杂度是（）。
A、O(nlog₂n)
B、O(n²)
C、O(n)
D、O(log₂n)

count=0;
for(k=1;k<=n;k*=2)for(j=1;j<=n;j++)count++;

解析：（A）
由for循环决定，假设最外层m次循b环结束，则有2^m+k=n，可得：m=log₂n，
另外，内层for循环n次，所以该程序段的时间复杂度：
O(n)=n×log₂n=nlog₂n。

题2

2、下列程序段的时间复杂度是（）。
A、O(logn)
B、O(n^1/2)
C、O(n)
D、O(n²)

x=0;
while(n>=(x+1)*(x+1))x=x+1;

解析：（B）
执行k次while循环，每循环一次，x加1，最终x=k，
故n≥k²，得O(n^1/2)。

题3

3 、下列程序段的时间复杂度是（）。
A、O(nlog₃n)
B、O(log₃n)
C、O(n²)
D、O(n³)

i=1;
while(i<=n)i=i*3;

解析：（B）
循环次数由i³=n，可得O(log₃n)。

题4

4 、下列程序段的时间复杂度是（）。
A、O(log₂n)
B、O(n)
C、O(n²)
D、O(nlog₂n)

int fact(int n){if(n<=1)return 1;return n*fact(n-1)
}

解析：（B）
由于是n次阶乘，即O(n)，一共执行n次递归调用fact()函数，所以即为O(n)。

题5

5、每个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，这种存储方式是（）。
A、顺序
B、链式
C、索引
D、散列

解析：（C）
顺序存储由存储单元的邻接关系体现；链式存储不要求逻辑上相邻的元素物理位置上也相邻，通过指示元素存储地址的指针来体现元素之间的逻辑关系；索引存储在存储数据元素的同时还需要建立附加的索引表，其中的索引项的形式为关键字和地址；散列存储是根据数据元素的关键字直接计算其存储地址，也称为哈希存储（Hash）。

题6

6、链式存储的存储结构所占存储空间（）。
A、分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针
B、只有一部分，存放结点的值
C、只有一部分，存放表示结点间关系的指针
D、分两部分，一部分存放结点的值，另一部分存放结点所占单元素

解析：（A）

题7

7、（多选）以下属于逻辑结构的是（）。
A、顺序表
B、哈希表
C、有序表
D、单链表
E、栈

解析：（C、E）
有序表是关键字有序的线性表，它是线性结构，可以顺序存储和链式存储，故属于逻辑结构。栈也属于线性结构（逻辑结构），在存储结构中既可以使用顺序存储，也可以使用链式存储。

题8

8、二维数组A[m][n]以行为主顺序存储，每个元素占用l个存储单位。元素A[0][0]的存储地址是b，则元素A[i][j]（0≤i≤m-1，0≤j≤n-1）的存储地址是（）。
A、b + ( i * n + j ) * l
B、b + i * j * l
C、b + ( i + j ) * l
D、b + ( ( i - 1 ) * n + ( j - 1 ) ) * l

解析：（A）
元素A[i][j]的前面一共有i行元素，每行元素有n个，A[i][j]为本行的第j+1个元素，j个元素位于其前面，所以共有i * n + j个元素，每个元素占用l个存储单位，乘以l，另外加上元素A[0][0]的存储地址，即元素A[i][j]的存储地址是b + ( i * n + j ) * l。