【数据结构入门精讲 | 第二篇】考研408、企业面试基础概念习题

在上一篇文章中我们学习了数据结构的概念、算法复杂度的概念及其相关计算，这篇文章侧重考研408、企业面试数据结构的导论、算法复杂度等练习。

判断题

1.时间复杂度是根据算法写成的程序在执行时耗费时间的长度，往往与输入数据的规模有关。（对）

2.斐波那契数列FN的定义为：F0=0, F1=1, F(N)=F(N?1)+F(N?2), N=2, 3, …。用递归函数计算FN的空间复杂度是O(N)。（对）

3.斐波那契数列FN的定义为：F0=0, F1=1, FN=FN?1+FN?2, N=2, 3, …。用循环函数计算FN的时间复杂度是Θ(FN).（错）
解析：在循环函数中，我们通过迭代的方式依次计算每个斐波那契数列的数值，只需要进行 N-1 次迭代即可。故O(N)

4.(NlogN)/1000是O(N)的。（错）
解析：(NlogN)/1000仍然是O(NlogN)级别的，而不是O(N)。因为在计算复杂度时，常数因子和低阶项都可以忽略不计，只考虑最高次项的系数，即1000可忽略。

5.抽象数据类型中，描述数据类型的方法与实现操作的算法和编程语言无关。（对）

6.解决问题的效率，跟数据的组织方式无关。（错）
解析：选择合适的数据结构可以显著提高算法的效率。例如，在查找操作中，使用哈希表可以实现常数时间的查找效率，而使用线性表则需要线性时间。

7.对应同一个数据结构，可以有不同的实现方法。（对）
解析：链表是一种常见的数据结构，它可以用指针来实现，也可以用数组来实现。

8.算法可以没有输入，但是必须有输出。（对）

9.递归程序往往简洁易懂，但占用较大空间。递归层数过大会造成系统堆栈溢出。（对）

10.N^2*logN和N*logN^2具有相同的增长速度。（错）
解析：N*logN^2相当于2N*longN，显然比N^2*logN小。

11.数据类型由数据对象集和数据集合相关联的操作集组成。（对）
解析：比如说数据类型中的整数类型（int），在操作集合方面，int支持的基本算术运算有加、减、乘、除等。

12.抽象数据类型中，描述数据类型的方法与数据存储的物理结构有关。（错）
解析：方法关注的是数据对象的逻辑结构和行为，而数据存储的物理结构则决定了如何在计算机内存中存储和表示这些数据对象。

13.抽象数据类型中，描述数据类型的方法与存放数据的机器有关。（错）
解析：方法关注的是数据对象的逻辑结构和行为，而数据存储的物理结构则决定了如何在计算机内存中存储和表示这些数据对象。

14.算法的优劣与算法描述语言无关，但与所用计算机有关。 （错）
解析：优秀的算法应当在不同计算机环境下都能够展现出高效的特性。

15.空间复杂度是根据算法写成的程序在执行时占用存储单元的长度，往往与输入数据的规模有关。（对）

16.斐波那契数列的递归实现与循环实现的时间复杂度均为O(n)（对）

17.描述抽象数据类型的方法与实现操作的算法无关，与数据存储的物理结构无关（对）

18.for(i=1;i<n;i*=2)
for(j=0;j<i;j++)
a++;
时间复杂度为O(N) （对）

19.与数据元素的形式、内容、相对位置无关的是数据的逻辑结构（对）

20.数据的存储结构包括数据的表示及数据元素的表示（对）

21.链表是链式存储结构，数组是随机存取的存储结构（对，因为访问一个节点不需要遍历之前的节点）

22.栈的栈顶是表首（对）

23.只带头指针的非循环双链表不适合作链队，因为查找队尾指针需要O(n)（对）

24.数据元素可由若干个数据项（data item）组成，数据项是数据的不可分割的具有独立含义的最小标识单位。（对）

