一、单选题

1. 下列数中最大的数为（ ）

{{ select(1) }}

• $(10010101)_2$
• $(236)_8$
• $(66)_{16}$
• $(142)_5$

2. 微型计算机的以下选项中,（ ）的存取速度最快。

{{ select(2) }}

• 内存储器
• 外存储器
• 高速缓存
• 寄存器

3. 表达式(3+5)*25-34/(7-5)的后缀形式是（ ）。

{{ select(3) }}

• $3 \quad 5+25 * 34 \quad 7 \quad 5-/-$
• $3 \quad 5 \quad 25 \quad 34 \quad 7 \quad 5+*-/-$
• $3 \quad 5 \quad 25+ * \quad 34 \quad 7 \quad 5-/-$
• $3 \quad 5 \quad 25+ * -34/7 \quad 5-$

4.定义一棵树有根数的深度:根节点的深度为 0，其余结点的深度等于该节点的父亲结点的深度加 1。一颗深度为 9 的完全二叉树至少包含( )个结点。

{{ select(4) }}

• 511
• 512
• 1023
• 1024

5.下列程序的时间复杂度是( )。

int m,n,s=0;
cin>>m>>n;
for(int i=0;i<m;i++)
    for(int j=1;j<=n;j*=2)
        s++;

{{ select(5) }}

• $O(m^2)$
• $O(n^2)$
• $O(m*n)$
• $O(m*log_2^n)$

6.下列各排序算法中，最坏情况下的时间复杂度最低的是( )。 {{ select(6) }}

• 选择排序
• 快速排序
• 堆排序
• 冒泡排序

7.已知二叉树的中序遍历为 DEGHFCABI，后序遍历为 HGFEDCIBA，则该二叉树的前序遍历为( )。

{{ select(7) }}

• ABCDEFGHI
• ACDEFHGBI
• ADCEFGHBI
• ACDEFGHBI

8.设栈 S 的初始状态为空，若干个元素{a,b,c,d,e,f}依次入栈 S，出栈序列为{b,d,f,e,c,,a}，根据出栈的序列求栈 S 的最小容量为（ ）。 {{ select(8) }}

• 2
• 3
• 4
• 5

9.小明想开个造纸飞机的公司，于是雇了 5 个人。接着他要去购买原材料了，已知一包 A1 纸中有 4 张纸，一张 A1 纸能折 7 架飞机，每位员工要制造 100 架飞机。因为制造飞机需要一个相对安静的环境，所以员工之间不能互相借纸，也不能提前裁纸。但是老板小明可以把一包纸拆开分开员工，以确保分给每个员工的纸张数量是一样的，又尽可能的少用原材料。求小明至少要买( )包 A1 纸。 {{ select(9) }}

• 16
• 17
• 18
• 19

10.中国古代的历史故事“田忌赛马”是大家所熟知的。话说齐主和田忌又要赛马了，他们各派出 10 匹马，每场比赛，输的一方将要给赢的一方 10 两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定的而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢取最多( )两黄金。第一行的 10 个整数表示田忌的马的速度。第 二行的 10 个整数为齐王的马的速度。

田忌的马	100	95	90	85	80	75	70	65	60	55
齐王的马	98	97	92	88	85	81	55	50	44	40

{{ select(10) }}

• 60
• 70
• 80
• 90

11.设W=true，X=Y=false，Z=true，以下逻辑运算表达式值为真的是( )。

{{ select(11) }}

• $W \vee (Z \vee Y) \vee X$
• $W \wedge (X \vee Y \vee !Z) \vee !Z$
• $（W \wedge X）\vee (Y \wedge Z \vee !W)$
• $（W \wedge X \vee Y）\wedge Z$

12.非常经典的汉诺塔问题，目标是将 A 柱上的盘子移到C 柱上，但是大的盘子不能放到小的盘子的上面。现在规定：A 柱上的盘子只能移动到B 柱，B 只能移动 C，C 只能移到 A。现在 A 柱上有 3 个盘子，要把这些盘子安照上述规则都挪到 C 柱上，每次移动一个盘子，至少要移动（ ）次。 {{ select(12) }}

• 7
• 17
• 21
• 31

13.有 5 本不同的书放在书架上。现重新摆放，使每本书都不在原来放的位置。有（ ）种摆法。

{{ select(13) }}

• 40
• 42
• 44
• 46

14.字符串“zhangnahz”，本质不同的子串个数为（ ）。

{{ select(14) }}

• 40
• 41
• 42
• 43

15.一颗无向树 T 有 7 片树叶，3 个 3 度顶点，其余顶点均为4 度，则T 有( )个 4 度结点。

{{ select(15) }}

• 1
• 2
• 3
• 4

二.阅读程序

