第 1 题 表达式a×(b+c)-d/f转后缀表达式的结果是( )。

第 2 题 以下字符串中，字典序最小的是( )。

第 3 题 在C++中,表达式('O'-'I')^13%9+5 的值是( )。

第 4 题 在8个数中，找出这组数的最小值与最大值，最坏情况下最少需要比较( )次。

第 5 题 在 TCP/IP协议族中，最核心的网络协议是( )。

第 6 题 应用快速排序的分治思想可以实现一个求第K大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法期望时间复杂度为( )。

第 7 题 在解决计算机主机与外设之间速度不匹配时通常设置一个缓冲池，主要将计算机输出的数据依次写入该缓冲区，而外设从该缓冲区池中取出数据。该缓冲池应该是一个( )结构。

第 8 题 (1E34)16-(676)8的结果是( )。

第 9 题 一棵二叉树前序遍历为ABDECFGH，后序遍历为EDBGFHCA，以下不是可能的中序遍历的是( )。

第 10 题 一个栈的输入顺序为1,2,3,4,5，下列序列中不可能是栈的输出序列的是( )。

第 11 题 Linux是一个用C语言写成的开源电脑操作系统内核，有大量的操作系统是基于Linux内核创建的。以下操作系统使用的不是Linux内核的是( )。

第 12 题 在下列关于计算机算法的说法中，正确的是( )。