25.线性结构的基本特征是:每个元素有且仅有一个直接前驱和一个直接后继。 【解答】错。
每个元素最多只有一个直接前驱和一个直接后继

26.数据结构研究的内容包括数据的逻辑结构、存储结构和数据的运算。（对）

选择题

1.给定程序时间复杂度的递推公式：T(1)=1，T(N)=2T(N/2)+N。则对该程序时间复杂度最接近的描述是：（选D）
A.O(N^2) B.O(N) C.O(logN) D.O(N*logN)
解析：根据递推公式T(N) = 2T(N/2) + N，可以使用主定理（Master Theorem）来求解时间复杂度。递推公式的形式符合主定理的第二种情况：T(N) = aT(N/b) + f(N)，其中a=2，b=2，f(N)=N。
根据主定理，时间复杂度可以表示为：

• 若f(N) = O(N^c) 其中c < log_b(a)，则 T(N) = O(N^log_b(a))
• 若f(N) = Θ(N^c * log^k(N)) 其中c = log_b(a)，则 T(N) = O(N^c * log^(k+1)(N))
• 若f(N) = Ω(N^c) 其中c > log_b(a)，且对某个ε > 0，有af(N/b) ≤ εf(N)，则 T(N) = Θ(f(N))

在这个递推公式中，a=2，b=2，f(N)=N，因此c=1，log_b(a)=log_2(2)=1，c=log_b(a)。
所以根据主定理，时间复杂度最接近的描述是 D.O(N*logN)。

另一种方法是将T(N/2)替代为含有T(N/4)的式子，再将T(N/4)替代为含有T(N/8)的式子，T(N) = 2T(N/2) + N = 2(2T(N/4) + N/2) + N = 4T(N/4) + 2N = 4(2T(N/8) + N/4) + 2N = 8T(N/8) + 3N = …因此，我们可以得到递推公式的展开形式： T(N) = 2^k T(N/2^k) +kN，当N/2^{k=1时，即N=2}k，解得k=log2(N)，最终得到T(N)为O(N*logN)

2.T(n)表示当输入规模为n时的算法效率，以下算法中效率最优的是(选C)。
A.T(n)=2n^2
B.T(n)=3nlog2N
C.T(n)=T(n/2)+1,T(1)=1
D.T(n)=T(n-1)+1,T(1)=1
解析：A复杂度为n的平方；B的复杂度为n*log2N；C的复杂度为log2N；D的复杂度为n；因此时间复杂度最小的为C。

3.下列函数中，哪两个函数具有相同的增长速度：（选B）
A.N^2*logN和N*logN^2
B.N*logN^2和N*logN
C.N和2/N
D.2^N和NN
解析：A：N*logN^2化为2N*logN；B的N*logN^2可化为2N*logN，故选B。

4.下列程序段的时间复杂度是（O(N)）

int  sum = 0;
for(int i=1;i<n;i*=2)
    for(int j=0;j<i;j++)
        sum++;

外层循环的迭代次数随着i的翻倍而增加，而内层循环的迭代次数等于i。因此，总的迭代次数是n/2 + n/4 + n/8 + … + 1，这个级数的和是约等于2n，所以时间复杂度为O(n)。

答案选D。解析：要查找一个三维数组中的最小元素，需要遍历每个元素并将其与当前最小值进行比较。因此，至少需要遍历N^{3个元素才能确定最小值。因此，时间复杂度至少为O(N}3)。

6.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（A）。
A.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
B.数据元素所包含的数据项的个数要相等
C.数据在同一范围内取值
D.每个数据元素都一样

7.与数据元素本身的形式、内容、相对位置、个数无关的是数据的（D）。
A.存储结构
B.运算实现
C.存储实现
D.逻辑结构

8.空间复杂度分析(阶乘，循环+动态数组版)
下面算法的空间复杂度为 ▁▁▁O(n)▁▁。

