总结

1：基于比较的排序时间复杂度的下限是( ) ，其中n表示待排序的元素个数。

A. O(n)O (n)

B. O(nlogn)O (nlogn)

C. O(logn)O (logn)

D. O(n​2)O (n​^2)

解析：比较排序的复杂度最大为O(n2)O(n^2)，最小为O(nlogn)O(nlogn)

2：计算机中的数值信息分为整数和实数（浮点数），实数之所以能够表示很大或者很小的数，是由于使用了（ ）。

A. 反码

B. 补码

C. 阶码

D. 较长的尾数

一个十进制数可以写成一个纯小数乘上10x10^x，相似的，一个二进制可以写以成一个纯小数乘2x2^x。例如：11.01=22×0.1101

一般地，任意一个二进制的数N=2j×s

补充一下：j为阶码

j如果j有正负号，则正负号为阶符

s为纯小数，叫做尾数

数符，指的是N个整数的符号

3：阅读程序

(1):

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int cnt[26];
char s[N];
int main()
{
	scanf("%s", s);
	int len = strlen(s);
	for (int i = 0; i < len; ++i) 
	{
		cnt[s[i] - 'a']++;
	}
	int maxcnt = 0, ans = 0;
	for (int i = 0; i < 26; ++i)
	{
		if (cnt[i] > maxcnt) 
		{
			maxcnt = cnt[i];
			ans = i;
        }
    }
printf("%c\n%d\n", ans+'a', maxcnt);
return 0;
}

判断题

1、输入只能是小写字母。( )

√ ×

第十行有cnt[s[i]-'a']，如果输入中不含小写字母字符，那么cnt会数组越界

2、将第11行的”maxcnt = 0”改为”maxcnt = cnt[0]”代码运行结果不变。( )

√ ×

因为maxcnt一定会变成cnt[0]

3、将第12行中”i=0”改为”i=1”不会改变代码运行结果。( )

√ ×

改完后cnt[0]如果是cnt数组中的最大值则被漏掉，maxcnt就成了统计后面的最大cnt值

4、将第13行”cnt[i]>maxcnt”改为”cnt[i]>=maxcnt”不会改变程序结果。( )

√ ×

不加是找最前面的最大值，加是找最后面的最大值

选择题

5、当输入是”abcabd”时，输出为( )。

A. a 2

B. b 2

C. c 2

D. d 1

程序统计出现最多的字母已经对应出现的次数，如果多个字母出现次数相同，则选小的字母，a出现2次，b出现2次，c出现1次，d出现1次，但是a在b前面

6、将第13行”cnt[i]>maxcnt”改为”cnt[i]>=maxcnt”，当输入是”abcabd”时，输出为( )。

A. a 2

B. b 2

C. c 2

D. d 1

程序统计出现最多的字母已经对应出现的次数，如果多个字母出现次数相同，则选小的字母，a出现2次，b出现2次，c出现1次，d出现1次，但是a在b后面

(2):

#include <iostream>
using namespace std;
int main()
{
	int n, x;
	scanf("%d", &n);
	int a[10];
	for (int i = 0; i < 10; ++i) a[i] = n;
	{
		bool ok = true;
		for (x = 1; ok; ++x) 
		{
			int y = x;
			while (y > 0) 
			{
			if (--a[y % 10] < 0) 
			{
				cout << x - 1<< endl; ok = false;
			}
				y /= 10;
			}
		}
	}
return 0;
}

1、将第7行改为”memset(a, n, sizeof(a));” 程序运行结果不变。( )

√ ×

memset是按字节进行初始化，只有将数组元素全部初始化为0或-1或极大值时才用。

2、将第12行的”ok=false”改为”break”程序可能会进入死循环。( )

√ ×

因为break的是while循环不是for循环

3、程序可能会输出多行。( )

√ ×

有时输入一个数会输出多行因为答案的数可能会被模很多次

4、将第12行”--a[y%10] < 0”改为”a[y%10]-- < 0”程序运行结果不变。( )

√ ×

因为--x是先减再用，而x--是先用再减

选择题

5、程序输入3时，输出( )。

A. 2

B. 3