01	#include<iostream>
02	using namespace std;
03	int main(){
04		 int a,b;
05		 scanf("%d%d",&a,&b);
06		 int anx=1;
07		 while(b){
08			 if(b&1)anx=anx*a;
09			 a=a*a;
10			 b>>=1;
11		 }
12	 	 printf("%d\n",anx);
13	}

判断题

1).输人 a=10,b=10，能够正确输出答案。（ ）

{{ select(16) }}

• √
• ×

2).第 06 行的 anx=1，改成 anx=0 不会影响最终结果。( )

{{ select(17) }}

• √
• ×

3).將第 08 行与第 09 行交换位置，不会影响最终结果。( )

{{ select(18) }}

• √
• ×

4).将第 10 行改成 b/=2，不会影响最终结果。( )

{{ select(19) }}

• √
• ×

单选题

5).如果输人 a=2，下列哪个数字最可能为该程序输出的结果（）。 {{ select(20) }}

• 14
• 15
• 16
• 17

6).输入 a=9,b=9,输出结果为（ ）。 {{ select(21) }}

• 387420489
• 387420191
• 388420489
• 3774204890

01	#include<bits/stdc++.h>
02	using namespace std;
03	struct num{int a,b;};
04	void fun(struct num s[],int n){
05 		int index,j,k;
06 		struct num temp;
07 		for(k=0;k<n-1;j++){
08 			index=k;
09 			for(j=k+1;j<n;j++)
10 				if(s[j].b<s[index].b)index=j;
11 			if(index!=k){
12 				temp=s[index];
13 				s[index]=s[k];
14 				s[k]=temp;
15 			}
16 		}
17	}
18	int main(){
19 		int count,i,k,m,n,no;
20 		struct num s[100];
21 		cin>>n>>m>>k;
22 		for(i=0;i<n:i++){
23 			s[i].a=i+1;
24 			s[i].b=0;
25 		}
26 		i=0;
27 		count=no=0;
28 		while(no<n){
29 			if(s[i].b==0)
30 				count++;
31 		if(count==m){
32 			no++;
33 			s[i].b=no;
34 			count=0;
35 		}
36 			i++;
37 			if(i==n)
38 			i=0;
39 		}
40 		fun(s,n);
41 		printf("%d:%d\n",s[k-1].b,s[k-1].a);
42 		return 0;
43	}

判断题

1).若输入为：0 0 0 时，程序运行会出错。（ ） {{ select(22) }}

• √
• ×

2).若输入为：1 2 3 时，则输出为 3：1。（ ） {{ select(23) }}

• √
• ×

3).若把 11 行的“index!=k”改为 1，不会影响程序运行结果。（ ） {{ select(24) }}

• √
• ×

4)若去掉 37 和 38 行，不会影响程序运行结果。（ ） {{ select(25) }}

• √
• ×

单选题

5).程序运行时，输入 5 4 3，输出（ ）。 {{ select(26) }}

• 3:5
• 2:3
• 1:2
• 4:1

6).程序运行时，输入 7 5 2，输出（ ）。 {{ select(27) }}

• 1:5
• 6:1
• 2:3
• 2:4

01	#include<iostream>
02	using namespace std;
03	long long a[100010],b[100010],ans;
04	void mmm(int L,int R)
05	{
06 		if(L==R)return;
07 		int mid=(L+R)>>1;
08 		mmm(L,mid);
09 		mmm(mid+1,R);
10 		int i=L,j=mid+1,k=L;
11 		while(i<mid && j<=R)
12 		{
13 			if(a[i]>a[j])
14 			{
15 				ans+=j-k;
16 				b[k++]=a[j++];
17 			}
18 			else{
19 				b[k++]=a[i++];
20 			}
21 		while(i<mid)b[k++]=a[i++];
22 		while(j<=R)b[k++]=a[j++];
23 		for(i=L;i<=R;i++)a[i]=b[i];
24	}
25	int main()
26	{
27 		int i,n;
28 		cin>>n;
29 		for(i=1;i<=n;i++)
30 			cin>>a[i];
31 		mmm(1,n);
32 		cout<<ans;
33	}

判断题

1).去掉第 06 行，程序运行结果相同。（ ） {{ select(28) }}

• √
• ×

2).第 21 行与第 22 行交换一下，程序运行结果相同。（） {{ select(29) }}

• √
• ×

3).第 07 行改为 int mid=(L+R)/2,程序运行结果相同。（） {{ select(30) }}

• √
• ×

4).该算法的原理是归并排序。（ ） {{ select(31) }}

• √
• ×

单选题

5).该程序的时间复杂度为（ ）。 {{ select(32) }}

• $O(n)$
• $O(nlogn)$
• $O(n^2)$
• $O(n \sqrt n)$