double Fac(int n)
{
    int k;
    double p, *a;
    a = (double*)malloc((n + 1) * sizeof(double));
    a[0] = 1.0;
    for (k = 1; k <= n; ++k)
    {
        a[k] = a[k - 1] * k;
    }
    p = a[n];
    return p;
}

解析：每次循环都能得到下一次循环所要参与运算的值，而代码执行了N次，故空间复杂度为O(n)。

9.设 0≤i,k<n，下面这段代码的时间复杂度是：(O(n))

if (i>k) {
    for (j=i; j<n; j++)
        a[j] = a[j-k]+1;
}
else {
    for (j=i; j>0; j--)
        a[j] = a[k-j]+2;
}

解析：判断后执行n次或i次，故时间复杂度为O(n)

10.下面的程序段违反了算法的（有穷性/有限性）原则。

void sam()
{  int n=2;
   while (n%2==0)    n+=2;
   printf(“%d”,n);
}

解析：程序不断执行while循环，违反算法有穷性原则。

算法的原则还包括：确定性（算法的每一步骤都必须明确且无二义性地定义。）、健壮性（一个健壮的算法应该能够在面对非预期的输入时，依然能够给出合理的输出或错误提示，而不会导致系统崩溃或产生不可预料的结果。）、可行性（算法的每个步骤不依赖于任何超出可用资源范围的操作。）

11.数据的存储结构包括 ▁▁A、D▁▁▁。
A.关系的表示
B.操作的实现
C.问题的描述
D.数据元素的表示
解析：A，关系的表示，用于描述数据元素之间的关系，比如链表、树等；D，数据元素的表示，即数据元素的内部结构和属性的表示方式，例如使用结构体或类来表示一个数据元素的各个属性。

编程题

R7-1 最大子列和问题

给定K个整数组成的序列{ N1, N2, …, NK }，“连续子列”被定义为{ Ni, Ni+1, …, Nj }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

• 数据1：与样例等价，测试基本正确性；
• 数据2：102个随机整数；
• 数据3：103个随机整数；
• 数据4：104个随机整数；
• 数据5：105个随机整数；

输入格式:

输入第1行给出正整数K (≤100000)；第2行给出K个整数，其间以空格分隔。

输出格式:

在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。

输入样例:

6
-2 11 -4 13 -5 -2

输出样例:

20

#include <stdio.h>
int main()
{
	int k;scanf("%d",&k);int a[k];
	for(int i=0;i<k;i++)scanf("%d",&a[i]);
	
	int sum=0,t=0;
	for(int i=0;i<k;i++)
	{
		sum+=a[i];
		if(sum>t)//如果原序列加上a[i]会大于原序列
		t=sum;//则更新原序列
		else if(sum<0)
		sum=0;
	}
	printf("%d",t);
}


方法二：
    #include <stdio.h>
int main(){
	int a=0,b=0,c[100001],d,i;
	scanf("%d",&d);
	for(i=0;i<d;i++)
	{
		scanf("%d",&c[i]);
	}
	
	for(i=0;i<d;i++)
	{
		a+=c[i];
		if(a>b)
		{
			b=a;
		}
		else if(a<0)
		{
			a=0;
		}
	}
	
	printf("%d",b);
	return 0; 
}

方法二的思路是：

1.声明变量a和b，并初始化为0。其中，a用于记录当前子数组的和，b用于记录最大子数组的和。

2.使用for循环遍历数组c，将数组c的元素依次输入到c[i]中。

3.使用另一个for循环遍历数组c，计算当前子数组的和。

4.在每一次的循环中，首先将当前元素c[i]加到a上，然后判断a是否大于b。如果a大于b，则将b更新为a的值，表示找到了一个更大的子数组和。

5.然后判断a是否小于0。如果a小于0，则将a重新置为0，表示当前子数组的和已经小于0，无需继续累加。

以上就是本篇文章的所有内容，在下一篇文章中我们将学习表的相关概念。