C. 10

D. 11

当x=1时，a[1]--。x=2时，a[2]--。 . . . . . .当x=11时x[1]--，然后11%10=1，a[1]--。

6、（4分）程序输入20是，输出（ ）。

A. 20

B. 99

C. 100

D. 101

同样用上一题的方法一个一个的试，因为我不知道怎么试，所以我就不写了

(3):

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N][N], b[N][N];
int n,m,ans,trans;
int x[9] = {0,0,0,-1,-1,-1,-2,-2,-3};
int y[9] = {-1,-2,-3,0,-1,-2,0,-1,0};
int main() 
{
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			cin >> a[i][j];
		}
	}
	b[1][1] = a[1][1];
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			int trans = INT_MIN;
			for(int t=0;t<9;++t)
			{
				if(i+x[t]>0 && j+y[t]>0)
				{
					trans = max(trans,b[i+x[t]][j+y[t]]);
				}
			}
			if (trans != INT_MIN) 
			{
				b[i][j] = trans + a[i][j];
			}
		}
	}
	cout<<b[n][m]<<endl;
return 0;
}

1、上述代码实现了在一个n*m的数字矩形中从(1,1)到(n,m)中选择一条路径，使得其路径上方格中数字和加起来最大，每个方格选择下一个方格只能向左或者向下走一格。( )

√ ×

你告诉我九个方向坐标只能往两个方向走

2、（2分）上述代码如果删除第4行的b数组定义，并将下面的b数组全部改成a数组，运行结果不变。( )

√ ×

中的b数组是保存(1,1)到当前格子的路径最大值，a数组是格子原始值，将b替换为a后，a数组的含义变成递推过的标识路径最大值，还没有递推过的是原始值。由于递推方向是从上到下从左到右，可以保证所求上一个格子的路径都已经被递推过，不会发生混淆。

3、第20行去掉”if(trans != INT_MIN)”程序运行结果不变。( )

√ ×

会变，因为如果去掉了那么INT_MIN声明了和没声明有什么区别呢

选择题

4、上述代码的时间复杂度为( )。

A. O(n+m)

B. O(n*m)

C. O(min(n, m))

D. O(max(n, m))

两个for循环一个到n，一个到m

5、代码使用了哪种算法思想( )。

A. 贪心

B. 动态规划

C. 分治

D. 深度优先搜索

因为只有动态规划是考虑全局的

6、（4分）如果输入是

3 4

-4 -5 -10 -3

7 5 -9 3

10 -2 6 -10

输出为( )。

A. 7

B. 8

C. 9

D. 10

可以一次走两格那就是：-4 -- 7 --10 -- 6 -- -10

四：完善程序

(1):

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int instk[N], outstk[N], intop, outtop;
int stk[N], top;
int main() 
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++) 
	{
		scanf("%d", &instk[i]);
	}
	for (int i = 0; i < n; i++) 
	{
		scanf("%d", &outstk[i]);
	}
	intop=0;
	top=-1;
	bool ok=true;
	for (int i = 0; i < n; ++i) 
	{
		int x = outstk[i];
		if (top >= 0 && stk[top] == x)   top--  ;
		else 
		{
			while (  intop < n && instk[intop] != x ) 
			{
				stk[++top] = instk[intop++];
			}
			if (intop>=n)
			{
				ok = false;
				break;
			}
			else  intop++ ;
		}
	}
	if (ok) 
	{
		puts("Yes");
	}
	else 
	{
		puts("No");
	}
return 0;
}

这个代码的作用是

1：输入一个入栈序列，再输入一个出栈序列

2：判断出栈元素是不是中间栈的首位，如果是top--，即指针指向下一位

3：如果不是，就判断在不在入栈序列里

4：如果在，则继续找下一个。

5：如果没有则继续看下一位，一直到n，ok=false

6：如果ok=false，输出no，否则输出yes

1、①处应填 ( )

A. top = 0

B. top = -1

C. outtop = 0

D. outtop = -1

初始化stk的栈顶指针为-1。

2、②处应填 ( )

A. outstk[outtop++] = x

B. instk[intop++] = x

C. top--