6).程序输入

4
3 2 3 2

则输出为（ ）。

{{ select(33) }}

• 2
• 3
• 4
• 5

7).(4分)程序输入 4 6 5 2 4，则执行到 32 行时，数组a[ ]的数据为（）。

{{ select(34) }}

• 6 5 2 4
• 6 5 4 2
• 2 4 6 5
• 2 4 5 6

三、完善程序

1.第一行输入一个正整数你，第二行输入 n 个整数，判断这些数是否构成等比数列。 试补全程序。

01	#include<bits/stdc++.h>
02	using namespace std;
03	int main()
04	{
05 		int cur,q,i,n,pre;
06 		cin>>n;
07 		①
08 		②
09 		pre=cur;
10 		for(i=3;i<n;i++){
11 			cin>>cur;
12 			if( ③ )
13 			break;
14 			q=cur/pre;
15 			④
16 		}
17 		if( ⑤ )
18 			printf("Yes\n");
19 		else
20 			printf("No\n");
21	}

1).①处应填（ ）。 {{ select(35) }}

• cin>>pre>>cur;
• cin>>pre;
• cin>>cur;
• cin>>cur>>pre;

2).②处应填（ ）。 {{ select(36) }}

• q=1;
• q=0;
• q=cur/pre;
• q=pre/cur;

3).③处应填（ ）。 {{ select(37) }}

• cur>pre
• cur==pre*q
• cur<pre
• cur!=pre*q

4).④处应填（ ）。 {{ select(38) }}

• A、cur=pre;
• B、cur=q;
• C、pre=cur;
• D、pre=q;

5).⑤处应填（ ）。 {{ select(39) }}

• n
• i>=n
• i<n
• i<=n

2.（次大值之和）给定一个 1 到 n 的数字各出现一次的排列a[1]、a[2]、···、a[n],定义 f(1,r)表示 a[1]、a[1+1]、a[1+2]···、a[r]中的次大值，你需要求出对于所有的$1\le i < j \le n (n \le 100000)$,$f(i,j)$的和。 输入第一行包含一个整数 n，第二行 n 个整数表示a[i]，输出所有的f(i,j)之和。 如输入为

3
1 2 3

则输出 5； 若输入为

8
8 2 7 3 4 5 6 1

则输出136. 提示：采用双向链表方式来存放读入的顺序，分别用数组pre[ ]和nxt[ ]来存放。 试补全顺序。

01	#include<iostream>
02	#define LL long long
03	using namespace std;
04	const int MAXN=100005;
05	struct T{
06		 int v,id;//v 存放读入元素值，id 存放读入顺序号
07	}x[MAXN];
08	int pre[MAXN],nex[MAXN];
09	int cmp(T t1,T t2){return t1.v<t2.v;}
10	void del(int p){
11		int L=pre[p],r=nxt[p];
12		nxt[L]=r;pre[r]=L;
13	}
14	int main(){
15 		int m,n,i,j,k;
16 		scanf("%d",&n);
17 		for(i=1;i<=n;i++){
18 			scanf("%d",&x[i].v);
19 			x[i].id= ① ;
20 			pre[i]=i-1;
21 			nxt[i]=i+1;
22 		}
23 		nxt[0]=1;
24 		pre[n+1]=n;
25 		② ;
26 		LL ans=0;
27 		for(i=1;i<=n;i++){
28 			LL L1,L2,r1,r2;
29 			L1=pre[x[i].id];
30 			if(L1) L2=pre[L1];else L2=-1;
31 			r1=nxt[x[i].id];
32 			if(r1!=n+1) r2=nxt[r1];else r2=-1;
33 			if(L2!=-1)ans+= ③ *i;
34 			if(r2!=-1)ans+= ④ *i;
35 			del( ⑤ );
36 		}
37 		printf("%lld",ans);
38	}

1).①处应填（ ）。 {{ select(40) }}

• -1
• 0
• i
• n

2).②处应填（ ）。 {{ select(41) }}

• sort(x,x+n)
• sort(x,x+n,cmp)
• sort(x,x+n+1)
• sort(x+1,x+n+1,cmp)

3).③处应填（ ）。 {{ select(42) }}

• (L2-L1)*(L2-x[i].id)
• (L1-L2)*(r1-x[i].id)
• (L1-L2)*(x[i].id-r1)
• (L2-L1)*(x[i].id-L1)

4).④处应填（ ）。

{{ select(43) }}

• (r2-r1)*(L1-x[i].id)
• (r1-r2)*(r1-x[i].id)
• (r1-r2)*(x[i].id-r2)
• `(r2-r1)*(x[i].id-L1)

5).⑤处应填（ ）。

{{ select(44) }}

• i
• L1
• x[i].id
• r1