第 13 题 以下关于二叉树性质中，正确的描述的个数有( )。 a.包含n个结点的二叉树的高度至少为log2n; b.在任意一棵非空二叉树中，若叶子结点的个数为n0，度为2的结点数为n2，则 n0=n2+1; c.深度为k的二叉树至多有2^k个结点 d.没有一棵二叉树的前序遍历序列与后序遍历序列相同 e.具有n个结点的完全二叉树的深度为[log2[(n+1)]

第 14 题 排序算法是稳定的，这句话的意思是关键码相同的记录排序前后相对位置不发生改变，以下排序算法不稳定的是( )。

第 15 题 给定m种颜色和有n个点的手环，要求用这个m种颜色给这条手环染色，其中旋转和翻转能够互相得到的算同一种染色方案，如对于3个点的手环，ABC的染色方法与BCA(旋转)、ACB(翻转)是相同的。当m=2,n=2 时，一共有三种染色方案，分别为AA、AB、BB，那么当m=5,n=4时，一共有( )种染色方案。

二、判断题（每题 2 分，共 20 分）

第 16 题

#include <iostream>
using namespace std;

unsigned short tot;
void Hanoi(int n, char A, char B, char C) {
	++tot;
	if(n==1) {
		cout<<A<<"->"<<C<<'/';
		return;
	}
	Hanoi(n-1,A,C,B);
	cout<<A<<"->"<<C<<'/';
	Hanoi(n-1,B,A,C);
}

int main() {
	int n;
	cin>> n;
	Hanoi(n,'A','B','C');
	cout<<'\n'<<tot<<'\n';
	
	return 0;
}

第 16 题 (1分)将第6行移到13行和14行之间，输出结果不会变化。( )

第 17 题 当输入的n=2时，输出的第一行为A->B/B->C/A->C/。( )

第 18 题 当输入的n=3时，输出的第二行为8。( )

第 19 题 本程序的含义可以是:有三根柱子，第一根柱子从上到下依次套有编号分别为1~n的圆环，现在每次可以移动某个柱子顶部的圆环到另一个桂子的顶部上，并且要求编号较大的圆环要始终不能在编号较小的上面，输出一种操作次数最少的方案以及对应的操作次数。( )

第 20 题 当输入的n=3时，输出的第一行的第21个字符是( )。

第 21 题 (5分)当n=17时,程序输出的第二行为( )。

第 23 题

#include <iostream>
#include <iomanip>
#include <cstring>
using namespace std;
const int N = 105;
int a[N][N];
int main() {
	int n, x, y,count;
	cin>> n;
	memset(a,0,sizeof(a));
	count=a[x=0][y=n-1]=1;
	while (count<n*n) {
		while (x+1<n && !a[x+1][y]) a[++x][y]= ++count;
		while (y-1>=0&&!a[x][y- 1]) a[x][--y]= ++count;
		while (x-1>=0&&!a[x-1][y])  a[--x][y]= ++count;
		while (y+1<n &&!a[x][y+1])  a[x][++y]= ++count;
	}
for (x=0; x<n; x++) {
		for (y=0; y<n; y++) {
			cout<<setw(5)<<a[x][y];
		}
		cout<<endl;
	}
	return 0;
}

第 23 题 (1分)删除第10行,不影响程序运行结果。()

第 24 题 将第12行改为“while (count<= n*n){”,不影响程序运行结果。()

第 25 题 当输入的n=4时,程序输出的a[3][2]的值为15。()

第 26 题 (3分)本题的时间复杂度为()。

第 27 题 当输入的n=100 时,a[33][66]的值为()。

第 29 题

#include <iostream>
#include <iomanip>
#include <cstring>
using namespace std;
string s;
int main() {
	int k;//限制输入0<=k<26
	cin>>k>>s;
	int n=s.length();
	for (int i=0; i<n; i++) {
		if (s[i]<='Z'&&s[i]+k>'Z')
			s[i]=(s[i]+k)%'Z'+'A'-1;
		else if ('A'<=s[i]&&s[i] <='Z')
			s[i]+=k;
	}
	char pre;
	int st=-1;
	for (int i=0; i<n; i++) {
		if(s[i]<'A'||s[i]>'Z') {
			if (st==-1) {
				st=i;
				pre=s[i];
			} else {
				char tmp=s[i];
				s[i]=pre;
				pre=tmp;
			}
		}
	}
	if(st !=-1)
		s[st]=pre;
	cout<<s<<endl;
	return 0;
}

第 29 题 (1分)删除第30行和第31行，不影响程序运行结果。( )

第 30 题 如果输入的s不含大写字母，则输出结果与k的值无关。( )

第 31 题 如果知道输出结果，能够反推出唯一的输入结果。( )

第 32 题 当k的值确定时，不存在两个不同的输入使得输出相同。( )

第 33 题 如果输入是6 KU96APY5,则输出为( )。

第 34 题 (5分)如果输出是ab1287F2Tguz,则输入可能为( )。

三、编程题（每题 25 分，共 50 分）

第 36 题 (拓扑排序) 在我们所学的课程中，部分课程之间可能存在依赖关系，如我们在学习图论知识之前，需要先学习离散数学中的基础知识。一门课可能有若干先修课程。现在李老师需要安排一些课程的授课计划，排课需要遵从一定的规则,即只有修习完某课程的全部课程后，才能修习该课程。 在本例中,用1~n表示n个课程,用x y表示x是y的先修课程，输入数据保证图中没有环与重边。要求输出任意一个可行的授课顺序。图用邻接矩阵方法储存。

#include <iostream>
#include <cstring>
# include <queue>
using namespace std;
const int N=105;
int a[N][N];
int in[N],s[N];
int n,m,u,v;
void Topo() {
	queue<int> q;
	int cnt;
	for(int i=1; i<=n; i++)
		if(___(1)___)
			q.push(i);
	while(!q.empty()) {
		int cur = q.front();
		q.pop();
		s[cnt++]=___(2)___;
		for (int i=1; i<=n; i++) {
			if (___(3)___) {
				___(4)___;
				if (in[i]==0)
					q.push(i);
			}
		}
	}
}
int main() {
	memset(in,0,sizeof(in));
	memset(a, 0,sizeof(a));
	cin>>n>>m;
	for (int i=0; i<m; i++) {
		cin>>u>>v;
		in[v]++;
		___(5)___;
	}
	Topo();
	for (int i=0; i<n; i++) {
		if (i)
			cout<<' ';
		cout<<s[i];
	}
	cout<<endl;
	return 0;
}

第 36 题 ①处应填( )

第 37 题 ②处应填( )

第 38 题 ③处应填( )

第 39 题 ④处应填( )

第 40 题 ⑤处应填( )

第 42 题 (8一皇后问题)要求用回溯法求解8-皇后问题，使放置在8*8棋盘上的8个皇后彼此不受攻击，即:任何两个皇后都不在同一行、同一列或同一斜线上。请输出8皇后问题的所有可行解。

#include <iostream>
#include<cmath>
using namespace std ;

bool Place(int k,int i,int * x) {
	for (int j=0; j<k; j++)
		if ((x[j]==i)||___(1)___)
			return false;
	return true;
}

void NQueens(int k, int n, int *x) {
	for (int i=0; i<n; i++) {
		if (Place(k,i,x)) {
			___(2)___;
			if(___(3)___) {
				for (int j=0; j<n; j++) cout<<x[j]<<" ";
				cout<< endl;
			}
			else {
				___(4)___;
			}
		}
	}
}
int main() {
	int x[8];
	for (int i=0; i<8; i++)x[i]=-1;
	___(5)___;
	return 0;
}

第 42 题 ①处应填( )

第 43 题 ②处应填( )

第 44 题 ③处应填( )

第 45 题 ④处应填( )

第 46 题 ⑤处应填( )