D. intop--

3、③处应填 ( )

A. instk[intop] != x

B. instk[intop] == x

C. intop < n && instk[intop] != x

D. instk[intop] != x && intop < n

4、④处应填 ( )

A. top > n

B. top >= n

C. intop > n

D. intop >= n

5、⑤处应填 ( )

A. intop++

B. outop++

C. top++

D. top--

(2):

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
int n;
using ll = long long;
int main() {
	ll ans = 0, n1, n2;
	int a[10], vis[10];
	for (int i = 1; i < 10; i++)  
        {
              a[i] = i ;
        }
	do {
		for (int j = 1;j < 9; j++) 
		{
		ll num1 = 0, num2 = 0;
		for (int k = 1;k<=j; ++k) 
		{
			num1 = num1*10 + a[k];
		}
		for (int k = j+1;k<=9; ++k) 
		{
			num2 = num2*10 + a[k];
		}
		ll num3 = num1 * num2;
		int tmp = num3, cnt = 0;
		bool ok = true;
		memset(vis, 0, sizeof vis);
		while (num3 > 0) 
		{
			int t = num3%10;
			if( D. t == 0 || ++vis[t] > 1 ) ok = false;
			num3 /= 10;
			cnt++;
		}
			if (cnt == 9 && ok && tmp > ans) 
			{	
				ans = tmp;
				n1 = num1, n2 = num2;
			}
		}
	} while (next_permutation(a+1, a+10));
	cout << n1 << "*" << n2 << "=" << ans << endl;
return 0;
}

这个代码的作用是：

1：保存1到9，9个数字

2：枚举乘号的位置，乘号有八个位置

3：然后判断num3是否只有1-9这9个数字，并且只出现一次

4：用next_permutation函数求下一个排列

1、①处应填 ( )

A. a[i] = 0

B. vis[i] = 0

C. a[i] = i

D. vis[i] = i

2、②处应填 ( )

A. j < 10

B. j < 9

C. j <= 10

D. a[j] > 0

3、③处应填 ( )

A. vis[t] > 1

B. ++vis[t] > 1

C. t == 0 && ++vis[t] > 1

D. t == 0 || ++vis[t] > 1

4、④处应填 ( )

A. cnt == 9

B. cnt ==9 && ok

C. cnt == 9 && ok && num3>ans

D. cnt == 9 && ok && tmp > ans

5、⑤处应填 ( )

A. next_permutation(a+1, a+10)

B. next_permutation(a, a+10)

C. next_permutation(a, a+9)

D. next_permuttion(a+1, a+9)

数据结构专题

1：如果树根算第1层，那么一棵n层的二叉树最多有（ ）个结点

A. 2​n−12​^n-1

B. 2n2^n

C. 2​的n+1次方2​的n+1次方

D. 2n+12^n+1

4：在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（ ）。

A．程序运行时理论上所占的内存空间

B．程序运行时理论上所占的数组空间

C．程序运行时理论上所占的硬盘空间

D．程序源文件理论上所占的硬盘空间

5：向一个栈顶指针为 hs 的链式栈中插入一个指针 s 指向的结点时，应执行（）

A.hs->next = s;

B.s->next = hs; hs = s;

C.s->next = hs->next; hs->next = s;

D.s->next = hs; hs = hs->next;

8：11. 双向链表中有两个指针域llink和rlink，分别指向该结点的前驱及后继。设p指向链表中的一个结点，它的左右结点均非空。现要求删除结点p，则下面语句序列中错误的是（ ）。

A. p->rlink->llink = p->rlink;

p->llink->rlink = p->llink; delete p;

B. p->llink->rlink = p->rlink;

p->rlink->llink = p->llink; delete p;

C. p->rlink->llink = p->llink;

p->rlink->llink->rlink = p->rlink; delete p;

D. p->llink->rlink = p->rlink;

p->llink->rlink->llink = p->llink; delete p;

  1. 以下哪个排序是稳定的（ ）

A. 冒泡

B.选择

C.插入

D.快排

E.堆排序

F.希尔排序

  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 19ms
  4. Powered by Hydro v5.0.0-beta.13 Community